Feedback Algoritmiada 2016 Runda 4

[•eudanip]

Runda 4 s-a încheiat. Felicitări câștigătorilor!  

Așteptăm aici impresiile voastre legate de această rundă.

[•depevlad]

Marvel - mi-a placut, o sortare topologica draguta

Symmetricgraph - foarte misto partea de dinamica oglindita, dar mi s-a parut un pic fortat faptul ca graful era dat unit si trebuia sa te chinui            putin cu el ca sa-l desparti in doi arbori

Despre celelalte doua nu pot comenta nimic de rau, din moment ce nu le-am rezolvat. Dar mi se par frumoase si grele amandoua. Mai ales magnetul

[•klamathix]

De fapt la SymmetricGraph sursa oficială nu separă arborii deloc și nu face nici dinamică .

Sunt 2 operații pe care le poți face până graful devine o singură muchie, cu capacitate egală cu fluxul:

- Dacă ai un nod X cu grad 2 (el nefiind sursa sau destinația) și cu vecinii A și B, poți tăia nodul X și muchiile sale și să duci o singură muchie A - B cu capacitate min(cap[A][X], cap[X][B ])

- Dacă ai mai multe muchii între două noduri, le poți contopi însumând capacitățile.

Operațiile se pot simula rapid cu o coadă și niște map-uri. http://www.infoarena.ro/job_detail/1719499?action=view-source

[•depevlad]

Am inteles. Imi retrag comentariile atunci, eu nu m-am prins decat de solutia de care am zis mai sus. Oricum, felicitari pentru runda! 

[•moise_alexandru]

Cand se afiseaza solutiile problemelor?

[•PlayLikeNeverB4]

Am inteles. Imi retrag comentariile atunci, eu nu m-am prins decat de solutia de care am zis mai sus. Oricum, felicitari pentru runda! 

Iar eu stau aici si ma uit la sursa mea cu heavy path... 

[•Djok]

Am inteles. Imi retrag comentariile atunci, eu nu m-am prins decat de solutia de care am zis mai sus. Oricum, felicitari pentru runda! 

Iar eu stau aici si ma uit la sursa mea cu heavy path... 

Trimite-o pe arhiva, sau descrie ideea, te rog ^_^

[•PlayLikeNeverB4]

Pentru fiecare muchie "speciala" gasesti drumul de ameliorare care trece prin ea. Pentru asta, te uiti pe drumul de la frunza la radacina si trebuie sa afli minimul dintre capacitatie muchiilor. Faci asta pe ambele parti ale muchiei "speciale" si apoi scazi niste capacitate de pe cele 2 drumuri.

[•andrei.arnautu]

Poate explica cineva cum se facea OneOuts de 100?

[•GavrilaVlad]

In primul rand vreau sa felicit echipa infoarena pentru runda bine organizata, rezultatele prompte si problemele interesante! In al doilea rand, o sa descriu experienta pe care am avut-o dand acest concurs in timp ce eram pe drum de la Cambridge la Edinburgh, pentru ca, zic eu, e nostima:

• 3:20 (ora locala UK, timpii sunt aproximativi) - Soseste autocarul National Express la Cambridge, cu o intarziere de 15 minute. Ma intreb daca mai merita sa dau concursul, fiindca picam de oboseala. Deoarece scorurile la general sunt stranse, decid ca da, inca e o idee buna.
• 4:00 - Dupa un scurt somn, ajung la Stansted Airport. Trec de check-in si security.
• 4:20 - In zona de duty-free, caut niste scaune libere sa ma intind sa dorm. Gasesc trei mai ferite (unde erau mai putini pasageri), imi pun ceasul pentru ora 7:15, ma intind si adorm.
• ~5:00 - 7:50 - Ma trezeste un om de la paza, zice sa ma trezesc ca vor si alti pasageri sa se aseze. Imi pierd urmatoarele 3 ore uitandu-ma prin magazine si cautand locuri sa stau jos.
• 7:55 - Se afiseaza poarta de plecare, merg pana acolo, scot laptopul, ma conectez la WiFi gratuit. Termin exact cand incepea concursul.
• 8:00 - Descarc toate enunturile problemelor si le salvez ca PDF. Nu se stie daca Chrome-ul o sa-mi tina paginile deschise fara net si nu vreau sa risc.
• 8:02 - Citesc Marvel. Nu pricep exact ce vrea de la viata mea. Incepe imbarcarea; decid sa urc ultimul in avion ca sa citesc toate problemele si sa am la ce ma gandi. Mai citesc o data Marvel, inteleg ce vrea, dar nu ma prind cum sa fac.
  
• 8:10 - Citesc Symmetricgraph2. Citesc "Prietenul vostru, pe care, pentru a-i păstra anonimitatea, îl vom numi Xdărăscu, v-a sugerat următoarea construcţie"; ma bufneste rasul; cativa oameni de acolo se uita dubios la mine. Ma prind ca de fapt trebuie sa gasesc arborele initial cu min(capacitate_din_primul, capacitate_din_al_doilea) pe fiecare muchie. Ma gandesc sa fac cu ceva BF in paralel.
• 8:15 - Citesc OneOuts. Geometrie, nu merci! Citesc Magnet. Pare interesanta, pacat ca n-am timp de ea.
  
• 8:20 - Boardingul e aproape gata. Pun laptopul pe sleep inapoi in bagajul de mana. Omul de la check-in zice ca nu mai e loc pentru bagajele de mana in avion, trebuie sa-l pun la cala (procedura standard Ryanair de care uitasem: primele 90 de bagaje de mana merg in avion, restul la cala). Ma targuiesc cu el, imi da voie sa iau laptopul cu mine.
• 8:25 - Imi iau locul in avion (2F), cumparat special pe 10 lire pentru loc extra pentru picioare laptop. Ma prind ca Marvel e de fapt sortare topologica si o dinamica simpluta.
• 8:35 - Se termina safety briefing-ul si avionul se indreapta spre pista. Ma prind exact cum fac BF-ul in paralel la Symmetricgraph2.
• 8:46 - Avionul decoleaza inaintea programului. Termin in minte detaliile de implementare la Symmetricgraph2 (ce vectori folosesc, structura sursei, etc.)
• 8:55 - Se stinge semnalul "Legati centurile". Scot laptopul din punga cu pliante cu informatii in caz de urgenta, de unde-l pusesem, deschid Codeblocks-ul si ma apuc de Marvel. Pasagerii de langa mine se uita ciudat si se muta pe scaunele de pe partea cealalta a culoarului. Sper ca nu se gandesc ca sunt terorist si ca doar ii deranjeaza tastatura.
• 9:15 - Termin de scris Marvel. Testez pe exemplu, pare ca merge. Extind exemplul cu o muchie, inca merge. Good enough. Ma apuc de Symmetricgraph2.
  
• 9:35 - Termin de scris Symmetricgraph2. Testez pe exemplu, nu merge. Nu mai am timp sa repar, stewardesa imi zice sa inchid laptopul pentru ca incepe aterizarea.
• 9:45 - Avionul aterizeaza in Glasgow cu 15 minute mai devreme. Mor de ciuda.
• 9:50 - Ies din avion, ajung la bagaje. Ma conectez la net, repar bugurile de la Symmetricgraph2 si trimit. Ambele teste de feedback trecute. Trimit Marvel - pica primul test de feedback. Damn...
• 9:55 - Preiau bagajul. Caut buguri in sursa la Marvel, gasesc ca doar initializarea poate fi problema.
• 10:04 - Comentez initializarea complet si trimit. WA pe ambele teste.
• 10:25 - Ma prind ca am comentat prea mult din initializare. Trimit comentariul doar la partea pe care o credeam gresita, OK pe ambele teste de feedback. Cred ca problema (mai exact solutia oficiala) e gresita (scapa un caz particular), apoi ma prind ca de fapt chiar initializam prost... Decid ca celelalte probleme sunt prea grele ca sa termin pana imi pleaca trenul (pana si bruturile) asa ca nu merita sa continui. Iau autobuzul si apoi trenul spre Edinburgh.
• 12:02 - Ma uit la monitorul de evaluare pe telefon. Constat cu surprindere ca rezultatele sunt puse deja si ca am luat 200. Yay!

[•depevlad]

Poate explica cineva cum se facea OneOuts de 100?

Si eu as vrea sa aud solutia de la oneOuts