infoarena

Runda 9 (http://infoarena.ro/monthly-2012/runda-9) a concursului Monthly 2012 (http://infoarena.ro/monthly-2012) s-a încheiat. Felicitări primilor clasați (http://infoarena.ro/monthly-2012/runda-9/clasament)!

Premiul special oferit de catre firma IXIA (http://www.ixiacom.com) va merge la Heidelbacher Andrei (http://infoarena.ro/utilizator/a_h1926), deoarece a obtinut cel mai mare punctaj (305 puncte) dintre cei inscrisi la concurs! Felicitari!

Asteptam opiniile si eventualele sugestii ale voastre în legatura cu organizarea, subiectele propuse și orice probleme intampinate.

Mult succes în continuare!

Ce smecher arata Ciclonia :P

Felicitari pentru probleme. Ce avea testul 10 la traseu2?

Tari problemele.  :thumbup: Chiar daca mai usoare (lucru care nu ma deranjeaza) ca sa ia toata lumea cateva puncte, mi-au placut. La servici era banal, iar la traseu2 trebuia sa le sortezi si apoi sa vezi daca rezultatul este solutie.
Care era idea la problema cu permutarea?

,Andrei

Dragut setul de probleme si foarte bine calibrat(simpla,de implementare,medie, grea)
Felicitari lui maritim pentru intersort, una din cele mai smechere probleme de la monthly =D>

Fain set-ul. In special problema Intersort.

Mergea limita de timp putiiiin mai mare la Petrecere.

La intersort, idea de baza era ca atunci cand interschimbai doua elemente unul dintre ele sa fie 1. Pentru asta descompuneai permutarea in cicluri ( de lungime > 1 sau formate doar din elementul 1) si rezultatul era suma lungimilor ciclurilor + nr de cicluri - 2.
Exista cam un singur caz particular care mi-a scapat si mie in concurs.

Super runda. Problemele au fost bine alese. Felicitari echipei  :D

Frumoase problemele si echilibrat setul. Felicitari !  :ok:

Cum ati facut la petrecere ?

Iei in considerare doar graful format din relatiile de tip 0 si il imparti in componente conexe (deoarece trebuie sa iei componentele cu totul). Apoi construiesti un graf nou G2 in care fiecare nod va reprezenta o componenta conexa si pui muchii intre componentele care contin noduri care se afla in relatia 1. Colorezi graful (poti considera ca negru = alegi nodul, alb = cazul contrar) astfel incat nodurile adiacente au culoare diferita (tot timpul vei putea face asta datorita conditiilor din problema). Pentru fiecare componenta conexa din G2 vezi care dintre cele 2 variante de colorare contine mai multe noduri din graful initial si aduni la rezultat.
Am luat TLE pe ultimul test cu aceasta idee, dar cred ca e de la implementare.

Edit: E buna ideea.

Si eu am gandit problema la fel insa nu mi-am dat seama cum se face exact colorarea. Daca cineva poate sa detalieze ii raman recunoscator. Multumesc anticipat.   :D

LE : Am omis ceva "Paftenie mai stie ca daca 2 prieteni de-ai sai se afla in relatia de al doilea tip, trebuie neaparat sa il invite pe unul din ei altfel vor fi amandoi suparati.". Nu mai trebuie nici o explicatie.

Felicitari lui Lambru Andrei Cristian (http://infoarena.ro/utilizator/maritim) pentru problema, in primul rand!  =D>

Problemele bine alese, si diverse.
Putem contribui si noi la editorial?

Cand se da update la rating-uri?

Multumesc pentru aprecieri :) !

poate actualiza cineva ratingul? intre rundele 7 si 8 a trecut o luna fara update...

Nu vreau sa fiu rautacios, dar eu zic ca Andrei doar a copiat  problema (http://infoarena.ro/problema/costperm) asta schimband doar enuntul si titlul, neadaugand nici un alt element(doar timpul de executie diferit, daca ar conta cu ceva), in comparatie cu cel din arhiva educationala unde sunt prob propuse, bazate pe aceeasi idee, dar cu rezolvari total diferite.

E o diferenta uriasa intre cele 2 probleme. La problema Costperm nu puteai interschimba decat doua elemente vecine. Asta schimba foarte mult algoritmul.

Nu stii ce vorbesti.

In primul rand, problemele sunt diferite, prin enunt, dar mai ales prin rezolvare. Din cate tin minte, problema este de multa vreme pe grupul nostru de gmail(poate chiar inainte de FMI No stress), foarte bine exemplificata si explicata. Andrei merita din plin felicitarile pentru problema.

In al doilea rand, puteti fi siguri ca in momentul in care selectam problemele luam in calcul asemanarea cu alte probleme disponibile nu doar in arhiva Infoarena, ci si in arhivele altor online judge-uri populare. E destul de improbabil sa propunem involuntar o problema cunoscuta de useri, dar necunoscuta de noi. Pentru cazurile rare in care acest lucru se intampla, ne cerem scuze. Cazul de fata, repet, nu este unul dintre ele.

Eu unul sunt impotriva problemelor copiate (in concursuri serioase) si cred ca ele ar trebui intr-adevar deconspirate. Cu toate acestea, va rog sa fiti mult mai prudenti in momentul in care faceti asemenea afirmatii, fiindca apar in mod inevitabil situatii controversate care nu prea inveselesc ziua nimanui  :)

Ar fi bine să și rezolvi problemele menționate înainte să tragi concluzii.

Fara rating :-'

Ma ofer sa scriu editorialul pentru runda 9, daca sunteti interesati puteti da PM. Poate in felul asta mai imi creste si mie karma, vad ca imi scade in fiecare zi cu cate 2-3, chiar fara sa postez nimic.  :-'

L.E. exact despre ce vorbeam. Aici e un PM pe care l-am primit dupa postul asta.