Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Feedback Runda 2  (Citit de 3931 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« : Iulie 26, 2017, 13:59:21 »

Runda 2 a luat sfarsit. Felicitari castigatorilor!

Asteptam feedback-ul vostru. Smile
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #1 : Iulie 26, 2017, 14:05:07 »

Super draguta xormites.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #2 : Iulie 26, 2017, 14:09:50 »

Xormites chiar e super. Am incercat 30 de minute sa gasesc patternuri si nimic(evident am incercat vreo ora sa o rezolv legit). Chiar nu iese din greseala, din fericire. La tribes, ce complexitate se voia? Mi se pare ca limita a fost totusi cam prea larga (dati fiind timpii de rulare ale anumitor surse de 100, extrem de la limita, presupun ca nu erau neaparat solutii corecte). Si intrebarea mai importanta: cum se face xormites?
Memorat
georgerapeanu
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 47



Vezi Profilul
« Răspunde #3 : Iulie 26, 2017, 14:13:56 »

La juniori au fost foarte faine problemele,hansha fiind cea mai interesanta.
Memorat
caesar2001
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #4 : Iulie 26, 2017, 14:16:44 »

Frumoasa problema Hansha de la juniori! Cu bfs iese de 40p, dar cu ce se face de 100? Smile
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #5 : Iulie 26, 2017, 14:30:36 »

Frumoasa problema Hansha de la juniori! Cu bfs iese de 40p, dar cu ce se face de 100? Smile

Ideea in mare este sa iti faci o functie recursiva care sa iti calculeze distanta si sa memoizezi toate starile prin care treci. Se observa ca sunt putine astfel de stari.
Memorat
andreiiii
Echipa infoarena
Client obisnuit
*****

Karma: 23
Deconectat Deconectat

Mesaje: 86



Vezi Profilul
« Răspunde #6 : Iulie 26, 2017, 14:56:26 »

La xormites solutia este urmatoarea:
Ne uitam la cel mai semnificativ bit pentru care suma jucatorului 1 are acel bit diferit de cel al jucatorului 2. Acest bit este defapt cel mai semnificativ bit cu valoarea 1 al sumei xor a intregului sir si ne intereseaza doar acesta.
Acum am redus problema la un sir de 0 si 1 in care numarul de cifre de 1 este impar. Avem 2 cazuri:
1) lungimea sirului e para:
In acest caz se observa ca al primul jucator poate alege sa ia doar cifrele de pe pozitiile pare sau doar cifrele de pe pozitiile impare. Cum sunt in numar impar de cifre de 1, el poate alege astfel incat numarul de 1 selectati de el sa fie impar. Deci in acest caz jucatorul 1 castiga.
2) lungimea sirului este impara:
Sunt mai multe subcazuri.
La ambele capete este un 0, caz in care jucatorul 1 ia unul din ele si se ajunge la cazul: lungimea sirului para, numar impar de 1, deci castiga jucatorul 2.
Exita cel putin un 1 la unul din capete. Jucatorul 1 il va alege pe cel castigator (in caz ca exista unul care il conduce la castig).
Presupunem ca am scos 1 de la unul din capete (facem asta pe rand). Trebuie sa vedem cine castiga stiind ca lungimea sirului e para, exista un numar par de cifre de 1 (si implicit un numar par de cifre de 0), primul jucator care muta e jucatorul 2, iar jucatorul 1 are deja un 1.
Sa vedem care este strategia jucatorului 1 de a castiga.
Se observa ca daca jucatorul 1 alege o cifra diferita de jucatorul 2, atunci se ajunge in cazul: lungimea sirului para, numar impar de 1 si jucatorul 2 e la mutare. Aici jucatorul 2 castiga pentru ca si in cazul 1)
In concluzie, singura strategie a jucatorului 1 este sa aleaga la fel ca si jucatorul 2. O sa rezolvam acum problema: are primul jucator o strategie de a alege aceeasi cifra ca jucatorul 2 la fiecare pas?
Pentru asta el poate alege din capatul opus sau din aceeasi parte ca jucatorul 2. Aici sunt cateva patternuri:
Patternul 1: Daca sirul este palindrom de exemplu, el poate mereu sa aleaga in oglinda, deci jucatorul 1 are strategie.
Patternul 2: Daca sirul este format din concatenari succesive de 00 si 11, atunci jucatorul 1 are stratetegie pentru ca ia mereu din acelasi capat.
Din aceste 2 paternuri putem forma altul: Un palindrom de lungime para (patternul 1) caruia ii inseram in centru un sir care respecta patternul 2. Se observa ca jucatorul 1 are castig deoarece ia in oglinda cat se poate, dupa care ia pana la sfarsit din acelasi parte ca jucatorul 2.
In orice alt caz, jucatorul 1 nu are strategie de a lua aceeasi cifra ca jucatorul 2.
Strategia jucatorului 1 de a lua aceeasi cifra este necesara, dar nu suficienta. El ia acealsi numar de cifre de 1 ca jucatorul 2 si castiga doar daca ia un numar par de cifre de 1, asta inseamna ca (numarul total de 1) / 2 trebuie sa fie numar par.

Cum demonstram ca jucatorul 1 nu are strategie de a muta la fel ca jucatorul 2 daca sirul nu respecta patternul?
Fie un sir cu urmatoare proprietate: daca eliminam prefiul maxim (de lungime cel mult jumatate din lugimea sirului) si sufixul de aceeasi lungime, cu proprietatea ca prefixul este identic cu inversul sufixului, ramane un sir in care exista cel putin o subsecventa maximala de 1 de lungime impara sau o subsecventa maximala de 0 de lungime impara. Pe acest sir jucatorul 1 nu o sa aiba strategie,  pe celelalte o sa aiba (cum am explicat mai sus).
Si aici exista cateva cazuri (dar care se rezolva asemanator). O sa zic doar unul din ele:
Exista cel putin o subsecventa de lungime impara de 1. Atunci e clar ca exista cel putin 2 (pentru ca numarul total de 1 este impar). Ne uitam la prima si la ultima dupa aparitia lor in sir. Ne uitam si la prima si ultima subsecventa de lungime impara de 0. Presupunem ca acestea nu exista sau se afla intre cele doua subsecvente de 1.
Un exemplu:
0110100)1100[111001]001100(0010110
Se observa ca am marcat cu '(' si ')' partile "palindromice", iar cu '[' si ']' secventa delimitata de cele 2 subsecvente de 1. Ne imaginam ca suntem jucatorul 2. Strategia celui de-al doilea jucator de a-l face pe jucatorul 1 sa ia o cifra diferita decat cea a lui este urmatoarea:
1) Il va forta sa ia partile "palindromice". Pentru asta o sa ia din cifra cea mai exterioara la un moment dat pana ce o epuizeaza. Se remarca ca nu conteaza din ce parte ia, decat la ultima secventa, adica aici:
00)1100[111001]001100(00
In cazul asta trebuia sa ia din stanga, ca sa nu il lase pe jucatorul 1 sa ia din partea "nepalindromica" prematur.
Am ramas cu:
1100[111001]001100
Acum strategia este sa ajungem la una din subsecventele impare de 1 inainte sa ajungem la cealalta.
Daca distanta de la secventa "[ ]" pana la unul din capete este mai mica decat pana la celalalt, atunci noi, ca jucator 2, luam doar din partea aceea si sigur vom ajunge inainte sa ajungem la cealalta. Daca sunt la distante egale, atunci putem lua din ce capat vrem prima data, iar apoi vom continua sa alegem din acel capat. Aceasta strategie merge deoarece capetele sunt diferite (am eliminat partea "palindromica"), deci jucatorul 1 va trebui sa aleaga din aceeasi parte ca noi si ajungem in prima situatie, in care secventa este mai aproape de un capat decat celalalt.
Odata ce am ajuns la una din secventele de lungime impara, in partea cealalta o sa avem ori o subsecventa de 1 de lungime para, ori o subsecventa de 0. Acest lucru se intampla mereu deoarece ce e in afara secventei "[ ]" este format din 00 si 11, deci o sa existe un numar par de 1, jucatorul 1 ia la fiecare pas ce ia jucatorul 2, deci o sa fie eliminat un numar par de 1 din exteriorul secventei "[ ]".

Celelalte cazuri ar fi cand prima si ultima secventa de 0 le cuprinde pe cele de 1 (sau acestea nu exista) si cand secventele nu se includ, care se rezolva asemanator.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #7 : Iulie 26, 2017, 16:03:27 »

Speram sa iasa ceva mai putin complicat Sad
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
StarGold2
Strain
*

Karma: 11
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #8 : Iulie 26, 2017, 17:02:58 »

Cand se updateaza rating-urile? Smile
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #9 : Septembrie 26, 2017, 18:43:37 »

Cand se updateaza rating-urile?  Smile
Memorat
GavrilaVlad
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 222



Vezi Profilul
« Răspunde #10 : Septembrie 27, 2017, 10:11:18 »

Sunt updatate de o luna - doua...
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines