Tasks

Hi
I'm not realy new to this and I see you have a lot of tasks here, so I was wondering could someone tell me which tesk could I do that would require some efford, since all (just few actually) tasks that I looked at now weren't realy hard, but meybe I just didn't looked at the right ones?
__________________________

Cao
Ja nisam bas nov u ovome ali vidim da imate dosta zaataka ovde, pa sam se pitao da li bi neko mogao da mi kaze koji bi zadatak ja mogao da uradim a da moram da ulozim malo napora u to, posto su svi (samp par zapravo) zadataka koje sam sad pogledao bili nekako prejednostavni, ali mozda samo nisam pogledao prave zadatke?

Hahahhaha, of course there are hard tasks...

For example:
http://z-trening.com/tasks.php?show_task=5000000341
http://z-trening.com/tasks.php?show_task=5000000949
http://z-trening.com/tasks.php?show_task=5000000455

If you need more tasks just say :D

Those 3 tasks I gave you are pretty hard in my opinion.
But there are nice challenging tasks that are not so hard in sections Serbian Regional Competitions and Serbian National Competitions.
You can find those sections at training page: http://z-trening.com/training.php

I mean I don't know how hard tasks you are looking for :)

Looks intresting, I'll do them when I finish 2 other that I planed to do.

But it's late and I have to do few things before going to bed.

Thanks

Nisam bas shvation prvi zadatak tako da sam sam sad odlucio da radim drugi (little eugen), ali dobijam puruku "Invalid memory reference (MLE or SEGF)" kad submitujem, i pitao sam se da li bi mi mogao reci sta to znaci.

I ako mozes da mi objasnis sta treba da se radi u prvom i drugom zadatku.

hvala

Nisam siguran sta radis u zadatku, ali MLE (memory limit excided) dobijas kad koristis vise memorije od dozvoljenog, a TLE (time limit excided) dobijes kad ti se program ne zavrsi u zadatom vremenu.

Mozes objasniti svoje resenje pa cu ti reci da li je dobro ili nije, posto mi je tesko da skontam iz tvog koda.

Ovi zadaci koje sam ti dao su dosta teski, moras da znas dosta naprednih algoritama kao sto su (matching, heavy-light decomposition, cumulative table, segment tree).

U zadatku z-red ti je dato drvo i treba da za svaki upit tipa 1 odgovoris koji je k-ti crveni cvor na putu od korena stabla do zadatog cvora, pri tome upit tipa 2 moze da menja boju cvora.

Onda cu pokusati da prilagodim program. Ovo sam radio samo da bi radilo. Mislim da imam ideju kako da poboljsam.
Inace mislim da nema smisla raditi zadatke ovde ako nisu izazov. A te algoritme koje si spomenuo cu guglovati sutra (spomeni jos ako ima...), sad idem na spavanje.
Laku noc.

Ukoliko si pocetnik, onda nemoj ni pokusavati da uradis ove zadatke :)
Ima dosta drugih koje je bolje da sada radis, kao sto sam napomenuo zadaci sa okruznih i drzavnih takmicenja su dobri, nisu ni malo naivni. Ides u meniju Training pa onda odaberes sekciju Serbian Regional Competitions ili Serbian National Competitions...

Preporucio bih ti da procitas ovaj tekst:
http://takprog.dms.rs/tekstovi/08.03.2011/slozenost_algoritama.pdf
A nije ni ovaj los tekst:
http://andrejko.ailic.in.rs/data/takmicenje/skripte/dinamicko.pdf

Ima tih algoritama koliko hoces, ali neces nista postici ako samo budes ucio algoritme...

Najbolji sajt za pocetnike je po meni http://ace.delos.com/usacogate
zato sto su zadaci sortirani po tezini i za svaku oblast imas tekst...
Napravi tamo account i pocni da radis i veoma brzo ces doci do teskih zadataka.

Procitacu to, neizgleda predugo.

I u vezi mog programa za drugi zadatak. Mislim da ipak nije ispravno ovo sto sam radio, tj da nedaje tacno resenje.

Znaci dosao sam do toga da imam sve moguce putanje (niz sokova koji mogu ici jedan posle drugg, i za svaki nov sok u nizu sam pravio novu putanju da bi mi i kraca i duza bili dostupni) i sad neznak kako to da sklopim.
Treba da probam da iskombinujem sve moguce kombinacije putanja i da vidim gde ima najmanje putanja. Jel bi mogao da mi pomognes?

Pa dobro si uradio to sto si nasao koji sok moze da ide posle koga (ako sam dobro shvatio da si to uradio), ali problem nastaje kad treba da gledas sve moguce kombinacije putanja.
Tih putanja ima previse, tako da treba nekako na pametan nacin da nadjes koji je najmanji broj putanja tako da svi sokovi budu napravljeni.

E sada kako se ovo resava, jeste da se te putanje posmatraju kao grafovsko stablo i postoji teorema koja kaze da je minimalan broj disjunktnih prostih puteva u stablu takvih da pokrivaju celo stablo jednaka maksimalnom matching-u u tom stablu.

Zvuci super, samo mi bjasni sta je matching u stablu ili ako mozes da mi pokazes gde mogu da procitam o tome?

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

Ovde mozes da procitas sta je maximum flow problem, pa se matching svede na taj problem,
sto imas tu i objasnjeno kako.

E tek sam sada skontao sta sam napisao.
Pogresno sam napisao, najmanji broj prostih puteva tako da pokrivaju stablo je broj grana u stablu - max matching.

A evo zasto to radi:
Imas stablo i ti treba da obelezis grane na neki nacin da napravis proste puteve, a da ostane sto manje neobelezenih grana (to su ustvari ciscenja), sto se dobija bas max matching-om.
Tj. sto je vise grana u max matching-u to ce manje ostati neobelezenih grana, a ako uzmes u obzir da postoji n-1 grana u stablu (n je broj cvorova), onda je broj neobelezenih grana u stablu posle matching-a n-1-max matching...

Ovo sto si mi dao o analizi algoritama me je inspirisalo da ubrzam svoj algoritam za ovo sto sam dosada imao.
Zapravo ja sam ranije koristio nizove bool promenjvih, koje koliko sam shvatio koriste jedan bajt, a sad koristim nizove nepotpisanih dugih dugih celobrojnih koje su 64 bita (naravno koristio sam sizeof da izracunam duzinu za svaki slucaj) i tako sam umesto da uporedjujem svaki bool pojedinacno upredjivao (sa &) te 64-bitne odjedared i time ustedeo mnogo na prolasku for naredbom kroz svaki, a i ovako koristim mnogo manje prostora. Imao sam gomilo bagova zbog toga ali sve sam otkrio. Takodje sad brisem tekst odma posle uporedjivanja.
Ovde imas vizuelno da vidis sta se dobija, samo ubaci primer iz zadatka ili bilo sta... E: je element (0/1 pokazuju koji elementi mogu ici posle njega), P: putanja (0/1 pokazuju koji su elementi u putanji).

http://www.solidfiles.com/d/06a8528c04/

To za matching cu probati za nekoliko dana, sad moram nesto da ucim. A i treba da dovrsim sudoku.