042 Xor Max

[•domino]

Aici puteţi discuta despre problema Xor Max.

[•ParrAzitU]

sorry,    am pus intrebarea precedenta la threadul gresit.. faceam xormax si nu-mi iesea testul 2.. si am postat la boom, pt ca aia o facusem inainte si .. Deci dc mai imi puteti zice again testu 2 de data asta de la xormax..    mersi

[•Stilgar]

am o intrebare cum poti scapa de o(n^2) ca banuiesc ca iese din timp...

[•Cosmin]

Ma de ce nu va uitati la articolele de pe info.devnet.ro? E chiar asa greu? Ai explicata acolo solutia la XOR max la solutiile problemelor de incalzire ... Nush ce naiba se intampla de o vreme: in alt thread intreaba lumea de cormen, si il gasesc online pe siteu nostru, altii intreaba ca si tine de probleme ce sunt explicate deja pe site ....

[•Stilgar]

scuza-ma pt lipsa mea de profesionalism dar de unde era sa stiu ca s-o dat la concursu de incalzire? daca nu stiu o problema ar trebui sa ma uit la toate conc. pe care le-ati organizat pana acuma sau ce? La articole in general recunosc ca nu ma prea uit dar incerc sa schimb chestia asta

scuze pt deranj si fi si tu mai calm k?

[•Cosmin]

Hmm, articole pe site sunt 20 numar care il consider mic, cat despre concursuri organizate pe site cu solutii in articole sunt 5, asta chiar e un numar mic, mai ales ca poti sa te uiti numai la numele problemelor din fiecare articol, nu trebuie sa citesti continutul. In 2 minute ai fi gasit daca problema e data sau nu  .... si ai fi stiut si pe viitor cam ce probleme sunt explicate. Sunt foarte calm da cand vad ca un site asa mic e greu de vizitat si studiat ma gandesc ca nu are rost sa ne mai chinuim sa facem alte concursuri cu solutii sau sa scriem alte articole daca ele oricum nu sunt citite. Si ce mai e nasol e faptu ca in general lumea trimite intrebari pe forum ca sa li se raspunda mura in gura, cand 5 minute de documentare prealabila le-ar aduce si mai multe cunostinte, ar si invata sa se descurce singuri si nu ar mai irosi timpul altora. Nu am nici o treaba cu tine dar am vazut mai multe chestii de genu asta pe forum.

[•realboss]

Imi spune si mie cineva ce operatie e Xor?
Chiar nu am auzit de ea...

[•filipb]

Sau exclusiv: A XOR B = 0 <=> Fie A si B sunt 0, fie A si B sunt 1

[•fireatmyself]

moke, nu mai posta solutii pe forum !!! (doar hinturi!!!)

[•amadaeus]

Care e diferenta dintre "Bine, Ionel!" si "Ok... pentru moment". Adica primesc 10p in amandoua cazurile, insa as vrea sa stiu daca s-ar putea mai bine (nu gasesc stop-ul minim, sau secventa cea mai scurta etc..)

[•azotlichid]

Cand sursa ta da rezultatul corect la un test, evalul afiseaza un mesaj aleator dintr-o lista predefinita. Nu e nici o diferenta deci... 

[•amadaeus]

Aham.. Ms mult

[•peanutz]

A mai picat cineva testul 2? E vreun caz particular? Un singur element poate reprezenta o secventa, nu?

Later: nevermind... am rezolvat

[•Mishu91]

se poate ca secventa sa fie formata dintr-un singur element?

[•wefgef]

Da, se poate, de ce nu ?

Daca ai de exemplu 2 numere: 1 si 3, raspunsul este 3.

[•DITzoneC]

S-a facut o reevaluare la aceasta problema.

[•emilian.miron]

Tot incerc sa iau puncte la problema fara succes.. pana si brute force-ul ia WA asa ca poate am inteles gresit problema.
De exemplu pentru testul de mai jos am rulat brute-ul si o solutie de 100

11
21 98 77 35 90 11 51 3 58 54 74

BRUTE:
125 6 11

SOLUTIE 100 (submit #196825):
124 10 11

Atasez si brute-ul meu, poate ma lumineaza cineva.

Cod:

int N;
int A[maxn];

int main(void)
{
    int i, j;

#ifndef CACAMACA
    freopen ("xormax.in", "rt", stdin);
    freopen ("xormax.out", "wt", stdout);
#endif

    scanf ("%d", &N);

    for (i = 0; i < N; i++)
        scanf ("%d", A + i);

    int best_y = -1;
    int best_start = 0, best_end = -1;

    for (i = 0; i < N; i++) {
        int y = 0;
        for (j = i; j < N; j++) {
            y ^= A[j];

            if (y > best_y || (y == best_y && j < best_end) ||
                (y == best_y && j == best_end && i > best_start))
            {
                best_y = y;
                best_start = i;
                best_end = j;
            }

        }
    }

    printf ("%d %d %d\n", best_y, best_start + 1, best_end + 1);

    return 0;
}

editat de moderator: Foloseste tag-ul code pentru postat cod.

[•devilkind]

125 6 11 imi da si mie. Probabil ca acea sursa de 100 nu e tocmai buna si nu merge pe toate cazurile, cazuri care nu se regasesc in testele problemei.

[•andrici_cezar]

la problema asta de ce merge doar cu arbori? adica daca cautam secventa de ce numerge? am facut ceva gen subsecventa de suma maxima dar totusi i-au doar 0 puncte imi explica si mie cineva de cE?

[•Mishu91]

Merge cu trie
Si nu prea merge sa faci ca la subsecventa de suma maxima pentru ca nu se prea respecta conditia ca daca a > b, atunci a^c > b^c (de exemplu 4^2 > 4^4).
 

[•APOCALYPTO]

, iar daca inca exista mai multe solutii se va alege secventa cea mai scurta.

Se refera la cea mai scurta din cele cu stop minim egal sau din toate cele care sunt solutii(nu neaparat cu stop minim)?

[•Mishu91]

Dintre cele cu stop minim egal.

[•APOCALYPTO]

Testele 10 si 20 contin ceva special? 
Primesc TLE pe ele.
 Am observat ca rezultatul este de forma max start start deoarece start=stop. Ma poate ajuta cineva( preferabil din echipa infoarena) sa-mi dau seama de ce nu trec acele teste.
Multumesc anticipat!

[•stocarul]

Nu va sta nimeni să vadă de ce nu-ți intră ție rezolvarea pe 2 teste.
Dar dacă te uiți atent, poți observa că la această prolemă poți vedea toate sursele trimise. Deci te poți inspira din sursele de 100 pct.
p.s. am observat că timpul este destul de larg. Ar trebui să-ți intre fără probleme dacă rezolvi cu Trie.

[•popoiu.george]

Are cineva niste teste mai mari ? Iau 10p cu WA-uri si nu imi dau seama ce gresesc. Imi merge pe testul postat de @Emilia Miron.

Later Edit : Ciudat, daca pun toate operatiile xor de forma a^b in paranteze , adica (a^b) iau 100p, iar daca le las fara iau 10p. Stie cineva de ce?