infoarena

Aici puteţi discuta despre problema Reguli (http://infoarena.ro/problema/reguli).

la problema asta, am scos un O(N), dar am WA pe 3 teste, pe 1,4,5. E posibil ca diferenta dintre 2 numere sa nu intre in long long in cpp? Am mai patit sa nu iau puncte cu long long, dar sa iau maxim cu long, s-ar putea si din cauza asta sa iau doar 70?

NU

Da-ne cateva detalii despre cum rezolvi tu problema :)

Pentru inceput, marchez lungimea sirului cerut cu max. Parcurg in continuare sirul initial, determin pentru fiecare pozitie un s_i, iar pentru fiecare s_i, determin cu ce valoare ar trebui sa se potriveasca, din primele max elemente (care reprezinta sirul cerut de lungime minima). Daca se potriveste cu ce ar trebui sa se potriveasca, atunci nu fac nimic, dar daca nu se potriveste, atunci reactualizez max, cu indicele i pe care ma aflu...mai exact i-1...

pare ok solutia ta. sa ai grija, atunci cand reactualizezi maximul, la cazul in care S[ i ] este egal cu S[0], ca doar atunci Noul_Max = i-1. altfel mai cauti... daca ai facut asta, nu stiu ce sa zic. daca nu iti reuseste imi poti trimite sursa pe mail ([email protected])

Abia azi am citit algoritmul lui KMP si nu m-am pus sa fac problema asta . Totusi mi se pare gresita/incompleta solutia oficiala .
 Spre exemlpu , luam N=8 si sirul diferentelor 1 2 3 1 2 3 1 1  . Ajungem la L=3 . Aici r=2,c=2
 vectorul reprezentat de functia prefix va fi 
       Pi  0 0 0 1 2 3 4 1
 indice  1 2 3 4 5 6 7 8         
    conditiile vor fi  1. Pi_N-r=Pi₆ >0  (adevarat)
                          2. (N-r) divizibil la (N-r-Pi_N-r) adica 6 divizibil la 3 (adevarat)
                          3  (N-r)/(N-r-Pi_N-r)=c adica 6/3 =2 (adevarat)   
  Si totusi  1 2 3 nu este o perioada a sirului ci 1 2 3 1 2 3 1 1 . N-am inteles eu  ceva ?   Eu zic ca trebuie verificate si elementele de la r+1 la N si comparate cu primele elemente . Adica Pi_N= N-L sau ceva de genu .   

LE : Spre ex am o sursa de 100 care da raspunsul
3
1
2
3
pt  datele de intrare
9
0
1
3
6
7
9
12
13
14

Ce zici tu este adevarat. Sursa mea returneaza rezultatul corect. E doar o mica scapare in articol :oops: Am modificat.

             Aviz pascalisti - daca nu va intra in timp citirea incercati sa cititi numerele ca stringuri  :thumbdown:

Nu cumva perioada e 1 2 3 1 2 3 1 ??

Pentru sirul

perioada este chiar sirul insusi.

Sustin ideea lui recviem. Pentru un sir care are sirul diferentelor
perioada minima este
La fel obtin si cu o sursa de 100 de puncte si asa mi se pare si corect si daca fac "de mana". La momentul cand am scris sursa (parca in concurs) am implementat o alta idee decat cea din solutia oficiala, dar care se bazeaza tot pe KMP.

Pai 1 2 3 1 2 3 1 - perioada iar unul din capat este inceputul perioadei 2 .. este secventa mai mica decat sirul insusi iar eu iau doar 90 pcte :| am pus un program care afiseaza tot sirul, fara a mai calcula altceva si iau 10 puncte pe testul care pica la sursa de 90  :fighting:

Da, uitasem cum am definit eu perioada :shock:. In sirul
perioada e intr-adevar
Pentru recviem. Vezi cat iti da de exemplu pe testul
Trebuie sa obtii
Cred ca obtii 90 de puncte pentru ca nu iei in considerare ca perioada poate fi si sirul intreg.

Pai ala era bugul .. am pus perioada <= n si a mers  :yahoo:

Pe testul tau am
:)

Mi se par destul de ciudate testele la problema asta ... o sursa gresita care pe testul
  13
  4 6 8 9 11 13 15 16 18 20 22 23 25
afiseaza un sir de lungime 11, ia 100 de puncte ; iar alta sursa care cred ca este corecta (si afiseaza rezultatul corect pe testul de mai sus) ia doar 30 ptc. 

Ar trebui să postezi la Îmbunătăţire teste, există un topic deschis pentru problema asta acolo.
Ca autor, e foarte greu să construieşti teste care să ia în calcul toate ideile care vin concurenţilor în timpul probei, multe dintre ele total greşite. Dacă o sursă greşită obţine punctaj maxim şi cele 10 teste sunt generate random înseamnă că în principiu ea va da răspunsuri incorecte pe mai puţin de 10% din cazurile posibile. Mie mi se pare că neajunsurile evaluării de azi îşi au originea nu în incapacitatea autorilor de a fabrica teste bune, ci în decizia antică, devenită tradiţie de a genera un număr mic de teste la o problemă.

Eu iau doar 70 pct..
Primesc W.A. pe testele 1, 4 si 5.
E nevoie de numere mari?

nu trebuie numere mari

trebuie sa folosesti long long, ai grija sa nu busesti aici

Nu cred k am cum sa busesc aici.
Am de tip long long si vectorul in care citesc sirul, cat si vectorul (a[]) in care retin diferentele dintre valorile elementelor de pe pozitii consecutive din sir.

atunci s-ar mai putea sa uiti cazul cand tot sirul este solutia :wink:

Nici asta nu e problema..
Am trimis acum sa afisez intreg sirul a[]. Si primesc 10 pct (pe testul 9 - test pe care luam punctaj si cu sursa de 70.).

inseamna ca gresesti altundeva, incearca sa verifici din nou daca determini corect sirul a[]