Solutii Junior Challenge 2021

• Lista de probleme
• Perrynator
• Capcana
• Rollercoaster

Solutia problemei Perrynator

Subtask 1: shiftarea se face doar la dreapta:

Facem mereu query cu o singura pozitie unde nu stim ce valoare e, apoi simulam shiftarea.

Subtask 2: n ≤ 4:

Pentru n ≤ 3 putem considera ca shiftarea se face doar la dreapta, deoarece ambele directii rezulta in aceeasi permutare.

pentru n = 4, pot exista mai multe solutii, una din ele este:

Initial aflam pozitia lui 4: Sa zicem ca momentan stim valoarea de pe o anumita pozitie, putem face query-uri de cate doua elemente cu pozitia asta si fiecare dintre celelalte, avand grija la swap-uri, iar cand raspunsul unui query este egal cu valoarea cunoscuta, inseamna ca am gasit o valoare mai mare pe care o putem afla cu un query doar pe acea pozitie. Putem repeta asta, pana cand gasim pozitia lui 4.

Dupa ce am aflat pozitia lui 4, putem face query cu 4 si fiecare dintre celelalte pozitii, tinand cont de swap-uri, pentru a afla toata permutarea.

Pentru 60-70 de puncte:

O solutie, cu numar mai mare de query-uri este aceea de a afla permutarea incepand cu cele mai mari valori, descrescator.
Cand cunoastem pozitiile celor mai mari k valori, facem query-uri cu toate aceste pozitii, si o alta pozitie aleasa aleator, pana cand gasim pe ce pozitie se afla al (k+1)-lea cel mai mare element.
Aceasta solutie face aproximativ N²/2 query-uri.

Pentru 100 de puncte:

Vom considera n > 3.

Initial, gasim pe ce pozitie se afla valoarea 1:
Putem cauta binar pozitia pe care se afla 1, pentru a verifica daca 1 este intr-un anumit interval, facem query cu toate pozitiile care nu sunt incluse in acel interval, astfel, daca raspunsul este diferit de 1, inseamna ca pozitia lui 1 se afla in acest interval, iar daca este 1, stim ca pozitia e in afara, si ca aceasta nu s-a schimbat.
Dupa ce stim valorile de pe un subset de pozitii, una din valori fiind 1, pentru a afla o noua valoare facem urmatorii pasi:

1. Query pe o singura pozitie pe care nu o cunosteam, pentru a afla o noua valoare.
2. Dupa acest query, noua permutare are 2 variante posibile. Pentru a afla in ce varianta ne aflam, e suficient sa aflam pe ce pozitie se afla 1, care la randul lui are 2 pozitii posibile pe care poate fi. Facand un query cu toate pozitiile mai putin una din acestea 2, putem afla daca valoarea 1 se afla pe acea pozitie, sau nu, fara a schimba deloc permutarea curenta. Astfel, odata ce am aflat in ce directie s-a shiftat 1, putem afla pozitiile tuturor valorilor pe care le stiam inainte, impreuna cu o valoare noua din query-ul precedent.

Putem repeta acesti doi pasi, pentru a afla toate elementele permutarii, unul cate unul, efectuand cate doua query-uri pentru fiecare valoare nou aflata.
Astfel, numarul final de query-uri este log(N) + 2*(n-2) = 203 query-uri, deoarece ne putem oprii odata ce am aflat n-1 valori.

Solutia problemei Capcana

Observaţia 1: Din 2 * K + 1 ≤ N putem deduce că plăcuţele normale sunt mai numeroase decât cele periculoase.

O primă soluţie care foloseşte N - 1 queryuri ar compara plăcuţa 1 cu fiecare din celelalte şi ar nota pentru fiecare plăcuţă dacă este de acelaşi tip sau nu cu prima.
Ştim că plăcuţele care apartin tipului mai numeros sunt cele normale.

Observaţia 2: Putem identifica o plăcuţă normală prin 2 * K + 1 queryuri dacă aplicăm strategia de mai sus primelor 2 * K + 1 plăcuţe.

Observaţia 3: Dacă cunoaştem un interval de plăcuţe normale de lungime len atunci noi putem identifica prima plăcuţă periculoasă dintr-un alt interval de lungime maxim len în log(len) queryuri.
În acest caz noi putem folosi o căutare binară pentru a găşi plăcuţa periculoasă.

Să spunem că la un anumit moment de timp cunoaştem tipul fiecărei plăcuţe dintr-un anumit prefix care se termină cu un interval de placuţe normale. Procedăm astfel:

• Pasul 1: Dăm query după intervalul de placuţe normale şi intervalul de aceeaşi lungime aflat imediat după acesta.
  • Pasul 1.1: Dacă am obţinut că au acelaşi număr de plăcuţe periculoase (adică 0) atunci ne extindem prefixul şi intervalul de plăcuţe normale, iar apoi revenim la pasul 1 cu noul interval de placuţe normale.
  • Pasul 1.2: Altfel, ştim că în intervalul nou testat se află una sau mai multe plăcuţe periculoase. Putem să o aflam pe prima dintre ele folosindu-ne de strategia de la observaţia 3.
• Pasul 2: După ce am identificat plăcuţa periculoasă dăm query după intervalul nostru de placuţe normale şi intervalul care urmează imediat după plăcuţa periculoasă găsită.
  • Pasul 2.1: Dacă acest query ne transmite că şi al doilea interval are doar plăcute normale atunci putem relua procesul de la pasul 1
  • Pasul 2.2: Dacă în schimb aflăm că şi acest interval conţine una sau mai multe plăcuţe periculoase, ne folosim din nou de observaţia 3 pentru a o găşi pe prima dintre ele, revenind practic la pasul 1.2.

Câte queryuri foloseşte soluţia prezentată mai sus?
2 * K - 1(că să descopere prima plăcuţă normală) +
log(N) (îşi dublează intervalul de placuţe normale lungimea) +
K (când transferăm intervalul de plăcuţe normale din interior la final, notat cu pasul 2.1 în explicaţie) +
K * log (de fiecare dată când descoperim o plăcuţa normală o căutăm binar)

Solutia problemei Rollercoaster

Subtask 1 (20 de puncte) - N ≤ 15

Pentru acest subtask se pot genera si verifica toate configuratiile de roller-coastere.
Complexitate timp: O(2^N*N)
Complexitate spatiu: O(N)

Subtask 2 (20 + 20 de puncte) - N ≤ 1000

Pentru acest subtask este nevoie sa ne gandim la solutii de programare dinamica.

Prima idee care ne vine este:
dp[i] = coeficientul maxim de distractie al unui roller-coaster si se termina cu turnul i

Relatia de recurenta va fi:
dp₀ = 0
dp[i] = max {dp[j] + cmmdc (a[j], a[i])| 0 <= j < i}

In acelasi timp mai tinem si:
cnt[i] = numarul de roller-coastere care au coeficient maxim de distractie si se termina cu turnul i

Complexitate timp: O(N²)
Complexitate spatiu: O(N)

Subtask 3 (20 + 20 + 60 de puncte) - N ≤ 250.000

Pentru punctaj maxim este nevoie sa exploatam operatia de cmmdc.

Vom crea o alta dinamica care nu tine cont de indicii turnurilor, dar va tine cont de divizorii inaltimilor.

dp[d] = coeficientul maxim de distractie al unui roller-coaster si se termina cu un turn cu inaltimea multiplu de d

Recurenta nu este foarte grea. Vom avea pentru fiecare turn i o variabila auxiliara best:
best = max{dp[d] + d| d este divizor al inaltimii turnului i}

Dupa vom actualiza dp-urile folosindu-ne de best:
dp[d] max= best unde d este divisor al inaltimii turnului i

Adaugarea vectorului cnt pentru aflarea numarului de solutii (cnt[d] = numarul de roller-coastere care au coeficient maxim de distractie si se termina cu un turn cu inaltime multiplu de d) se va face ca la solutia de 40p.

Complexitate timp: O(N*sqrt(MAXVAL))
Complexitate spatiu: O(MAXVAL + N)