128 Curse de cai

[ditzone]

Aici puteţi discuta despre problema Curse de cai.

[•vladcyb1]

Greedy-ul pt problema asta va ramane un mister pt multa lume sau cineva se va indura sa dea un hint ? ....

[•domino]

Din cate am vazut la concurs, n-a fost un mare mister greedy-ul corect...  apropo, problema poate fi rezolvata si cu dinamica.

[•wefgef]

incearca sa maximizezi numarul curselor castigate de gigel, incercand sa pui fiecare cal de-al sau sa concureze cu un adversar pe care poate sa-l invinga, cat mai puternic.

[•greco]

Cred ca ar fi bine sa nu mai spuneti cum se rezolva problemele... altii vor invata destul de greu daca nu mai trebuie sa gandeasca, gasind pe forum solutiile care au fost acceptate.  

[cristi8]

nu, deci pe bune. ce faceai in caz ca un cal al lui gigel avea aceasi viteza cu un cal de-al adversarului (si nu putea bate nici un alt cal) ? il bagai la egalitate sau il puneai sa piarda ? cum decideai ?

[•calinux]

Ahem... poate ca pare ciudat... dar... n-ar fi fost mai buna egalitatea?  
Adica ... daca nu putea bate un alt cal... e clar ca profitul adus era <=0 ... deci ... cea mai mare valoare... nu ar fi 0? Adica remiza?

Eu faceam in felul urmator:
1. Sortam caii si ai lui gigel si ai lui ionel crescator.
2. Pornind de la 1 parcurgeam caii astfel:
  2.a. Daca cal Gigel > cal Ionel => Gigel+200 lei. Se trece la urmatorii 2 cai.
  2.b. Daca cal Gigel = cal Ionel se trece la urmatorii 2 cai.
  2.c. Daca cal Gigel < cal Ionel => Gigel-200 lei. Se compara calul acesta al lui Gigel cu urmatorul cal al lui Ionel.

In mod normal ar trebui sa asigure ca caii care vor castiga sunt maximi.  

[•domino]

Ahem... poate ca pare ciudat... dar... n-ar fi fost mai buna egalitatea?  
Adica ... daca nu putea bate un alt cal... e clar ca profitul adus era <=0 ... deci ... cea mai mare valoare... nu ar fi 0? Adica remiza?

Eu faceam in felul urmator:
1. Sortam caii si ai lui gigel si ai lui ionel crescator.
2. Pornind de la 1 parcurgeam caii astfel:
  2.a. Daca cal Gigel > cal Ionel => Gigel+200 lei. Se trece la urmatorii 2 cai.
  2.b. Daca cal Gigel = cal Ionel se trece la urmatorii 2 cai.
  2.c. Daca cal Gigel < cal Ionel => Gigel-200 lei. Se compara calul acesta al lui Gigel cu urmatorul cal al lui Ionel.

In mod normal ar trebui sa asigure ca caii care vor castiga sunt maximi.  

Ce faci pentru?

Cod:

1 2 3 4 5
1 2 3 4 5

Se poate obtine castig 600 astfel: 2-1, 3-2, 4-3, 5-4, 1-5.

[•bogdan2412]

Nu e atat de simplu... In primu rand sortezi descrescator.

Adica ... daca nu putea bate un alt cal... e clar ca profitul adus era <=0 ... deci ... cea mai mare valoare... nu ar fi 0?

Se poate obtine profit pe viitor daca pierzi la momentul actual. Uite un exemplu:
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

Greedyu tau iti da 0, solutia corecta este 1000   (1 joaca cu 7, 7 cu 6, 6 cu 5, 5 cu 4, 4 cu 3, 3 cu 2, 2 cu 1)
In caz de egalitate trebuie sa analizezi toti caii ce urmeaza dupa cei doi care se afla la egalitate si sa vezi care din cele doua cazuri ar fi mai bun (te las sa te prinzi). De asemenea daca la pasul i calul al lui Gigel ar pierde in fata calului lui Ionel atunci pui calul cu viteza cea mai mica a lui Gigel sa concureze cu calul lui Ionel, ca sa pastrezi caii cei mai buni pentru restul cailor lui Ionel.

[cristi8]

In caz de egalitate trebuie sa analizezi toti caii ce urmeaza dupa cei doi care se afla la egalitate si sa vezi care din cele doua cazuri ar fi mai bun

backtracking ?

[•Zeus]

ceva in O(N) asa ... back nu prea intra [ depinde ce intelegi prin back ].

[cristi8]

pai din cate am inteles eu e O(2^N).
daca ai vitezele lui gigel egale cu cele ale lui ionel

Cod:

v1 v2 v3 v4 v5
v1 v2 v3 v4 v5

vezi ca v1 sunt egale, treci la urmatoarele. vezi ca v2 sunt egale, treci la v3.. si  tot asa.. si vine O(2^N)

..am inteles gresit ?

[•fireatmyself]

La problema aceasta sunt doua solutii la care poti sa te gandesti :
1) greedy
2) dinamica

Prima solutie este un N^2. Cristi, tu ai inceput bine cu backtracking-ul, dar trebuie sa vezi cum il faci astfel incat sa efectueze N^2 operatii. de fapt nu este nevoie sa generezi toate combinatiile intre caii lui ionel si caii lui gigel, ci doar cateva.

A doua este o dinamica 2d ce se bazeaza pe trei chestii : ce faci cand calul tau e mai incet decat al adversarului, ce faci cand e mai rapid si ce faci cand caii sunt egali d.p.d.v al vitezei.

Sper sa ajunt, nu sa supar, pe cineva cu hint-urile astea . Daca vor fi probleme se poate sterge post-ul meu

Codare fericita in continuare.

Btw. stie cineva cand invie evaluatoru

[•greco]

pai din cate am inteles eu e O(2^N).
daca ai vitezele lui gigel egale cu cele ale lui ionel

Cod:

v1 v2 v3 v4 v5
v1 v2 v3 v4 v5

vezi ca v1 sunt egale, treci la urmatoarele. vezi ca v2 sunt egale, treci la v3.. si  tot asa.. si vine O(2^N)

..am inteles gresit ?

Nu te mai gandi la nimic ne-polinomial.  

[•y2k]

am si eu o problema...... nu imi ajunge memoria (am o matrice de 1000 pe 2) si imi da eroarea RUN ERROR - Invalid memory reference . Cata memorie este  disponibila?

[VladS]

Ce ai declarat tu are aproximativ 2 kb deci nu depasesti memoria. Ca sa te prinzi de ce primesti mesajul ala ai putea sa consulti
articolul din cadrul site-ului.

[cristi8]

iti intra si matrice 1000 pe 1000. sunt 64 de mb parca

vezi ca ti-o iau razna indicii si te duci in balarii

[•y2k]

nu depaseste

[•MarcvsHdr]

Va rog eu mult, puneti in textul problemei si limitele la problema asta. De exemplu:
- Cate teste sunt in fisier?
- Cat de mari/mici pot fi vitezele?

Oricum, eu tot ia 0 si nu imi dau seama de ce .
Fac cam asa ceva: (ambele grupuri de cai sortate desc)
Suntem la gigel [ i ] :
1. gaseste cel mai rapid cal al lui Ionel pe care il poti bate si bate-l (eivdent, nu luam in calcul caii care deja au luat parte la concurs).
2. daca nu poate bate pe nimeni, vezi, totusi, poate macar faci o remiza.
3. daca nici macar o remiza nu poti face, atunci de acum incolo sigur pierd toti caii lui Gigel, pt. ca gigel[i+1]<=gigel[ i ], oricare ar fi i=1,n-1

Am incercat o gramada de teste si toate dau corect. Si deja stau de ceva vreme la problema asta, si ma frustreaza.

[•Florian]

Uite un exemplu:
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

Greedyu tau iti da 0, solutia corecta este 1000  (1 joaca cu 7, 7 cu 6, 6 cu 5, 5 cu 4, 4 cu 3, 3 cu 2, 2 cu 1)

Nu stiu dak ideea ta functioneaza...

[later edit] Nu ! Am gresit eu...iti da corect...sorry.. Dar si eu am aceeasi problema... iau 0 puncte cu un algoritm care da corect pe toate exemplele mele...help me careva,...am citit toate mesajele de pe forum...dar pb asta ma dispera...

[•devilkind]

totusi la problema asta ar mai trebui puse niste restrictii, cum ar fi viteza maxima a unui cal

[•cos_min]

Cat va da pentru :

Cod:

1
31
42 18468 6335 26501 19170 15725 11479 29359 26963 24465 5706 28146 23282 16828 9962 492 2996 11943 4828 5437 32392 14605 3903 154 293 12383 17422 18717 19719 19896 5448 
21727 14772 11539 1870 19913 25668 26300 17036 9895 28704 23812 31323 30334 17674 4665 15142 7712 28254 6869 25548 27645 32663 32758 20038 12860 8724 9742 27530 779 12317 3036 

[•DITzoneC]

3000

[•Robytzza]

mie imi da tot 3000 si pe orice test facut de mine da bine,si iau incorect 

[•c_sebi]

Ia vedeti ce obtineti pentru

9
6 4 4 4 4 2 2 2 1
4 4 4 4 4 2 2 1 1

ar trebui sa va dea

600

Edit: Am corectat raspunsul.