Probleme de formula

[•Cosmin]

Comentarii la postul http://infoarena.ro/blog/probleme-de-formula

[•wefgef]

Si totusi... uneori se ascunde o idee foarte frumoasa in spatele unora dintre problemele de formula. E mare pacat ca se poate "ghici" rezultatul.

[•domino]

Si totusi... uneori se ascunde o idee foarte frumoasa in spatele unora dintre problemele de formula. E mare pacat ca se poate "ghici" rezultatul.

Nu s-a contestat ca ideile n-ar fi frumoase, pur si simplu n-au ce cauta problemele astea la olimpiada de informatica.

[puiu29]

 Poi daca nu au ce cauta atunci comisia mult iubita de ce le propune ?

[•greco]

Subscriu la ideea lui Cosmin, pe care am sustinut-o in repetate randuri.

Wefgef are dreptate: de multe ori se ascund in spatele lor idei frumoase, dar exact asa cum spune si Mircea ele ar trebui sa fie folosite la concursurile de matematica sau rezolvate pe cont propriu de catre elevii cu astfel de pasiuni. Din moment ce componenta informatica e foarte mica, ce sa caute la ONI, baraj sau lot?

Pai... trebuie sa fim sinceri: de multe ori cineva vine cu o astfel de problema iar restul comisiei nu are alternative mai bune. Si-a dat seama cam toata lumea ca nu sunt bune, dar atata timp cat nu se pot inlocui cu altceva, care sa fie solutia? Concursuri cu mai putine probleme? Ma rog, in timp ce scriam asta mi-am dat seama si ce o sa raspundeti: da, concursuri cu mai putine probleme, cu un numar variabil si anuntat la inceputul probei, mai exact. Daca membrii comisiei nu reusesc sa gaseasca 3 probleme "adevarate" s-ar putea da numai 2, si ar fi mai bine decat 2 + una de formula...

In orice caz, sa nu uitam ca infoarena are ca scop pregatirea elevilor pentru olimpiade, deci atata timp cat la olimpiade se dau probleme de formula ele isi au locul si aici. Desi ar fi interesant sa se intample asta, infoarena n-a devenit inca un scop in sine ci ramane un mijloc online de a obtine rezultate offline.

[puiu29]

de multe ori cineva vine cu o astfel de problema iar restul comisiei nu are alternative mai bune.

Adica nu exista cineva suficient de capabil sa faca alte probleme ca asa am inteles eu de aici ?

[•wefgef]

de multe ori cineva vine cu o astfel de problema iar restul comisiei nu are alternative mai bune.

Adica nu exista cineva suficient de capabil sa faca alte probleme ca asa am inteles eu de aici ?

Sau destul de motivat (financiar si nu numai) sa o faca

[•greco]

Da, ai înţeles perfect (dacă punem completarea lui Wefgef). Capacitatea "profesională" restului comisiei plus motivaţia existentă (bani, faimă, interes pentru buna desfăşurare a concursului, etc.) egal mai puţin decât probleme mai bune decât cele de formulă.

[•sciobaca]

Chestia cu "e usor de vazut [n!/e + 1]" mi se pare cel putin dubioasa. Adica cum sa-ti vina ideea sa imparti fix prin e?

In rest, subscriu ca problemele de formula nu sunt de dorit in cadrul unui concurs de programare. De fapt, putem generaliza putin si spune ca problemele de numarare nu sunt tocmai de dorit. De obicei, o solutie la o problema de numarare sau ia 100 daca e corecta, sau ia 10 daca merge pe exemplu, sau ia un punctaj intermediar daca are o complexitate mai proasta. Dar nu am vazut sa greseasca cineva un program de numarare astfel incat sa mearga pe doar cateva inputuri de test si pe altele sa nu mearga (nu ma refer acum la timeout).

Oricum isi au si aceste probleme rostul lor. Un algoritmist bun trebuie sa se descurce cu de toate. Cai de a "trisa" sistemul prin obtinerea de solutii care sa mearga desi autorul nu cunoaste demonstratia exista. Si se folosesc din plin la concursurile de programare. Si aceste cai  "dubioase" fac parte din frumusetea concursurilor de programare.

[•Cosmin]

@stefan Nu iti vine ideea sa imparti fix prin e, dar observi ca de la n = 9 la n = 10 rezultatul creste de 10 ori.

[•sciobaca]

@stefan Nu iti vine ideea sa imparti fix prin e, dar observi ca de la n = 9 la n = 10 rezultatul creste de 10 ori.

Si mai departe?

[•Cosmin]

Asa te poti prinde ca formula finala e [n! * constanta1 + constanta2] si e simplu sa aflii constantele.

[•wickedman]

In orice caz, sa nu uitam ca infoarena are ca scop pregatirea elevilor pentru olimpiade, deci atata timp cat la olimpiade se dau probleme de formula ele isi au locul si aici. Desi ar fi interesant sa se intample asta, infoarena n-a devenit inca un scop in sine ci ramane un mijloc online de a obtine rezultate offline.

Eu cred ca ne-am raportat destul (prea mult?) la olimpiadele scolare. infoarena te ajuta sa inveti informatica si programare. Invatatul e un lucru fundamental, olimpiadele sunt doar catalizatori.

Indiferent daca se dau sau nu la olimpiade, problemele "de formula" sau de numarare isi au locul aici, macar pentru cei dispusi sa le rezolve conventional. In plus, poti sa inveti ceva chiar si din intuirea unei formule, asa cum fac fizicienii. Nu intotdeauna e simplu.

[•sciobaca]

Asa te poti prinde ca formula finala e [n! * constanta1 + constanta2] si e simplu sa aflii constantele.

Nu te cred ca te poti prine asa

[•greco]

Eu cred ca ne-am raportat destul (prea mult?) la olimpiadele scolare. infoarena te ajuta sa inveti informatica si programare. Invatatul e un lucru fundamental, olimpiadele sunt doar catalizatori.

Nu ştiu... prima pagină infoarena are în titlu motto-ul "te ajutăm să devii olimpic"... Dacă e cum zici tu, poate ar trebui schimbat! Pe lângă ce-şi doreşte echipa infoarena să realizeze, trebuie să luăm în calcul şi ce-şi doresc membrii comunităţii. În cazul meu, a fost în primul rând să mă descurc mai bine la olimpiade, cu ajutorul IA. Crezi, sincer, că s-a schimbat atât de mult lucrul ăsta?

Poate ar merita făcut un sondaj, deşi nu ştiu cât de sincere ar fi răspunsurile (e mai frumos să zici că "vreau doar să învăţ" decât să recunoşti că tot ce vrei e un premiu la olimpiadă).

[•fireatmyself]

Da, ai înţeles perfect (dacă punem completarea lui Wefgef). Capacitatea "profesională" restului comisiei plus motivaţia existentă (bani, faimă, interes pentru buna desfăşurare a concursului, etc.) egal mai puţin decât probleme mai bune decât cele de formulă.

marea majoritate a elevilor care ajung la olimpiadele nationale (si internationale), depun un efort considerabil. daca un profesor nu este destul de "motivat" si da o chiftea (nu neaparat de formula), tocmai si-a batut joc de toata pregatirea participantilor. cred ca motivatia tine mai mult de respectul fiecarui profesor pentru munca elevilor.

[•greco]

Pe lângă faptul că am menţionat în lista aia "interes pentru buna desfăşurare a concursului" (care tocmai de aici vine, din respectul pentru munca depusă de elevi), nu cred că abordarea ta e una prea productivă. Comisiile olimpiadelor sunt formate, în general, pe bază de voluntariat, iar responsabilitatea propunătorilor e cea pe care şi-o asumă ei, nu cea pe care vrei să le-o impui tu.

La fel de bine, eu aş putea să spun că e responsabilitatea elevilor să se pregătească minim 10 ore pe zi şi să ia numai medalii de aur la competiţiile internaţionale, şi că mai puţin de atât ar fi o lipsă de respect faţă de efortul depus de comisii.

Să revenim puţin cu picioarele pe pământ...

[•wickedman]

Imi cer scuze ca o sa continui discutia aceasta off-topic. Ar fi interesant sa dezbatem subiectul mai pe larg, eventual pe marginea unui nou blog post.

Nu ştiu... prima pagină infoarena are în titlu motto-ul "te ajutăm să devii olimpic"...

Tiberiu, ai dreptate. In plus, concursul cel mai mare pe care-l organizam - preONI - se raporteaza prin definitie ONI. Nu neg ca asta e starea de fapt. Este clar ca aceasta a fost directia in care am mers dintotdeauna. De asemenea sunt convins ca succesul la olimpiade este printre motivele predominante ale utilizatorilor infoarena, un fapt pe care eu nu il blamez.

infoarena poate sa fie un instrument foarte bun pentru cei care se pregatesc la olimpiade dar in acelasi timp sa aiba un scop mai grandios decat atat.

[•fireatmyself]

[...]
Comisiile olimpiadelor sunt formate, în general, pe bază de voluntariat, iar responsabilitatea propunătorilor e cea pe care şi-o asumă ei, nu cea pe care vrei să le-o impui tu.
[...]

intr-adevar. fiecare membru al comisiei isi asuma o anumita responsabilitate fata de ce propune, dar insasi postura de propunator ar trebui sa aduca de la sine responsabilitati.

nu vreau sa arunc cu noroi in niciuna din parti. spun doar ca decizia de a da in concurs o problema de formula, a carei rezolvare "se ghiceste" (de cele mai multe ori), poate afecta pe un elev bun, mai "neinspirat" in acel moment. de la acest lucru ar trebui pornita discutia despre a propune sau a nu propune o problema de idee in concurs. cum ziceai si tu mai sus, 2 probleme sunt mai bune decat 2 + una de idee...

[•sima_cotizo]

cum ziceai si tu mai sus, 2 probleme sunt mai bune decat 2 + una de idee...

Cred ca daca vrei sa abordezi problema de formula, o faci, daca nu, nu... Acea problema totusi va fi abordata de cineva care renunta la a obtine 100 pe celelalte 2 si prefera sa se limiteze la 40 pe subiect - lucru in avantajul elevilor la primele contacte cu ONI. De aceea, cred ca e bine sa se mai dea cate o problema de formula la gimnaziu / clasele 9-10 (maxim), dar la 11-12, unde domeniul din care poate fi ales un subiect este foarte vast, ar trebui probleme de alt fel de idee.

PS: ar fi monoton ca toate problemele sa fie doar pentru aplicat X algoritmi intr-o sursa sau folosit Y structuri de date, doar ca sa minimizam o complexitate cat sa intre in timp. De aceea exista solutii de departajare (50-80p daca nu ai ideea dar optimizezi frumos, 100 daca o ai ... si mai e categoria cu 10-20p daca ai ideea dar o busesti ).

[•greco]

Apropo de PS-ul tău, Cotizo, există destule probleme care nu se rezolvă numai prin folosirea unor algoritmi şi a unor structuri de date tradiţionale. Un exemplu elocvent e problema "becuri" a lui Cosmin de la lotul din 2006, să zicem. Şi multe altele intermediare, la care ai nevoie de o idee deosebită şi după ce o găseşti poţi merge pe drumuri mai bătătorite până la cele 100 de puncte.

Numai că problemele astea se găsesc (compun) greu, şi autorii lor din alte ţări sunt mai bine motivaţi decât românii. Nu vreau să dau jos de pe un piedestal o activitate până la urmă frumoasă (munca profesorilor, elevilor şi studenţilor pentru o olimpiadă interesantă şi rezultate internaţionale bune), dar nici să nu ne ascundem după deget dacă vrem o estimare sinceră a situaţiei curente.

Problemele de formulă sunt un defect între multe altele al concursurilor de informatică, însă aceste defecte nu se pot rezolva peste noapte. E ca atunci când ne plângem de străzile pline de gropi... cât timp nu ne dezvoltăm în mod real şi organic, străzile "bombardate" şi problemele de formulă sunt doar metastaze ale unor boli mai profunde.

[•rgrig]

De multe ori mi se pare foarte instructiv sa gasesc formula, chiar si prin ghicire urmata de demonstratie.

Atunci cand sunt folosite in concursuri avantajeaza
 (1) pe cei care ghicesc si nu demonstreaza si
 (2) pe cei care au vazut problema.

Totusi, cred ca varietatea problemelor e mai importanta.