Solutii Junior Challenge 2021

• Lista de probleme
• Perrynator
• Veverite
• Rollercoaster
• Capcana

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 Veverite

Subtaskul 1: N,Q ≤ 2000

O soluţie greedy uşor de intuit ar fi ca pentru fiecare query să parcurgem şirul de la stânga la dreapta şi să menţinem un set cu elementele pe care nu le-am adăugat încă la suma totală. În momentul când întâlnim un "blocaj" (adică suma este mai mică strict decât valoarea de la pasul curent) extragem din setul de elemente maximul până când se respectă restricţia din nou. După ce am rezolvat blocajul îl adaugăm şi pe el în set şi trecem mai departe.
Deoarece elemente din vector sunt în ordine crescătoare, extragerea elementului maxim şi adăugarile pot fi simulate uşor cu ajutorul unei stive.

Complexitate: O(N * Q)

Subtaskul 2: A_i ≤ 100, pentru 1 ≤ i ≤ N, N,Q ≤ 10⁵

Se observă că pentru query-urile mai mari decât 100, răspunsul va fi clar 0. Putem precalcula răspunsul pentru fiecare valoare iniţială posibilă de la 1 la 100 folosind soluţia anterioară şi să răspundem la query-uri în O(1).

Complexitate: O(N * valmax + Q)

Subtaskul 3: 1 ≤ N, Q ≤ 10⁵, 1 ≤ A_i ≤ 10⁹

Observaţie: Pentru un vector există maxim 2 * log(valmax) blocaje.
Demonstraţie: Pentru oricare 3 elemente adiacente din şirul de elemente pe care le vom considera "blocaje" se împlineşte următoarea inegalitate:
a * 2 < c (unde a, b şi c sunt cele 3 elemente), deoarece la pasul în care ne-am blocat în b am adăugat cel puţin un element mai mare sau egal decât a la sumă (întrucât şi a se afla la acel moment în set). Astfel, la fiecare 2 elemente suma se dublează, ceea ce înseamnă că în 2 * log(valmax) paşi îşi va atinge valoarea maximă. Dacă menţinem setul necesar în greedy ca o listă de intervale de valori nefolosite putem procesa mult mai rapid şirul. Căutam binar poziţia primului blocaj şi adaugăm în listă intervalul de elemente până la acel blocaj. Pentru a simula procesul de extragere de maxim din set de un număr repetat de ori, verificăm dacă trebuie să adaugăm complet ultimul interval din listă. Dacă da, atunci îl adaugăm şi trecem mai departe, altfel căutam binar cât este necesar să adaugăm din el. Apoi căutam binar poziţia următorului blocaj şi tot aşa mai departe până am procesat tot.

Complexitate finală: O(N * log(valmax) * log(N))

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)

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)