asta http://hackpedia.info/viewtopic.php?f=121&t=5065 ? 

Am pierdut un pariu

Uitati-va aici:
http://infoarena.ro/job_detail/551091?action=view-source

=))))))))))))))))))))))

incredibil hahahahah. mai vazusem un hello world cu zeci de constante, dar asta intrece orice chestie =))

Am implementat bellman ford cu coada cu liste si a aparut o problema...
Structura e

Cod:

struct lista
{
    int inf,c;
    lista *nod;
} *g[nmax];

si nmax din ce stiu eu inseamna numarul de noduri... si 1 ≤ N ≤ 50 000 din enunt. cu 50 005 iau killed by signal, cu m ( 250 005 ) pus iau la fel killed by signal, bea cu 500 005 iau 100 puncte. E gresit in enunt sau problema este de la mine? Tot ce am modificat a fost doar nmaxul respectiv ca sa obtin 100.

iei dreapta 1-2, 3 e la stanga.. iei dreapta 2-3, 4 e la stanga.. iei dreapta 3-4, 5 e la stanga.. iei dreapta 4-5, 6 e la stanga ... etc
primele 2 puncte selectate nu conteaza.. poti incepe si din 5-6 ...

of of ... faza cu backtrackingul era doar de verificare a rezultatului. din moment ce tu nu ai teste oficiale / sau nu e pe infoarena/campion cum vrei sa te verifici ?

4 directii... nu am citit problema in amanunte... e o problema clasica... in fine. Daca intrebi de backtracking la a IX-a ... banuiesc ca nu stii recursivitate deci vorbesc singur T_T

ideea era ... sa iti faci 2 vectori de deplasare, dx si dy cu valorile -1, 0, 1, 0 si 0, 1, 0, -1 si sa apelezi backtrackingul dupa pozitia i si j... in el faceai un for de la 0 la 4 pentru deplasare... si foloseai inca o matrice uz[j] = 1 daca a mai fost pe acolo sau nu... din ce-am citit parca iti cere din (1, 1) in (n, m) sa ajungi... si de fiecare data cand atingi n, m verifici daca e mai mare ca maximul curent...

nah si daca vrei si drumul... de fiecare data cand gasesti un maxim nou, faci reconstituirea recursiv... ai putea de fapt in loc sa folosesti uz[j] = 1 sau 0 sa pui chiar o valoare care tot creste pana ajunge in (n, m)... daca esti in i, j si te duci la dreapta, in uz[j+1] = uz[j] + 1; si pe baza asta faci recursiv... din (n, m) cauti cu unu mai mic... de acolo iar cu unu mai mic si tot asa


....

am uitat de italic .. ma rog cred ca se intelege

Faci un backtracking. pe 8 directii ( parca asa cere ), iti faci vectorii aia si te duci pe fiecare drum posibil si.. la sfarsit afisezi doar maximul ala sau cat iti cere si cam asa te verifici. ( reconstituirea drumului nu cred ca fi o problema ... daca a aflat bine maximul ... da-l incolo de drum )

iar pentru teste dai pur si simplu ... random. pui si tu valori mai mici in matrice intre 1 si 10 nah.. vezi tu ...

oricum backtrackingul asta merge repede implementat..

Pe desenul ala ... numai cu intoarceri la stanga si da bine.

Iei oricare 2 puncte prima oara, si urmatorul sa fie la stanga sau la dreapta fata de dreapta ... urmatorul sa fie la fel la stanga sau la dreapta (cum ai ales inainte) fata de ultima dreapta formata ... bla bla bla etc tra la la .

Poti folosi codeblocks sa vezi in cat timp iti ruleaza si dai pe un test random ... fisierul .in continand doar n, m si o matrice n-ar fi mare chestie.

Mai erau o functie/ sau functii sa iti afiseze si timpul de executie, dar nu le-am folosit niciodata, doar le-am vazut prin alte surse ... poate aici gasesti http://www.cplusplus.com/forum/beginner/1769/

Iar codul sursa ... din ce m-am uitat pe el nu stiu daca da mereu solutia cea mai buna ... asta ai verificat ? Intra sigur in 1 s oricum ... din ce vad faci doar n*m maxim (acuma nush cat e n si m ... )

In arhiva aia se precizeaza 3 licee... probabil asa au aflat
stiu doar de racovita ... dar e unu si in iasi daca nu ma insel

Mersi, am gasit ... 18-24 Aprilie ... pacat ca nu am gasit si orasul.

pe cat e ONI (daca stie careva) ? si... unde? nu am gasit nicaieri T_T

http://www.youtube.com/watch?v=O13luYEu6P0

To the metric system!

(uitati-va la tot)

Pe 4 2 si 4 1 raspunsul e 3 deci 2 felinare si in enunt zice nicio strada sa fie complet luminata, deci care e explicatia ?

Pentru 3 8 4 si punctele 2, 2, 3, 1 o parcurgere de genul
- urc 2 bete in sus, 2 bete la dreapta, un bat in sus si 3 in jos

e corecta?

Intra pe campion, cauti ceva anume, gen grafuri sau programare dinamica si lei iei pe alea de 1-2 stele... daca nu ies, te uiti la solutii

Imi da careva un hint/ o idee cum se face cu arbori de intervale ? In comentarii n-am gasit... iar sursele... plagiate una dupa alta (toate cu cautare binara) )

arbori de intervale nu AIB !!!!

Am incercat un backtracking cu vector de blocaj si iau maxim = 2^n si din fiecare combinatie fac << 1 sau (... << 1) + 1 si rezultatul sa nu fie mai mare ca maxim.
Problema e cand ajunge la ceva in genul 110 si sa ma duc in 100... daca fac 110<<1 imi da 1100 > maxim si (110<<1)+1 imi da 1101 care e la fel > maxim.

Cum naiba retin blocajele ?

M-am uitat pe solutia oficiala si am vazut ca au a [ i ] [j] = numarul de permutari de lungime i cu ultima subsecventa crescatoare avand lungimea j si...
a[ i ][j] = a[i-1][j] + a[i-1][j-1]
a[ i ][j] = a[q][k-1] * a[i-q-1][j] * comb[i-1][q]
si ma gandeam de ce nu ar fi bun asa
a[ i ][j] = a[i-1][j] + a[i-1][j-1]
a[ i ][j] = (a[q][k-1] + a[i-q-1][j]) * comb[i-1][q]
pentru ca am nevoie de numarul de permutari cu lungimea q cu ultima subsecventa de lungime j + cealalta bucata a[i-q-1][j] si in final combinarile ca sa vad plasarile in q si i-q-1

Care este complexitatea care intra in timp ?
Eu faceam dfs initial si aflam distantele din 1 la restul si pentru fiecare muchie noua cautam sa vad daca pot "minimza" prin x, sau y... tot un fel de dfs cat timp vecinul nu e blocat si distanta de la 1 la el e mai mare decat distanta de la 1 la x sau y la el.

La fel... altfel nu luam 10 pct

Are careva un test mai... ciudat?
Tot trimit surse si iau fisier corupt pe 9 teste, am facut 6 teste si imi da corect, nu stiu ce gresesc... iar testele de la oji nu le gasesc -_-;