infoarena

Aici puteţi discuta despre problema Panouri (http://infoarena.ro/problema/panouri).

cam ce complexitate ar trebui la problema asta pentru ca eu am facut un N*T si nu iau decat 50 de puncte. Ar trebui sa incerc sa mai caut niste optimizari sau exista un algoritm mai rapid?????

Pai complexitatea ii NlogN. Hint cauta binar lungimea. Problemele astea ii clasice incearca sa faci si secventa 3 ideea ii cam aceeasi.

Se poate rezolva si in O(N+T).

da cred ca de aia luam numai 80p.

Nu prea vad nici o asemanare intre secventa 3 si problema asta, decat ca sunt amandoua probleme in care trebuie sa dai ca rezultat o secventa.

Asemanare dintre secventa 3 si panouri e ca el le-a rezolvat la fel, probabil cautand binar lungimea (deshi nu inteleg ce lungime cauta el la secventa 3 ptr ca acolo nu lungimea e baza ci costul dar ma rog). Oricum asta inseamna ca tre sa caut alta rezolvare, oare cum ash putea face O(N)  :-'

nu am facut problema inca...dar probabil e o coada...

:) pai cum rezolvarea e O(n) ar fi cam nasol sa fie rezolvarea bazata pe un arbore binar de cautare :).

ok, la ONI am facut in n*t si am luat 100, aici iau 0... nu merge :D
problema e alta: am facut-o si in O(n) cu o coada, am 8 WA si 2 TLE... am incercat sa citesc doar si sa afisez direct -1, fara sa mai procesez datele.. si inca iau  1 TLE ( uneori 2, ideea e ca e la limita)

postez si citirea...
trebuie sa citesc mai eficient?

eu cu n*t iau 50 de pct si in rest TLE.

am luat 100 citind cu scanf.. dar daca din cauza asta iei tle de ce nu bagi un fgets si rezolvi problema

Ai luat 100 cu O(n*t)??

nu :) spuneam numai de citire

M-am linistit. Mare pacat ca la Oni s-a luat 100 cu N*T, problema a fost facuta mai slaba ca sa intre in timp si in Borland ... pacat.

merge si N*logT de 100 :) (cu un min-heap)

Merge si O(N+T).  :P

O(n + t) e si solutia oficiala.

Ar trebui "acordata" fraza asta: Nu ca ma deranjeaza dar ati spus ca ar trebui sa raportam orice greseala care scade calitatea enuntului. :)

Am modificat.

Si eu am facut O(N+T)   (asta daca +T reprezinta citirea panourilor, altfel O(N)) si iau 30 puncte??? Am testat programul pe testele oficiale (si sub Windows, si sub Linux), imi merge perfect, raspunde instant si corect pe testele mari (alea mici nu le-am testat, sigur merg).  :eyebrow:

Sa fie de la scanf?

_______________Mai tarziu________________________________________-

30 de puncte cu scanf si 100 de puncte cu fstream. Oare de ce se recomanda sa folosim scanf (am mai auzit din diferite locuri)?

Se recomanda sa implementezi cum trebuie :). Eu am luat 100 cu scanf.

Am implementat cum trebuie pt ca aici programul imi merge pe toate testele oficiale f bine.
Ideea e ca exact aceeasi sursa ia 30 pct cu scanf si 100 pct cu fstream.

Pe ultimele versiuni de gcc merge mai repede sa citesti cu streamuri.

M-am uitat aleator prin niste surse de 100 si majoritatea citeau cu scanf. Probabil ca tie iti merge mai incet din cauza ca folosesti 2 functii pe care le apelezi destul de des. Muta codul si renunta la cele 2 functii. Ar trebui sa mearga mai repede.

Astfel de probleme, pentru care se cere o solutie O(N), trebuie implementate cu grija. De obicei limita de timp este destul de stransa pentru a nu permite solutiilor O(N log N) optimizate sa intre in timp.

Nu am spus nicaieri ca nu este corecta, ci doar ca daca implementezi cu grija iei 100 fara fstream, parsare etc. Ideea e ca nu prea sti care merge mai repede. La unele concursuri merge mai bine stdio (campion), la altfel merg mai bine streamurile, cel mai bine implementezi sursa astfel incat sa nu ai nevoie de optimizari d-astea.

La .campion merge mai repede citirea in C pentru ca ei folosesc un compilator mai vechi (poate ar merge un upgrade?  :)). Va trece un timp pana cand toate concursurile vor fi evaluate sub o versiune destul de noua de gcc. Daca timpul e strans si ai impresia ca sursa e la limita, cel mai sigur e sa parsezi.

Salut! Poate cineva sa verifice testele sau sa imi spuna daca gresesc ceva, am trimis doar asta
pentru ca nu imi intra in timp si nici macar citirea de mai sus nu intra in timp pe ultimele teste.

Ma poate ajuta si pe mine cineva? Iau 80p cu TLE pe testele 8 si 10, chiar daca am complexitatea O(N+T).

cod:
#include<fstream>
#include<iostream>
using namespace std;
int a[ 200005 ],f[ 20005 ],ff[ 20005 ],f_sol[ 20005 ];
ifstream in ("panouri.in");
ofstream out("panouri.out");
int main()
{
    int n,i,T,x,nr1=0,p,u,min=2000000;
    in>>n>>T;
    for(i=1;i<=n;i++)
        {in>>a[ i ];f_sol [ a [ i ] ]++;}
    for(i=1;i<=T;i++)
        {
            in>>x;
            ff [ x ] ++;
        }
    p=u=1;
    if(ff[a[1]]) nr1=1;
    else nr1=0;
    f[a[1]]++;
    while(u<=n)
        {
            while(p<=u && nr1==T)
                {
                if(u-p<min) min=u-p;
                f[a[p]]--;
                if(ff[a[p]] && f[a[p]]==0) nr1--;
                    p++;
                }
            while( u <= n && nr1 != T )
                {
                u++;
                f[ a [ u ] ]++;
                if(ff [ a [ u ] ] && f [ a [ u ] ] == 1)
                    nr1++;
                }
        }
    if(min!=2000000)
        out<<min<<endl;
    else
        out<<"-1"<<endl;
    return 0;
}

Daca un admin considera ca nu e bine ca am postat codul, sa il stearga :)

Pentru 100 ai nevoie de parsare.