Sushi

[•eudanip]

Aici se pot pune întrebări legate de problema Sushi de la Runda 2 a concursului .com 2012

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Î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.

[•dutzul]

nu cumva se cere secventa cu j-ul minim?? am modificat asa si mia dat ok

[•eudanip]

NU. Trebuie maxim. Problema e buna.

[•SebiSebi]

Problema se rezolva cu trie?

[•klamathix]

Problema se rezolva cu un for ).

[•Steve]

v[ i ] * 2
Am si demonstratie.

[•geniucos]

Cum se facea cu un for?Eu am facut o dinamica 3D cu complexitatea O(nlogVmax)
Multumesc anticipat!

[•repp4radu]

Trebuia sa gasesti prima secventa de elemente de valoare maxima si sa afisezi 2 * MAX.

[•SpiderMan]

Dupa cum zicea steve, rezultatul este dat de max * 2, unde max este elementul maxim din vector. Daca afisai pozmax pozmax max * 2, atunci luai 90 cu un incorect, si ca sa iei 100, trebuie sa iei cea mai lunga secventa care cuprinde elemente maxime, pentru ca-ti cere solutia cu i-ul minim si j-ul maxim. Pentru exemplul :

Cod:

2 2 2 1

Rezultatul o sa fie 1 3 4, nu 1 1 4, cum ai fi facut altfel, pentru ca 1 3 are j-ul mai mare ca si 1 1. Sper ca ti-a fost de folos .

[•vendetta]

Steve, care ar fi demonstratia ?

[•geniucos]

Multumesc pentru raspunsul prompt!

[•tzipleatud]

Demonstratia cred ca e ceva de genul:

Sa zicem ca alegi doua elemente consecutive X,Y care au cel mai semnificativ bit pe pozitia B ambele. Sa zicem ca X,Y=2^B (cele mai mici numere care au bitul cel mai semnificativ pe pozitia B). (Vom lua B in asa fel incat nu exista numar in sir cu bit de 1 pe o pozitie mai mare de B).

Atunci X si Y arata ceva de genul:
1000000...00
1000000...00

Solutia iti va fi (X&Y)+(X|Y)=X+X=2*X = 2^(B+1).

Acum sa luam un numar Z care nu are 1 pe pozitia B in reprezentarea binara (Vom lua Z=2^B - 1 - cel mai mare numar care se poate gasi in sir si care nu are 1 pe pozitia B in reprezentarea binara). Numerele vor arata asa
X: 10000000...0
Y: 10000000...0
Z: 01111111...1

Solutia iti va fi (X&Y&Z)+(X|Y|Z)= 0 + 2^(B+1) -1 = 2^(B+1) -1 < 2^(B+1) (rezultatul initial).

Deci la pasul curent e bine sa alegem o secventa care are 1 pe pozitia B in reprezentarea binara a fiecarui numar din secventa.
Extinzand rationamentul pentru pozitiile B-1, B-2, ..., 0 din reprezentarea binara, se observa ca se obtine ca rezultat o secventa ce contine numere egale cu maximul din sir.

Cam asta ar fi demonstratia, sper ca nu am gresit nimic .

[•Steve]

*luai 70 cu 1 incorect , trist cand implementezi o dinamica in ultima ora, si te prinzi in ultimele 5 min de chestia asta...ma rog.

O proprietate:
ai 2 nr. a si b atunci a&b + a|b = a + b
1 & 1 = 1; 1 | 1 = 1; 1 + 1 = 2 (se shifteaza bitul);
1 & 0 = 0; 1 | 0 = 1; 1 + 0 = 1;
etc.
Asta se aplica pt orice biti de aceeasi importanta, deci luand separat toti bitii din cele 2 numere, practic se aplica individual operatia si o sa dea a + b (se aplica doar la 2 nr., la mai multe nu mai e asa)

Fie A = maximul, de forma a[n]a[n-1]...a[k]a[k-1]...a[1].
Cazul 1: Presupunem ca secventa de sushi maxim il contine pe A si se continua spre dreapta cu P numere (spre stanga e analog). Aceste P numere le vom numi numere considerate pentru secventa.
Fie primii biti de la a[n] la a[k+1] comuni la toate numerele considerate. (Poate sa fie nu fie niciun bit.) Aplicand si respectiv sau si adunand, raman neschimbati, deci rezultatul este acelasi cu primii biti din 2A (se shifteaza la stanga). a[n]...a[k + 1] e secventa comuna maxima a partii cele mai semnificative => exista un numar B in grupul de numere considerate de forma a[n]...a[k + 1]b[k]b[k -1]...b[1] cu b[k] != a[k]. Cum A > B => a[k]  = 1, b[k] = 0. Nu ne intereseaza primii biti de la a[n] la a[k +1], deci vom considera doar A' = 1a[k -1]a[k - 2]...a[1] si B' = 0b[k - 1]b[k - 2]...b[1]. Notam AND, rezultatul operatiei & pe grup, si OR, rezultatul operatiei | pe grup. =>  AND <= a[k -1]a[k -2]...a[1], iar OR <= 11...1 (k cifre de 1) = 1000..00 (k cifre de 0) - 1 => AND + OR  <= 1000..00 (k cifre de 0) - 1 + a[k - 1]a[k -2]...a[1], dar 2A' = 2(1000..00 (k - 1 zerouri) + a[k - 1]a[k - 2]...a[1]) = 10000..00 (k cifre de 0) + 2 * a[k - 1]a[k - 2]...a[1]. Comparam cele doua relatii:

AND + OR    ?   2A'
1000..00 (k zerouri) - 1 + a[k - 1]a[k -2]...a[1]    ?    1000...00 (k zerouri) + 2 * a[k - 1]a[k - 2]...a[1]
-1    ?    a[k - 1]a[k - 2]...a[1]
a[k - 1]a[k - 2]...a[1] >= 0, de unde => concluzia.

Alt caz ce trebuie analizat este cand secv. maxima nu include pe a. Notam numerele analog de forma X0b[1]b[2]b[3]...b[n] (a = X1a[1]a[2]...a[n]). Presupunem cazul maximal in care b[1] = b[2] =...b[n] = 1. Atunci aplicand sushi pe aceste numere se obtine X01111...110 (n de 1), in schimba 2a > (X1000...00 (n de 0) << 1 = X100...00 (n + 1 de 0)) deci > X011111...110, deci prob. e rezolvata.

LE: Am gresit ceva in demonstratie, o sa o rescriu.

LE2: Acum e corecta.