Felicitari pentru feature!

Pentru unele probleme nu am permisiuni sa vad statisticile (autentificat sau nu). De exemplu:

Problema Pietre: http://www.infoarena.ro/statistici_problema?task=pietre => merge
Problema Adunare: http://www.infoarena.ro/statistici_problema?task=adunare => nu merge (primesc: Nu ai permisiuni suficiente pentru a executa aceasta actiune! Te redirectez ...)

Stiu ca e beta, dar poate asta e un bug valid.

better_nerf_irelia Nu.

@uaic_rfb Nu.

Fara comentarii.

Members 1 to N-1: each says the sum of numbers he sees. Then member N can sum all those sums and subtract (N-2) * sum of numbers he sees. He is left with (N-1) * his number. I guess. // I read it a bit too quickly, as this does not apply if the guesses aresimultaneous.

Salut. Incerc sa creez un concurs virtual pentru un coleg. Cand selectez problemele, trebuie sa caut fiecare problema in toata lista, deoarece nu sunt ordonate dupa nume.

As dori sa propun o alta solutie la problema agendatelefonica pe care am luat 300 de puncte, care consuma memorie O( (N+M)*L), unde N este numarul de prefixe, M numarul de nume si L lungimea unui nume/prefix si timp O(N*logM*L). Unde as putea posta sursa si explicatiile?

Trimite-ne un mail la [email protected] sau [email protected] si vedem

Rugăm toți participanții care au primit / vor primi e-mail de confirmare că sunt finaliști să ne răspundă cât mai repede cu datele următoare:

pentru toți oamenii care participă din partea echipei
{
 Prenume + Nume
 Institutie de invatamant + Clasa/An
 Adresa + Oras + Judet
 Serie act identitate (poate fi buletin, paÈ™aport, carnet de student, permis auto, brevet pilot, licență  etc) trebuie doar sa vină cu el la IaÈ™i la finală
 Data naÈ™terii
 Email1 (+ Email2)
 Telefon1 (+ Telefon2)
 Concurent / Mentor?
}

Cei din echipele de pe pozițiile 1-6 pot trimite deja mail, deoarece sunt finaliste.

Nu ni se poate da un "exemplu" care sa evidentieze CEL MAI CLAR raspunsul la intrebarea 4) pusa de Spatarel ? Multumim.

Fie următoarea configuraţie de intrare:

4 50 120 3
0 40
0 50
100 100
0 0
1 2 10 10
2 3 10 30
2 4 10 100


Se pleacă de pe planeta 1 cu 40 combustibil, se ajunge pe planeta 2 cu 30 combustibil
1. Varianta I - se alimentează pe planeta 2
Se pleacă de pe planeta 2 cu 80 combustibil, se ajunge pe planeta 3 cu 50 combustibil. Se încarcă mineralele şi se face plinul.
Se pleacă de pe planeta 3 cu 120 combustibil, se ajunge pe planeta 2 cu 90 combustibil. Nu se mai poate face plinul pentru că deja s-a epuizat combustibilul de pe planeta 2 în pasul anterior. Nu se poate pleca spre planeta 4 deoarece drumul necesită 100 combustibil. Nu există soluţie.

2. Varianta II - nu se alimentează pe planeta 2
Se pleacă de pe planeta 2 cu 30 combustibil şi se ajunge pe planeta 3 cu 0 combustibil. Se încarcă mineralele şi se face plinul.
Se pleacă de pe planeta 3 cu 100 combustibil, se ajunge pe planeta 2 cu 70 combustibil. Deoarece există încă 50 combustibil pe planetă, se poate face plinul. Se pleacă spre planeta 4 cu 120 combustibil şi se ajunge cu 20 combustibil. Soluţia este:
100 40

Sa zicem ca avem o capacitate C de 100 de litrii. Eu am in rezervor 50 litrii cand ajung intr-o localitate in care exista un depozit de 60 litrii.
Decid sa realimentez. Ce se intampla? In rezervor am 100 litrii iar in depozit raman 10 litrii, sau nu ramane nimic?

Pe planetă rămân 10 litri.

@dragos Am trimis intrebarea ta. Voi actualiza după ce voi primi răspunsul de la autorul problemei.
@robert Explicația pentru întrebarea 4 conține și un exemplu dat de autorul problemei. Voi trimite oricum încă o dată autorului întrebarea ta.

[el va face de fiecare dată plinul rezervorului]

Adaug aici raspunsurile autorului problemei la intrebarile tale:

Care este interpretarea raspunsului afirmativ de la prima intrebare? Daca pot realimenta, la realimentare cu cat pot realimenta? Cu cantitatea de combustibil din datele problemei? Sau doar cu cantitatea de combustibil ramasa in urma primei alimentari?

În mod absolut evident se poate realimenta doar în limita cantităţii de combustibil rămase în urma alimentărilor anterioare.

Alternativ, daca realimentarea nu se poate face decat in limita combustibilului ramas, atunci ar putea exista urmatorul scenariu:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 30
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si nu mai ramane nimic in A

Insa! Aceasta problema devine foarte... complicata, pentru ca, la fel de bine, putem presupune urmatorul scenariu:
Sa spunem ca in A avem 60 de combustibil. Atunci avem scenariul:
1) Alimentam in A (R: 30 + 20 = 50) - si pastram in A 40
2) Mergem in B (R: 50 - 30 = 20)
3) Alimentam in B (R: 20 + 100 = 120)
4) Ne intoarcem in A (R: 120 - 30 = 90)
5) REAlimentam in A (R: 90 + 30 = 120) - si pastram in A 10
Insa, in scenarii derivate acestuia, putem sa pastram 5 in A si 5 in B, sau 3 in A si 7 in B samd.; iar daca B are legaturi si cu alte planete, o revenire a mea in B, prin aceste alte planete s-ar putea sa fie posibila plastrand un pic de combustibil si acolo - la fel de bine, s-ar putea sa vreau sa revin in A si sa am nevoie de combustibil si de acolo - si chiar trebuie sa analizez toate aceste cazuri: 5/5, 3/7 etc.

Cităm încă o dată din enunţ: "Dacă o dată ajuns pe o planetă Ambasadorul se decide să alimenteze cu combustibil, el va face de fiecare dată plinul rezervorului în limita cantităţii de deuteriu prezentă pe planetă şi a capacităţii C a rezervorului." Astfel, o dată decizia de a realimenta fiind luată, cantitatea de combustibil încărcată va fi de fiecare dată min(C, cantitatea de combustibil rămasă pe planetă).

Intrebare:
De ce aceasta problema pare sa fie atat de complicata? Nu inteleg eu ceva sau autorul problemei chiar vrea sa ma chinuie?

Problema doar pare să fie complicată, dar într-adevăr autorul este un individ eminamente sadic.  

Am trimis autorului întrebările.

4) Are sens. Să presupunem că sunt pe o planetă A din care am două trasee posibile, unul spre planeta B şi altul spre planeta C. Din planeta B singurul drum este cel înapoi spre A. Dacă am suficient combustibil să ajung pe planeta B, să alimentez acolo şi să mă întorc, atunci are sens să alimentez doar la plecarea din A spre planeta C (teoretic am păstrat mai mult combustibil în A pentru drumurile viitoare care includ această planetă şi care nu mai trec prin B)
Cazul ar putea fi ceva de genul: am 30 combustibil, pe planeta A există 50 combustibil, pe planeta B există 100 combustibil, costul drumului A - B este 30, capacitatea maximă a rezervorului este 120. Dacă parcurg drumul A - B - A şi fac plinul în prima vizită în A, plec spre C cu 90 combustibil, dacă fac plinul la a doua vizită plec spre C cu 120 combustibil (diferenţa este dată de faptul că ajung cu prea mult combustibil în B şi nu pot să iau tot combustibilul de acolo din cauza capacităţii rezervorului)

5b) este varianta corectă

6) Nu există restricţii în acest sens, deci teoretic se poate

Problema "drum":

1) Daca ambasadorul ajunge pe o planeta, alimenteaza nava, face un ciclu si revine pe planeta de pe care a alimentat, mai poate REalimenta?

2) Daca ambasadorul ajunge pe o planeta, NU alimenteaza nava, face un ciclu si revine pe planeta de pe care NU a alimentat, mai poate alimenta?

3) Daca ambasadorul poate ajunge pe Pamant cu aceeasi cantitate maxima de minerale, dar prin mai multe drumuri (cu timpi diferiti) ce timp se afiseaza? Timpul minim?

Am trimis întrebările tale autorului problemei. Răspunsul este afirmativ la toate cele trei întrebări.

[No solution]

La problema "drum", afisul pentru nicio solutie este asta : No solution, adica fara '.' ( punct ) nu ?

Fără .

Toate punctele au coordonate strict pozitive. Am clarificat și în enunț.

Runda 5 a concursului F11 se desfasoara intre 16 si 20 mai. http://www.fiicompetition.ro/f11/category/algoritmica/probleme-alg/#5 Intrebarile le puteti pune pe blogul concursului http://blog.fiicompetition.ro/2011/intrebari-algoritmica-si-programare/ sau la adresa [email protected]

1.) e greșit, se referă la același stâlp.
2.) pe extremitate (e mai apropiat). dupa care își continuă drumul, dacă are sens...
Clarific și în enunț.

Extremitățile sunt distincte. Deci nu se poate întâmpla situația descrisă.

Nu inteleg.

Runda 4 se desfășoară în perioada 5 - 11 Mai 2011 pe situl competiÈ›iei http://www.fiicompetition.ro/f11/ la secÈ›iunea Algoritmică È™i Programare http://www.fiicompetition.ro/f11/category/algoritmica/ PuteÈ›i posta întrebări pe blog http://blog.fiicompetition.ro/2011/intrebari-algoritmica-si-programare/ sau aici. ContestaÈ›iile le puteÈ›i trimite la [email protected]
Mult succes!

Motivele pentru care am mărit timpul cred ca sunt (mai) clare. Ne-am dat seama că sursa oficială, compilată cu 2.2.2, nu lua toate testele abia după contestații, deci runda era terminată. Sursa oficială nu a recurs la optimizările pe care le-au găsit băieții cu 0.1s, deci nu am considerat necesar să păstrăm 0.1s ca să intre obligatoriu cu optimizări. Pe scurt, nu a fost acesta scopul problemei, deși am fi fost bucuroși să ne dăm seama de ea.

Totuși, diferența de la 30p la 200p pentru respectiva optimizare nu se justifică. Complexitatea timp e aceeași. Dacă sursa oficială (compilată cu 2.2.2) rezolva corect testele, rămânea 0.1 și nu era nimic de observat. Dar nu am avut norocul. Aceeași sursă (compilată cu 2.4.2) rezolvă corect, dar depășește 1s pentru câteva! O sursă C++ asemănătoare se încadrează în 1s. Adevărul e la mijloc, așadar 1s este o limită ok din punctul de vedere al surselor oficiale.

Este suspect pentru Cosmin (și nu numai) că nu am păstrat 0.1s - și are și el dreptate! Dacă știam de problemă, o remediam în timpul rundei și (cu mare probabilitate) schimbam atunci tot la 1s. În orice caz, am răspuns cum am considerat mai bine și mai prompt acestor probleme, și în avantajul celor care au rezolvat corect problema, indiferent de abordare, i/o, structuri etc.

Nu am organizat concursul pentru a fi neserios și nici pentru a promova anumiți concurenți selectați de noi. S-ar putea face asta și direct, fără un concurs în care să investim noi timp și resurse. Sunt de acord că unele decizii nu sunt perfecte, dar e imposibil să se întâmple așa ceva. Vom căuta să fim mai atenți la sursele și testele oficiale în următoarele runde.

Sursa oficială inițială a prof. Sergiu Corlat (.pas de 0.1 secunde, presupusă a fi greșită) rezolvă problema corect, dar doar în altă versiune de FPC (un concurent ne-a demonstrat cu 2.4.2). În 2.2.2, însă, ea nu prinde unele teste. În orice caz, cea compilată cu 2.4.2 depășește 1 secundă la evaluare pe unele teste. În concluzie, domnul profesor NU a greșit sursa oficială, iar limita de 1s este rezonabilă.

MenÈ›ionez că, dacă vreunul dintre voi are de depus o contestaÈ›ie nominală, le primim È™i le rezolvăm după un mail cu numele echipei, problema È™i ...problema la [email protected]

Observ că s-a iscat o discuÈ›ie aprinsă pro-contra reevaluării de 1 secundă. Consider corect să explicăm ce s-a întâmplat. Pe scurt, când am primit arhiva, nu am văzut fiÈ™ierele .ok È™i le-am generat cu sursa oficială. Sursa oficială a generat teste greÈ™ite, ceea ce am observat azi dimineață în urma contestaÈ›iilor (pentru care vă mulÈ›umim), fapt pentru care am realizat ulterior o sursă de la 0 în C++. Deoarece spaÈ›iul stărilor era mare, surse care implementau coada, vectorii diferit (STL, versus de mână) obÈ›ineau punctaje mai mici. Am considerat corectă în principal ideea de rezolvare È™i în secundar super optimizarea - pentru care îi felicit pe băieÈ›i.  Acordarea limitei de 1s/test a fost în avantajul celor care rezolvaseră problema corect, dar au folosit Q.push(x); în loc de Q[++sf] = x; Ne cerem scuze pentru inconvenienÈ›e, în special celor care s-au chinuit să rezolve de 0.1 È™i le urăm succes tuturor în continuare.