La Algoritmus erau bine realizate enunturile, desene clare, si erau intradevar mai dificile, in special cele de geometrie. Tin minte ca la o runda s-a dat o problema cunoscuta NP ( niste obiecte ce trebuiau puse in mai multi rucsaci), deci cu rezolvare euristica. Tot aveam impresia ca e simpla si se rezolva in timp polinomial, si implementasem o dinamica "norocoasa" de vreo 60% din punctaj

Faine vremurile alea...
Tin minte ca eram pe la sfarsitul lui 2004 si participam pentru a treia oara la .Campion, insa cautam si ceva nou.
Algoritmus aparuse recent, si venea cu ceva inedit, faptul ca eram motivati de mici premii.
Rundele erau faine pentru ca erau  6 probleme care acopereau cam toata materia (geometrie, grafuri, PD + ceva euristici)
Tot pe atunci am zis sa ma apuc serios de infoarena, pana la judeteana faceam cam 6-7 probleme pe zi (era norma).

Raspuns: O(N) cu o constanta.

CATEVA NOTIUNI:

Consideram nr de operatii de marcare a multiplilor pt fiecare numar de la 1 la N

cntMark = {O(1) daca i nu este prim
              O(N/i) daca nr este prim

Suma cu i de la 1 la N de  cntMark =  (O(1) * N - pt fiecare nr se fac cel putin un nr constant de op
                                                       +
                                                 O(N/2) + (N/3) + (N/5)...- marcajele pt nr prime
Stim ca
1) N/1 + N/2 + N/3 +..N/i+...N/N ~= O(NlogN) (aprox. grosolana) E simplu de arat, rotunjind fiecare nr i spre cea mai mare putere de 2 mai mica ca i
   N/1 + N/2 + N/3 +..N/N <= N/1 + N/2 + N/2 + N/4 +... N/[2^x] = O(NlogN),  x= max{ y/ 2^y <= N}
 

2) se stie ca in primele N nr naturale exista N / lnN nr prime

REZOLVARE:

O(N/1) + O(N/2) + O(N/3) + ... O(N/N) - cu limita O(NlogN)
O(N/2) + O(N/3) + O(N/5) + .... - subsir de termeni al prime sume, cu  nr de elemente = N / lnN, exista lnN astfel de subsiruri, fiecare avand limita O(NlogN)  / lnN ~= O(N) cu o constanta

Complexiate Ciur eratostene = O(N) * logN/lnN ~= O(N)


P.S. La 1) limita adevarata e mai mica de NlogN,e chiar NlnN

Mi se pare mie sau solutia oficiala de la Barman e gresita..inclusiv 2 teste?

Pustiu are dreptate(adik Mircea de la CNU). Sa citesti un fisier caracater cu caracter e total diferit de a citi acelasi fisier prin blocuri mari(de 64Kb de exemplu). Ca il parcurgi in memorie inca o daca n-are importanta daca iei in considerare timpul mic  de acces la memoria RAM, insa hard-ul e mullltttt!!!! mai lent si o citire caracter cu caracter poate sa-ti ia ca timp de peste  10-20!! mai mult decat o citire "OPTIMA".

Testu' 2 e cu shmen? tot iau WA...daca se poate va rog sa mi-l postati...

Cine a ales cartile, echipa infoarena sau MS ?
Visual Basic?...ha?! chiar asa de multi fani basic sunt in competitia asta?

eu personal nu cred ca voi programa in viitor Visual BASIC(pe care in detest de altfel ) sau C#(chiar daca e la moda).

Deci cred ca tricourile erau cea mai buna alegere...

In primul rand varianta asta nu te ajuta la rezolvarea problemei.
Dar pentru stiinta iti explic:

cand intalnesti un punct de pe poligon te uiti la cele doua segmente care il contin: daca ambele seg au celalalt capat de aceeasi parte a dreptei ignori intersectia, altfel o numeri. Mai exista cazul cand intalnesti segmente ale poligonului care sunt incluse in dreapta de scanare. Le ignori pur si simplu de parca nici n-ar exista. Ok?

Ar trebui sa-ti dea raspunsul corect...  

Gata..gata.. nu mai zi ca mi-ai zis destul..chiar prea mult...thx

poate cineva sa-mi dea un indiciu la problema asta  Am avut impresia c-am facut-o da dupa ce am vazut 20p in fata ochilor mi-am dat seama ca nu merge. Banuiesc ca e N*logN da in nici un caz dinamica mea...

Se mai intampla...
  Se poate si in N^3 da cum ziceam mananca multa memorie...

sigur ai folosit foaie de matematica?..si vezi sa nu le numeri pe alea care sunt pe granita..foloseste si o rigla ca sa-ti iasa bine poligonu'.

greco: si cati MB ai folosit pt. N^3. As presupune ca 37.5...nu ...la ONI trebuie sa te incadrezi in 15, deci e numai buna in N^3*log(N^3).

Belea..daca nici solutia de N^6 n-o scrii corect?..nu cred ca o s-o faci prea curand. Trebuie sa te apuci serios de DEBUG... :lol:

uite aici o solutie N^6 corecta
compar-o cu a ta si vezi "diferenta"

Cod:

#include<stdio.h>
#define MAXN 101

FILE *in=fopen("loto.in","r"),*out=fopen("loto.out","w");
int N,S,V[MAXN];

void citesteDate()
{int i;
  fscanf(in,"%d %d",&N,&S);
  for(i=1;i<=N;i++)
     fscanf(in,"%d",&V[i]);
  fclose(in);
}

void proceseaza()
{int i,j,k,l,m,n;
  for(i=1;i<=N;i++)
      for(j=1;j<=N;j++)
         for(k=1;k<=N;k++)
             for(l=1;l<=N;l++)
                 for(m=1;m<=N;m++)
                     for(n=1;n<=N;n++)
                        if (V[i]+V[j]+V[k]+V[l]+V[m]+V[n]==S)
                           {fprintf(out,"%d %d %d %d %d %d\n",V[i],V[j],V[k],V[l],V[m],V[n]);
fclose(out);
return;}
 fprintf(out,"-1\n");
 fclose(out);
}

                   

 

int main()
{
 citesteDate();
 proceseaza();
 return 0;
}

Iei pe ea exact 35p daca o copiezi corect.  

Bafta la cautare N^3 * log(N^3)!

[edited by svalentin] foloseste [*code*][*/code*] (fara *) pentru a formata o sursa corect

Nasol testu 9.  L-a facut cineva din prima? Tot iau TLE.
 Da cu bellman-ford a facut careva?, eu asa am facut si merge binisor, poate chiar mai bine decat Dijkstra cu costuri mici. M-am uitat la solutia prezentata oficial, pare simplu, dar tocmai constanta din fata lu' N*M care este 3*8*(cate operatii efectuate cu un nod din lista) si care nu este precizata face diferenta de scor. In cazurile astea constanta n-ar trebui ignorata, e importanta!!!

eu am gasit o rezolvare in O(n).;
care a mers pe teste...
chestia e ca tu parcugi vectorul ca pentru o suma maximala, cu conditia din enunt

Chiar daca o scoti in O(n) e posibil sa-ti iasa din timp. Poti folosi "vraja marii la malu' marii" adica sa-ti pui un bufer la fisierul de intrare.
Cam 1 MB iti este de ajuns sa elimine neplacerile cauzate de o citire greoaie. Functia e "setvbuf", si iti poate folosi la multe probleme in care timpul e critic.

vreau si eu un test intre 6-9 la problema asta cu nu-mi gasesc hiba. oricate teste i-as da merge.

Rectific: Ma refer la problema ZERO

Nu inteleg ce se cere la punctul B.

ce se intelege prin "cel putin doi de zero consecutiv"? enuntul asta poate
lua zeci de interpretari
ex L=5 B=2 Q=2
1 11111 - de ce nu e bun?
2 10010 - este bun?
3 10011 - este bun?
daca-mi raspunde cineva la cele trei intrebari cred ca o sa-mi dau seama despre ce e vorba.

Care e problema cu testu' 19 ca inebunesc . nu stiu ce poate avea solutia mea, ca e scrisa impecabil.

Nu se pot afisa datele de intrare?