Z-magija realizacija

Iimam ideju za resavanje zadatka ali mi realizacija predstavlja problem.

Naime zanima me sledeca stvar :
Jos od takmicenja imam ideju za resavanje zadatka z-magija ali ne znam kako da je realizujem.
Ideja je sledeca :
nK - broj karata.
Imamo npr. 10 nizova (n1,n2 ... n10).
ovi nizovi obuhvataju sledece intervale zateva :
n1 - u njemu se nalaze zahtevi koji obuhvataju neke od delove 0-nK/10, nK/10-2nK/10 . . . 9nK/10-nK.
Dalje , svaki nivo ima 10 puta vise intervala (10 x manjih)
Pitanje glasi :
Kako ja da raspodelim zahtev?
Znaci ako je zahtev obuhvatio nK/10 onda dalje ispitujem samo za deo koji je ostao (nK/10 - 2nK/10) .
To se ponavlja sve do poslednjeg nivoa. i na kraju ostatak smestim u poslednji , jedinicni ,niz (200 000 elemenata).
Interesuje me najoptimalniji nacin da se ovo resi ?
Nadam se da ce te razumeti na sta mislim.

Pozdrav

Ja sam radio tako, samo ja korisio heap koji je odgovoran za te podintervale, znaci meni je islo sa dva umesto kod tebe sa 10, ali opet mi nije proslo sve. Imao sam neke greske i nisam stigao da posaljem onda, ali kasnije kad sam poslao nista. Mada mozda sam imao neke greske koje su uticale na to da mi ne prodje!

boba, ti ni si koristio heap nego binary tree.

renovator, so binarno drvo ke imas vise nivoa ali
ke ti bide nesto lakse za kodiranje nego ako kodiras da svaki
cvor ima 10 djeca.
Ja ne razumem bas najdobro tvoja ideja, jel mozes da mi objasnis
sta ti je K? I evo recimo imas zahtev 17600-143000, kako ke
ispitujes za ovaj zahtev?

Najbolje sto sam ja izmislio je:

Imamo lista na intervali, i na pocetku u lista ima jedan cvor (1-200000). Ako je sledeci zahtev, recimo 12435-54321, razdeluvame go
taj jedan cvor na 1-12345 i 54321-200000, i izmedju niv dodavamo
nov cvor 12345-54321... Ali slozenost je O(k^2*logk), pa nisam siguran
da je ovo optimalno resenje.

Pa i napisao sam da koristim heap koji je odgovoran za intervale, znači ne u buvalnom smislu.
U binarnom stablu visina listova može biti veća od jedan, a kod heap ne, a kod mene su svi listovi na istom nivou, zato je bliže heap-u nego stablu, a ustvari nije ni jedno ni drugo.
Moj bi rastavio ovako
neka je neki manji broj od 3 do 7 i neka je čvor odgovoran za 1 do 8
onda podeli na 1 do 4 i 5 do 8
pa podeli na
3 do 4 (od 1 do 2 nema ičeg) pa to poveća za jedan
a drugu stranu podeli na
5 do 6 i poveća za 1
i podeli na 7 do 8
pa poslednji podeli na
7 i poveća za jedan, a 8 nema ičeg.

Kad hoću da vidim tza 5, prođem za sve koji su dogovorni i saberem te vrednosti i nađem koliko je puta okrenuto.

Nadam se da je moja ideja jasna i mislim da je dobra, samo meni se ispostavilo da je spora.

Ok, ja sam bukvalno pomislio na heap, pa sam si rekao zasto mu je sad heap potreban. Trebalo da napises balansirano drvo :)

Ok, tako ima više smisla, jer su uređeni međusobno. Znači pre je AWL nego heap, mada nije išta tačno od toga... :-)

evo me. Pa da , i ja sam mislio kao boba.Ali ako tu nema leba kako se onda radi ?

Samo malo, to što meni nije prošlo je možda razlog što sam loše isprogramirao :-(

ok.
Napisao si ovo :
"mada nije ista taÄ?no od toga... :-)"
pa sam ja pomislio da ideja pada u vodu.

Ma to je više bilo za dimitra. Bilo je vezano za to da li sam koristio heap ili AWL. Nisam konkretno koristio ni jedno ni drugo, ali nešto što se može uporediti. Heap je jer su listovi iste dubine, mada je i AWL balansiran, a AWL je jer mogu da radim pretragu dok u heap-u ne možeš, možeš samo min ili max niza, ali se AWL obično dinamički pravi (kao stablo) a heap statički, tako da ne mogu da poistovetim sa nekim od ta dva. Taj komentar se odnosio na ovo što sam objasnio.

Samo da te popravim: nije AWL nego AVL :)

Hvala. To je ozbiljna greška.

Nije vezano za realizaciju al' ajde. Meni na vreme padaju test-primeri od 12-20. Jedanaesti prolazi za oko 0.67 sekundi. Koliko vama prolazi? Pitam jer mislim da nesto nije u redu sa tajmetrom ili test primerima.

Ne verujem da ima neki takav problem, posto admin je vec
resio zadatak. Najverovatno problem je u tvoj program, a ne u
testovi.

Mogu ponovo iskodirati, pa ti javiti kako mi radi, ali ne danas...

To sam i ja mislila, ali sam onda poslala ovakav program (iako je netacan). Samo sam ucitala podatke i ispisala jedinice. Dobila sam pogresna resenja (sto je i ocekivano) za primere 1-11 i prekoraceno vremensko ogranicenje za 12-20. Kako na ovakvom programu mogu da imam prekoraceno ogranicenje od 1.2 sekunde? Cisto radi napomene, test-primer 11 je radio za 0.64 sec.

type
TNiz=array[1..200000] of longint;
var
s:TNiz;
a,b,m,i,n,k,com:longint;
begin
readln(n,k);
fillchar(s,sizeof(s),0);
for i:=1 to k do begin
read(com);
if com=1 then begin
readln(a,b);
end
else begin
readln(m);
writeln('1');
end;
end;
end.

Posalji onda i mejl adminu. To treba da se zavrsi za MANJE OD 0.1 sekunde.

Znas kako , kad koristis Brute-Force kod ovog zadatka , onda se 5. test primer izvrsava za 0.05 sec , ali na ostalim primerima pada na vremenu.
Prema tvom iskazu , trebalo bi da se ocekuje da ovaj zadatak prolazi sa Brute-Force-om :)
Pozdrav.

Ne znam kome je ovo bilo upuceno, ali ako je meni...
Nisam mislio da moze da se uradi Brute-Force-om. Ona (cool_nerd) inicijalizuje sve na nulu (to moras uraditi, sem ako nisu pokazivaci, ali opet to radis samo kad ti zatreba) i prakticno samo ucita. To ti je 200 000 + 200 000 = 400 000 operacija, a program bi trebao da izvrsi oko 1 000 000 operacija za 0.1 sekundu. Mozda je bolje da neko prokomentarise ko se bolje razume u sve ovo, ali meni je uvek tako bilo kad ocenjujem algoritam i nisam pravio greske u OCENI (u kodu jesam, ali to nema veze). Zavisi sta radis od operacija. Nije isto ako je "jedna operacija" koren ili sabiranje. Ovo su elemntarne operacije, inace njih moras svakako odraditi. Njen program ima 20-ak linija i vidi se sta radi. Ovo je linijski algoritam, a od toga nema brze. Naravno nije tacan, ali to nije tema razgovora (pisanja).

Izgleda da citanje tipa longinta zafati toliko vreme!

Kad sam ja ispratio ovo:

type
TNiz=array[1..200000] of longint;
var
s:TNiz;
a,b,m,i,n,k,com:longint;
begin
readln(n,k);
for i:=1 to k do begin
end;
end.

Gorni post je greska.

E sad, meni izgleda da program je optimiziran za c++ (a ne i pascal), evo sta sam dobio kad sam ispratio isto resenje u c++

#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;

int main() {
long a,b,m,i,n,k,com;
scanf("%ld %ld", &n, &k);
for (i=0; i<k; i++) {
scanf ("%ld", &com);
if (com==1)
scanf ("%ld %ld", &a, &b);
else {
scanf ("%ld", &m);
printf ("%d", 1);
}
}
return 0;
}

Test 1 Pogresno resenje vreme izvrsavanja programa 0.01 sekunde
Test 2 Pogresno resenje vreme izvrsavanja programa 0.01 sekunde
Test 3 Pogresno resenje vreme izvrsavanja programa 0.01 sekunde
Test 4 Pogresno resenje vreme izvrsavanja programa 0.01 sekunde
Test 5 Pogresno resenje vreme izvrsavanja programa 0.02 sekunde
Test 6 Pogresno resenje vreme izvrsavanja programa 0.12 sekunde
Test 7 Pogresno resenje vreme izvrsavanja programa 0.14 sekunde
Test 8 Pogresno resenje vreme izvrsavanja programa 0.16 sekunde
Test 9 Pogresno resenje vreme izvrsavanja programa 0.17 sekunde
Test 10 Pogresno resenje vreme izvrsavanja programa 0.19 sekunde
Test 11 Pogresno resenje vreme izvrsavanja programa 0.21 sekunde
Test 12 Pogresno resenje vreme izvrsavanja programa 0.47 sekunde
Test 13 Pogresno resenje vreme izvrsavanja programa 0.5 sekunde
Test 14 Pogresno resenje vreme izvrsavanja programa 0.54 sekunde
Test 15 Pogresno resenje vreme izvrsavanja programa 0.57 sekunde
Test 16 Pogresno resenje vreme izvrsavanja programa 0.62 sekunde
Test 17 Pogresno resenje vreme izvrsavanja programa 0.65 sekunde
Test 18 Pogresno resenje vreme izvrsavanja programa 0.69 sekunde
Test 19 Pogresno resenje vreme izvrsavanja programa 0.73 sekunde
Test 20 Pogresno resenje vreme izvrsavanja programa 0.77 sekunde

Pojma nemam, sam ciklus od 1 do k je 0sec. znaci tih 0.77 su cisto od citanje.
Najbolje bi bilo da ovo objasni admin.

Boba:

citanje 200000 brojevi nije bas 0.1sec (kako sto je ispalo duri 0.8), posto citanje nije bas jedna operacija

@boba nije tebi.Cool_nerd je napisala da joj se 11. test primer izvrsava za 0.64 sec.

Ljudi imam neko novo razmisljanje.Ako uspem da ga realizujem , a mislim da hocu javljam.

Slazem se sa tobom dimitar, zato sam i stavio pod navodnicima, mada mi ipak nije jasno zasto toliko treba.

renovator, citaj postovi bolje! Koji je taj iskaz spored koj se ocekuje
da prolazi sa bruteforce? Ona je samo napravila test program za da proveri
koliko vreme traje samo citanje, i ispalo je da so dadeni time limit nije
moguce da se zadatak resi u Pascal.
Znaci admin treba da promeni time limit, posto io u Pascal izgleda je
sporiji od taj u C++

Dobro. Izvinite .

cool_nerd:

Samo prevedi tvoje resenje u C++. I pazi da koristis scanf i printf (namesto cin i cout)

Poslala sam mail adminu pa cemo da vidimo sta on kaze :)

@dimitar: steta sto ne znam C++ :)

Bolje sedi i nauci ga. Savladaces ga za 10 dana.Milsim ,nece to biti neki zavidan nivo znanja , ali ces moci da radis sigurno sve ono sto radis u pascalu .
Mnogo je lakse raditi u C++-u nego u pascalu , bar sto se tice zivaca :).

admin rece da za pascal treba iskoristiti neki "trik" za ucitavanje.

Inace, koja je razlika izmedju scanf-a i cin-a? Mozda ce to da mi pomogne u nalazenju trika.
A C cu da naucim. Cim budem imala tih 10 dana :(

Cin je uzasno sporiji .
Meni je zadatak "jezerca" prvi put pao na vremenu samo zbog toga sto nisam koristio scanf.Program je pao na , ja mislim, oko 7-8 primera.
Poz.

osim toga ne postoje nikakve druge razlike?

Pa najbitnija je razlika u efikasnosti .
Ako si mislila na razliku u koriscenju :
Pa postoje jedino sto u scanf koristis text kao format upisa .
znaci "%d %d" za brojeve ako ucitava 2 broja."%c" za char[].I OBAVEZNO PROSLEDI PROMELJIVU PO REFERENCI :
scanf("%d %d", &n, &k);

Poz.

Ok. Tnx. To vec daje ideje u kom pravcu treba da idu moja razmisljanja.
Poz

Ljudi, proslo je. Poslala sam program u C++-u. Dakle, radila sam preko kumulativnih tabela. Test-primer 20 je prosao za 0.83 sec. Hvala svima!
Poz
Sanja

Fino, samo gde su se tu nasle kumulativne tabele? Jel' to znaci da ona ideja za koju sam ja mislio da radi ne valja?

Jedan predlog:
Svako ko uradi neki zadatak nek kaze metodu koju koristio pri radu.
Znaci da li ga neko ne pita ili pita sve jedno.
Milsim da je ovo veoma vazno za one koji pocinju da uce algoritme , a ne znaju odakle da pocnu , kao recimo ja.
Kad covek cita nesto o nekom algoritmu a pre toga ga nije primenio , on nema potpunu predstavu o njemu. A ovako ,kada se zna kako se moze primeniti odredjeni algoritam u resavanju zadatka, mnogo se lakse kapira .

Bilo bi jos bolje kada bi za svaki zadatak postopjao jedan red teksta u kome se navodi metoda za resavanje zadatka .No ne verujem da bi se admin cimao s tim.
Ovo je samo predlog !
Pozdrav.

ne znam Bobo, mozda i moze.
Ja sam radila ovako: pri okretanju karata, a-ti clan niza povecam za 1, a b+1 smanjim za jedan i sve one ostale koje treba u nizu (s obzirom da radim s kumulativnim). E a kod naredbe 2, saberem sve karte do zakljucno s m-tom. suma mod 2 je bas ono sto treba da se isipse. Posto obe operacije imaju slozenost (log n), generalno je slozenost O(m log n), ako se zanemari pascalov problem sa ucitavanjem :)
Ne znam koliko sam jasno ovo rekla, posto umem da budem prilicno konfuzna, ali to je to. Ako treba, poslacu i kod.

I've done it :D

Samo da se zahvalim.

Ako nekog zanima, ono resenje koje sam ja predlagao puca na vremenu, na poslednjih 5 test primera.
Test 1 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 2 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 3 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 4 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 5 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 6 Tacno resenje vreme izvrsavanja programa 0.23 sekunde
Test 7 Tacno resenje vreme izvrsavanja programa 0.28 sekunde
Test 8 Tacno resenje vreme izvrsavanja programa 0.31 sekunde
Test 9 Tacno resenje vreme izvrsavanja programa 0.35 sekunde
Test 10 Tacno resenje vreme izvrsavanja programa 0.38 sekunde
Test 11 Tacno resenje vreme izvrsavanja programa 0.43 sekunde
Test 12 Tacno resenje vreme izvrsavanja programa 0.92 sekunde
Test 13 Tacno resenje vreme izvrsavanja programa 0.98 sekunde
Test 14 Tacno resenje vreme izvrsavanja programa 1.08 sekunde
Test 15 Tacno resenje vreme izvrsavanja programa 1.16 sekunde
Test 16 Prekoraceno vremensko ogranicenje
Test 17 Prekoraceno vremensko ogranicenje
Test 18 Prekoraceno vremensko ogranicenje
Test 19 Prekoraceno vremensko ogranicenje
Test 20 Prekoraceno vremensko ogranicenje

moracu sada da se nadovezem na sve (uglavnom sa pitanjima!)...
prvo, Sanjin nacin za resavanje ovoga je bas dobro osmisljen! svaka cast!
:)
ali moracu da pitam:
1. poslao sam i ja (kada mi je resenje zadatka padalo na vremenu) samo ucitavanje u pasclu! i proslo mi je za sve testove! zasto mi onda sve posle 5. testa koji prolazi za SAMO 0.03 sekunde, pada na vremenu i,
2. posto sam pokusao i u c++u da otkucam ovo, (ako nema odgovora na ovo 1. :) ) kako tu da inicijalizujem niz od 200001 clan - prijavljuje gresku u kompajliranju!

Ne znam da li C++ ima fillchar, ali mozes da ides od 0 do 200001 i postavljas na 0. Ja sam tako radio. Isao sam od 0 do N.

Sto se tice prvog pitanja... Pa nisam ni najbolje shvatio, a mozda i da sam shvatio ne bih znao razlog :(

vezano za pascal:
resenje ovog zadatka nece da mi prodje dalje od 5. testa koji prolazi za 0.03! (to ne znam zasto)!
a kada sam isprobao da li ce na vremenu da prodje samo ucitavanje u pascalu - proslo je kada sam taj niz punio nulama sa for i:=1 to n!

e, a za c++:
jel moze da se definise niz[200001] a da ne pravi problem!

da, svatam da nije problem u definisanju vec bilo da posaljem kod u pascalu bilo u c++ 6. primer i ostali nadalje padaju na vremneu a 5. se izvrsava za 0.02!!!!

Jednostavno uradi ovo :
#include <vector>

vector <int> niz(200001);

i to je sto se tice inicijalizacije (automatski inicijalizuje na 0 sve elemente);
Ako hoces neku drugu vrednost :

vector <int> niz(200001,1)

ovaj vector sadrzi elemente inicijalizovane jedinicom.

Sto se tice vremena :
prvih 5. test primera se izvrsava za mnogo manje vremena od ostalih.
za moj kod :
Test 1 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 2 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 3 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 4 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 5 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 6 Tacno resenje vreme izvrsavanja programa 0.13 sekunde
Test 7 Tacno resenje vreme izvrsavanja programa 0.14 sekunde
Test 8 Tacno resenje vreme izvrsavanja programa 0.16 sekunde
Test 9 Tacno resenje vreme izvrsavanja programa 0.18 sekunde
Test 10 Tacno resenje vreme izvrsavanja programa 0.21 sekunde
Test 11 Tacno resenje vreme izvrsavanja programa 0.23 sekunde
Test 12 Tacno resenje vreme izvrsavanja programa 0.49 sekunde
Test 13 Tacno resenje vreme izvrsavanja programa 0.52 sekunde
Test 14 Tacno resenje vreme izvrsavanja programa 0.59 sekunde
Test 15 Tacno resenje vreme izvrsavanja programa 0.63 sekunde
Test 16 Tacno resenje vreme izvrsavanja programa 0.67 sekunde
Test 17 Tacno resenje vreme izvrsavanja programa 0.72 sekunde
Test 18 Tacno resenje vreme izvrsavanja programa 0.75 sekunde
Test 19 Tacno resenje vreme izvrsavanja programa 0.81 sekunde
Test 20 Tacno resenje vreme izvrsavanja programa 0.83 sekunde

@renovator
Sto se tice tvog predloga da onaj ko resi zadatak posalje svoj nacin resavanja nije dobra. Cilj foruma nije da se postavljaju resenja i nacini resavanja zadataka vec da se pomogne drugima u resavanju zadataka.

Nisi me dobro razumeo.
Ja sam mislio ovako:
vecina tezih zadataka se radi pomocu nekih algoritama kao recimo :
DP , Greedy , BFS , DFS ...
U ovom slucaju su to "cumulative tables" ( zbirne tabele ).
Verujem da vecina ljudi prvi put cuje za ovo.Da sanja nije rekla kako je radila , sumnjam da bi iko drugi uradio (@sanja hvala :) ).
Isto tako , kad neko , manje iskusan , radi neki zadatak za koji je potrebno poznavanje , recimo , DP-a onda se moze ubiti od razmisljanja i na kraju ce verovatno pokusati da hack-uje sajt da bi video tudja resenja jer bi mu to bilo lakse nego da se muci oko resvanja :D .
Znaci , ja nisam mislio da neko pise ovako :
" prva linija kucaj #include <iostream> , druga linija kucaj... ".
nego da kaze jednostavno : "ovaj zadatak se radi DP-om " i onda neko ko gori od zelje da uradi taj zadatak uzme da nauci DP i to je najbolji nacin da nauci DP i da odmah nadje njegovu primenu.Toliko o tome.
Pozdrav,
Relja

Da, ali svaki zadatak mize da se uradi na nekoliko nacina, izuzev nekih koji moraju da se rade na odredjen nacin.
NPR.
Odrediti najvecu sumu podniza A od Ai do Aj.
ovaj zadatak moze da se urani sa slozenoscu N^3, N^2 i N odnosno ima tri razlicita resenja i u zavisnosti od vremenskog ogranicenja ili memorije (ako se koristi 10^9 i vise clanova) moze da prodje samo 1 ili 2

Ma dobro , 'ajd nek bude da si u pravu .
Pozdrav.

Meni interesuje taj trik za u pascalu. Jel mozda postoji druga procedura za citanje osim ReadLn?

Vidish, to je i mene interesovalo. Ja osim readln ne znam nista drugo... Pali su mi na pamet stringovi, ali mislim da je konertovanje stringa u broj jos sporije od readln-a.

Postoji, ali ona verzija koju ja znam koristi
uses crt

pa onda necu dalje da objasnjavam posto treba da se izbaci svaki uses u paskalu.

Jel moze neko ko je resio ovaj zadatak da pogledne u moj kod?
Nemam pojma sta nije u redu, testirao sam ga i radi sasvim ok,
a kad ga ispratim daje pogresno resenje na site testovi!

Drakce, zasto treba da se izbaci svi uses?

imas dve greskse :

Ti ucitavas a i b pa onda povecavas c[a] i c[b+1] a max index za c je 199999.Tebi moze da ispadne i 200 001.
++c[a]; --c[b+1]; - to ti ne treba.
ali ,najvaznije je to sto nisi lepo implementirao zbirne tablice.
prvo treba :++c[a];
pa :if (!a) break;
i na kraju :a += a & (-a);

mislim da je to sve sto se tice gresaka.
Pozdrav.

u stvari nije sve..
to isto treba da uradis za b+1.
znaci niz od 2000002 elemena ,inicijalizacija svih elemenata na 0 i ovo gore navedeno i to prolazi - isporbano.
poz.

Hvala renovator, proradio je!

E sad nesto drugo... Znaci ja u osnovu znam kako rade kumulativne tabele, ali pojma nemam kako su primenjeni u ovaj zadatak, i zasto to radi, koja je ideja... Jel moze neko ko je shvatio ovo da objasni bolje? Nadam se da nisam dosadan :)

pa ovako , kada ti se zada komanda za okretanje karata , ti uvecas prvu kartu a od koje se okrece i zadnju b + 1 do koje se okrece. Znaci ,sad kad uzmes bilo koji element niza on ce predstavljati zbir okretanja karata do njega.
znaci imas ovako :
1 2 4
1 2 5
za svaki index glasi :
0 2 0 1 1
sad ako uzmes trecu kartu ona je okretana 2 puta.Ako je karta okretana paran broj puta znaci da je okrenuta prema stolu i sutrotno.
ak uzmes 4 onda je zbir 3 i ona je okrenuta na gore.

e sad to je drugacije implementirano u zbirnim tablicama tako da ne mozes direktno da pristupas elementima niza po indexu i da saznas zbir do nje niti da racunas zbir svih okretanja do n-1 ( n je index karte za koju hoces da vidis polozaj) jer bi to bilo sporo.
to je koliko ja znam o ovome ...
znam kako radi ali zato su mi operacije nad bitovima mucne :(
poz.

E sad sam shvatio. Hvala ti jos jednom!

e sad , ukoliko nekom nije jasan princip funkcionisanja kumulativnih tabela moze zadatak raditi na drugi nacin.Vreme izvrsavanja je neznatno vece(za zadnji primer je 0.96).Meni je proslo iz prve :)
Naime , niz od 200000 elemenata se moze posmatrati kao jedno 'rasklopljeno' binarno drvo.Naime levi i desni clan sam trazio ovom funkcijom :

__inline int child(int a , int l)
{
if ( (a - l) == 1 ) return 0;
else return ( l + ( a - l )/2 );
}
ovde je 'a' levi a 'l'(ala ispade :) ) desni kraj u kome se trazi desno ili levo dete nekog elementa.
Element na vrhu je u stvari A[(n+1)/2] gde je n broj elemenata a A niz inicijalizovan nulom.Za pocetak se stavi da je levi kraj intervala 0(l) a desni n+1(d).Mislim , verovatno vam nece biti jasno sta pricam ali evo pogledajte kod.Ako nesto nije jasno , pitajte.Mozda nekom zatreba ( samo funkcije get i set a ostalo je standardno ):

( n - broj karata , N - niz ( 1..n ) inicijalizovan nulom )

__inline void set(int a)
{
int p = child(n+1 , 0);
int l = 0, r = n+1;
do {
if( a < p ) { N[p]++; p = child( (r = p) , l);}else
if( a > p ) { p = child(r , (l = p) ); }
if( a== p ) N[p]++;
}while( p != a && p);
}

__inline bool get(int a)
{
int p = child(n+1 , 0);
int l = 0, r = n+1;
int s = 0;
do{
if( p < a ) { l = p; s += N[p]; p = child(r , p);}else
if( p > a ) { r = p; p = child(p , l); }
if( p ==a ) s += N[p];
}while( p != a && p );
return s%2;
}

pozdrav.

Koristio sam Bobinu ideju, i sve je proslo :

Testiranje
Test 1 Tacno resenje vreme izvrsavanja programa 0.01 sekunde
Test 2 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 3 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 4 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 5 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 6 Tacno resenje vreme izvrsavanja programa 0.18 sekunde
Test 7 Tacno resenje vreme izvrsavanja programa 0.2 sekunde
Test 8 Tacno resenje vreme izvrsavanja programa 0.23 sekunde
Test 9 Tacno resenje vreme izvrsavanja programa 0.26 sekunde
Test 10 Tacno resenje vreme izvrsavanja programa 0.29 sekunde
Test 11 Tacno resenje vreme izvrsavanja programa 0.32 sekunde
Test 12 Tacno resenje vreme izvrsavanja programa 0.69 sekunde
Test 13 Tacno resenje vreme izvrsavanja programa 0.76 sekunde
Test 14 Tacno resenje vreme izvrsavanja programa 0.83 sekunde
Test 15 Tacno resenje vreme izvrsavanja programa 0.89 sekunde
Test 16 Tacno resenje vreme izvrsavanja programa 0.96 sekunde
Test 17 Tacno resenje vreme izvrsavanja programa 1.01 sekunde
Test 18 Tacno resenje vreme izvrsavanja programa 1.08 sekunde
Test 19 Tacno resenje vreme izvrsavanja programa 1.14 sekunde
Test 20 Tacno resenje vreme izvrsavanja programa 1.19 sekunde

jedva, ali je ipak proslo :)