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)
