Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Sushi  (Citit de 3066 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 695



Vezi Profilul
« : Ianuarie 12, 2013, 09:49:28 »

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.
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #1 : Ianuarie 12, 2013, 11:21:00 »

nu cumva se cere secventa cu j-ul minim?? am modificat asa si mia dat ok
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 695



Vezi Profilul
« Răspunde #2 : Ianuarie 12, 2013, 11:25:38 »

NU. Trebuie maxim. Problema e buna.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #3 : Ianuarie 12, 2013, 14:15:54 »

Problema se rezolva cu trie?
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.212



Vezi Profilul
« Răspunde #4 : Ianuarie 12, 2013, 14:21:35 »

Problema se rezolva cu un for Smile).
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #5 : Ianuarie 12, 2013, 14:45:21 »

v[ i ] * 2 Embarassed
Am si demonstratie.
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #6 : Ianuarie 12, 2013, 16:12:56 »

Cum se facea cu un for?Eu am facut o dinamica 3D cu complexitatea O(nlogVmax)
Multumesc anticipat!
Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #7 : Ianuarie 12, 2013, 16:15:05 »

Trebuia sa gasesti prima secventa de elemente de valoare maxima si sa afisezi 2 * MAX.
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #8 : Ianuarie 12, 2013, 16:15:19 »

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 Smile.
Memorat
vendetta
De-al casei
***

Karma: 72
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #9 : Ianuarie 12, 2013, 16:18:44 »

Steve, care ar fi demonstratia ? Very Happy
« Ultima modificare: Ianuarie 12, 2013, 16:25:00 de către Salajan Razvan » Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #10 : Ianuarie 12, 2013, 16:37:26 »

Multumesc pentru raspunsul prompt! Very Happy
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #11 : Ianuarie 12, 2013, 17:21:24 »

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 Smile.
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #12 : Ianuarie 12, 2013, 17:21:38 »

*luai 70 cu 1 incorect Cry, 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.
« Ultima modificare: Ianuarie 12, 2013, 18:32:10 de către Stefan Eniceicu » Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines