Solutii Junior Challenge 2021

• Lista de probleme
• Perrynator
• 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.