Blog infoarena

Lot Informatică 2023

freak93
Adrian Budau
08 mai 2023

În perioada 7-14 Mai se desfăşoară Lotul Naţional de Informatica 2023 în Slatina, Olt.

Probele vor avea şi o varianta online găzduită de CS Academy.

Mult success elevilor!

 Comentarii ()

Categorii:

"Adolescent Grigore Moisil" International Programming Contest

xtreme77
Patrick Sava
04 aprilie 2023

Ediţia a IX-a a Concursului Internaţional de Informatică "Adolescent Grigore Moisil" (AGM) a început oficial !

Pentru a vă înscrie la Concurs, vă rugăm să folosiţi formularul următor: https://forms.gle/ViXe3VwpA1gLm1uW6

Concursul AGM se adresează elevilor de liceu care concurează în echipe de max. 3 persoane, pe stilul ICPC. Concursul are 2 runde:
- Runda de calificare (online) – 22 aprilie 2023 între orele 14:00 şi 19:00 GMT+2
- Runda finală (găzduită de ICHB, Campus Pallady în Bucureşti) – TBD

Înscrierile se închid joi, 20 aprilie, la ora 17:00 GMT+2

Problemele din concurs sunt dezvoltate integral de actuali şi foşti studenţi din Marea Britania, România şi Olanda.

Primele 10 echipe la Runda Finală vor primi diplome. De asemenea, primele 3 echipe la Runda Finală vor primi premii în bani:

Locul I: 1200 RON
Locul al II-lea: 900 RON
Locul al III-lea: 600 RON

Problemele de la ediţiile anterioare sunt disponibile pe Codeforces si in Arhiva ACM

Link-uri utile:

Website: https://agm-contest.com
Pagina de Facebook: @AGM.Contest
Regulamentul competiţiei: https://agm-contest.com/competition-rules
Adresă de e-mail: [email protected]

Cel de-al nouălea capitol al acestui proiect nu ar fi fost posibil fără efortul (voluntar!) şi dedicarea comisiilor organizatorice, tehnice şi ştiinţifice. Le suntem incredibili de recunoscători partenerilor (HandsAcross România şi Liceul Teoretic Internaţional de Informatică Bucureşti), precum şi sponsorilor (Fundaţia 'Nouă ne pasă' şi SolvIT) noştri, atât pentru susţinerea concursului, cât şi (implicit) pentru susţinerea comunităţii româneşti de informatică/programare competitivă !

 Comentarii ()

Categorii:

Nitro NLP Hackaton - 2023

Asgari_Armin
Armin Asgari
12 martie 2023

Te invităm să te înscrii la Nitro NLP Hackathon care va avea loc în perioada 20-26 martie 2023.

Înscrierile sunt deschise până pe 17 martie 2023 (inclusiv), aşa că nu pierde şansa de a participa la acest eveniment inovator!

Programul evenimentului este următorul:

  • 3 zile de workshop-uri (20-22 martie), unde vei avea ocazia de a învăţa de la experţi din industrie şi din comunitatea academică despre cele mai recente tehnologii din NLP (Procesarea Limbajului Natural).
  • O zi de conferinţă (23 martie), unde poţi asista la prezentări inspiraţionale studenţi mai mari, doctoranzi, dar şi de la lideri din domeniul Inteligenţei Artificiale.
  • Hackathon-ul de 23 de ore (25-26 martie), unde vei putea lucra în echipă pentru a găsi cele mai bune soluţii de a rezolva task-ul la care vă provocăm.

Premiile totale pentru acest eveniment sunt de 1500€, aşa că pregăteşte-te să-ţi pui abilităţile în practică în încercarea de a câştiga marele premiu!

Pentru mai multe informaţii despre eveniment şi pentru a te înscrie, vizitează site-ul nostru nitronlp.rocks şi pagina de inscriere.

Nu uita sa ne urmăreşti pe reţelele de socializare pentru a fi la curent cu ultimele noutăţi şi anunţuri despre eveniment. Te aşteptăm!

 Comentarii ()

Categorii:

Fmi No Stress11

marius135
Dumitran Adrian Marius
29 octombrie 2022

Vă invităm să luaţi parte la un concurs organizat de membrii ai Facultăţii de Matematică şi Informatică, Universitatea Bucureşti.
FMI No Stress este un concurs cu dificultate uşoară spre medie şi este destinat în primul rând începătorilor în domeniul algoritmicii. Concurenţii vor avea de rezolvat 13-15 probleme de natură algoritmică.
Proba va avea loc Duminică, 30 Octombrie, ora 10:00 pe platforma Codeforces şi se va desfăşura pe durata a 5h.
Studenţii Facultăţii de Matematică şi Informatică pot participa fizic în facultate în sălile Pompeiu, Google şi Laborator 221.
Toate detaliile se găsesc pe codeforces
Cei mai buni 10 elevi de clasa a 12-a se vor califica automat la faza finala a concursului MateInfo-UB-2023 prin care pot obtine admiterea fara examen la FMI-UB.
Vă aşteptăm în număr cât mai mare! Succes tuturor!

 Comentarii (0)

Categorii:

Retrospectiva Anului 2021

alexpetrescu
Alexandru Petrescu
29 decembrie 2021

Infoarena alături de partenerii săi

Neobosita comunitate de informatică din România s-a mobilizat să vină în ajutorul elevilor dornici să înveţe programarea şi algoritmica în aceste vremuri în care Ministerul a renunţat să-şi mai asume organizarea Olimpiadei.

Profesorii au pregătit OSEPI, studenţii i-au ajutat şi au pregătit ei înşişi Science On, iar alături chiar de elevi, Junior Challenge şi Summer Challenge. Echipe deja profesioniste au organizat InfO1Cup, EJOI, RMI şi runde de calificare ale IIOT. Departamentul Educaţional al Societăţii a publicat articolul educaţional al anului şcolar, ca început promiţător al activităţii sale.

ICPC

O victorie răsunătoare a informaticienilor români este câştigarea medaliei de argint la ICPC World Finals de către echipa Universităţii din Bucureşti, formată din livliviLivia Magureanu livlivi, retrogradLucian Bicsi retrograd şi theodor.moroianuTheodor Moroianu theodor.moroianu. Le port recunoştinţă cu adânc respect pentru abolirea mitului că ... De fapt, îl las pe însuşi Lucian să ne vorbească:

Rezultatul pe care am reuşit să îl obţinem anul acesta la ICPC a fost unul care ne-a bucurat nespus. Mă bucur că am reuşit cu această ocazie să destrămăm mitul popular că obţinerea unei medalii la ICPC este un obiectiv imposibil de realizat din partea României şi cu ocazia asta sper că această realizare să fie doar începutul.

Pentru concurs ne-am pregătit în principal simulând diverse concursuri stil ICPC pe Codeforces Gym (în principal regionale şi finale ICPC, dar şi alte concursuri foarte bine cotate) şi Opencup. Foarte important mi se pare, însă, că de multe ori am dat concursuri chiar şi în momentele în care nu ne sincronizam toţi 3 (câteodată cu Adi, câteodată în echipă de 2, câteodată singuri). Astfel, mi se pare că am avut parte de o consistenţă mai bună în pregătire (mai multe concursuri decât dacă am fi reuşit în "full team", posibilitatea de a da concursuri foarte bune pe care unul din noi se întâmpla să le ştie, dar ceilalţi nu, etc.), am căpătat o încredere mai mare în a implementa probleme singuri, dar am şi învăţat să interacţionăm mai bine fiecare cu fiecare (fiind forţaţi să nu depindem de a treia persoană). Bineînţeles, cele mai bune rezultate le obţineam în echipa de câte 3, dar tot mi se pare că am avut multe de învăţat. Recomand viitoarelor echipe să se pregătească în tot felul de formate şi să pună accent pe plăcerea de a rezolva concursuri şi entuziasmul de a discuta în echipă probleme şi idei.

În acelaşi timp, cred că pentru ICPC este important să fii mereu in linie cu ideile şi algoritmii noi care apar şi să înveţi tehnici considerabil mai avansate decât în liceu (e.g. optimizare convexă, geometrie, structuri de date, probabilităţi), dar şi să ştii când se pretează ceva complicat şi când nu. În ideea asta, cred că un mare avantaj al nostru a fost documentaţia complexă şi concisă pe care am avut-o, la care am dedicat foarte mult timp de research. Cantitativ vorbind, documentaţia ne-a ajutat la 5 dintre problemele pe care le-am rezolvat în timpul concursului, pentru 2 dintre care am primit şi First To Solve :-)

Când Lucian vorbeşte despre Adi, se referă la antrenorul echipei, freak93Adrian Budau freak93, pe care îl felicităm cu la fel de mult drag! Iar dacă vreţi să vedeţi ce bine îi şade Universităţii din Bucureşti între marile facultăţi ale lumii, vă invit să derulaţi clasamentul.

IOI

Şi la cea mai prestigioasă competiţie de liceu performanţa românilor a fost excepţională. Echipa a câştigat ţării două medalii de bronz prin Mircea_DonciuDonciu Mircea Mircea_Donciu şi AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1, una de argint prin Tiberiu02Tiberiu Musat Tiberiu02 şi una de aur prin giotoPopescu Ioan gioto, căruia am cinstea să-i dau cuvântul:

Experienţa de la IOI a fost interesantă. Deşi a fost un concurs online, pentru mine a fost şi deplasarea la Bucureşti care a făcut să fie totul mai ‘autentic’. Deviez puţin, dar mi s-a părut un gest foarte drăguţ din partea celor de la Nerdvana care s-au ocupat să organizeze o cină festivă înainte de competiţie, unde am mâncat preparate asemănătoare cu cele din Singapore. Legat de experienţa din concurs (SPOILERS AHEAD), sunt uimit de faptul că în prima zi am implementat un cuplaj, tare conexe şi un segment tree beats (care în final nu a mers), de faptul că nu a fost nicio problemă interactivă, iar problema constructivă avea legătură cu reţele de sortare. Problema mea preferată din concurs este candies, una dintre cele mai interesante structureli pe care le-am văzut.

EJOI

Păstrând registrul celor mai importante concursuri de informatică şi scăzând mai departe vârsta, ajungem la Olimpiada Europeană pentru Juniori, organizată de către SEPI. Cu experienţa pregătirii InfoPro, OJSEPI, ONSEPI, a barajelor şi a loturilor SEPI, echipele tehincă, ştiinţifică şi organizatorică le-au aranjat tinerilor europeni un concurs internaţional online.

Cei opt juniori care au reprezentat ţara gazdă au obţinut o medalie de aur, patru de argint şi două de bronz. Mulţumindu-le pentru pregătirea pe care au depus-o de la vârste fragede în condiţii de pandemie, îi felicităm scriindu-le numele, în speranţa că le vom mai citi adesea în cele mai onorabile contexte. În ordinea poziţiilor în clasament:

  • Ştefan Cătălin Savu
  • Mihai Valeriu Voicu
  • Iulian George Arsenoiu
  • Luca Mihai Ilie
  • Rareş Felix Tudose
  • Tudor Ştefan Muşat
  • Tudor Iacob
  • Tudor Ştefan Grecu

La finalul unui an bogat

Ne amintim efortul celor care şi-au vărsat cu responsabilitate şi entuziasm timpul şi energia în marele voluntariat al menţinerii şi reinventării informaticii româneşti. Aprecierea ne-o amestecăm cu sfială, pentru că nici nu ştim prin câte au trecut profesorii aceştia ca noi să avem ce rezultate să comemorăm. Uimirea ne-o împletim cu elanul de a păstra bucuria acestor realizări în noul an, atât în amintire cu recunoştinţă, cât şi în fapte cu noi succese!

 Comentarii (0)

Categorii:

Zilele Algoritmice Romanesti 2021

heracle
Radu Muntean
02 iunie 2021

Vă înaintăm un mesaj din partea domnului profesor Gabriel Istrate, de la Universitatea de Vest Timişoara.

Impreună cu Elena Grigorescu (Purdue University, Statele Unite) îmi face plăcere să vă transmit invitaţia de a participa la Zilele Algoritmice Româneşti/ Romanian Algorithms Days, un workshop dedicat cercetării româneşti în algoritmică.

Evenimentul va avea loc online in dupa-amiaza zilelor de 7-8 iunie, şi va include prezentări ale mai multor cercetători romani în algoritmică din toată lumea. Prezentările vor fi în limba engleză.

Pentru o variantă preliminară de program vă rog să consultaţi pagina:

https://sites.google.com/view/zilelealgoritmiceromanesti/home

Inscrierea la workshop e gratuită dar obligatorie, şi se poate realiza pana vineri 4 iunie pe pagina conferinţei. Worskshop-ul va avea loc folosind Google Meet, legătura fiind trimisă pe adresa de email cu care vă înregistraţi.

Cordial,
Gabriel Istrate
Universitatea de Vest din Timişoara.

 Comentarii (1)

Categorii:

"Adolescent Grigore Moisil" International Programming Contest

xtreme77
Patrick Sava
08 februarie 2021

Am plăcerea de a anunţa ediţia cu numărul şapte a Concursului (acum Internaţional) de Informatica “Adolescent Grigore Moisil” (pe scurt, AGM).

AGM a debutat în anul 2015, având drept scop crearea unui eveniment atractiv pentru elita elevilor români de liceu care reprezintă România la concursurile şi olimpiadele internaţionale de Informatică.

Anul acesta runda de calificare va avea loc pe data de 20 februarie, la ora 15:00 a României. Motivul pentru care am ales această oră este pentru a evita ca participanţii noştrii internaţionali (care apropo, sunt din Bulgaria, Italia, Israel, Singapore sau chiar Cuba!) să fie dezavantajaţi din cauza fusului orar.

În urma rundei de calificare, cele mai bune 20 de echipe româneşti şi 6 echipe internaţionale vor fi invitate la runda finală (pe care plănuim să o ţinem on site, în iulie; totuşi nimic nu este încă total stabilit). Tot la runda finală vă aşteaptă premii generoase din partea sponsorilor (TransElectrica, SolvIT, EduApps) noştri, cărora le mulţumim foarte mult (şi) pe această cale pentru susţinere.

Aş dori de asemenea să le mulţumesc tuturor colegilor (şi prietenilor!) mei din comisia ştiinţifică ( george_stelianChichirim George george_stelian, teoionescuIonescu Teodor teoionescu, vladm98Munteanu Vlad vladm98, GinguIonutGinguIonut GinguIonut, geniucosOncescu Costin geniucos, mihneacazCazacu Mihnea mihneacaz, HumikoPostu Alexandru Humiko, cosmin79Carabet Cosmin Andrei cosmin79, Alex18maiAlex Enache Alex18mai, Eman98Ghinea Mihail Emanuel Eman98, Stefan_RaduStefan Radu Stefan_Radu, LucaSeriSeritan Luca LucaSeri, bogdan10bosBogdan Sitaru bogdan10bos, Mihai22eMihai Ionut Enache Mihai22e, stelian2000Stelian Chichirim stelian2000, usureluflorianUsurelu Florian-Robert usureluflorian şi caesar2001Stoica Alexandru caesar2001) fără de care AGM nu ar putea să vă ofere un set de probleme dificil şi original (sperăm noi!).

Nu în ultimul rând, AGM a avut parte în ultima perioadă de schimbări pozitive la nivel organizatoric, datorate în mare parte parteneriatului solid dintre noi şi Asociaţia Handsacross România --- cărora le mulţumim de asemenea!

Mai jos aveţi link-uri către:

Formularul de inscriere

Regulament

Site-ul oficial

Problemele de la runda precedenta de calificare

 Comentarii (0)

Categorii:

Retrospectiva Anului 2020

alexpetrescu
Alexandru Petrescu
29 decembrie 2020

Infoarena şi concursurile comunităţii

În lipsa Algoritmiadei, comunitatea s-a mobilizat să creeze şi să participe la câteva concursuri Infoarena.

  • Concurs de încălzire: născut din tensiunea aşteptării olimpiadei naţionale. Poate primul concurs românesc la care comisia s-a jucat cu limbajele de programare, aşa încât sursele oficiale sunt scrise în C++, Java şi Python. Legenda spune că testele au fost făcute în Haskell...
  • Junior Challenge: un succes încoronat cu premiul oferit câştigătorului; prima probă desfăşurată în pace, a doua... cât de cât :-)
  • Summer Challenge: foarte atipic. Cei care au pregătit problemele au aflat că nu toate concursurile au o comisie pe deplin centralizată: fiecare cunoştea doar problema de care se ocupa, pe celelalte le-au descoperit odată cu participanţii. Aceştia din urmă au aflat că probe cu 2 probleme de tipul ~output-only & aproximativa (din care una bazată pe geometrie şi alta pe expected value), şi una pe bună dreptate numită Voodoo, nu se dau numai la olimpiadele internaţionale. Eu unul am aflat că dacă vrei ca lumea să participe la un concurs de vară, data trebuie măcar să nu coincidă cu ziua afişării rezultatelor la BAC
  • Autumn WarmUp: poate primul concurs pregătit aproape complet cu 10 zile înainte de desfăşurarea sa. Una din probleme este aproape aceeaşi cu o alta, din 2015, doar că promovează o soluţie mai eficientă. Ce m-a impresionat e că, la nici 2 săptămâni după concurs, retrogradLucian Bicsi retrograd şi freak93Adrian Budau freak93 au găsit, independent, alte 2 soluţii şi mai eficiente, foarte diferite între ele. Cea a lui Lucian poate fi adaptată în aşa fel încât să rezolvăm o problemă de la Concursul de încălzire într-o complexitate mai bună decât cea oficială, dând naştere unor articole şi unei postări pe blog
  • Winter Challenge: Goodbye 2020. L-aş numi concursul-"priveghere". Cele 4 probleme au permis concurenţilor să se expună unor paradigme diverse. Pe de o parte, recapitulative. Pe de altă parte, food for thought pentru vacanţa de iarnă.

L-am rugat pe TincaMateiTinca Matei TincaMatei să ne spună cum a fost experienţa de propunător la Junior/Summer Challenge:

Am învăţat multe lucruri din participarea în comisie, şi acum înţeleg mai bine problemele cu care se confruntă propunătorii la un concurs. Propunerea de probleme ar fi un alt tip de antrenament şi ar fi un prim pas în afara competitive programming-ului. Ca membru al comisiei, pe lângă problema propriu-zisă pe care o propui, apar mai multe „subtaskuri” separate, precum: generarea testelor, calibrarea timpilor şi a subtaskurilor, scrierea de cât mai multe bulăneli pentru a le preveni, scrierea enunţurilor sau a editorialelor.

Matei ne-a împărtăşit mai multe gânduri foarte folositoare. Voi relua încheierea mesajului său la finalul postării.

InfoPro

Printre cele mai importante, dragi şi decisive iniţiative ale comunităţii este InfoPro. Mulţumim întâi şi întâi profesorilor care s-au dedicat cu pasiune şi determinare desăvârşită acestui proiect!

Pentru acest subiect, am onoarea să dau cuvântul lui bciobanuBogdan Ciobanu bciobanu:

Cred că finalul acestui an a fost un moment foarte bun pentru concursul InfoPro. Încercăm ca fiecare ediţie a concursului să se adreseze în egală măsură tuturor participanţilor, indiferent de nivel. Participarea în regim de concurs este la fel de importantă ca rezolvarea problemelor din arhive, iar cu acest concurs sper că am adus în atenţie acest lucru. Cât pentru comisie, este un exerciţiu organizatoric foarte bun, pentru că nu am mai organizat concursuri online cu mii
de participanţi. Direcţia pe care o urmărim este cea a olimpiadelor internaţionale. Problemele tehnice întâlnite aici ne vor ajuta să înţelegem cum putem extinde cel mai bine un sistem de feedback complet online şi ne pregăteşte pentru ce va urma în cadrul olimpiadei de informatică din România. Cât despre InfoPro, putem să ajungem la nivelul unor concursuri ca USACO sau COCI.

IOI

Nu ştiu cine a pus aceasta la cale, dar cele 4 medalii româneşti au fost obţinute de Alexandru, Maria Alexa, Alexandra Maria şi George Alexandru. Îi felicităm pentru succes, alături de toţi ceilalţi medaliaţi la celelalte olimpiade online ale anului, netrecând sub tăcere trei "curiozităţi" îmbucurătoare:

Oxford: licenţă

Despre succesul uimitor al unui român la proiectul său de licenţă la Computer Science, Oxford, s-a vorbit mai pe larg într-o altă postare pe blog. Fără să schimb contextul, vreau să subliniez felul în care s-au acoperit de glorie (şi anul acesta) tamionvTamio Vesa Nakajima tamionv şi Andrei1998Andrei Constantinescu Andrei1998 prin obţinerea celor mai mari două note finale dintre toţi absolvenţii promoţiei 2020 ai facultăţii menţionate.

Mesajul de încurajare e foarte clar. Nu e întâmplător că cei despre care acum spunem "Uite-i, de-ai noştri, cum se întrec pe podium în universităţi de top!" sunt aceiaşi cu cei despre care acum câţiva ani spuneam "Uite-i cum se străduiesc să cucerească concursurile de informatică!" E o realitate, că şansa pe care o au liceenii să studieze algoritmica şi aşa-numitul competitive programming este una uriaşă, şi în sine o sursă de motivaţie şi bucurie.

Vreme trece, vreme vine

Cu peste 14 luni în urmă, în chip aproape profetic, am lansat infoarenauţilor o chemare. Spun profetic deoarece conceptul că fiecare dintre noi poate contribui la creşterea valorii comunităţii poate că e mai important ca niciodată. Confiscarea olimpiadelor ne îndeamnă să ne facem singuri dreptate. Să dăm dovadă că formăm un corp sănătos şi puternic! Pentru început, vă invităm să scriem editoriale, mai ales la problemele care nu au unul.

Avem motive să fim optimişti că vom putea organiza în continuare concursuri online, ca mângâiere că nu putem să ne întâlnim încă. Pun problema aşa, pentru a sublinia că tot ce se mişcă în comunitate este pe bază de voluntariat. Profesori, concurenţi, organizatori, sponsori, comisie tehnică, comisie ştiinţifică. Fiecare îşi găseşte locul său. Esenţial e faptul că fiecare dintre noi o face de bunăvoie, cu responsabilitate şi nu fără sacrificii. Ne unim din pasiune pentru informatică şi din drag de colegi.

Aşteptăm să ne revedem cu bucurie! Sper că prin această răbdare ne vom întări să lucrăm cu mai multă mărime de suflet.

 Comentarii (0)

Categorii:

98

alexpetrescu
Alexandru Petrescu
22 decembrie 2020

Doresc să vă împărtaşesc un nou succes al comunităţii informatice din România. Vara aceasta unul dintre membrii săi a obtinut cea mai mare nota all-times pentru lucrarea sa de licenţă la Universitatea Oxford. Vă propun să ne bucuram cu ţotii de acest eveniment şi să ne hrănim cu invăţăturile acestei lucrări.

De ce e atât de wow!

Ca să inţelegem mai bine ce inseamna această notă de 98 din 100, am selectat câteva informaţii bine-cunoscute românilor studenţi la informatică în Oxford:

  • Lucrarea de licenţă este un proiect la care lucrezi cu un profesor specializat în domeniul tău de interes. Rezultatul este, practic, un fişier pdf constând în cel mult 10 000 de cuvinte.
  • O lucrare excelentă primeşte în jur de 70 din 100 de puncte.
  • Notele de peste 80 sunt rezervate lucrărilor demne de publicat într-un jurnal sau la o conferinta, sub forma unui paper.
  • Convenţiile de examinare recomandă ca în jur de 5% dintre lucrări să primeasca o nota în intervalul 80-90.
  • Cea mai mare nota cunoscută nouă este obţinută anul trecut tot de către un român, lucrare cotată cu 91 de puncte.

Despre ce e vorba in proiectul de 98

Domeniul se numeşte 'Computational Social Choice', şi este stiinţa ce studiaza dintr-o perspectiva algoritmică orice conţine cuvintele alegători şi candidaţi. În general, un alegător are preferinţe, pe care cel mai des şi le exprima ordonând candidaţii dupa valoarea lor în ochii lui. De exemplu, într-o alegere pentru cea mai bună fetiţă Powerpuff, alegătoarea Bessie ordonează candidaţii astfel: Blossom > Bubbles > Buttercup. Date fiind preferinţele alegatorilor, se pune problema determinării câstigătorilor (unul sau mai mulţi!) într-un mod cât mai echitabil. Cuvântul echitabil este intenţionat vag, deoarece explicitarea lui în diverse modaliţăti dă naştere diverselor sisteme concrete de votare pe care le folosim (e.g. sistemul cu două tururi folosit pentru alegerile prezidenţiale).

L-am rugat pe Andrei1998Andrei Constantinescu Andrei1998 să facă un rezumat al detaliilor algoritmice ale proiectului său.

Îi dau cuvantul:

Cu toate că domeniul isi are originile in politică şi economie, ceea ce poate frapa este caracterul izbitor algoritmic al problemelor de interes. Nu voi intra foarte adânc in amănuntele de Social Choice ale proiectului, dar cred că ar fi interesant pentru comunitate să explic în ce masură cunoştinţele din liceu ajută mai departe în cercetare. Iata câteva exemple de tehnici de la concursurile de algoritmică pe care le-am folosit pentru a obţine complexităţile îmbunătăţite din lucrare:

  • Tehnica "Parametric Search", care a apărut în scena programării competiţionale o dată cu problema Aliens de la IOI 2016. Tehnica a mai fost folosită ulterior în problema Popcorn, iar membrii comunităţii au găsit soluţii alternative mai simple ce o folosesc în probleme propuse în trecut: Padurari şi Flooow.
  • Optimizarea "O(nk^2) devine O(nk)", care a apărut în România o dată cu problemele Arbkset, Lianyu şi Cli. Aceasta este o rafinare a mai cunoscutei "O(n^3) devine O(n^2)", folosită în probleme precum: Politic, Purification şi Tricolor. Dacă nu aţi auzit de acest smen, puteţi citi o superba explicaţie începând cu pagina 22 de aici (problema Barricades).
  • În afara programei de olimpiadă: Algoritmul Simplex. Cu toate acestea, problema Echilibrare admite o soluţie inedită, alternativă, folosind această tehnică; pentru majoritatea elevilor, Simplex nu e mai mult decât un "black-box". Aside: Având în vedere soluţia oficială a problemei, ce putem înţelege, sau intui, din acestea? Există strânse legături între problemele de flux întâlnite la olimpiada, forma lor matriceala şi problemele lor duale de optimizare. Nu nu, nu o să explic ce am vrut să zic cu asta - să vă provoc şi pe voi puţin!

Sistemul de vot pe care îl studiem se numeşte Chamberlin-Courant, şi este destul de uşor de descris. Avem n candidaţi şi m alegatori, fiecare alegător exprimându-şi preferinţele prin liste ordonate de preferinţe. Pentu un k dat, scopul este să alegem un comitet câstigător format din k candidaţi, adica unul de cost minim. Cum calculăm costul? Pentru fiecare alegător număram candidaţii mai bine văzuţi de către el decât toţi aleşii din comitetul de k, şi apoi adunăm la costul total acest număr. De exemplu, dacă primele opţiuni ale tuturor alegătorilor formeaza o mulţime de cel mult k candidaţi, atunci comitetul câstigător va avea cost 0! Din păcate, problema generală este NP-hard, dar nu este totul pierdut, deoarece în alegeri reale preferinţele candidaţilor nu sunt arbitrare, sau "worst-case", aşa cum ne obisnuiesc temerarii comisiilor, ci au destul de multa structură. În ce sens au structură? Depinde - esenţa este să restrângem domeniul de preferinte suficient de puţin încât să putem înca modela alegerile reale, dar şi suficient de mult încât să putem rezolva problema în timp polinomial. Nu zic mai mult să nu plictisesc!

Totuşi, cel mai mare efort pentru mine a fost acela de a prezenta noile rezultate clar şi fără "leap"-uri în raţionament. Am observat în general o oarecare superficialitate când vine vorba de asta - de foarte multe ori într-un salt în raţionament se ascunde o greşeală extrem de subtilă. În sensul ăsta, vă las cu o anecdotă: primul rezultat pe care l-am avut a constat pur şi simplu în a citi un paper vechi de aproximativ 5 ani. Am observat cum autorii prezentau un algoritm polinomial bazat pe programare dinamică pentru o problema pe arbori, dar algoritmul era redactat de aşa natura încât micile greşeli de scriere (cum ar fi un ' uitat aici, un indice dincolo) se aliniau perfect cât sa dea naştere unui algoritm care părea corect. Şi mai interesant, în funcţie de cum corectai typo-urile, fie devenea greşit, dar polinomial, fie corect, dar atunci analiza complexităţii nu mai mergea dusă la capăt (algoritmul devenea exponenţial pe un arbore stea, aşa cum arătăm în paper-ul complet). Ironia este că am fost la un milimetru să zic "mda, are sens, probabil e corect", cum nu înţelegeam încă toate notaţiile şi ideea centrală părea naturala. Totuşi, ceva tot parca nu se lega şi eram încăpăţânat! Fast-forwarding, am găsit un algoritm nou pentru problemă, unde am putut folosi chiar optimizarea menţionată în lista de tehnici de la olimpiade de mai sus.

Două gânduri

Andrei a fost de acord cu mine că nota a fost obţinută după un efort considerabil de a explica cât mai bine cum curg ideile una din alta. Nu era suficient să fie clar, trebuia să şi pară natural şirul logic al ideilor prezentate. După aceasta "dezvăluire a secretului", aş încheia postarea cu un mesaj de încurajare adresat juniorilor, seniorilor şi studenţilor nostri, din partea lui Andrei:

Mi se par sincer prea puţini aceia care îsi doresc o carieră în cercetare, şi sunt uimit de numărul covârsitor al oamenilor, în unele cazuri medaliaţi chiar şi cu aur la olimpiadele internaţionale, care nici nu iau în calcul această variantă. Industria tech nu trebuie văzută ca un life goal după olimpiade - există atât de multe lucruri stimulante intelectual în cercetare şi pe care nu le vei găsi niciodată în industrie, lucruri care pot aduce o satisfacţie extraordinară - de la a învăţa lucruri noi şi până la descoperi o nouă teorie, poate chiar ceva ce poate salva vieţi!

 Comentarii (0)

Categorii:

Nave Ordonate

alexpetrescu
Alexandru Petrescu
28 septembrie 2020

De dorul intalnirilor care aveau loc in anii mai darnici in concursuri onsite, simt sa va impartasesc cateva idei, vechi si (mai ales) noi, de rezolvare a unor cerinte. As dori sa deschid o discutie tehnica inspirata de noile solutii eficiente descoperite la problemele Nave (in varianta initiala sau de actualitate) si Ordonare. Mi se ofera astfel ocazia sa implic intreaga comunitate: am structurat postarea in asa fel incat fiecare pasionat, indiferent de experienta sa in algoritmica, sa gaseasca o idee deosebita si o cerinta care sa il intrige. Mai mult: cu cat veti dori sa studiati mai adanc subiectul propus, cu atat mai multe lucruri frumoase veti descoperi. Pentru a nu va incurca din a gasi singuri tainele acestea, am ascuns prin linkuri orice cuvinte si referinte la detaliile tehnice ale solutiilor.

Enunturile

Dandu-se un sir de N numere intregi, numim operatie schimbarea uneia (la alegerea noastra care anume) dintre valorile sirului, fie ea x, in x - 1 sau x + 1 (la alegerea noastra).

Pe scurt, problema Ordonare cere gasirea numarului minim de operatii pentru a transforma sirul dat intr-unul care are toate elementele distincte.
Problema Nave, spoiler, cere ceva asemanator: dandu-se si un numar pozitiv K ≤ N, gasiti numarul minim de operatii pentru a transforma un sir dat intr-unul care are cel putin K elemente distincte. Adica numarul de valori care apar cel putin o data in sirul obtinut este cel putin K. Daca veti citi enuntul, totusi, veti vedea ca pare mai complicat decat ce spun aici, deoarece sirul din input e de perechi de numere si operatiile sunt 2-dimensionale. Incercati sa demonstrati ca simplificarea pe care am facut-o este justificata. Cand va poticniti, aruncati un ochi la hint.

Pentru restul discutiei, vom presupune ca sirul este gata citit si gata sortat (putem sorta inputul fie cu std::sort, fie, de dragul complexitatii, dar intinand simplitatea implementarii, cu radix sort), si vom analiza solutiile plecand din acest punct.

Intrepatrunderea Cerintelor

Ce nu am mentionat inca este marimea valorilor din sir. In problema Ordonare, ele sunt, in modul, mai mici ca 109. Dincolo, desi in enunt scrie 104, voi creste dificultatea problemei si voi spune ca sunt restrictionate sa fie maxim 2N. Practic, problema Ordonare pare mai complicata deoarece valorile pot fi mai mari.

Dintr-o alta perspectiva - mai exact, ignorand faptul ca limitele pentru valori sunt diferite - Ordonare este o subproblema a cerintei de la Nave: daca facem un subtask al problemei Nave in care garantam K = N, obtinem exact enuntul de la Ordonare.

Reducerea

Acum vom face o transformare a problemei Ordonare in asa fel incat sa devina cu totul o subproblema a noului enunt de la Nave. Tot ce ne trebuie este un algoritm (daca se poate, liniar, ca sa fim siguri ca am facut reducerea fara sa afectam in vreun fel complexitatea finala) care sa rezolve urmatoarea problema:

Se da un sir de N numere intregi cu valori oricat de mari. Sa se construiasca un sir de N numere cu valori intre 0 si 2N care sa fie echivalent cu primul, din punct de vedere al cerintei problemei Ordonare.

Ce ne dorim este un fel de normalizare, care sa fie justificata in contextul cerintei noastre. Spre exemplu, sirul 5 38 38 38 40 40 40 43 43 43 se poate normaliza la 0 15 15 15 17 17 17 20 20 20, intrucat distantele relative dintre valori s-au pastrat, mai putin in cazul 5 - 38, care a devenit 0 - 15, doar ca aceasta schimbare nu poate afecta rezolvarea problemei Ordonare: orice operatii am face pe valorile ≥ 38 (respectiv 15) intr-o solutie optima, nu se vor putea apropia de valoarea 5 (respectiv 0) (care e clar ca in solutia optima nu va suferi vreo modificare).

Va invit sa rezolvati si sa implementati problema aceasta. As zice ca e excelenta pentru un interviu de algoritmica si programare - aceasta afirmatie nu mi-ar fi trecut prin cap acum un an, dar asa e cand cresti :-) Va puteti ghida dupa aceasta descriere a solutiei cand va mai poticniti.

Cateva solutii posibile

Dupa cum puteti intui din subtaskurile problemelor, exista multe solutii, de diverse complexitati, care le rezolva. Puteti vedea, in aceste linkuri, editorialele de la problema Nave Planare, respectiv Interdimensionale, precum si de la Ordonare. Cu toate acestea, discutia care urmeaza nu se foloseste decat intr-o mica masura de aceste descrieri.

Ordonare: O(N), fara reducere

Solutia oficiala (care nu face reducerea de care am vorbit mai devreme) are complexitatea O(N logN). Cu toate acestea, particularitile problemei fac in asa fel incat sa pastram operatiile dar sa schimbam structura de date si sa obtinem complexitate liniara!

Am pregatit un hint care va deslusi care este structura aceasta de date. Incercati sa va prindeti cum se poate folosi. Am scris si un scurt articol care descrie noua solutie.

Puteti gasi aici o implementare usoara a ideii. Problema e ca are comportament patrati pe anumite teste. Sursa se poate modifica usor, asa cum puteti vedea in aceasta poza la un text-compare cu implementarea corecta, pe care o puteti gasi aici.

Nave: O(N logN), raspunde pentru toate valorile lui K

freak93Adrian Budau freak93 a gasit un algoritm eficient care gaseste raspunsul pentru K = 1, apoi adapteaza structura pentru K = 2, si tot asa, pana ce determina raspunsul pentru toate valorile lui K, pana la K = N. Va recomand sa va ganditi cum se poate obtine o solutie atat de indestulatoare, dar, pentru moment, va pun linkuri doar la o sursa in Rust si la cateva hinturi: 1, 2, 3, 4.

Pana acum deja am avea cele mai bune solutii la care puteam spera la ambele probleme, dar sunt foarte diferite intre ele. Exista, totusi, un algoritm, care se poate folosi de faptul ca problemele sunt asa de asemanatoare, si, dupa ce face reducerea problemei Ordonare la un subtask al problemei Nave, obtine:

O(N logN) la Nave & adaptabila sa obtina O(N) la Ordonare

Punctul culminant al postarii - si motivul principal pentru care ea exista - este solutia la Nave a lui retrogradLucian Bicsi retrograd. Tin sa mentionez ca este foarte diferita de toate celelalte.

Mai intai, vom face o transformare a sirului dat, intr-o reprezentare echivalenta, si anume un sir de 2N frecvente, input[i] = numarul de valori egale cu i din sirul dat.

Pentru a va ghida spre patrunderea ei, am pregatit o serie de hinturi (1, 2, 3, 4, 5, 6), un mic articol care merge mana in mana cu indiciile, precum si doua surse foarte asemanatoare, bine comentate si codate cat mai clar. Prima mi se pare mai intuitiva, iar a doua (recomand text-compare.com) urmeaza ceva mai indeaproape implementarea originara a lui Lucian.

Odata ce intelegeti solutia aceasta, puteti rezolva (si o puteti privi ca pe o tema) si problema Ordonare, doar ca in timp liniar (reminder: dupa ce faceti reducerea!). In caz ca nu-i dati de cap, iata un indiciu. Avantajul aici e ca multe detalii la care trebuia sa aveti grija la Nave nu mai conteaza, deci sursa e mai lejer de scris.

Va recomand sa si implementati aceste idei. Nu numai ca doar asa va puteti asigura ca ati inteles intru totul fenomenul (si va spun asta din proprie experienta), dar este o provocare fascinanta sa duci aceste surse la capat, adica la 100 de puncte.

 Comentarii (0)

Categorii:
Vezi pagina: 1 23456... 3738394041 (407 rezultate)