infoarena

Aici puteţi discuta despre problema Politic (http://infoarena.ro/problema/politic).

Nu e un pic (dar doar un pic) cam mare limita de timp? adica o sursa optimizata nu se apropie nici pe departe de 0.5 sec (atata ia executia pt un brute-force)  :D

Sustin ideea ca ar trebui scazuta limita de timp, in conditiile in care si o sursa cu complexitatea O(N^2) ia 100

o sursa pe ideea corecta intra in 12 ms, ar trebui scazuta la 0.1 limita de timp :)

Am incercat sa re-rezolv problema asta folosind cautarea binara. Brusc nu mai inteleg problema nici cu rezolvarile anterioare. Sunt total confuz #-o
Imi explica si mie cineva exemplul? De unde sunt doar 4 coalitii posibile?! Programul meu afiseaza 7, ceea ce mi se pare si foarte logic.

Partidul 1 se poate asocia cu 2, cu 3, cu 4 si cu 5.
Partidul 2 se asociaza cu 4 si 5.
Partidul 3 cu 5.
Partidul 4 nu se asociaza cu nimeni..
In total 4+2+1=7...

Am folosit cautarea binara ca sa aflu nr minim de partide dintr-o coalitie.

In situatii ca acestea e recomandat sa recitesti enuntul cu atentie. Rezolvarea ta nu respecta urmatoarea conditie: pentru a guverna o coalitie trebuie sa aiba mai mult de jumatate din parlamentari. In solutia ta asocierea partidului 1 cu 2 nu e suficienta deoarece nu sunt destui parlamentari (2+3 = 5 > 10/2 fals).

Ce a fost scris aici in enunt e valabil? :-k

Da.

Problema apare si pe campion.edu.ro. Primul raspuns, 5=numarul de partide este ok, dar cel de-al doilea raspuns, numarul posibil de coalitii majoritare este complet aiurea. In explicatiile lor zice ca cele patru variante de formare a coalitiilor sunt:P1+P2+P3, P1+P2+P3+P4, P2+P3+P4, P2+P3+P4+P5 (P sunt partide) P2+P3+P4 au in total 5 membri, adica exact jumatate, nu mai mult de jumatate cum zice in enunt. In acest caz de ce nu este coalitie buna si P1+P2? Apoi, nicaieri in enunt nu zice ca sa nu se formeze coalitie din toate partidele! Enunt foarte neglijent, dat la ONI !!

Pentru ultimul test (cel de la oni e de forma: 1, 3, 5 6 7 ... 20000 20001 20002, si tind sa cred ca si aici e acelasi) poate sa imi explice cineva de ce raspunsul corect la cerinta a 2-a este 3?  ???

In cazul asta, exista 3 partide, primul format dintr-un singur parlamentar, al doilea la fel, si al 3-lea din 19 998 de parlamentari.
Coalitiile posibile ar trebui sa fie: P1+P2+P3 si P2+P3. Coalitia P1+P2 nu cred ca ar trebui sa fie numarata, pentru ca cele 2 partide au impreuna 2 parlamentari, numar mult mai mic jumatate din numarul total de parlamentari (10 000).

Atat solutia in O(n log n) pe care am trimis-o, cat si brutul in O(n^2), dau raspuns incorect la cerinta a 2-a...

Am ajuns intamplator la aceasta pagina si m-am gandit ca ar fi util sa dau unele lamuriri, desi a trecut ceva timp de la trimiterea ultimului mesaj.
In primul rand as vrea sa ofer o explicatie corecta a rezultatului din exemplu (cea de pe campion nu e ok). Exista intr-adevar 5 partide: P1=(1,2,3), P2=(5,6), P3=(8), P4=(10,11) ÅŸi P5=(14,15). Cele 4 coalitii majoritare sunt: P1 + P2 + P3, P1 + P2 + P3 + P4, P1 + P2 + P3 + P4 + P5 si P2 + P3 + P4 + P5.
Raspunsul corect la cea de-a doua cerinta de la ultimul test (P1 si P2 cu cate un parlamentar, P3 cu 19998) este intr-adevar 3. Cele 3 coalitii sunt: P1 + P2 + P3, P2 + P3, P3.
In al doilea rand, legat de limita de timp, problema a fost evaluata la vremea respectiva (ONI 2007) pe Borland C++/Pascal. Complexitatea timp pentru care s-au luat 100 de puncte era O(N). Pentru a departaja solutiile ar fi necesare probabil alte limite si alte teste.