Drzavno 2015 B kategorija - 2,3 zadatak


#1

Kako se resavaju drugi i treci zadatak iz ove godine?

U drugom sam pokusao ovako nesto ali ideja mi izgleda nije dobra

U trecem sam uspeo 80 poena da izvucem, ali iskreno mislim da je sreca (sortiram po brzini tragace, i onda radim BFS ali to uopste nije tacno, slabi testovi)

  1. zadatak: https://petljamedia.blob.core.windows.net/root/Media/Default/Problem/Drzavno%202015%20B2%20Izmena.pdf

#2

Evo i treceg: https://petljamedia.blob.core.windows.net/root/Media/Default/Problem/Drzavno%202015%20B3%20Anti%20zmurke.pdf


#3

Drugi:

Ucitavas slovo po slovo od stringa sa komandama i na osnovu toga pomeras robota, napravis brojace za L,R,U,D i povecavas ih i pamtis na kojoj je poziciji pomocu neka dva inta npr(pozRobotX i pozRobotY). Svaki put kada dodas novo slovo pomeris robota na osnovu tog slova(komande) i sad proveravas koliko najmanje komandi treba da se promeni da bi robot prosao kroz tacku ako su uzete samo komande do kojih si stigao.
Izracunas koliko je udaljen robot od tacke po x kordinati(x-pozRobotX) i takodje po y kordinati. Resenje za udaljenost robota od tacke ti je ukupna udaljenost/2(deli se sa 2 jer svaki put kada promenis komadnu robot promeni svoju poziciju za 2) . Da bi robot mogao da prodje kroz tacku 2 uslova moraju biti ispunjena:

  1. (x-pozRobotX) i (y-pozRobotY) moraju biti iste parnosti u suprotnom nikako ne moze proci kroz tacku
  2. Broj komandi koje su suprotne od komandi sa kojim bi robot dosao do tacke mora biti veci ili jednake od razdaljine robota u odnosu na tacku podeljeno sa 2, primer za to:
    Ako se robot nalazi na 0,0 a tacka na -3,-5 jedini nacin da se pomeri u levo i na dole jeste da se Right prebaci u: Left ili Down i da se Up prebaci u: Left ili Down. Dalke za taj slucaj trebas da gledas samo koliko imas komadni Right i Up jer jedino njih mozes da menjas kako bi se robot pomerio levo i dole - u kodu imas nacin kako da jednostavno izracunas koliko imas suprotnih komandi bez da pises sve ifove(gore levo, gore desno, levo dole…)

Ovo gore je bilo za A(svaki put pitas da li je A najmanje do sada, pamtis ga i na kraju ga ispises)
B se dobija isto kao i A samo sto odmah uzmes sve komande u obzir(racunas robota da se nalazi na krajnjoj destinaciji) i resis B u O(1).

Evo koda sa komentarima:
KOD
Moguce da ti ovaj 2 uslov nece biti najjasniji, valjda ce ti kod pomoci, ako ti nesto nije jasno slobodno pitaj, znam da nisam bas najbolje objasnio


#4

Trebao sam malo vise da se potrudim, do formule se dolazi lako. Inace, vidim da si resio 3. jel moze neki hint?


#5

Ne secam se kako se resava 3, sad cu ponovo da ga uradim pa cu ti hintovati


#6

Uradio sam kao i ti samo sto sam stavljao da duzina[red-tragaca][kolona-tragaca] = 0 tek kada dodje taj tragac na red i dobio sam 100 poena. Ne znam da li je 100 poena zbog losih test primera ili tako treba da se radi :confounded:


#7

Nije mi bas jasno sta ti znaci duzina[red-tragaca][kolona-tragaca] = 0?
Takodje, ako je za svako i Vi = 1, kako da se zadatak resi u boljoj slozenosti od O(NMK)?


#8

Nije duzina, razdaljina :stuck_out_tongue: Razdaljina od nekog tragaca do polja, na to sam mislio


#9

Mozes da mi posaljes svoje resenje?


#10

#11

Hvala, radio sam isto ali sam imao TLE, sad sam ga malo optimizovao i dobio jedva AC (0.81s najgori) Evo koda ako nekom treba za ubuduce: https://ideone.com/vp6rZy