Imi cer scuze. Intre timp am observat si eu ce am inteles gresit si am sters cu totul mesajul. Nu am observat ca intre timp mi s-a raspuns. Multumesc pentru promptitudine.

Poate gresesc. In ce ordine trebuie afisate codurile Huffman? Crescator sau descrescator dupa lungime?  M-am uitat pe primul OK de la atasamente si am vazut ca acolo erau descrescator. Pe exemplu mie mi se pare ca sunt afisate invers.

Este o problema cu evaluatorul?

Raport evaluator
A aparut o eroare in rularea evaluatorului pe testul 1: Time limit exceeded.: timp 5052ms: mem 216kb

Am o mare nelamurire. Algoritmul pe care il folosesc utilizeaza un for de lungime exact k=n/2 in care am doua printf("%d %d\n",...), doua incrementari si doua decrementari. In rest doar operatii aritmetice ( foarte putine ) Tinand cont ca n<=1.500.000
 de ce oare imi poate iesi din timp un test ?

L.E. Never mind. Am pus totul intr-un singur printf si a intrat (aproape la limita ) in timp. Daca totusi are cineva o parere legata de ideea de mai sus, va rog sa mi-o impartasiti si mie.

Qk. Am inteles. scanf nu inseamna parsare. Intrebarea insa ramane. Ambele procedee fac acelasi lucru adica incarca in stringul L cate o linie din matrice (scanf imi incarca toata linia cat timp ea contine numai caractere 0 si 1 fara spatii) . Apoi procesez linia in exact acelasi mod, aplic acelasi algoritm. Intrebarea era: ce face diferenta intre citirea cu scanf si cea cu fgets? de ce este fgets atat de rapid prin comparatie cu scanf? La unele teste diferenta de timp este de aproape 0.3 sec. iar aceasta diferenta vine din maxim n=15000 citiri de linii. Daca e sa calculez fiecare citire cu fgets e mai rapida fata de o citire cu scanf cu 0.3/15000= 0.00002 sec pentru o linie de maxim 1500 caractere. Interesant.

Am folosit initial parsarea folosind scanf("%s",L). http://infoarena.ro/job_detail/346877
Apoi am inlocuit cu fgets(L,m+10,stdin).  http://infoarena.ro/job_detail/346881
In al doilea caz timpul de executie a scazut foarte tare reusind astfel sa trec de la 90 la 100 de puncte.
Poate cineva sa imi explice care este diferenta?

@adib : Sper sa fi citit cu suficienta atentie sursa ta si sa nu gresesc in ceea ce spun.
           Efectul final al functiei reactsume ar fi urmatorul -> se schimba semnul pe o anumita linie si apoi
           se calculeaza suma fiecarei coloane in matricea modificata in vectorul x.
           Apeland apoi functia back este adevarat ca iei in calcul toate modurile in care s-ar putea schimba
           semnele pe coloane.
           Concluzia este simpla. Realizezi toate posibilele Flip-uri pe coloana dar corespunzator unui singur Flip pe linie.
           Probabil ca testele pe care obtii punctele sunt obtinute exact pe astfel de situatii particulare.
           Sper ca ai inteles ce am vrut sa spun. Oricum ideea de a lucra cu back mi s-a parut interesanta si poate fi
           un inceput pentru o rezolvare putin diferita de solutia oficiala a problemei.
         

Folosind ideea din solutia oficiala am procedat astfel :
-am initializat xmin=xmax=x intersectie d1,d2
-am initializat ymin=ymax=y intersectie d1,d2
-am stabilit daca am dreapte verticale si/sau orizontale si am intersectat cu toate celelalte drepte actualizand solutia. am eliminat aceste drepte din calcul (implicit am modificat n cu 0 1 sau 2 )
- am sortat dupa a[ i ] / b[ i ]. am intersectat dreptele i si i+1 cu i=1..n-1
- am sortat dupa b[ i ] / a[ i ]. am intersectat dreptele i si i+1 cu i=1..n-1
la fiecare intersectie am actualizat solutia

Cu toate astea am obtinut 60 puncte ( WA pe 4 teste ). Poate cineva sa imi sugereze ce gresesc?

folosesc tipul double pentru coeficienti si pentru coordonatele intersectiilor.
citesc pe int si fac conversie (explicita) la double.
folosesc comparare directa pentru double ( x<y ) nu cu un epsilon foarte mic.
Afisez cu printf("%.5lf",...
L.E.

Nu vor exista două drepte paralele.

Pot exista doua drepte care sa coincida?

La Joc11 mergea cu un Lee cu marcaj impar pentru A si par pentru B?  Am mers asa, am gresit un pic la vecini si am uitat sa dau submit la sursa modificata. Mor de curiozitate daca merge. Cand apar problemele la arhiva?

Bafta tuturor la urmatoarele runde. Bafta baietilor la IOI. 

Ai grija si la situatii de genul

Cod:

12
1 100 100 1 1 100 100 1 1 1 100 100

Raspunsul corect pare a fi aici 600 ( sper sa nu gresesc) folosind cele trei perechi de 100.
Este posibil sa sari doua sau chiar 3 pozitii intre doua zone pe care se face "culegerea".

[do]

Pai tu ai mai multe greseli. Una ar fi ca nu iei deloc in calcul ca Ion ar putea sa culeaga primul si ultimul sector.

In plus, primul si ultimul sector sunt adiacente.

In sursa ta nu vad sa fi luat in calcul si acest caz.

Pentru testul :

Cod:

3
100 1 100

programul tau da rezultatul 101 . Corect ar fi 200.

O alta greseala: Tu consideri mereu secvente de cate 4 sectoare folosind acel do.
Daca urmaresti cu atentie ce faci acolo, vei observa ca nu iei niciodata in considerare ultimul din cele 4 sectoare.

Pentru testul :

Cod:

12
1 1 1 1000 1 1 1 1000 1 1 1 1000

programul tau da rezultatul 6 . Evident ca Ion poate sa culeaga mai putin de 3000 de oua.

Faza cu lungimea codurilor poate fi "pacalita" foarte usor. Se alege cea mai lunga codificare si orice codificare mai scurta se completeaza cu zerouri asa incat la final toate codificarile sa aiba aceeasi lungime. Mie mi-a mers asa.

@ Mishu91
In nici un caz nu e asta motivul. Am testat cu programe foarte simple de genul

Cod:

#include<stdio.h>
int main()
{
       return 0;
}

sau mai explicit merge cand folosesc pe programe mai serioase Step into (F11) la final si programele sunt ok (fisiere de iesire corecte). Pur si simplu nu merge sa-i dau Execute Program (CRTL+F5). Numai in cazul asta se blocheaza in acel executer.exe

LE : Nu merge nici cu F8. In fine, ma descurc asa cu F11/F10 deocamdata. Daca mai are cineva o idee multumesc anticipat.
LLE: Am reinstalat din alta sursa . Acum merge.

Am si eu o problema cu mingw. Folosesc mingw de cateva luni. Ieri am instalat pachetul OJI de pe site pe un nou calculator. Totul merge bine (compile,build) pana la executarea programelor. Acolo mi se deschide o fereastra MsDOS (C:\OJI\MINGW~1\executer.exe ) si cam atat. Poate cineva sa ma lamureasca despre ce poate fi vorba ? Mentionez ca am mai instalat mingw inainte pe alte calculatoare si a mers fara probleme.

@ oricine care a luat 100 de puncte
Ce idee ati folosit ? Eu am reusit pana la urma sa iau 100 cu urmatoarea idee :
1. La citire contorizez cati pixeli am pe fiecare linie si pe fiecare coloana
2. Stabilesc prima si ultima linie pe care am pixeli (U=up, D=down) si inaltimea H = D - U + 1 a "zonei de tiparit".
3. Fiecare caracter va corespunde unei "ferestre" delimitate de liniile U si D si vertical de coloanele L=left si R=right. Capetele L si R corespund unei secvente continue de valori nenule pentru contoarele coloanelor.
4. Elimin ultimele coloane cu contor nul (elimin spatiul de dupa caracterul = ) si ultima secventa de contor nenul ( elimin caracterul = ).
5. Identific caracterele de la stanga la dreapta : (prin eliminare determin daca am 1 , 2 , - , + , 4 sau 3 )
        am      Caracterul 1 daca pe  pozitiile (U,R) si (D,R) am pixel .
altfel am       Caracterul 2 daca pe pozitia (D,R) am pixel (deci pe pozitia (U,R) nu am )
altfel am       Caracterul - daca subsecventa contoarelor pe verticala de la L la R este constanta.
altfel am       Caracterul + daca subsecventa contoarelor pe verticala de la L la R este palindrom.
altfel am       Caracterul 4 daca subsecventa contoarelor pe verticala de la L la R contine un H.
altfel am       Caracterul 3.

Din pacate ideea mi-a venit dupa concurs cand am vazut cum arata exact un fisier de intrare. 

Ce defineste maximalitatea benzii? Numarul de valori de 1 sau numarul de segmente(latimea)?

L.E. M-am prins. E vorba de numarul de valori de 1. Totusi ar fi bine sa faca aceasta precizare in enunt sau exemplul sa fie edificator (cata vreme raspunsul ne da banda maximala din ambele puncte de vedere).

Raspunsul 9 este corect. Tu ai de 4 ori TLE si de 3 ori incorect. Incearca sa detaliezi. Cam ce metoda de rezolvare incerci? 

Banuiesc ca nu verifici initial daca toate valorile sunt negative.

Eu am declarat matricea fix 4096x1000 si am indexat din 0.
Complexitatea este intradevar n*(2^p)*p.
Chiar am sa incerc de curiozitate sa modific sursa. In forma asta cel mai mare timp de executie la mine e de 300 ms. Revin cu un L.E. dupa ce incerc.

L.E.  Intradevar efectul este devastator. Aceeasi sursa dar schimband liniile cu coloanele imi da 50 de puncte iar restul testelor sunt T.L.E.
        Cu ocazia asta am mai invatat ceva.

n * (2^p)

Nu am implementat de mult in pascal dar banuiesc ca tu ai o problema cu controlul asupra numarului de citiri pe care la faci pe o linie. Daca mai ai de citit pavari pe o linie citirea s-ar face ( daca imi amintesc bine) cu read daca nu trebuie sa treci la linia noua si astfel citirea primului numar sa o faci cu readln . Poti controla aceste doua cazuri astfel : contorizezi cate pavari ai pe fiecare linie
1. daca ai citit numarul pozitiv x atunci adaugi valoarea x la contorul liniei curente
2. daca ai citit numarul negativ -x atunci adaugi cate o unitate la contorul celor x linii consecutive
   incepand cu cea curenta

Astfel daca pe linia curenta contorul = numarul de coloane, ai terminat de citit linia curenta si urmatoarea citire trebuie facuta pentru primul numar de pe linia urmatoare.

Sper sa nu gresesc, dar strategia asta cred ca te-ar fi scapat de controlul finalului de linie.

[Echipa infoarena]

 Intradevar, o lectie de omenie, colegialitate si spirit de echipa poate mai importanta decat tot ce am invatat pe infoarena.

 Ar trebui sa constientizam cat de mult inseamna Echipa infoarena pentru noi, cat de banale au ajuns sa ni se para gesturile extraordinare cu care am fost obisnuiti. Traim un miracol creat de oameni pentru oameni si acest miracol poarta un nume:

INFOARENA

 

Poate sa imi spuna cineva ce IDE-uri putem folosi la ONI? Mingw este?
Multumesc.

Am doua propuneri pentru Guinness Book.

1. danyboy93 pentru cel mai evaluat concurent pe un site de pregatire.
2. problema factorial pentru cea mai evaluata problema.

si un sfat.

Cand calculati factorialul nu folositi inmultirea prin adunare repetata ca dureaza prea mult sau ramane evaluatorul mut de uimire.

Just kidding.

Am trimis o sursa in care am utilizat un radixsort pe biti. Ulterior am descoperit ca avea o eroare (vezi http://infoarena.ro/job_detail/249770 la linia 18 ar fi trebuit sa am d=dr-st+2 in loc de d=dr+1). Cu toate acestea sursa "defecta" mi-a scos 100 de puncte.
Nu reusesc sa inteleg de ce. Poate cineva sa se uite un pic pe sursa?