Alien Party Invites

Moze li neki hint za rjesavanje zadatka?

postavis resenje=n

ides kroz glavni niz i pamtis koliko je kojih imena unutra

kad od svakog imena bude bar po jedan stanes

sad sa pocetka izbacujes sve koje mozes tako da ostane bar po 1 od svakog

ako je ta lista kraca od trenutne prepravis resenje

pa onda izbacis sledeceg od dole i ponovis sve ovo bez inicijalizacije resenja i tako dok ne dodjes do kraja




ja sam bar tako radio

i ja sam tako radio, dobio sam 75 poena, mozda nisam bas vnimavao na granicne slusajeve :). Ali ona sto najvise me plaselo kod ova zadaca je to sto u granicen slucaj ako imas 10000, i 40,000 da sporedujes so svaki od ti unikatni to je u najlos slucaj 40000*10000=400,000,000 sto je prevelik broj da se presmeta za ova vreme.

hmm, kad ste vec otvorili temu, jel moze neko ko zna c++ pogledat moj kod jer mi pada na 2 primjera...

ups, mislio sam na prvi zadatak s alienima

loverboy o kakvih 400000000 govoris

ako zelis vidjeti da li neki od tih 40 000 stringova imas prije ne moras to raditi u O( N ), mozes recimo koristiti balansirano binarno stablo koje ce ti osigurati O( lg N ) sto je dovoljno brzo, u stl-u imas "map" koji ti moze posluziti, ili da koristis hash

sortiranje i binarna pretraga resavaju problem ako sam dobro razumeo o cemu se radi

a i pamtis koliko je puta koje ime na spisku u trenutnom intervalu

Radio sam tako, prolazi na vremenu (20.test - 0.37 s.) , koristio sam binary search i qsort.....

pada mi jedino na 18. test primjeru, pa ako netko ima vremena pogledati što ne valja, bio bih zahvalan

Verovatno je neki specijalni slucaj. Razmisli malo o tome kakve se situacije sve mogu dogoditi i pogledaj da li tvoj program postupa ispravno u svakoj od njih.

Najčešća greška: ona sitna u kodu, najme, varijaablu mini sam inicijalizirao na 10 000 a trbalo je 40 000 jer ona označava poziciju u drugoj listi, hvala.... :]

Moze li ko malo bolje pojasniti kako se rjesava. Ja sam koristio map, ali mi stalno javi wrong result.