z-green

Koristio sam BIT, nevidim razlog zašto ne prolazi.
Molim pomoć.

http://z-trening.com/submit.php?submit=7100091769&subm_code=1

1. Postavi da je MaxN = 201.


2. U proceduri log.set, imaš
...
for ( ; i >= m ; i += i & -i) {
...

Zar ne bi trebalo:
...
for (int _i = i ; _i <= n ; _i += _i & -_i) {
...

3. U funkciji Get nisi obuhvatio sve slučajeve. Mislim da bi trebalo:


int Get (int x1, int y1, int z1, int x2, int y2, int z2) {
return log.get (x2 , y2 , z2 )
- log.get (x1 - 1, y2 , z2 )
- log.get (x2 , y1 - 1, z2 )
- log.get (x2 , y2 , z1 - 1)
+ log.get (x1 - 1, y1 - 1, z2 )
+ log.get (x1 - 1, y2 , z1 - 1)
+ log.get (x2 , y1 - 1, z1 - 1)
- log.get (x1 - 1, y1 - 1, z1 - 1);
}

4. U main() delu ne treba ++x,++y,++z,++x1,... Sve koordinate su u intervalu [1,n].

5. Moraš proveravati da li je data sijalica već upaljena, kao što je u primeru iz teksta zadatka.

Opet mi neradi.

EDIT:
zapravo radi, prenaglio sam se.
Imao sam greške poput:

a[ i ][ _j ][ _k ] += value;

a trebalo je

a[ _i ][ _j ][ _k ] += value;

i

log.set (x, y, z, 1);

a trebalo je

log.set (x, y, z, 1 - Get (x, y, z, x, y, z));

i još nešto, nema potrebe provjeravat je li upaljeno ili ne, tj. je li obojano zeleno, prolazi i bez toga.

Puno hvala

Znaš li možda još neki zadatak koji se rješava s logaritamskom strukturom (BIT-om)??

Baš ovom zadnjom
log.set (x, y, z, 1 - Get (x, y, z, x, y, z));
to i radiš.
Program bi mogao nešto brže da radi da se stanje sijalica čuva u pomoćnom nizu.

Ma ok je, samo jel mi možeš odgovorit na pitanje?

Imas MATSUM, on se resava BIT-om.

Rješio sam ga, znam još za z-names i z-product, ali onu su mrvicu teži od ovog i MATSUM-a, mislim čak da bih i mogao rješit z-product, ali trebalo bi malo razmislit

BIT sam koristio u zadacima magija, matsum, reli, names...

E hvala, to sam tražio

Mislim da je z-names najteži koji bi se trebao pojavljivati ovdje i na natjecanjima uopće, ali svejedno ću ga pokušati rješiti, pa ne postoji nerješiv zadatak, osim možda zadatka z-shortest koji je JAAAAKO težak, (gotovo) nerješiv.

@halil:
hoćeš li da ti dam svoj mail??

Moji mailovi:
igorh@sbb.rs
fahrudin.halilovic@cimos.si

Moj ti je:
matteokinkela@hotmail.com

z-names preko BIT?
hmm ne znam bas...

Imaš li ti bolju ideju??

pa gledaj sad pretpostavlja da misli na BIT kao ako imas ime sa prvi slovom npr p ti trebas da saberes sve one a,b,c...o da bi doso do p,pa za to koristi bit
e a kad prodje to onda sve koje pocinju na t mora da prodje za sledece slovo.i za njega moze BIT ali mislim da taj pristup moze samo do nekog slova zbog prevelike memorije koju zauzima tad BIT
a to znaci da npr moze do prva 5 slova
e sad ako bi ja ubacivao sve imena za koja su ta 5 jednaka a ova ostala se razlikuju moglo bi da dodje do TLE
moja ideja je da stavim u BST koje bi pamtilo neke podatke koji bi mi omogucili da odma po ubacivanju dobijem poziciju tog imena

E probat ću to skodirat sa BST jer sam ga naučio pred par dana.
Još nešto u c++u imaš red-black BST u mapu i setu i on je brži ob BST-a po tome šta nikada ne dođe do O( N ).

da znam to ali za ovo ovde neces moci obican set da koristis da bi dobio koliko njih ima ispred a koliko iza(osim u nekom linearnom vremenu)
evo ti bolja ideja:prvo napravis prvi niz koji ostaje sortiran po prvom slovu
a onda kada dobijes neku rec ti ako njeno slovo nije tu ubacis ga a ako jeste povecas pojavljivanje za 1
i tako ides redom za svako slovo
posto za svako slovo ima oko 30 mogucnosti
a duzine je 30
znaci najvise 30*30=900 po 1 reci
10000*900=9000000
sto ce lagano proci,a to je slucaj koji se ustavri prakticno nikad nece desiti znaci bice i manje cesto.
najbolje resenje je da napravis ne niz nego BST za svako slovo
i onda dobije log30=6 slozenost po slovu
i onda imas 30*6=180
sto ce ti dati vrlo dobro vreme:D
Ti mozes sam da napravis balansirano drvo(kao set)
potrazi na netu red-black tree
tako se u c++ uglavnom stvara set

E dobra ideja, hvala.
Ili možemo skodirat taj zadatak 2 puta sa BST-om i sa RB BST-om. Da vidimo razlike u vremenu

@Matteo, sa ne-balansiram BST to nece proci, a i zadatak je moguce rijesit logaritamskom( BIT )...

a ok

ajde dgleich objasni kako ga resavas sa BIT?

Ja ću ti ga objasnit.
Znači kod učitavanja bilježiš ime i poziciju na kojoj se nalazi( pozicija neka bude od 1 do N zbog fenwick-a ) i sortiraš ih po imenu. onda u logaritamskoj označiš sve koji su manji od njega, jer tako logaritamska radi. i na kraju spremiš u niz sol rješenja query-a, tj. koliko ih ima manjih i ispišeš pomoću malo računanja, tj. prvi broj ti je sol[ i ] - 1 a drugi i - sol[ i ]. važno je kod ispisivanja da ideš petljom od 1 do N jer si tako numerirao pozicije. ako ti nešto nije jasno pitaj.

E sada jel ti meni možeš objasnit ideju za Bubble knight??

ma znam ja vrlo dobro kako BIT radi nego kako ces da ih sortiras.npr kako bi ih preveo u brojevni sistem?
a gledaj ideju za knight.radi neki greedy.ja imam npr ideju da smanjujes razliku koordinata potezima tako da na kraju ostane jedna razlika koordinata 0,ili obe 1.
a onda kad na primer imas da u x smeru treba da se pomeri 0,a u y smeru npr 4 pokusaj da dodjes do nacina da i tu y smanjis do 0 a x da ostane 0.pod x i y smatram razliku x i y koordinata pocetka i kraja
halil je imao neku drugu ideju,imam to njego resenje ako hoces da vidis,ja ovo moje nisam kucao samo sam proverio da daje dobre rezultate(msm u skladu sa halilovim)

Neću kod, sam ću rješit. Hvala. jedino ne kužim kakav brojevni sistem

ajde objasni kako ces da radis na primer kada dobijes neku rec evo na primer "cao"
sta radis?za knight moze vise resenja uglavno su to greedy algoritmi(jer je za nesto sa grafovima mngoo velika razlika koordinata)

@Milos: danas idem van pa ću ti sutra objasnit, hvala ba bubble knight

gle, kada učitavaš bilježi si poziciju na kojoj si učitao tu riječ npr.

for ( int i = 0 ; i < n ; ++i ) {
     cin >> arr[ i ].rijec;
     arr[ i ].index = i + 1;
}

i onda sortiraš po riječi koju si učitao, i s time si gotov, više nemoraš koristiti riječ nego u ostatku koda gledaš indexe.
Onda imaš for petlju u kojoj pozivaš Bit.set ( arr[ i ].index ) i u neki niz bilježiš ono šta ti query vraća tj. sol[ arr[ i ].index ] = Bit.query ( arr[ i ].index ).
i na kraju ispišeš tako da imaš for petlju od 1 do N

dobro ti prvo ucitavas sve reci i tek onda ides sort ili ucitas jednu rec pa uradis pomeranja tako da dobijes opet sortirani niz?

Prvo učitam sve riječi

onda nemas zasto BIT...uzmes i sortiras sve tako da svakom pamtis koja je njegova pocetna pozicija bila(odnosno koji je po nredu ucitan)

a probaj tako, meni je sa BIT-om lakše