Feedback Algoritmiada 2013, Runda 4

[•savim]

S-a terminat Runda 4 a concursului Algoritmiada 2013. Rezultatele se vor pune in cel mult 10 minute. Va asteptam parerile despre aceasta runda !

[•costyv87]

Stiti cati se califica la finala ?

[•vld7]

fac exceptie anul asta si-i iau pe primii 20 de la 11-12.

[•PetcuIoan]

Problemele au fost smechere,dar am busit cam mult asa ca nu pot spune ca mi-a placut.

[•costyv87]

eu intrebam la modul serios

[•harababurel]

Se va face un update de rating pentru ultima runda .com si cea de astazi?

@Vlad Costin: din cate stiu, primii 10 / grupa de varsta, + cei de pe locul 10, in caz ca exista punctaje egale.

[•rares96cheseli]

cand se vor publica solutiile ?

[•Anduu]

La 5-9 nu stiu daca avea ce cauta problema Drumetii, tinand cont ca a fost data si la 11-12...

[•veleandu]

La 5-9 nu stiu daca avea ce cauta problema Drumetii, tinand cont ca a fost data si la 11-12...

Viata e dura si are multe aspecte.
Daca problemele nu s-ar repeta, ar trebui un set urias de probleme.

[•danalex97]

Una peste alta mi-a placut runda. Felicitari comisiei !

[•superman_01]

intr-adevar o runda interesanta

[•Anduu]

La 5-9 nu stiu daca avea ce cauta problema Drumetii, tinand cont ca a fost data si la 11-12...

Viata e dura si are multe astecte.
Daca problemele nu s-ar repeta, ar trebui un set urias de probleme.

Nu am zis sa se faca set separat pentru fiecare, dar cred ca mai bine nu o mai puneau sau.. nu stiu. Din cate am inteles, se facea cu dinamica pe arbori, sau ceva de genul?

[•GavrilaVlad]

Runda a fost tare, cu exceptia enuntului de la Drumetii.

Precizarea "Stim ca in padure exista cel mult N luminisuri terminale." este neclara, si se poate referi fie la fiecare configuratie de drumuri in parte pe care merg personajele (ceea ce ar fi evident, deoarece fiecare se opreste in maxim un luminis), sau la reuniunea tuturor configuratiilor de drumuri (ceea ce ar insemna ca sunt maxim N frunze in arbore).

Eu am inteles ca ar fi vorba de prima varianta (pentru ca enuntul referitor la luminisuri terminale se construia pe un caz "In cazul in care un personaj ajunge intr-un luminis din care nu poate iesi (nu exista cararui nevizitate), atunci acel personaj se va opri."). Asa ca am rezolvat problema pe caz general (3^N * P complexitate). Dupa a doua interpretare, pe care am aflat-o abia dupa concurs, problema era mai usoara, si se putea rezolva intr-o complexitate de 2^N * N^3 sau 2^N * N^2.

Thumbs down pentru neclaritati de genul asta  

[•SebiSebi]

Pana la urma cati se vor califica la runda finala pentru clasele 11-12?   Multumesc!

[•wefgef]

Cel putin 10. Speram sa calificam mai multi, depinde de sponsori.

[•andreii1]

tare runda , pacat doar ca la prima problema de la a X-a era doar de aplicat un algoritm pe graful dat  
aveti cumva idee cand se updateaza ratingurile? ( si de la .com, si de la runda asta)

[•klamathix]

Nu era de aplicat niciun algoritm . In general, politica noastra e sa nu propunem probleme care au nevoie doar de un algoritm SF sau necunoscut in concursuri cu miza.  Ca lumea cauta pe google si gaseste diverse obscuritati, asta e altceva. Problema asta era rezolvabila cu meet in the middle, no wikipedia needed.

[•Mihai22e]

Cand se desfasoara runda finala?

[•MciprianM]

Mie mi-a placut problema lumanari. Genul de problema la care e foarte usor sa crezi ca ai solutia corecta - desi esti destul de departe. Am mai vazut pe topcoder ceva greedy-uri despre care ai jura ca sunt corecte, cand de fapt sunt total gresite si necesita de fapt ceva DP sau ceva cuplaje/fluxuri pe grafuri. Asta nu stiu cum se rezolva, dar sigur e ceva tare.
Legat de problema alianta - nu's genul care sa optimizeze back-uri. Asa ca nu prea mi-a placut. Desi ar trebui sa ma uit peste ca apar tot mai multe meet in middle.
La Rama am facut in O(n^3) si am luat 40p cu TLE pe restul. Cica se ia 100 cu O(n^3)  
La radacina2 nu am apucat sa ma uit prea bine.

In total a fost bine si site-ul s-a descurcat acceptabil. Pacat ca anul asta nu vedem la finala!

Distractie la finala celor care s-au calificat si sa luati premii mari!

[•gapdan]

Cand se afiseaza niste solutii la problemele date astazi?

[•proflaurian]

Solutia mea e un fel de greedy. Sortez lumanarile si adun in ordine descrescatoare 0,1,2,...,m-1. Apoi sortez iar si pun lumanarile in ordine descrescatoare. Solutia e prima pozitie unde inaltimea modificata este strict mai mica dacat indicele. Din pacate nu am sesizat ca lumanarile pot avea si inaltime nula si acelea nici nu trebuiau luare in calcul. In cele din urma am luat 7 teste dar cu gruparea la teste am  mai pierdut un test.

L.E. Solutia e gresita. Intradevar pe exemplul de mai jos dat de Alex Velea nu functioneaza.

[•savim]

Testul 2 nu are lumanari de inaltime 0 .

[•veleandu]

Solutia aceea merge pe un test de genul

6
4 4 4 4 4 4

?

Cam asa a fost si ideea mea initiala .. Dar am ajuns la concluzia ca era gresita

[•repp4radu]

Cred ca un articol cu solutiile ar fi binevenit 

[•danalex97]

Cred ca un articol cu solutiile ar fi binevenit 

De acord.