Avem si scoreboard live

http://scoreboard.ioinformatics.org/Ranking.html

O invitatie din partea Japoniei la un concurs on-line ( dupa modelul IOI )

JOI Open Contest 2015 is an IOI-like open competition for students at
schools for secondary education. The main purpose of this contest is
to give Japanese delegations and candidates of delegations an opportunity
for training and practice. But the contest itself is open to everybody.
Everybody is welcome to attend JOI Open Contest 2015!

This year, the contest will be held on 14 June, 2015.
The duration of the contest is 5 hours. The same contests will be held
twice (Round 1 and Round 2). Contestants can participate in one of
Round 1 or Round 2 according to their time zone. After Round 2 finishes,
we will open the judging server for one day. Interested contestants can
improve and resubmit their solutions by themselves.

After the contest finishes, we will fix the standings.
No prizes will be given to the contestants.


Contest website: http://cms.ioi-jp.org/open-2015/index.html
Contest duration: 5 hours
The number of tasks : 3 tasks
Language : English, Japanese
Programming Language : You can use C/C++/C++11.
  We have not yet determined whether we will support Pascal or Java
  this year. Details will be announced on the contest website.

Date & Time :
Round 1
  Sunday, June 14, 2015
  13:00-18:00 +0900 (JST)
  04:00-09:00 (UTC/GMT)
Round 2 (tasks for Round 1 and Round 2 are the same)
  Sunday, June 14, 2015
  19:00-24:00 +0900 (JST)
  10:00-15:00 (UTC/GMT)
Judging Server is open until
  Monday, June 15, 2015
  23:00 +0900 (JST)
  14:00 (UTC/GMT)

======
Executive director of the Japanese Committee for the IOI
Seiichi Tani

Chairperson of the Scientific Committee of JCIOI
Tetsushi Ito

Va transmit mesajul primit de la Kresimir Malnar - Project Manager COCI - in legatura cu concursul de selectie al echipei IOI - Croatia.


As part of the COCI series, we are hosting an Internet online contest with problems from the Croatian Olympiad in Informatics 2015.
The contest is primarily intended for high school contestants,but is open to all interested!

This contest is used in Croatia to select members of the IOI team. There will be 3-5 tasks and the contest will be 5 hours long. It will be held on Saturday, March 28, starting at 14:00 (GMT/UTC). Check out your local times at http://hsin.hr/coci/next_contest.html. You may use Python, Pascal, C, C++ or Java as your programming language of choice.

The two relevant websites are:
http://hsin.hr/coci/ - information about the contest
http://evaluator.hsin.hr/ - contest system
We hope that you will join us or encourage your students to do so!

This is the ninth year in a row that we are hosting the COCI series. You can find tasks (statements, test data and solutions) from the previous eight years at http://hsin.hr/coci/. That is over 350 original tasks for students to practice on!

Succes participantilor !!!

Exact ce zice Marius asta s-a intamplat. Daca nu a fost bifat compilatorul in Code :: Blocks  atunci pe calculatorul tau nu a aparut eroare la compilare. Evaluatorul si-a luat compilatorul corect si acesta nu a mai recunoscut functia itoa().

citez:

Portability
This function is not defined in ANSI-C and is not part of C++, but is supported by some compilers.

Intradevar - cred ca ar trebui sa sesizezi Comisiei judetene ce s-a intamplat si e probabil sa iti reevalueze sursa.

[0]

Denis are dreptate pana la un punct si anume ca te intereseaza doar ultimele 9 cifre si inceputul de idee.

Cel mai usor e sa folosesti metoda backtracking prin care sa depistezi cifra cu cifra numerele de 1, 2 , 3, ..., 9 cifre care ridicate la patrat se termina in 1, 21, 321, ..., 987654321. Iti dau mai jos o posibila implementare a unui astfel de back.

Cod:

void bk(int poz) 
{
    int i,j,c;
    if(poz==9)
    {
        for(i=8;i>=0;i--)
            g<<sol[i];
        g<<'\n';
        return;
    }
    for(c=0;c<=9;c++)
    {
        sol[poz]=c;
        for(i=0;i<=poz;i++)ver[i]=0;
        for(i=0;i<=poz;i++)for(j=0;j<=poz;j++)ver[i+j]+=sol[i]*sol[j];
        for(i=0;i<=poz;i++){ver[i+1]+=ver[i]/10;ver[i]%=10;}
        for(i=0;i<=poz;i++)if(ver[i]-i-1)break;
        if(i==poz+1)bk(poz+1);
    }
}

Am rulat si se pare ca raspunsul la intrebarea ta e foarte simplu. In primul rand trebuie sa ai n > = 9. In al doilea rand ultimele 9 cifre nu pot fi decat in una dintre urmatoarele 8 variante:

Cod:

111111111
611111111
380642361
880642361
119357639
619357639
388888889
888888889

Daca nu gresesc atunci raspunsul este :
0 daca n<9
8 daca n=9
8*10^n-9 daca n>9 ( 8 moduri de a forma sufixul de 9 cifre a numarului cautat si 10^n-9 moduri de a pune cele cel mult n-9 cifre din prefixul numarului.

In luna ianuarie va avea loc International Zhautykov Olympiad in Mathematics, Physics and Computer Science

Concursul are pentru Computer Science o varianta neoficiala online.

Link-uri

Site-ul oficial al concursului : http://izho.kz/
Pagina pentru inregistrare la concursul online : http://goo.gl/jpkHo9

Va urez tuturor un an nou fericit si mult succes !!!

La problema ciocolata va fi prezentata demonstratia completa la prima tabara de Lot.

Voi scrie aici in linii mari despre ce e vorba.

Inductia dupa numarul de mutari se bazeaza pe descompunerea jocului in doua jocuri - unul utilizeaza cate un baton din cele care au un numar impar de aparitii si un joc formar din restul batoanelor ( este posibil sa nu avem primul joc - daca toate tipurile apar in numar par , este posibil sa nu avem al doilea joc - daca avem cel mult un baton din fiecare tip). Am sa explic aici doar cazul in care un jucator are strategie de castig. Daca sunt la mutare aplic mutarea care ma duce la configuratia castigatoare pe primul joc. Atunci trec intr-o configuratie castigatoare pentru mine , cu adversarul la mutare si am cu o mutare mai putin ( deci prin inductie voi castiga la diferenta anticipata). Daca nu sunt la mutare astept mutarea adversarului. Daca adversarul muta cu un baton care apare cel putin de doua ori imit mutarea adversarului si ajung la aceeasi configuratie de paritati cu cea initiala si s-au efectuat cu 2 mutari mai putin deci pot sa aplic inductia. Daca se muta intr-un baton care apare o singura data atunci consider ca s-a jucat in jocul 1 si aplic mutarea castigatoare cu care continua acel joc( implicit se ajunge pe o configuratie castigatoare dar la doua mutari mai putin - deci inductie) . Exista aici si un caz particular si anume cand doar numarul de batoane de 2 e impar ( sau altfel spus jocul 1 se termina dintr-o singura mutare) dar aici ajung ca adversarul a mancat deja 2 si se intra pe configuratia cu toate resturile 0 care duce la remiza.
Partea mai delicata la aceasta inductie este initializarea acesteia. Mai precis - ar trebui sa ma asigur ca observatia este valabila pana la un numar dat de mutari - dar acest numar initial sa ma asigure ca am tratat toate configuratiile posibile si nu risc sa ajung mai tarziu la o configuratie care nu a mai fost luata in calcul. Acest numar minim de mutari care asigura aparitia tuturor configuratiilor intr-un numar mai mic de mutari este 1+2+...+15 si se obtine pentru cunfiguratia in care avem exact un baton de fiecare tip. Daca cineva isi doreste sa demonstreze riguros acest pas al inductiei atunci ruleaza un brut care determina deznodamantul jocului pana la acel numar de mutari.
Nu a fost scrisa in descrirea solutiei demonstratia completa ci doar ideea de rezolvare. Mai sunt si alte observatii care ar duce la intelegerea completa a demonstratie dar sa le prezint pe toate ar insema sa mai scriu inca pe atat in acest post.

O solutie tot in O(N) ar fi sa se inceapa o parcurgere BF plecand din frunze cu scaderea gradului odata cu eliminarea unei muchii si introducerea in coada a unui nod numai cand ajunge frunza (ideea e oarecum similara cu cea de la sortarea topologica). In felul asta solutia este suma distantelor pana la ultimele doua noduri parcurse ( distanta este calculata bineinteles din nod pana la cea mai indepartata frunza ). O implementare pe aceasta idee :
http://www.infoarena.ro/job_detail/1106081?action=view-source

Eu cred ca Mugurel are un pic dreptate in sensul ca solutia e putin exprimata neclar. Sunt sigur ca problema nu e cu solutia in sine ci cu descrierea acesteia. Pe de alta parte eu nu prea inteleg de ce e necesar sa se verifice 3 laturi.

Practic eu pot sa generez toti vectorii cu extremitati in punctele date si sa le stabilesc originea, directia, sensul si lungimea fara sa tin cont de extremitate ( daca am doua puncte A si B vectorul AB e definit de origine - punctul A si coordonate X = XB-XA si Y=YB-YA ) Dupa ce sortez acesti vectori dupa X si apoi dupa Y ei se grupeaza pe vectori egali in sensul geometriei vectoriale ( aceeasi directie lungime si sens i.e. aceleasi coordonate )
Daca doi vectori sunt pe o aceeasi grupa de vectori egali insemana ca din originile lor pleaca doi vectori egali spre alte puncte din configuratie  (un vector e translatatul celuilalt) . Memorez aparitia unei astfel de situatii folosind seturi pentru fiecare punct si punand originile una in setul celeilalte. Daca la un moment dat folosind o alta grupa de vectori egali ar urma sa inserez a doua oara un elemet intr-un set asta ar spune ca apare pentru acea pereche de puncte ( ca origine) o a doua pereche de vectori egali care impreuna cu prima imi determina perechea de triunghiuri care confirma plagiatul. In consecinta pentru determinarea triunghiului nu folosesc deloc a treia latura ci de fapt (in mod indirect ) unghiul dintre primele doua (sau altfel spus directiile primelor doua)

L.E. Am citit eu neatent solutia oficiala. Descrierea este super OK iar ceea ce am scris eu mai sus e cu totul altceva. ( E corect dar nu are nicio legatura cu solutia oficiala)

Pana una alta problema asta are un vot de la mine pe sondajul cu problema preferata la runda 2  

Am o intrebare pentru cei care sunt acum la Sarajevo. Pagina de scoruri live arata ca Voro si Mihai ar fi plasati pe medalii de aur. Dupa socoteala mea ar trebui sa fie aur pana la locul 5 inclusiv  si argint pana la locul 14 inclusiv . Baietii nostri sunt pe locurile 5-8. Ce medalii ar obtine daca ar ramane asa pana la sfarsit ? Aur sau argint?

Rares Darius Buhai - Medalia de aur 
Vlad Alexandru Gavrila - Medalia de aur 
Andrei Heidelbacher - Medalia de argint 
Mihai Popa - Medalia de bronz 

Felicitari baieti si la mai mare 

Da. Confirm de a spus Wef. Sedinta care a decis ca rezultatele primei zile sa ramana neschimbate s-a terminat recent.
Deci scorurile de aici live.ioi2013.org sunt cele corecte pentru prima zi. Sa le tinem pumnii baietilor pentru a doua zi.

Este posibil ca numarul de invitati sa fie 0? Mie mi se pare ca daca in teste nu apare nicio conditie x y 0 atunci o solutie banala ar fi sa nu fie invitat nimeni la petrecere . Am dreptate?

@Cristian Avramescu

Banuiesc ca ai aceeasi greseala pe care am avut-o si eu. Lumanarile de inaltime 0 care trebuie ignorate ( si eu tot 60 de puncte am avut)

Solutia mea e un fel de greedy. Sortez lumanarile si adun in ordine descrescatoare 0,1,2,...,m-1. Apoi sortez iar si pun lumanarile in ordine descrescatoare. Solutia e prima pozitie unde inaltimea modificata este strict mai mica dacat indicele. Din pacate nu am sesizat ca lumanarile pot avea si inaltime nula si acelea nici nu trebuiau luare in calcul. In cele din urma am luat 7 teste dar cu gruparea la teste am  mai pierdut un test.

L.E. Solutia e gresita. Intradevar pe exemplul de mai jos dat de Alex Velea nu functioneaza.

La rugamintea unuia dintre moderatori incerc sa iti dau eu un raspuns la problemele ridicate. Raspunsul meu nu este unul oficial dar din cate stiu eu Inspectoratul Scolar Judetean de care apartine un elev calificat la orice Olimpiada Nationala are obligatia sa asigure insotirea elevului/elevilor calificati. In mod normal profesorul insotitor ar trebui sa fie un profesor de specialitate. Probabil ca in situatii exceptionale cand nu exista un profesor de specialitate disponibil se poate apela la un profesor de alta specialitate (aici nu pot sa iti dau un raspuns sigur dar cred ca este posibil ). La intrebarea daca parintele ar fi o optiune iarasi nu pot sa iti raspund cu certitudine. Imi amintesc ca am intalnit astfel de situatii dar parintele era in acelasi timp si cadru didactic. Olimpiada de TIC ( cum o numesti tu ) - faza judeteana este pe 23 martie. Eu cred ca ar fi mai bine sa ai rabdare pana luni cand - cred eu - vei primi un raspuns din parte Inspectoratului. Problema nu este una a organizatorilor ci decizia apartine Inspectoratului Scolar Judetean.

prof. Adrian Panaete

Ceea ce este intr-adevar o eroare relativa  de exemplu cand raspuns = 0.0005001 si rezultat = 0.0005. Calculul imi da o eroare relativa de cam 0.0002 pentru o eroare reala de 0.0000001.  Inteleg care ar fi logica unei astfel de aprecieri a rezultatului dar pare destul de riscanta si greu de controlat. Evident ca la multe probleme merge dar cred ca eroarea de 10^-9 este cam drastica.

[121]

Nu ai inteles ce am vrut sa spun. Ma refer la faptul ca in mod obisnuit noi evaluam la cate zecimale dupa virgula se potrivesc rezultatele. Normal ar fi sa apreciem precizia unui rezultat dupa numarul de cifre semnificative fara sa conteze ca diferenta apare la cifra zecimilor, sutimilor, unitatilor, zecilor sau chiar sutelor de mii. Examplu:

121315.12
121415.23

se potrivesc pe 3 cifre

0.00114
0.00125

se potrivesc pe o cifra.

Eu nu pun in discutie acolo problema particulara ci pur si simplu pun in dezbatere o filosofie de evaluare. Fara ca asta sa spuna ca am si dreptate

L.E. Nici eu nu intelesesem ce vrei sa spui cu merge pe long double. Acum am inteles.

Ca fapt divers. Ideea deschiderii acestui topic mi-a venit imediat dupa rezolvarea problemei Aria din Arhiva educationala la care cu doua solutii corecte dar diferite putin de cea oficiala am obtinut 70 de puncte cu probleme la precizie pe ultimele 3 teste.

[1. Ar trebui sa eliminam complet problemele in care se folosesc tipuri reale.]

As vrea sa redeschid o discutie veche lagata de problemele de concurs in care fisierul de iesire contine numere cu zecimale.
In multe situatii concurentii pierd puncte pretioase datorita erorilor la o anumita zecimala in afisarea rezultatului si asta in concursuri cu miza este frustrant.
Am urmarit cateva topicuri pe forum in care este dezbatuta tema asta si parerea mea este ca tema merita o dezbatere ampla in care cat mai multi sa isi exprime opinia.
Voi incepe aceasta dezbatere exprimand cateva puncte de vedere pe care nici nu mi le asum si nici nu le consider perfecte.
Iata cateva exemple:

1. Ar trebui sa eliminam complet problemele in care se folosesc tipuri reale.

Opinia mea e ca asta ar fi politica strutului de a-si baga capul in nisip. S-ar pierde in acest caz probleme foarte interesante de geometrie sau de probabilitati.

2. Ar trebui sa lasam libertatea concurentului sa afiseze rezultatul cu oricate zecimale si sa folosim o valoare rezonabila cu care sa testam eroarea fata de solutia din fisierul ok.

Dar daca autorul in constructia fisierelor ok foloseste o anumita aproximare iar rezolvitorul foloseste o mai mare acuratete in calcule obtinand un rezultat chiar mai aproape de cel corect si care nu corespunde cu cel din ok? Asta se poate intampla cand de exemplu:

3. Concurentul muta virgula zecimala spre dreapta un numar rezonabil de pozitii si apoi lucreaza cu numere de tip intreg

Operatia este fireasca dar e posibil ca numarul de cifre cu care se lucreaza sa nu incapa pe nici un tip intreg.
Sau cand:

4. Concurentul foloseste o solutie alternativa care duce tot la rezultatul corect dar manipuleaza prin alte calcule numerele cu zecimale


Pentru ca nu vreau sa inchid multe dintre directiile in care s-ar exprima opinii in aceasta ( sper ) discutie am sa ma opresc la o ultima opinie pe care o apreciez ca fiind una dintre solutiile de compromis care ar putea conduce la o imbunatatire a evaluarii in problemele de acest tip.

Plec de la ideea ca a verifica precizia rezultatului in numar de zecimale nu este prea buna. Motivul ar putea fi exprimat plastic cam asa.

Ce precizie e mai buna: 0.01 kilometri sau 10 milimetri ?

5. Ar trebui sa comparam rezultatul din out si din ok privite ca stringuri si sa alegem in mod adecvat cate caractere din out / ok ar trebui sa coincida

Un exemplu:

out 1.2345 ok 1.2344 => eroare de 0.0001

out 12345678.9 ok 12345678.8 => eroare de 0.1

Totusi mie mi se pare ca in al doilea caz suntem mai aproape de raspunsul corect dacat in primul caz.

Ce parere aveti?

Aici puteţi discuta despre problema Aria.

Felicitari. Excelenta organizare. Un '+' mare pentru timpul scurt in care au aparut rezultatele. Astept plin de curiozitate solutiile oficiale in special la Flux2 si Unicat. Sunt sigur ca vor fi idei din care vom avea cu totii ceva de invatat.


L.E. O(1) timp de executie la afisarea rezultatelor 

Tot cu trie dar in O(N^2). Probabil prea mult

Eu am dat o solutie O( N log N + M ). Sortez indicii dupa valori in ordine crescatoare si la valori egale iau mai in fata indicele mai mare. Procesez indicii in ordinea data de sortare folosind o lista dublu-inlantuita cu indicii initiali si folosind doi vectori ( predecesor - succesor).
Imediat ce un indice este procesat este scos din lista. La momentul procesarii sunt sigur ca urmatoarele (cel mult) 5 pozitii cu valori  strict mai mari sunt exact urmatoarele (cel mult) 5 elemente din lista deoarece pozitiile cu valori strict mai mici sunt deja iesite din lista fiind deja procesate iar cele egale (daca exista) sunt situate mai la inceputul listei. 

& Dani: Da. M-am prins de greseala mai devreme. Iar plangerea mea cu gruparea testelor nu era chiar o plangere. Mai degraba incearca sa o iei ca pe o gluma. Imagineaza-ti ca la teste foarte bine alese cu sursele noaste se puteau lua si 0 puncte. Cat despre KMP si Z-algorithm exista similitudini si deosebiri. Am sa vad dupa ce intra problema in arhiva cum sta treaba pentru ca tot mai cred (fara sa fiu convins 100%) ca, dupa calculul functiei prefix se poate scoate partea a doua in timp liniar. Ar fi O(N^2) daca s-ar actualiza la pozitiile acelea de mai multe or. Eu cred ca se poate face actualizare o singura data la fiecare pozitie.  Cum,  inca nu stiu sigur,  dar am sa ma straduiesc si daca reusesc am sa prezint varianta de rezolvare.

L.E. Cred ca tocmai a dat Vlad Campeanu raspusul in postul de mai sus.