Pagini: 1 ... 3 4 [5]   În jos
  Imprimă  
Ajutor Subiect: OJI Liceu 2010  (Citit de 46294 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #100 : Martie 12, 2010, 23:36:41 »

@ Radu Vlad: Nu sunt de acord cu tine.
La prima problemă, Gigel ar fi trebuit să citească limitele, iar cu puțină experiență și-ar fi dat seama că o abordare de tip greedy nu ar lua mai mult de 10 puncte, și că problema nu pare a admite soluție polinomială.

La cea de-a doua problemă, dacă ar fi citit din nou limitele ar fi văzut N <= 5000 și K <= 10. Cum K << N (a se citi mult mai mic) este destul de evident că o rezolvare care nu ține cont de K e extrem de probabil să ia 0. Iar dacă nu îi venea ideea de dinamică în mod sigur ar fi fost mult mai bine să facă un back. Decât un greedy cu șanse serioase de a lua 0, mai bine un back care să ia 40, și povestea cu profesoara care i-a zis să nu facă back mi se pare absurdă.

Ca o concluzie, subiectele mi s-au părut echilibrate, nu au fost nici prea simple, dar nici prea grele, motiv pentru care comisia cred că ar trebui felictată pentru efortul depus.
Memorat
cricri
Strain


Karma: -3
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #101 : Martie 12, 2010, 23:46:57 »

polinomiala?saracu Gigel n-a auzit de asa ceva,face info dintr-a 9a,nu de secole...

omule,daca tu vezi back intr-o problema din aia(2)....respectul meu...ei bine,mie imi pare rau dar nu vad...recunosc,nu imi place backul,nu pentru ca nu as sti sa-l folosesc,ci pentru ca e ineficient.oricat ai imbunatati un back,tot ineficient ramane....dar ma rog,fiecare vede cum are ochii.

zici ca sunt echilibrate....uite , ca sa-ti dau o statistica...in 2009 primii 100 de informatiieni de clasa a11a au avut peste 58 de puncte...anul asta doar 32 au resit aceasta performanta...nu crezi ca e o discrepanta cam mare?deasemenea,doar 42 de a12a din cei 100 de anul trecut au luat peste 58....asta in cazul in care mai sunt unele persoane care spun ca din a11a pana in a12a mai inveti informatica

daca deranjeaza postul meu,spuneti si-l voi sterge...is doar frustrarile mele pe care nu am avut unde sa le postez,asta e!o sa inghit in sec!
« Ultima modificare: Martie 12, 2010, 23:56:39 de către Radu Vlad » Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #102 : Martie 12, 2010, 23:51:47 »

Mi-e mi s-a parut anul asta mai usor decat in ultimii 2-3 ani ( referitor la problemele de la cls 11-12 ). Si da, daca ai pretentii sa rezolvi probleme de OJI, ar trebui sa stii sa faci legatura intre restrictii si rezolvare. De obicei, restrictiile iti "dicteaza" complexitatea rezolvarii. Repet, back la a-11a, mi se pare usor.
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #103 : Martie 13, 2010, 00:01:38 »

Polinomială este derivat din polinom, mai pe scurt nu poți găsi un algoritm care să aibă complexitatea N2, N5 sau N37.

Sunt de acord că backul este ineficient ca timp. Dar limitele erau mici (N, M <= 20 și cel mult 15 nemuritori), deci nu se cerea ceva eficient ca timp și mai degrabă ceva care să dea rezultatul corect. Recunosc că și eu m-am țăpit la problema asta pentru că în loc de back am făcut o chestie care deși ajungea mai repede la rezultat mânca mai multă memorie și am pierdut 50 de puncte.

În legătură cu rezultatele ai dreptate, în sensul că sunt mai slabe decât anul trecut, dar dacă te uiți sunt 25 de oameni de a11a care au peste 100 si 35 de a12a. Prin urmare, eu zic că se putea.

Îți înțeleg supărarea, pentru că s-a dat ceva ce nu se prea aștepta nimeni, dar nu trebuie să te descurajezi. Smile
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #104 : Martie 13, 2010, 08:55:34 »

Asta ar trebui privita ca pe o experienta de invatare din care tragi 2 concluzii importante:

- Referitor la problema 1: Nu exista asa ceva ca "cea mai ineficienta metoda de programare", nu toate metodele de programare fac acelasi lucru. Backtracking-ul are un scop: sa exploreze toate posibilitatile, trebuie sa realizezi ca nu toate problemele pot fi rezolvate cu solutii mai rapide. Daca reusesti sa o faci fara backtracking, s-ar putea sa fi eligibil sa iei un milion de dolari. http://en.wikipedia.org/wiki/P_versus_NP_problem Smile

- Referitor la problema 2: Nu te poti astepta sa iei mai multe puncte cu o solutie care rezolva *alta* problema, decat cu o solutie care rezolva problema corect dar e mai eficienta.
« Ultima modificare: Martie 13, 2010, 09:45:15 de către Bogdan-Cristian Tataroiu » Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #105 : Martie 13, 2010, 10:37:08 »

In plus, la scoala se studiaza backtracking, si exista probleme care se rezolva cu backtracking'ul. Probabil nu te plangeai daca aveai ceva permutari sau combinari de facut..

Totusi, e olimpiada si e normal sa fie ceva original, si mai greu decat o problema clasica.
Memorat
ucc_5
Client obisnuit
**

Karma: -11
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #106 : Martie 13, 2010, 11:26:10 »

In principiu ar trebui sa stii ca backtrackingul e defapt cel mai important algoritm pentru olimpiada. Au fost ani la oni in care doar daca faceai back la toate te clasai in primii 20, eventual intrai si in lot. De asemenea orice problema pe care nu intelegi cum sa o faci (si esti bun, adica nici ceilalti nu or sa fie mult mai buni ca tine) fa-o cu back, ca s-ar putea si fii singurul care ia ceva puncte pe ea. Si noua ne spun profii sa nu folosim niciodata back ca e prost, mai ales cel recursiv (desi ma indoiesc ca o sa fie usor sa implementezi ceva iterativ), dar daca ar fi sa ascultam de ei ... multi nu s-ar califica.
Oricum e clar ca subiectele de anul asta au fost incredibil de usoare, cred ca doar a fost ceva in atmosfera in timpul oji si d-aia au luat multi punctaje mici  Tongue.
Memorat
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #107 : Martie 13, 2010, 11:39:52 »

In primii 20 sa intri doar cu back...... poate doar la clasa a 11a , ca acolo sunt punctaje mici....iar despre lot nici vorba!
E bine sa stii back, poti sa-ti verifici sursa cu el.... iar cel recursiv nu e mai lent decat cel iterativ (nu se simte diferenta prea mare).

Memorat
cricri
Strain


Karma: -3
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #108 : Martie 13, 2010, 14:14:19 »

In plus, la scoala se studiaza backtracking, si exista probleme care se rezolva cu backtracking'ul. Probabil nu te plangeai daca aveai ceva permutari sau combinari de facut..

Totusi, e olimpiada si e normal sa fie ceva original, si mai greu decat o problema clasica.

daca tie back-ul ti se pare original , imi pare rau ca te contrazic...in rest,prefer sa nu mai comentez... traiasca back-ul....
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #109 : Martie 13, 2010, 14:32:46 »

Ar trebui sa intelegi ca tu nu ai experienta oamenilor care ti-au raspuns si in loc sa-ti plangi soarta, sa inveti de la ei pentru a fi mai bine pregatit. Un factor important, adesea decisiv, la Olimpiada (la toate etapele) este psihologia de concurs si, din povestea ta, mi-a fost foarte clar ca tu duci mare lipsa de asa ceva. Poti depasi acest neajuns lucrand mai multe probleme (nu doar in ajunul Olimpiadei) si participand la mai multe concursuri (Algoritmiada, .campion, etc.).

Anual, vad ca foarte multa lume are pretentia sa ajunga la Olimpiada Nationala, dar foarte putini cunosc si sunt dispusi sa faca sacrificiile necesare pentru asa ceva.
Memorat

Am zis Mr. Green
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #110 : Martie 13, 2010, 14:58:00 »

Anual, vad ca foarte multa lume are pretentia sa ajunga la Olimpiada Nationala, dar foarte putini cunosc si sunt dispusi sa faca sacrificiile necesare pentru asa ceva.

Foarte adevărat grăiești din punct de vedere al sacrificiului și al pregătirii. Ok
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #111 : Martie 13, 2010, 21:20:43 »

Smile cred ca rezolvatul de probleme interesante e distractiv si motivant nu e un sacrificiu.
Memorat
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #112 : Martie 13, 2010, 23:14:59 »

Smile cred ca rezolvatul de probleme interesante e distractiv si motivant nu e un sacrificiu.

Cred ca Paul se referea la timpul "asa zis pierdut" cu pasiunea ta. Eu cel puțin am o plăcere imensa când rezolv o problema pe infoarena de 100p. Am asa o satisfacție ca am învățat ceva nou. Poate alții nu au același interes.
Memorat
tvlad
De-al casei
***

Karma: 63
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #113 : Martie 14, 2010, 15:02:20 »

Scenariu: Gigel scrie paragrafe, nu totul pe o linie.
Concluzia: Cineva citeste ce a scris. wink
Memorat
Pagini: 1 ... 3 4 [5]   În sus
  Imprimă  
 
Schimbă forumul:  

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