infoarena

Aici se pot pune întrebări legate de problema Arcas (http://www.infoarena.ro/problema/arcas) de la concursului AGM 2016 (http://www.infoarena.ro/agm2016).

Sageata se poate deplasa doar de jos in sus?

"Acesta trage de M ori cu arcul din diferite pozitii reprezentate de perechea de coordonate (x,y) si cu puterea r, care semnifica faptul ca dupa ce sageata a trecut prin punctele (x,y), (x+1,y+1), (x+2,y+2),..., (x+r,y+r) acesta isi foloseste puterile si o face ca si disparuta"

Tintele nu ar trebui sa fie paralele cu axa Ox?
Pe desen sunt paralele cu Oy.

" Mai exact, in plan se afla N tinte verticale reprezentate prin x, y1 si y2 cu semnificatia ca tinta se afla de la poztia (x,y1) la pozitia (x,y2) in plan. "

Desenul trebuie rotiti la dreapta cu 90grade sa respecte enuntul.

Desenul este corect.
"Tintele sunt colorate cu maro, iar traiectoria sagetii este colorata cu rosu"

In enunt se spune ca "... aceasta dispare". Este vorba de sageata sau de tinta?

De sageata.

Problema se poate face in M*log(N) ? :)

Da, aceasta se poate face in M*log(N) atat offline cat si online.

Imi poate explica cineva care este solutia oficiala? Eu am incercat sa sortez tinele dupa x si la fiecare query (tragere cu arcul) cautam binar in vector intre care tinte se afla x-ul actual, din care trag, iar daca y-ul tragerii + (x-ul tintei - x-ul tragerii) se afla in intervalul determinat de tinta, daca da inseamna ca sageata va zbura peste tina aia si trebuie contorizata si repetam asta pana cand x-ul tintei este mai mare decat x-ul tragerii+puterea tragerii. Insa imi da TLE pe 7 teste.

Pentru fiecare tinta (x,y), faci o translatie. Cu alte cuvinte, fiecare tinta (x,y) va deveni (x,y-x). Acum sageata e aruncata orizontal si nu mai e inclinata la 45 de grade. Aceasta problema se poate cu smenul lui mars pe un arbore de intervale persistent sau cu o preprocesare offline a query-urilor.

Seara faina :D

Extinzand un pic explicatia lui Patrick cu o demonstratie care arata de unde vine solutia respectiva:

In principiu vrem sa determinam in ce conditii o "tragere" intersecteaza o "tinta". Unei tinte oarecare ii corespunde un triplet (x0, y0, y1), iar unei trageri un (x', y', r).
Observam ca punctele de pe traiectoria tragerii sunt de forma (x' + r', y' + r'), 0 <= r' <= r. Pt a avea intersectie, trebuie ca (x' + r', y' + r') sa fie pe dreapta verticala (x0, y0, y1) corespunzatoare tintei, pt un 0 <= r' <= r (exista maxim o intersectie intra o dreapta transversala si una verticala) <=>
exista 0 <= r' <= r, a.i:
1) x0 = x' + r'
2) y0 <= y' + r' <= y1

Observatie 1: singurul r' candidat este r' = x0 - x', care tb sa fie intre 0 si r. Inlocuind in a 2-a conditie avem:
y0 <= y' + r' <= y1 <=> y0 <= y' + x0 - x' <= y1 <=> y0 - x0 <= y' - x' <= y1 - x0

Observatie 2: Avem 2 conditii pt intersectie: una la nivel de x si una la nivel de y dupa cum am vazut mai devreme. Conditia pt y nu depinde deloc de r', si implicit de r. Putem rescrie conditiile de mai devreme ca:
1) x' <= x0 <= x' + r
2) y0 - x0 <= y' - x' <= y1 - x0

De aici ne vine ideea de a ne creea un nou sistem de drepte a.i:
a) "tinta" (x0, y0, y1) -> (x0, y0 - x0, y1 - x0)
b) "tragerea" (x', y', r) -> (x', x' + r, y' - x')

Astfel avem numai drepte orizontale si verticale ; iar o intersectie intre o dreapta verticala si una orizontala respecta conditiile 1) si 2). Aceasta problema este un exemplu clasic de line sweeping prezentat spre ex la https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ sub sectiunea "line segment intersections". Se poate folosi intr-adevar un AIB + Smenul lui mars pt a numara numarul de intersectii intre "portiunea activa" si o dreapta verticala.

Multumesc de ajutor ! Big up !  :thumbup:

Seara faina !  :D

Multumesc mult, foarte faina ideea de rezolvare si desi am gasit care sunt criteriile sa se intersecteze nu mi-a dat prin cap sa transform sistemul  :aha: