idei si idei

[•vladcyb1]

Vreau si o lamurire in urmatoarea privinta:
 O problema precizeaza ca dimensiunea toatala a memoriei ce poate fi alocata este de 2 MB din care 1 MB pentru stiva. Acest lucru ma impiedica sa declar o matrice ce ocupa 1,9 MB ? Ce inseamna pt ei stiva, deoarece pt mine nu e nimic mai mult decat mecanismul LIFO implementat static sau dinamic.


       Da-tim\-mi pls o explicatie ca de gradinita, poate intleg shi yo.

           Thanks.

[alexjj]

spatiul alocat stivei (aici) inseamna spatiul total pe care-l poti folosi cand declari ceva static intr-o functie (orice functie). (vrei exemple ? )  :lol:

[•silviug]

Acest lucru ma impiedica sa declar o matrice ce ocupa 1,9 MB

Raspuns: DA, indiferent daca e static sau pe stiva.
In consecinta, mare atentie!

Silviu

[•sarabogdan]

In legatura cu memoria , cum imi dau seama cat ocupa o matrice
a[501][501][501][501] ?

[•rgrig]

Le inmultesti . Daca e o matrice de int pe un calculator 32b atunci sunt vreo 250 GB.

[•vladcyb1]

Silviu,

Dar daca fac o smekerie de genul

 type vector = array[1..1000]of byte;
 var a:array[1..1000]of ^vector;

Crezi ca merge?
P.S. La USACO zicea ca limta de memorie este 17 MB din care 1 MB pentru segmentul de stiva. Eu am declarat un array[1..4000,1..4000] of byte si am luat aproape tot punctajul. (mi-a iesit din timp, dar a mers)

Unde gasesc niste informatii despre kestiile astea?
Thanx

[•wickedman]

Silviu,

Dar daca fac o smekerie de genul

 type vector = array[1..1000]of byte;
 var a:array[1..1000]of ^vector;

Crezi ca merge?
P.S. La USACO zicea ca limta de memorie este 17 MB din care 1 MB pentru segmentul de stiva. Eu am declarat un array[1..4000,1..4000] of byte si am luat aproape tot punctajul. (mi-a iesit din timp, dar a mers)

Unde gasesc niste informatii despre kestiile astea?
Thanx

Nu ma cheama Silviu, dar am sa-ti raspund eu, ca mai oboseste saracul baiat.  

La USACO ti-a mers treaba pentru ca tu ai alocat static o matrice de 4000 * 4000 bytes adica mai putin de 16 MBytes (1 MB = 2 ^ 10 KB = 1024 KB). Te-ai incadrat in limita de memorie.

Cat despre "smecherie" ...
Acei 1000 de vectori pe care urmeaza sa-i aloci se vor duce toti in heap (adica nu in stack - stiva). Intrucat ai la dispozitie 2 MB din care 1 pentru stiva => 1 MB pentru heap.
Cei 1000 de vectori incap in heap si ii vei putea folosi.

Insa asta nu rezolva problema de la care am plecat (sa aloci o matrice de 1,9 MB).


Daca tii neaparat, poti face niste trucuri ieftine sa imparti matricea ta cea mare intre heap si stack dar mai bine zi-ne si noua problema sa gasim impreuna o solutie care merge lejer in limita de memorie.

[•sarabogdan]

Am reusit sa fac problema folosind o matrice a[501][501] . Multumesc oricum pentru sfaturi!!

[•vladcyb1]

Problema este la campion in desfasurare, deci nu avem voie sa o discutam.
 Mai, la USACO ai vazut ce zicea: Segment de stiva max. 1 MB si eu am declarat 16 MB

 Am vazut ca cineva a postat un reply in care zice ca stiva de 1 MB se aplica doar la subprograme.
 
 Eu pana acum credeam ca restrictia asta de stiva ma impiedica la recursivitate si atat.

 Thanks anyway.
  O sa incerc o fragmentare a matricei. Asa merge sigur.

[•domino]

Problema este la campion in desfasurare, deci nu avem voie sa o discutam.
 Mai, la USACO ai vazut ce zicea: Segment de stiva max. 1 MB si eu am declarat 16 MB

 Am vazut ca cineva a postat un reply in care zice ca stiva de 1 MB se aplica doar la subprograme.
 
 Eu pana acum credeam ca restrictia asta de stiva ma impiedica la recursivitate si atat.

 Thanks anyway.
  O sa incerc o fragmentare a matricei. Asa merge sigur.

Pe stiva, din cate stiu eu, se duc toate variabilele declarate local (adica intr-un subprogram) si apelurile din recursivitate. Restul, pe heap (adica si variabilele globale), deci probabil ca matricea ta de 16mb era o variabila globala.

[•vladcyb1]

Domino,
Concluzia din ce mi-ai spus tu este urmatoarea:
= daca problema spune ca spatiul total ce poate fi alocat este de 2 mb, din care 1 mb pt stiva atunci o declaratie de genul
 var a:array[1..1000,1..1000]of word ; va fi perfect valabila.

[•domino]

Domino,
Concluzia din ce mi-ai spus tu este urmatoarea:
= daca problema spune ca spatiul total ce poate fi alocat este de 2 mb, din care 1 mb pt stiva atunci o declaratie de genul
 var a:array[1..1000,1..1000]of word ; va fi perfect valabila.

Daca din 2mb, 1 e de stiva, ramane 1 pentru heap, deci variabila ta nu va incapea fiindca are ~2mb.

[•vladcyb1]

Hai ca i-am dat de cap !
 Thanx!

Sarabogdan,
 Ce complexitate ai la problema ? N^2?

Se poate sa obti intr-un graf toate cuplajele maximale intr-un timp de 0.2 secunde ?
 
  Nu-mi dati idei. Vreau doar sa stiu daca se poate. 101 noduri in stanga si 101 in dreapta.

[•domino]

Hai ca i-am dat de cap !
 Thanx!

Sarabogdan,
 Ce complexitate ai la problema ? N^2?

Se poate sa obti intr-un graf toate cuplajele maximale intr-un timp de 0.2 secunde ?
 
  Nu-mi dati idei. Vreau doar sa stiu daca se poate. 101 noduri in stanga si 101 in dreapta.

Cred ca vroiai sa zici graf bipartit.. si sa treci prin TOATE cuplajele maxime e cam mult.. numarul lor e exponential.

[•sarabogdan]

Am O(n*(n+1))^2 si nu intra in timp!!

[VladS]

vladcyb1, ai complexitate O(N^2) din cate am citit de pe forumul .campion. Se poate determina un poligon folosind doar 2 puncte?
(DA/NU). Eu am aproape O(N^3) (32mil. operatii pt n=500).

[•vladcyb1]

Nu se poate determina un poligon cu 2 puncte. Citeste enuntul. Te intreaba cate paralelograme se determina, nu care sunt.

Mai, ati facut problema bomboane. Pe mine ma cam depaseste teoria necesara. Invat de zor si sper ca pana miercuri sa scot un algoritm.

Spunet-mi si mie daca vre unul de clasa a X-a a facut-o pana acuma. Nu cred ca trebuia bagata la a X-a. Ce parere aveti?

[•domino]

Nu se poate determina un poligon cu 2 puncte. Citeste enuntul. Te intreaba cate paralelograme se determina, nu care sunt.

Mai, ati facut problema bomboane. Pe mine ma cam depaseste teoria necesara. Invat de zor si sper ca pana miercuri sa scot un algoritm.

Spunet-mi si mie daca vre unul de clasa a X-a a facut-o pana acuma. Nu cred ca trebuia bagata la a X-a. Ce parere aveti?

Desi nu sunt la clasa a X-a si eu sunt de parere ca e cam dificila pentru clasa a X-a, dar totusi in 10 zile sau cate au fost la dispozitie se putea invata teoria necesara.

[alexjj]

nu se da n=500 pentru un O(n^2), fratilor. tot O(n^3) shi un pic am shi io, dar merge kam greoi. daca era problema de n^2 dadeau n-ul mai mare.

[VladS]

Pana la urma cred ca am scos ceva destul de bun la "Paralel". Am O(n^2*(log n  +  1) ). In sfarsit putem discuta despre problema ca s-a terminat runda.

[•vladcyb1]

Ai luat 100? Vrei sa-ti dau sursa mea ? Da-mi mailul sau o postez pe forum.

[VladS]

Chiar ma intereseaza algoritmul tau(in N^2). Poti sa mi-o trimiti la [email protected]. Sper sa fie lizibila. Poti sa scrii si pe scurt metoda (geometrica).

[•vladcyb1]

Ti-am trimis mailul. Este in pascal pt ca altceva nu stiu. Sper sa intelegei. Am incercat sa o fac cat de cat lizibila. Oricum are cateva randuri.

[•vladcyb1]

Ar putea cineva sa-mi prezinte si mie rezolvarea detaliata (ca pt gradinita) a problemei JOC de la Runda 7? Va rog mult, deoarece sper ca la un moment dat sa reusesc si eu sa rezolv probleme de acest tip. Va multumesc !

P.S. Am citit descrierea solutiei de pe liis dar nu inteleg nimic

[•domino]

Ar putea cineva sa-mi prezinte si mie rezolvarea detaliata (ca pt gradinita) a problemei JOC de la Runda 7? Va rog mult, deoarece sper ca la un moment dat sa reusesc si eu sa rezolv probleme de acest tip. Va multumesc !

P.S. Am citit descrierea solutiei de pe liis dar nu inteleg nimic

O sa incerc sa explic eu.. desi am luat doar 10p   dupa concurs am reusit sa fac o sursa care merge de max.
Am construit o matrice bst[j] = diferenta maxima de scor Ana - Ion, daca incepe Ana din pozitia (i, j) si o matrice C[j] = valoarea casutei (i ,j) (0 pt '.' 1 pt bomboana, 3 pentru suc si 5 pentru ciocolata)

Prima observatie este ca bst[j] poate fi considerat si ca diferenta de scor Ion-Ana daca incepe Ion.
Daca Ana muta din (i, j) in (i+1, j), atunci vom lua in considerare valoarea -bst[i + 1][j], fiindca presupunem ca in casuta (i+1, j) incepe Ion deci bst[i+1][j] va fi diferenta de forma Ion-Ana, iar -bst[i+1][j] va fi de forma Ana-Ion. La -bst[i+1][j] vom aduna C[i+1][j]. Analog se procedeaza si pt (i,j+1) si (i+1, j+1).

Rezumand
bst[j] = max(C[i+1][j] - bst[i+1][j],
                       C[j+1] - bst[j+1],
                       C[i+1][j+1] - bst[i+1][j+1])

Pentru a trata cazul cand diferenta de scor e 0, am mai construit o matrice move[j] care imi zice paritatea numarului de mutari de la (i, j) la o casuta din care nu se mai poate muta. Daca move[j]=1 atunci ultima mutare a facut-o Ion, altfel a facut-o Ana. move[j] ne ajuta la departajare cand alegem maximul dintre cele 3 variante, daca 2 sunt egale de exemplu, alegem pe cea cu valoarea move[j] cat mai mare (pentru ca sa piarda Ion). Sper ca ai inteles, daca vrei iti dau si sursa.