Concursurile USACO

[VladS]

Am doua intrebari in legatura cu, concursurile USACO.
1. De unde putem lua testele la Concursul ddin Decembrie, Silver Division?
2. Daca nu am concurat la concursul din noiembrie si vreau sa concurez i Ianuarie in ce divizie voi fi repartizat?

Multumesc anticipat.

[•diac_paul]

Daca ai cont la usaco, poti chiar sa-ti evaluezi problemele din concursul precedent (adica cel din decembrie) la adresa http://ace.delos.com/contestgate, dupa ce te intrii pe contul tau. Poti trimite surse pentru toate problemele, la toate grupele (gold, silver si bronze).
Tot acolo poti citi si regulamentul, de exemplu cum trebuie sa arate o sursa pentu a fi acceptata de evaluator:
La inceputul sursei trebuie specificat numele problemei si limbajul de programare:
/*
PROG: nume_problema
LANG: C
*/
Pentru C sau java inlocuieste C cu C++/JAVA iar pentru pascal:
{
PROG nume_problema
LANG: PASCAL
}
Daca programul tau nu merge pe un test ti se va afisa si testul (complet, daca acesta nu depaseste o anumita limita), alaturi de raspunsul corect si raspunsul tau, daca acesta exista .
Daca n-ai mai participat la concurs, poti participa doar la BRONZE, deoarece pentru SILVER si GOLD e nevoie de invitatie. Invitatiile se obtin  pentru rezultatele la runda precedenta, deci daca obtii un punctaj destul de mare la BRONZE in ianuarie, luna viitoare participi la SILVER si de-acolo, daca iar obtii punctaj destul de mare, la GOLD. (asta abia in a treia luna).
Daca vrei sa te pregatesti, poti trimite surse la problemele de la concursul din decembrie (la ace.delos.com/contestgate), sau la setul lor de probleme, o pregatire foate folositoare, deoarece contine atat probleme cat si teorie: ace.delos.com/usacogate.
Mult succes la concurs  

[•silviug]

1. De unde putem lua testele la Concursul ddin Decembrie, Silver Division?

Am sa pun eu o arhiva care contine enunturile si testele. Cu putin noroc va aparea si un articol cu solutii. Ramaneti conectati pe frecventa !

2. Daca nu am concurat la concursul din noiembrie si vreau sa concurez i Ianuarie in ce divizie voi fi repartizat?

Cu siguranta, dupa cum a spus Paul, vei fi repartizat la BRONZE division. Cu un rezultat foarte bun (>899 de puncte) il poti convinge pe Rob Kolstad sa te mute la divizia superioara in timpul concursului pentru a putea concura si acolo. Asa am facut eu la concursul precedent: eram calificat la SILVER (in urma primului concurs, spre rusinea mea ) si am facut maxim la divizia asta iar Rob m-a mutat la GOLD si am putut concura si acolo. Deci solutii sunt, sa fii tu bun acuma !

[•silviug]

Am pus subiectele diviziei Silver a concursului Usaco, decembrie 2004. Se gasesc in sectiunea DOWNLOAD. Daca e cazul, voi scrie si un articol cu solutiile dar vreau sa aud solicitarile voastre, sa stiu ca nu muncesc in zadar .

[VladS]

In legatura cu articolul, nu cred ca e neaparat  nevoie de un articol. Dar poti sa scrii algoritmul(Kruskal etc.) care trebuie folosit si sa il lasi ca tema de studiu. Intre timp am gasit de unde pot download-a ace.delos.com/DEC04 parca.

[•Dust]

Solutiile la USACO sunt foarte binevenite!!! Dar ar fi bine sa existe si niste solutii, ma refer la problema SKIAREA.... De ce raspunsul este min(top,bottom)?Vreo demonstratie??? Fara intuitie?

[•silviug]

Solutiile la USACO sunt foarte binevenite!!!  Dar ar fi bine sa existe si niste solutii, ma refer la problema SKIAREA.... De ce raspunsul este min(top,bottom)?Vreo demonstratie??? Fara intuitie?

In primul rand nu e min(top, bottom) este max(top, bottom).
Uite o demostratie relativ scurta, dupa cateva notatii:
- P = numarul de noduri din multimea top (noduri IN care nu intra nici o muchie)
- Q = numarul de noduri din multimea bottom (noduri DIN care nu iese nici o muchie)
- S = solutia problemei

Avem S >= max(P, Q) pentru ca trebuie sa construim un set de muchii astfel incat fiecare nod din top si din bottom sa aiba cel putin o muchie la care este incident (daca nu are graful nu este tare-conex).

Se arata ca exista un set de muchii cu S = max(P, Q) care face graful nostru tare conex si deci S <= max(P, Q). Din cele doua inegalitati (S <= max(P, Q) si S >= max(P, Q)) rezulta ca S = max(P, Q).
Pentru a construi un astfel de set de muchii se gaseste cuplajul maxim dintre multimea top si multimea bottom (intre doua noduri A si B din top respectiv bottom exista muchie daca avem drum in graf de la A la B). Cuplajul maxim va fi T = min(P, Q) datorita constructiei grafului si acum luam cele T perechi si facem un ciclu cu ele (vom avea nevoie de T muchii - punem perechile una dupa alta si le conectam). Pentru restul nodurilor necuplate este suficient sa le conectam cu ciclu nou creat. Asta e tot, simplu nu ?

Pentru exemplificare:
top = {1, 2, 3}
bottom = {4, 5}
muchii = {(1, 4), (2, 4), (3, 5)}

se obtine cuplajul = { (1, 4), (3, 5) }
se vor construi muchiile (4, 3) si (5, 1) pentru a obtine ciclul
pentru nodul necuplat 2 se construieste muchia (4, 2) (sau oricare alta)

Numa bine,

Silviu

[•Dust]

Multumesc, dar am o intrebare....
Fie multimea de sus A1,A2,.....An, si cea de jos B1,B2,....,Bn
Unim A1 cu B1,B2,...B(n-1) si fiecare din A2,A3,....An cu Bn.
In acest graf cuplajul maxim ar fi 2, si nu N, deci demonstratia nu prea merge.
Poate eu nu inteleg ceva.....
Nu stiu daca pentru acest exemplu ar exista un tabel de inaltimi corespunzator, dar oricum, demontratia nu e corecta....
Sunt de acord ca pentru configuratia pe care am dat-o exista o cuplare cu doar n muchii, de exemplu B(i) cu A(i+1) A(n) = A(n+1) , dar ea nu respecta demonstratia!!!!!

[•silviug]

Dude.. nu se poate gasi graf cum ai spus tu.. graful nostru e graf planar.. si tind sa cred ca exista un cuplaj maxim intotdeauna.. [de altfel am luat toate testele]

[•Dust]

55151552151511
55555552111111
15555512511115
55555552111111
15555512511115
55555552111111
55151552151511

Uite un graf pe care demonstratia ta nu merge. Cred ca idea de constructie e clara. Avem 2 regiuni diferite. Una e o bucata mare de inaltime 5, unita cu multe bucati de marime 1, si alta regiune este mare de inaltime 1, unita cu bucati de marime 5..... Cred ca regiunea de 2 nu prea influenteaza cuplajul....
Faptul ca ai luat toate testele nu e o demonstratie,
DUDE  

[•silviug]

Okay precedentul post al meu nu prea a fost gandit.. (ma grabeam or something) dar asta nu scuza cu nimic remarcile tale tendentioase. Oricum, ca sa-ti demostrez ca "daca iei toate testele inseamna ca solutia e corecta" (si daca nu e, I don't give a shit! Am luat punctele ) hai sa corectez demostratia initiala:

Deci tot asa.. avem grafu bipartit, avem cuplajul maxim (care multumita exemplului tau vedem ca nu e neaparat min(P, Q)). Fie C = numarul de perechi din cuplaj. Cu C muchii facem o componenta tare conexa din cuplaj (conectandu-le cum am spus in celalalt post). Nodurile care raman inafara cuplajului au o muchie catre(sau de la) componenta conexa nou formata. Le luam cate doua (unu din multimea A si unu din multimea B) si le conectam printr-o muchie pe care o orientam convenabil. Evident se poate intampla ca sa nu le putem conecta pe toate asa (sa mai ramana noduri intr-o multime) si pe astea le conectam individual la componenta conexa.

Uite si un exemplu care sa te convinga (cum l-ai construit tu pe cel initial de fapt):

A = {1, 2, 3, 4, 5}
B = {5, 6, 7}
Muchii:
1 5
2 5
3 5
4 6
4 7

Cuplaj maxim (unul dintre ele)
1 5
4 6

Facem componenta tare conexa initiala conectand:
5 -> 4
6 -> 1

Facem perechi din nodurile care au mai ramas (2, 3 si 7):
7 -> 2

A mai ramas nodul 3 si adaugam muchia:
6 -> 2                

Sper ca acum e clar

Numa bine..

PS: All in all.. Felicitari pentru contraexemplu

[•sarabogdan]

Cine imi zice si mie cum se rezolva prima problema de la silver  

P.S.  cerinta pe scurt : se da un numar n  <= 1 000 000 cate modalitati de al descompune in puteri ale lui 2 exista ?

[•silviug]

Tot eu

Problema face parte din categoria dinamici clasice si este cunoscuta sub numele de "problema monezilor". In forma generala problema suna asa: "Avand un set de monezi dat in cate moduri distincte se poate plati suma S?". In cazul nostru monezile sunt speciale fiind puteri ale lui 2 (acest lucru ne va ajuta mai tarziu).

Okay, am spus ca rezolvarea este prin programarea dinamica. Avem astfel Count[j] = numarul de moduri in care poate fi platita suma j folosind puterile 2^K, 2^(K - 1), .., 2^(K - i) unde K = puterea maxima astfel incat 2^K <= N (K = [logN]). Avem recurenta urmatoare:

Count[i + 1][j] = Count[j] + Count[i + 1][j - 2^(K - i - 1)],
                          daca j >= 2^(K - i - 1)

sau

Count[i + 1][j] = Count[j]
                          daca j < 2^(K - i - 1)

Recurenta o obtinem analizand ce se intampla daca pentru suma j alegem sa platim utilizand moneda i + 1 sau nu. Astfel daca nu o folosim avem Count[j] modalitati sa platim suma j iar daca alegem sa o folosim atunci avem Count[i + 1][j - 2^(K - i - 1)] modalitati (puneti mana pe un pix, luati un exemplu si vedeti cum se traduce recurenta asta lucrand cu o matrice si va veti lumina ).

Okay, acum vine intrebarea "de ce am ales sa parcurg setul de monede descrescator si nu crescator" ? Raspunsul este simplu: pentru ca la pasul i va fi nevoie sa va numarul de moduri de a scrie sumele ce sunt multipli de 2^(K - i) si asta pentru ca orice suma pe care o pot plati este divizibila cu 2^(K - i). Astfel complexitatea se va reduce simtitor si (calculata rapid de mine) e O(N) si nu O(N * nr_monede) = O(N * log N).

Sper ca nu te-am speriat facand dintr-o chestia mult prea simpla ceva prea complicat .

Cu bine,

Silviu

[•sarabogdan]

Multumesc pentru rezolvare , acum stiu de ce nam rezolvat-o.

O sa incerc si eu sa o implementez si sa fac pe foaie!

P.S : Solutia e in count[n][n] ?

[•silviug]

Solutia e in Count[K][N]. Si inca o observatie: sa te gandesti cum se reduce memoria la un singur vecotor de lungime N (pentru ca altfel iese din memorie).

[•rgrig]

Incerc si eu o explicatie de o natura un pic diferita, care urmeaza un pic felul in care am gasit eu rezolvarea (pe care n-am scris-o bine in cod, mai exact am uitat sa iau modulo 1e+9, adr asta e alta poveste).

Intai observam ca orice numar impar trebuie sa aiba un numar impar de termeni 1 si orice numar par trebuie sa aiba un numar par de termeni 1. De exemplu pentru a construi 7 putem avea in suma 1, 3, 5 sau 7 termeni de 1. Pentru a construi 8 putem avea in suma 0, 2, 4, 6 sau 8 termeni de 1. Diferenta care ramane dupa ce ei in considerare termenii de 1 este intotdeauna un numar par. De exemplu:

7 = 1 + 6
7 = 3x1 + 4
7 = 5x1 + 2
7 = 7x1

Mai ramane sa vedem in cate feluri poate fi scris numarul par folosind puterile lui 2 mai mari ca 1: 2, 4, 8, .... Dar asta e simplu: il impartim la 2 si repetam procedeul anterior. Si asa am gasit recurenta:

ways[0] = 1
ways[N] = \sum_{0<=2i<=N} ways

Daca scrii primele cateva valori o sa vezi ca e usor de observat ca:
  ways[2k+1] = ways[2k]

si in plus
  ways[2k+2] = ways[2k] + ways[k]

De aici iti poti da seama ca ai nevoie de un array doar de dimensiune 500001 si solutia (o posibila solutie) arata cam asa:

Cod:

N >>= 1;
ways[0] = 1;
for i = 1 to N do ways[i] = (ways[i-1] + ways[i>>1]) % 1000000000;
return ways[N];

[•rgrig]

Cu putina imaginatie solutia asta poate fi facuta sa mearga si cu un array de doar 125000, dar codul ar arata cam urat.

[andreit1]

Ar putea sa imi dea cineva o idee de rezolvare la problema cover de la Gold? Pe site scrie ca a fost cea mai simpla insa eu nu am nici o idee de un algoritm in timp neexponential.

[•silviug]

Voi face un articol cu solutiile de la usaco in zilele urmatoare. Pana atunci iti dau un hint: se rezolva cu cuplaj..

[•Cosmin]

Hai ca iti dau eu un hint mai serios:

  Fiecare bucata continua pe linie ce trebuie acoperita o transformi intr-un nod, fiecare bucata continua pe coloana o transformi intr-un nod, daca o bucata continua pe linie se intersecteaza cu una pe coloana atunci intre cele doua noduri exista o muchie, deci practic toate patratele ce trebuie sa fie acoperite sunt muchii intre nodurile din graful nostru. Este clar ca acest graf este bipartit. Acum noi daca punem o scandura orizontala pe un patratel nu are rost sa ocupam cu ea mai putin decat toata bucata orizontala din care face parte patratelul respectiv, la fel daca punem scanduri verticale. Pe graful nostru punerea unei scanduri orizontale este echivalenta cu selectarea unui nod dintr-o parte a grafului bipartit si acoperirea tuturor muchiilor ce pleaca din acel nod, la fel o scandura verticala e echivalenta cu selectarea unui nod din cealalta parte a grafului bipartit si acoperirea tuturor muchiilor care au un capat in acel nod. Deci problema noastra s-a transformat in selectarea unui numar minim de noduri intr-un graf bipartit astfel ca pentru fiecare muchie unul din capete e in multimea noastra. Aceasta este o problema clasica, numita suport minim in romana si minimum edge cover in engleza. Este NP completa in graf oarecare dar usor rezolvabila in graf bipartit. La concursul algoritmus s-a dat o asemenea problema numita Paznici (http://algoritmus.org/probleme/Probleme_Runda04.php) si rezolvarea are la baza teorema lui Konig care spune : Cardinalul unui suport minim intr-un graf bipartit este egal cu cardinalul cuplajului maxim. Deci rezolvarea se reducea la determinarea cardinalului unui cuplaj maxim in graful construit mai sus.

[VladS]

Rezultatele de la ace.delos.com/JAN05 sunt finale?
Eu am trimis solutii in 3 ore si nu apar in clasament. La sursele mele tot "Saved for grading" scrie. Stiti de la ce ar putea fi

[andreit1]

Mersi de explicatii Cosmin. Din cate observ problema are un algoritm clasic pe care daca nu il stii e cam greu sa il descoperi singur deci puteam sa ma chinui mult si bine la el...

[•svalentin]

Rezultatele de la ace.delos.com/JAN05 sunt finale?
Eu am trimis solutii in 3 ore si nu apar in clasament. La sursele mele tot "Saved for grading" scrie. Stiti de la ce ar putea fi

Da, sunt finale rezultatele!
"saved for grading" spune si la mine si apar in clasament!
poate nu ai cautat cum trebuie rezultatul (incearca sa dai search pe user id)

... iar din cate stiam eu, cei care nu apar in clasament de loc, inseamna ca au trisat si ca au fost anuntati corespunzator!

[•sarabogdan]

Eu n-am aparut in clasament pentru ca am completat gresit la graduation year , in loc de 2007 am pus 2003 si altfel am fost pus la obervers ce nu au fost afisati numai cei  la gold parca!

[VladS]

Nu am trisat, iar graduation year e 2007.