Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Arcas  (Citit de 1986 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 804



Vezi Profilul
« : Martie 26, 2016, 08:56:22 »

Aici se pot pune întrebări legate de problema Arcas de la concursului AGM 2016.
Memorat
CNGrigoreMoisil_Dospra_Ciobanu_Preda
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #1 : Martie 26, 2016, 09:48:59 »

Sageata se poate deplasa doar de jos in sus?
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #2 : Martie 26, 2016, 09:54:16 »

"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"
Memorat
RaduToporan
Strain


Karma: -3
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #3 : Martie 26, 2016, 10:05:13 »

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


Karma: 9
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #4 : Martie 26, 2016, 10:10:31 »

" 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. "
Memorat
RaduToporan
Strain


Karma: -3
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #5 : Martie 26, 2016, 11:28:24 »

Desenul trebuie rotiti la dreapta cu 90grade sa respecte enuntul.
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #6 : Martie 26, 2016, 11:37:53 »

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"
Memorat
CNGrigoreMoisil_Dospra_Ciobanu_Preda
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #7 : Martie 26, 2016, 11:43:57 »

In enunt se spune ca "... aceasta dispare". Este vorba de sageata sau de tinta?
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #8 : Martie 26, 2016, 11:51:29 »

De sageata.
Memorat
andrew_assassin789
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #9 : Martie 29, 2016, 16:43:10 »

Problema se poate face in M*log(N) ? Smile
Memorat
george_stelian
Echipa infoarena
Strain
*****

Karma: 6
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #10 : Martie 29, 2016, 17:35:57 »

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


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #11 : Martie 30, 2016, 22:09:19 »

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.
Memorat
xtreme77
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #12 : Martie 30, 2016, 23:44:16 »

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 Very Happy
Memorat
cosmin79
Strain
*

Karma: 36
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #13 : Martie 31, 2016, 18:18:39 »

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.
Memorat
xtreme77
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #14 : Martie 31, 2016, 19:20:10 »

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 !  Thumb up

Seara faina !  Very Happy
Memorat
Vicktor
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #15 : Aprilie 01, 2016, 21:16:45 »

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
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines