infoarena

Aici se pot pune întrebări legate de problema Placute (http://infoarena.ro/problema/placute) de la Runda 11 (http://infoarena.ro/monthly-2012/runda-11) a concursului Infoarena Monthly 2012.

Timpul alocat întrebărilor este de 1 ora. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

"Flamanzila nu va fura niciodata doi porci consecutivi care au aceeasi culoare a placutei"

Restrictia se refera la doi porci consecutivi ca si greutate sau ca si moment in care Flamanzila merge la furat?

Ca si moment in care Flamanzila merge la furat.

Atunci de ce raspunsul este 12? El practic poate sa fure toti porcii in exemplul dat.

NO COMMENT (scrie in enunt)

Pentru a se asigura ca Ionel nu observa lipsa porcilor, Flamanzila nu va fura niciodata doi porci consecutivi care au aceeasi culoare a placutei.

Consecutivi ca indici ai porcului sau Flamanzila nu va fura niciodata consecutiv doi porci care au aceeasi culoare a placutei?

Consecutiv doi porci care au aceeasi culoare a placutei - Nu ca indici ai porcilor.

Daca am porcii cu urmatoarele culori: a, b, a. Se considera mutari valide sa iau primul "a", dupa "b", iar apoi ultimul "a" ?

Ideea enuntului e ca daca azi fura un porc de culoare x , maine nu mai are voie sa se fure de culoare x ?

@tzipleatud DA, mutarea "aba" este considerata corecta.
@RaduDo DA. Daca acum se fura un porc de culoare X, este interzis ca urmatorul porc furat sa fie tot de culoare X.

Daca cei mai grasi doi porci sunt de culoare X, iar al treilea cel mai gras e de culoare Y, vor fi furati in ordinea X Y X sau hotul se va opri dupa primul X furat?

O sa ii fure in ordinea X, Y, X.

Pai daca nu fura doi porci consecutivi pe exemplul dat :
El nu fura prma data primul porc , apoi al doilea porc , apoi ultimul porc , iar apoi ramane de furat al 3lea porc , pe el de ce nu il ia ?

Consecutiv ca moment de timp.

Atunci enuntul este incorect... ar trebui sa fie "doi porci consecutiv" nu "doi porci consecutivi" (ceea ce duce cu gandul la unul dupa altul ca indici....)

Am modificat enuntul. Prin "consecutivi", enuntul facea referire la lista de porci pe care Flamanzila ii fura.

Pentru testul
3 2
4 1
3 2
5 1

Care este raspunsul ?   8?

12.
Ia mai intai porcul (5,1), dupa (3,2), dupa (4,1)

5+4+3 = 12.

Ce se afiseaza pentru:
7 3
5 1
3 3
6 3
4 3
1 2
2 2
7 2

Multam fain!

Mie imi da 28, nu stiu daca te mai ajuta acum dupa concurs :-"

Nu vreau sa fiu rau, dar cred ca puteati sa dati la feedback cel mai mare test, cand am vazut ca intra fara probleme pe cele doua tese de feedback nici nu am mai stat sa verific, e urat sa iasa din timp pe ultimul test :-". Cred ca la concursuri cum e monthly ar fi mai bine cu full feedback  :oops:

(http://img5.imageshack.us/img5/1274/16173496.png)

Poate sa-mi explice si mie cineva ideea de la aceasta problema? Am stat tot timpul pe ea si n-am reusit sa-mi dau seama. #-o Multumesc anticipat!

cu un algoritm brut in o(n*k) am luat 2 tleuri. solutia tinea doar de optimizare? :)

Cu o solutie neoptima eu luam TLE doar pe testul 9 (care a fost la feedback).  :)

Eu am facut-o in O(n*log k) cu heap si nu cred ca se poate optimiza brutul tau ca sa intre :)

@ Mihai22e
Eu am o abordare greedy, folosit o coada, initial goala.
Am sortat mai intai porcii dupa greutate. Am pornit de la ultimul porc (cel cu greutatea cea mai mare) pana la cel cu greutatea cea mai mica. Cand nu puteam sa iau un porc din sir, treceam "peste" el si il puneam in coada. Aici iti dai seama, cum sirul este sortat, restu porcilor ramasi in sir au greutatile mai mici decat ale celor din coada. Deci, la fiecare pas, incerc sa iau un porc mai intai din coada. Daca nu aveam nici un porc disponibil in coada, luam urmatorul din sir, pana cand nu mai pot sa iau nici un porc.
Am facut eu un exemplu, pentru ca pe cel de la problema nu se vede greedy-ul.
Deci sunt 6 porci pe care ii sortezi.
Sortare : Il iau pe primu : 6,2
Nu am nimic in coada, deci incerc sa il iau pe 5,2 . Nu pot sa il iau, deci il bag in coada. il iau pe 4,3 .
Urmatorul pas, ma uit in coada si il scot pe 5,2 .
Urmatorul pas, incerc sa ii iau pe 3,2 si pe 2,2 dar nu pot. Il iau pe 1,1. Acum am terminat elementele din sir, dar mai am coada. E evident ca in coada nu pot sa fie decat porci cu aceeasi culoare, deci pur si simplu il scot pe primu din coada, daca exista vreunu.
Deci il scot pe 3,2 din coada si am terminat.
Solutia optima 6 + 4 + 5 + 1 + 3 = 19.

Sper ca am reusit sa iti dau o idee :) . Nu prea sunt asa bun la explicatii.
P.S. Trebuia folosit long long :P
http://infoarena.ro/job_detail/842995

Eu am sortat ( NlogN ) si apoi ...

am scos O( N ).

Ideea e sa te plimbi cu "2" pointeri in felul urmator.
Daca ai sirul sortat dupa greutatea porcilor descrescator ..
Si sa zicem ca primi 5 porci sunt de culoare 1 ..
O sa fie ceva de genul.
10 1
9 1
8 1
7 1
6 1

Si tu parcurgi cu 1 pointer "varful" stivei .. si vezi ca ai porcul cu greutate 10. - "il scoti"
Apoi mergi in continuare cu al 2-lea pointer si scoti un porc care nu are culoarea '1'.

Apoi cu primul pointer, care arata cel mai mare porc, il scoti ..
Apoi cu pointerul 2 iterezi in continuare.

Acum. ( 1 )
De ce merge?
Daca primi x porci sunt de culoarea 1 .. e clar ca o sa fie scosi in oridnea asta .. porcul 1 .. primul porc care are culoarea != cu 1 .. porcul 2 ... porcul x ..

Acum, dupa ce am terminat un 'sir' ( adica o secventa in care aveam porc de culoare 1 .. altceva .. porc de culoare 1 .. altceva. )
! aici trebuie adaugat faptul ca daca am culorile 1 1 1 2 1 1 1 .. tot un sir am, deoarece toti cei 6 * 1 vor fi scosi conform regulei. adica .. 1 .. altceva ..1 .. altceva .. 1 .. etc. ^^

Acum, dupa ce am terminat sirul, sa zicem ca culoarea mea e '2' ... si SUNT SIGUR ca e cel mai 'valoros' porc.
Unde il gasesc pe urmatorul diferit de 2?

hmm .. Surprinzator, problema are o legatura cu cea cu parantezarile corecte ^^
De ce?
Deoarece se poate reformula aceasta 'subproblema' in felul urmator.

sa zicem ca culoarea celui mai valoros porc este 1 :))

Putem reprezenta sirul de culori ca fiind '1' daca culoarea este 1 .. si 0 altfel..

Sa avem exemplu.

1100111001000011111
Si putem spune ca o sa se termine "domnia" sirului ( cum am spus mai sus .. ) 1 altceva ..1 .. altceva .. 1 .. altceva ..
pe pozitia x, astfel incat .. numarul de 1 si de 0 este egal pana la pozitia x, si pozitia x+1 este 0.

Adica .. daca am avea -1 in loc de 0 ..
Ar fi cea mai mare pozitie a.i. suma pana acolo este pozitiva.
Sau cea mai lunga parantezare corecta care incepe de la "inceput" ( de unde incepe sirul ).

xD
Poate ca nu am fost foarte coerent, dar in principiu cam asta ar fi ideea.

Daca suntem la pozitia x, si gasim acea pozitie cheie descrisa mai sus la pasul y .. atunci putem sa punem toti porcii intre x si y, si sa consideram y ca fiind inceputul algoritmului.
Nu putem gasi pozitia 'y' atunci cand numarul de 1 este mai mare decat cel de 0 pe tot parculsul sirului .. Ex: 1101010111

Atunci numaram cati de '0' sunt .. si luam toti porcii marcati cu '0' si acel numar+1 de porci marcati cu '1' ..

Aparent pare destul de greu de implementat .. poate daca se reformuleaza altfel, o sa fie mai ok ..

Dar asa mi s-a parut cel mai usor de explicat.

Craciun Fericit, si Sarbatori Fericite, Infoarena!

@Alex Velea
Am facut la fel ca tine dar luam incorect :(
Am renuntat si am bagat heap :)

mie mi-a mers ^^

Si in principiu ideea e buna ..
Ai prima culoare x.

Gasesti ultima pozitie pentru care numarul de porci cu 'x' este egal numarul de porci de alte culori .. si nu ai ajuns sa ai mai multi porci de alte colori pe parcurs.

Daca dupa ce ai facut asta ai ajuns sa ai mai multi porci de culoare x pana la final .. iei numaru_de_porci_de_alte culori pe toti .. si iei primi porci de culoare x + 1 ^^


Sper sa te ajute =))

fuck, am uitat sa pun un viz :))
ms veli ^_^

Puteti sa imi dati si mie niste teste?Imi merg primele 4 si apoi am TLE si WA dar sunt sigur ca TLE-le sunt de la o greseala in program si imi cicleaza.
Multumesc anticipat!