Raco

[•eudanip]

Aici se pot pune întrebări legate de problema Raco de la Runda 2 a concursului .com 2012

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

[•a_h1926]

Nu se precizeaza nimic despre numerele din sirul dat. Sunt numere pozitive, mai mici ca 2^31? Pot fi negative?

[•eudanip]

Modificam acum enuntul.

[•a_h1926]

Subsirul vid se considera solutie?

[•eudanip]

NU

[•mugurelionut]

1) "subsir" inseamna ca elementele trebuie sa fie consecutive ca pozitie in sir ?


2) Daca NU, atunci pentru exemplul din enunt, cele 3 subsiruri sunt (ca valori):
2 1
3
2 3 1
?


3) Doua subsiruri se considera diferite daca contin aceleasi numere (ca valoare), in aceeasi ordine, dar cel putin unul din numere provine de pe pozitii diferite ale sirului initial ?

4) Un subsir este determinat de pozitiile din sirul initial pe care se afla elementele sale (considerand pozitiile in ordine crescatoare) ?

[•edp100]

1) NU
2) DA
3) DA
4) DA

[•edp100]

Comisia stiintifica a hotarat sa va mai dea un test la feedback.

[•alex_unix]

Numerele trebuiau declarate unsigned int ?  

Pe testele mici imi mergea bine, dar pe 15 (care tind sa cred ca e un test mare), imi busea. Credeam ca e din cauza asta 

[•Mihai22e]

Eu asa le-am declarat.2^31 + x ( 1 <= x < 300 ) depaseste int

[•edp100]

Numerele sunt < 2³¹ deci intra si pe int.

[•Challenge]

S-a dat reevaluare la problema sau in timpul concursului au fost evaluatele doar pe feedback? Si daca s-a dat reevaluare, ce s-a modificat?

[•Mihai22e]

"valorile sirului sunt din intervalul [0,2^31]"
Daca la 2^31 adaugi ceva, nu depaseste int?
Dar asa e, se putea face si fara unsigned int.

[•edp100]

S-a dat reevaluare la problema sau in timpul concursului au fost evaluatele doar pe feedback? Si daca s-a dat reevaluare, ce s-a modificat?

Am mai grupat niste teste pentru ca brute-ul lua prea multe puncte.

[•a_h1926]

Am avut o solutie in complexitate O(M^3 + N). Este o solutie mai buna?

[•Challenge]

Am avut o solutie in complexitate O(M^3 + N). Este o solutie mai buna?

Poti sa detaliezi cum ai facut in O(M^3 + N)? Eu nu am reusit sa scot decat O(M^3+NlogN) care evident ia TLE ..

[•edp100]

@Andrei
Solutia ta nu e O(NlogN + M^3)?
Solutia oficiala are complexitatea O(N + M^3) pentru ca imi precalculez inversele modulare in O(N).

[•a_h1926]

Imi cer scuze, asa e, am NlogN de la calcularea inverselor modulare.
Nici mie nu imi intra in timp si nu stiam de ce . Multumesc pentru observatie.

[•danalex97]

Puteti detalia , va rog ? 

[•klamathix]

Iti tii frecventele pentru fiecare rest si faci dinamica pe primele clase de resturi, nu pe primele numere. Mai ai nevoie de niste combinari ca sa faci asta.

[•geniucos]

Cand se pun rezultatele?Vad ca s-a terminat de reevaluat.