218 ZParcurgere

[ditzone]

Aici puteţi discuta despre problema ZParcurgere.

[•vladcyb1]

Care e faza cu testele 5, 6 ? Nu le am luat nici in concurs..nici in arhiva acuma...  

[•alexthero]

Cred ca x si y depasesc 2^n pe testele 5 si 6.. am trimis o rezolvare care face verificarea datelor si intra in ciclu infinit daca ceva nu e in regula.

Ce trebuie afisat in cazul in care x-ul sau y-ul depaseste limita?

[ditzone]

Nu terbuie afisat nimic... testele 5 si 6 s-au schimbat si s-a reevaluat

[•cristy]

nu imi ies mai mult de 20 de pct pe problema asta... ....asa arata parcurgerea pt n=4?

Cod:

1	2	5	6	17	18	21	22	65	66	69	70	73	74	77	78
3	4	7	8	19	20	23	24	67	68	71	72	75	76	79	80
9	10	13	14	25	26	29	30	81	82	85	86	89	90	93	94
11	12	15	16	27	28	31	32	83	84	87	88	91	92	95	96
33	34	37	38	49	50	53	54	97	98	101	102	105	106	109	110
35	36	39	40	51	52	55	56	99	100	103	104	107	108	111	112
41	42	45	46	57	58	61	62	113	114	117	118	121	122	125	126
43	44	47	48	59	60	63	64	115	116	119	120	123	124	127	128
129	130	133	134	145	146	149	150	197	198	201	202	213	214	217	218
131	132	135	136	147	148	151	152	199	200	203	204	215	216	219	220
137	138	141	142	153	154	157	158	205	206	209	210	221	222	225	226
139	140	143	144	155	156	159	160	207	208	211	212	223	224	227	228
161	162	165	166	177	178	181	182	229	230	233	234	245	246	249	250
163	164	167	168	179	180	183	184	231	232	235	236	247	248	251	252
169	170	173	174	185	186	189	190	237	238	241	242	253	254	257	258
171	172	175	176	187	188	191	192	239	240	243	244	255	256	259	260

Foloseste  "code" ca sa se vada mai bine matricea...

[ditzone]

Ceva nu e in regula la matricea aia... fiind 2ⁿ*2ⁿ (n=4) trebuie sa ai 256 de valori .. la tine apare si un 260 pe-acolo... si lipsesc 193-196

[•cristy]

scuze...ai dreptate...am gresit la copiere acolo...dar asta e ideea?...eu am facut 20 de puncte si restul WA...

[VladS]

Vezi si tu daca iti merge pe testele de aici
http://www.topcoder.com/stat?c=problem_statement&pm=4808&rd=7999

[•svalentin]

insa iti trebuie user pe topcoder pt alea..

[•cristy]

ms...acuma ma apuc sa bibilesc codul...am gasit cateva greseli...

[•cos_min]

nu inteleg de ce iau numai 20 de pcte    ... testele de pe topcoder imi merg ...

voua cat va da pe :

7 2
4 5
21 3

[•tm_radu]

mie imi da :

Cod:

27
549

[•AlexandruValeanu]

Se poate raspunde in O(1) pe intrebare?

[•deneo]

Nu

[•cont_teste]

Aceasta este o problema clasica de DEI.

[•breahnadavid]

ma ajuta si pe mine cnv ??
am facut un fel de divide et impera.. dar nu trec de 70 pc.
tu TLE..
si nu-mi dau seama ce as putea face ?
unde pierd puncte, ,

Cod:

#include<iostream>
#include<fstream>
#include<math.h>

using namespace std;

ifstream f("z.in");
ofstream g("z.out");

int x,y,t[10000][10000],i,j,k,n;
int q;
void parcurg(int i,int j,int x,int y)
        {
        if(i==x&&j==y)t[i][j]=++q;
        else
                {
                parcurg(i,j,(x+i-1)/2,(y+j-1)/2);
                parcurg(i,(y+j-1)/2+1,(x+i-1)/2,y);
                parcurg((x+i-1)/2+1,j,x,(y+j-1)/2);
                parcurg((x+i-1)/2+1,(y+j-1)/2+1,x,y);
                }
        }
int main()
{
f>>n>>k;
q=0;
parcurg(1,1,int(pow(2,n)),int(pow(2,n)));
while(k>0)
        {
        f>>x>>y;
        g<<t[x][y]<<'\n';
        k--;
        }
g.close();
return 0;
}

va rog mult cineva > !? !?  

[•harababurel]

Incearca sa renunti la cateva apeluri ale functiei.

De fiecare data cand faci o impartire in 4 cadrane, in loc sa repeti impartirea in mod succesiv pentru fiecare dintre ele (complexitate pentry query O(2^n)), poti sa reapelezi doar pentru cadranul in care se afla elementul cautat (complexitate O(log (2^n)) = O(n * log 2) = O(n)).

Observa ca fiecare cadran initial contine un interval compact de valori. Pentru cazul din exemplu: [1, 4], [5, 8], [9, 12], [13, 16].
Daca ai de cautat un element care se afla in cadranul 3, poti sari peste 2 cadrane (adica 8 valori), fara sa le mai parcurgi, si iti ramane sa cauti doar in intervalul/cadranul imediat urmator.

Pentru simplitate, considera ca ai scazut valoarea 8 din fiecare element al cadranului ales. in modul asta, cadranul o sa obtina exact structura initiala a tablei (valoarea 1 in coltul stanga-sus, 2^dim in coltul dreapta-jos, si aceeasi ordine de numerotare), ceea ce iti simplifica impartirea urmatoare.

Solutia o sa fie suma tuturor valorilor scazute astfel, pana in punctul in care ajungi la un cadran de dimensiune 1.

Am rezolvat problema acum un an; daca am omis sau gresit ceva, o sa corectez.

[•breahnadavid]

Mersi, mult, am incercat s-o fac,
Dar nu mi-a reusit ti-am trimis un PM, daca poti sa ma ajuti .. ?
As fi recunoscator. 

[•harababurel]

Ti-am trimis un PM cu explicatiile din sursa mea.
Sper sa te ajute.