infoarena

Aici puteţi discuta despre problema Dmg (http://infoarena.ro/problema/dmg).

Au ceva special testele 15, 16, 17? (numerotate de la 1 la 20)
Iau restul testelor, dar astea:

(numarul de drepte e raportat corect)

probabil ca e o problema cu precizia pe undeva.. dar am folosit matrici de transformare, iar pt cazul de egalitate am incercat precizii intre 1e-2 si 1e-5 (la 1e-6 dadea inca 2 erori..)


*** possible spoilers below!  (nu cititi daca vreti sa rezolvati problema complet singuri!) :) ***


Eu calculez coeficientii dreptelor din 2 puncte:
centrul dintre primul punct si punctul i
considerand ca transformam sistemul de coordonate a.i. dreapta de simetrie pe care o verific sa coincida cu Ox si in (0,0) e acel centru; mai iau punctul (10, 0) si il transform inapoi in sistemul de coordonate normal

Am incercat sa iau al doilea punct ca fiind centrul de greutate (in cazul cand acesta nu coincide cu centrul)... si mai imi da pe inca 2 teste "Wrong Axis of Symetry"

Any hints/ suggestions? :)

Cum tratezi cazul in care ai doi politisti la aceleasi coordonate?

Enuntul e dubios in privinta asta... ne intreaba pe noi ce se intampla... daca ar fi dupa mine, nu i-as lua in considerare, pentru ca se ciocnesc. ;)

Nu ii iau in considerare. Dar nu e de aici problema; daca asta ar fi fost, as fi luat "wrong number of axis"

Testele la problema asta sunt destul de ciudate. Numarul de axe de simetrie se pare ca e extrem de mare fata de ce ma asteptam. Nu mi se par cinstite testele cu mai mult de 10 axe de simetrie pentru sunt evident fortate.
Oricum, stiu ca nu e prea indicat dar nu poate cineva sa puna macar un test asemanator cu ultimele?
Cred ca asta e una din cele mai dificile probleme de pe infoarena si nu e deloc usor de depanat sau de facut generator de teste la ea.
Apropo, de ce tot timpul cam tot raportul evaluatorului apare si in monitorul de evaluare?

Si cum masori cat de cinstit e un test ? :) In general se urmareste construirea unor teste care sa acopere (spre testele dificile) cazul cel mai defavorabil. Asta se urmareste in concursuri.

Silviu

Modul in care ar trebuii facute testele pentru o problema e destul de subiectiv si tot timpul e o provocare pentru cel care propune problema. Tot timpul trebuie sa ai grija la cazurile particulare si trebuie sa ai grija sa nu dai multe puncte la programele prost gandite, limita de timp nu trebui sa fie nici prea stransa dar nici prea lejera, etc.

Eu personal prefer testele cat mai aleatoare pentru ca consider ca 80 sau chiar 90% din punctaj ar trebui sa fie obtinut cu o solutie cu un timp de executie bun pe cazul mediu, situatiile rare care ar forta pe cineva sa implementeze solutia mai buna teoretic fiind mai putin importante dupa parerea mea.

Nu cred ca toata lumea e de acord ca testele sa fie facute intr-un asemenea mod dar mie mi se pare cel mai "corect". Din pacate e aproape imposibil sa faci teste cu puncte random care sa aiba o axa de simetrie deci nu prea ai de ales la probleme ca dmg.

PS: cred ca am aflat ce are monitorul de evaluare cand mai arata bucati din borderou. Mesajele evaluatorului sunt prea lungi. De exemplu, atunci cand apare: "Wrong Answer : Number of axes is not correct!" toate mesajele apar in monitor. Motivul s-ar putea sa fie altul dar e un bug enervant.

Chestia cu bug-ul e de la caracterul ":" de fapt.

S-a reevaluat problema Dmg :)

Imi cer scuze ca postez aici dar n-am stiut unde . Am o intrebare usoara legata de geometrie(eu sunt cam praf la geometrie).
Am 2 puncte cum determin ecuatia dreptei (ax+by+c=0 ). Am vazut intr-0 carte ca
a=y1-y2
b=x2-x1
c=x2*y1-y2*x1
am cautat pe net si inca tot nam inteles cum se ajunge la asta..
eu m-am gandit sa scriu ecuatia dreptei ca y=panta*x+constanta care nu coincide cu formula de mai sus. Si inca ceva din cate vad eu
a,b,c nu sunt unice pentru o dreapta.daca poate cineva sa ma lamureasca.mersi :D

Da. Exact cum ai zis a,b,c si nu sunt unice. Poti sa le inmultesti pe toate cu aceeasi valoarea si ecuatia ramane valabila. Deci pentur una din valori fixata exista fix o solutie pentru celelalte 2. Poti gasi usor valori dupa ecuatia y = panta*x + constanta daca il faci pe b = 1. Iti ax + y + c = 0
sau
y = -ax - c. Unde -a e panta si -c e constanta dupa cum le-ai zis tu. Totusi aceste 2 valori in general sunt fractii. Daca incerci sa scapi de numitor ai sa ajungi la forma a = y1-y2, b = x2-x1 si c = x2*y1 - y2 * x1

Salut! Imi poate spune cineva cum as putea sa fac un hash pentru numere reale, si sa am precizie, de exemplu 1e-4? Multumesc anticipat! :)

Cred ca merge daca faci functia de hash de aici : http://infoarena.ro/tabele-hash-scurta-prezentare (pentru numere reale),
dar aplici functia pentru y zecimale ale lui x (asta pentru precizie).

Mersi de raspuns! :) Am incercat sa fac chestia aia, dar greseste pe anumite teste. Foarte probabil ca am gresit eu la implementarea ei. Ma voi mai uita peste ea.

Totusi, rog pe cineva sa verifice daca se mai poate lua 100 cu actuala limita de timp, pentru ca ma chinui de mult timp si tot nu reusesc sa trec de 55 de puncte. Multumesc anticipat! :)

Cu complexitate worst case O(N ^ 2) nu se pot lua mai mult de 55 pct, desi teoretic ar trebui sa intre.

Am marit limita la 0.5. Sursa lui Filip Buruiana are complexitatea O(N^2) si ruleaza in 304 ms.

Limitele pt |X| si |Y| nu sunt bune, am pus assert si iau KBS 6 pe 9 teste, dar nu influenteaza rezolvarea problemei.


LE: am luat 100 cu noua limita de timp, mersi wefgef  :winner1: