infoarena

Runda 2 (http://www.infoarena.ro/algoritmiada-2015/runda-2) a concursului Algoritmiada 2015 (http://www.infoarena.ro/algoritmiada-2015) s-a incheiat. Felicitari castigatorilor (http://www.infoarena.ro/algoritmiada-2015/runda-2/clasament/juniori)! Asteptam feedback-ul vostru. :)

o sa fie disponibil si clasamentul pertotal (cele 2 runde) sau e doar pt inspectori ?

Felicitări lui Vlad Gavrilă, singurul care a rezolvat problema Victorie!

Felicitări și lui Alex Velea, singurul care ar fi rezolvat problema Poveste dacă matricea ar fi fost pătratică!

o fost dragu problemele chiar daca nu mam prins de iele , felicitrari comisiei, #FLC

Credeam ca runda dureaza 5 ore, si la un moment dat ma uitam pe monitor si ziceam "Lol, le pica evaluatorul si putem vedea punctajele"  :banana: . Pe langa asta, problemele au fost interesante si vad ca domnul Calancea s-a tinut de cuvant si a dat mai greu la runda 2.

Problemele mi s-au parut interesante.Totusi la two sets solutia oficiala era hash sau era ceva mai destept?

Hashuri cu multe numere prime mari. Probabilitatea ca numarul sa se divida cu toate fiind foarte mica :-).

Mie mi-a intrat din prima cu un hash de ordinul 10^14. Stiu ca e mai mica probabilitatea sa pice la 2 hashuri de 10^9 dar e mai comod asa :)).

Poate sa-mi dea cineva si mie ideea de 100 la poveste?M-am prins de o solutie in M^2*N/18, dar n-am nicio alta idee si sunt chiar curios.

Gandeste-te ca fixezi linia de jos a submatricii. Dupa sorteaza lexicografic coloanele, vezi ce iese :P

Ar fi bine daca s-ar posta solutiile, va rog.   :roll:

Inteleg ca e mult lucru sa scrii o solutie bine explicata, dar totusi ar fi bine ca dupa fiecare concurs sa fie cel putin postate niste indicii care sa elucideze rezolvarea problemei.(vreo 4-5 randuri)

Spui bine. Poti sa intrebi aici si iti vom raspunde :-).

cum sa face problema drum6 printr - o complexitate mai optima decit O(n^3) si cum se face problema k-bubblesort??

Drum6 - Motivul pentru care nu merge un simplu greedy e ca la un moment dat s-ar putea sa ai 2 celule egale si nu stii pe unde sa o iei. Deci, poti sa tii intr-o lista celulele pana la care ai un drum minim lexicografic si tot inaintezi. E un fel de bfs.

K-BubbleSort - Simulezi algoritmul din problema, cu optimizarea ca retii pozitiile la care ai v[i] > v[i+1]. Complexitatea e O(N+K).

Problema Drum6 nu se poate face si cu programare dinamica ?  ](*,)

La solutia cu programare dinamica ar trebui sa retii sirul minim lexicografic pe care il poti obtine ajungand la o celula (i, j) iar asta e O(N^3).

Eu am facut dinamica in N^2, bazandu-ma numai pe celula de deasupra si cea din stanga celulei curente. :P

Prin dinamica eu inteleg ca rezultatul se afla in dinamica. Ce ai facut tu e tot un fel de BFS.

ni ba , daca tot pica inainte de bac algoritmiada r 3 rog propunatorii de probleme sa creeze enunturi care au legatura cu operele de bac
 (enigma otiliei, morometii , floare albastra , plumb , sau ultima noapte ) poate asa o sa trec si eu :) multumiri . :D

Sustin!