E corect exemplul 2? Se cere nivelul minim 100 iar el termina jocul cu nivelul 19?

In caz ca nu mai poate merge pe alta misiune pentru ca are N-ul la un moment dat prea mic, se returneaza valoarea respectiva.
Nu se precizeaza in enunt, dar si eu am dedus asta din exemplul 2.

Va rog... imi poate spune si mie cineva cu 100 puncte care este rezultatul pentru cateva teste cu valori mai mici...
de exemplu: 
S 3
S 4
C 3
C 4
pentru ca chiar nu reusesc sa ma prind de formula...                             

La testele date de tine, in ordine, mie-mi da:

Cod:

6
9
16
25

Daca nu iti iese, poate te ajuta articolul cu solutii !!
 

Ma indoiesc. Problema a fost adaugata in 22 februarie.
In principiu e greu sa inventezi un nou tip de problema. Deci e normal sa aiba pe undeva unele asemanari cu alte probleme.

am facut problema de 90 puncte...iese din timp la un test...cum ati rezolvat-o voi?...care ati luat 100...eu am facut pur si simplu , un lee clasic...

Si eu am patit la fel. Incearca sa maresti coada ...

Ma bag eu la Componente Tare Conexe, Sortare Topologica si Algoritmul lui Kruskal.
Am trimis mesaj privat si la Filip B.

Super initiativa !
 

Ca sa intelegi operatiile de baza pe biti te poti uita aici.

 

Hm...si eu mi-am instalat MinGW zilele trecute la sugestia din postul lui Silviu Ganceanu.

Si eu intampin probleme dar la alt capitol.
Nu imi dau seama ce nu poate sa iti mearga.Dai File - New - Files - C/C++ Source File. Ca sa iti faci fisierele de intrare si iesire alegi din lista fisier de tipul "Text File".

Problema la mine e ca nu pot sa compilez.Nici sa dau Compile, nici Debug si nici Build. Am scris o sursa de test si nicicum nu reusesc sa il fac sa o compileze.

[Later Edit] M-am prins de ce nu merge.Din cate am inteles din postul lui  Pripoae Teodor Anton, MinGW compileaza numai proiecte. ( topic)

sau C#  ( Visual Studio 2005 Express Edition )

[Hardware failure. This round is nullified. Tomorrow at the same time will be a new qual round.]

Din motive tehnice, Qualification Round 3 din cadrul TopCoder Open 08 s-a mutat Miercuri 13 februarie, ora 14:00.

Citez mesajul unui admin:

visualage:" Hardware failure. This round is nullified. Tomorrow at the same time will be a new qual round. "

Ca se da examenul a 2-a zi dupa Politehnica Buc. . Si ca e destul de grea admiterea

Sa inteleg ca dai in UPB ?

cat va da pe testul asta:
5
1 1 1 2 3
3 1 3 3 3
1 2 3 4 4
5 6 6 6 6
1 1 1 1 1

Cu sursa de 100.

Cod:

5
1 3
1 4
2 4
3 4
4 4

Ar merge o grupare a testelor pe problema asta.Se poate lua 85 de puncte facand DF din fiecare nod si actualizand costul minim dintr-unul din fii sai.

Eu lucrez cu 2 vectori in care retin: v - nr minim de pasi de a fi ajuns la treapta i si p - pretul minim de a fi ajuns la treapta i in v pasi.
Parcurg i de la 1 la n si de pe scara i analizez cele 3 cazuri de a actualiza v si p pentru scarile de dupa i (beau apa, beau energizanta, urc normal). cand v[j]>v (cu j dupa i) actualizez v[j]=v+1 si p[j], iar cand v[j]=v+1 actualizez p[j]. Plec cu v[1]=1 si p[1]=0 si afisez v[n] si p[n].
Unde gresesc ? (iau 35 p, in rest WA)...

Si eu luam tot 35 cand in dinamica, la partea du energizant faceam

Cod:

for ( j = 1; j <= suc[i]; ++j )

si actualizam  (i + 2*j ).

Ar trebui sa iti mearga daca faci

Cod:

for ( j = 1; j <= 2*suc[i]; ++j )

si actualizezi i + j.

Mai era si Eric Price(USA) parca...

care e diferenta dintre scanf ("%g", &N)si f<<g[/i]

Pai scanf e mai rapida.E citire specifica limbajului C, pe cand cu f >> g este specifica C++.
Exemplu daca citesti de la tastatura numarul intreg n, atunci o sa ai

Cod:

scanf( "%d", &n )

sau

Cod:

f >> n; // citirea cu streamuri

Si din pacate 7 romani care nu o participe in finala.

Chiar nici unul nu mergeti ? 

4 romani in primii 10 si in total 7 calificati in finala.

Bravo pentru toti romanii !
( Victorsb, PaulDB, mastermage, Prostu, devilkind, donalexey, sims, dmihai, binary_fire, moga_florian )

Misto articolul.
Am o intrebare...Cum de ai putut face si mate si info in liceu ? Ca din cate tin minte ai luat si Premiu III pe la ceva ONM ....si totusi si locul I la ONI in clasa XII ...

Cum ai avut timp de amandoua ?   

testul 4 are ceva special ?

Nu cred sa fie ceva special.Ai grija la implementarea operatiei pe numere mari.Eu uitam sa reinitializez sirurile cu 0 cand calculam al n-lea termen Fibonacci. ( sau vezi cu dimensiunea sirurilor )

 

Si eu pot ajuta la scris enunturi pt a fi adaugate problemele in arhiva...

Daca mai aveti material ma bag si eu 

Articolul e terminat. Sper doar sa ajute pe cineva.

http://infoarena.ro/Heavy-path-decomposition

Misto articol Marius.
@admini: Ar merge un news in Arhiva de Stiri despre articolul nou-postat.
 

Am si eu o intrebare.
Eu am facut initial un O(N^2 * log(N) ). ( presupunand ca am a, b, c , am cautat binar (2*c -b, respectand precizarile din enunt) ).Totusi nu TLE-urile pe ultimele 6 teste ma deranjeaza, ci faptul ca iau WA pe pe testele 1, 3, 4. Am diferente foarte mici. ( chiar o unitate pe 2 teste ).Nu imi dau seama ce poate sa fie .... ( pe exemplele problemei imi da corect. ). Am tot facut Debug dar nu imi dau seama ce gresesc.

In al doilea rand, m-am uitat dupa aceea pe solutia oficiala.La ce foloseste functia aia de random() pe valorile sirului inainte de aplicarea efectiva a rezolvarii descrise ?

 

si sa nu uiti sa faci % C la fiecare pas pentru ca (A*B) % C = (A%C)*(B%C) 

(A*B)%C = ((A%C)*(B%C))%C

Pf...care poate sa-mi explice mai clar principiul cu care rezolv problema asta...ca nu inteleg...

si sa nu uiti sa faci % C la fiecare pas pentru ca (A*B) % C = (A%C)*(B%C) 

Iau 90 de puncte cu 1 TLE

Am optimizat tot ce am putut optimiza. Dinamica are complexitatea de O(A*nrdiv(B)*KONSTANTA )
unde KONSTANTA <= 9(defapt e numarul de divizori a lu B mai mici ca 9). Am pus scaderi in loc de modulo si tot nu merge. Iau TLE pe testul 9.

Ce optimizari as putea sa mai fac ?

Am trimis ca test si solutia oficiala si ia TLE pe acelasi test 9.
Am citit mai sus ce a scris peanutz dar nu prea am inteles.

[LATER EDIT] A mers pana la urma de 100.Trebuia sa scap cumva de operatia aia de impartire care manca mult timp.   ( Thanks Cosi )