Intr-adevar, faci dinamica care ai spus-o tu:
M(i,j) = costul minim daca imparti primele j numere in i secvente
Relatia de recurenta este destul de usor de scos:
M(i,j) = minim(M(i-1, k) + maxim(v(k+1), ... v(j))), unde 0 <= k < j => O(N^2 * K) daca faci direct.

Un hint pentru O(N*K): Pentru a calcula M(i,j) ai doua cazuri: ori v(j) este maxim in ultima subsecventa (a i-a), ori nu. Daca consideri alt element ca fiind maxim in ultima subsecventa atunci M(i,j) = M(i, B), unde B este cel mai din dreapta element a. i. v(B) >= v(j). Egalitatea are loc deoarece maximul ultimei secvente trebuie sa fie undeva mai in stanga lui B, si elementele v(B+1) ... v(j) nu influenteaza in niciun fel costul final. Gandeste-te ce se intampla daca v(j) este maxim in secventa lui si noteaza costul pe cazul asta cu valoare_caz_2. Aceasta valoare poate fi obtinuta in O(1) amortizat.
In final M(i,j) = minim(M(i, B), valoare_caz_2).

Daca nu descoperi cum poate fi obtinuta valoare_caz_2, posteaza pe forum ca sa te lamurim .

O componenta conexa intr-un graf neorientat este o submultime maximala C a multimii de noduri astfel incat oricare ar fi doua noduri x si y din C, exista drum de la x la y si de la y la x.
Google it. In plus, uita-te pe sursele din arhiva si ai sa vezi cum functioneaza algoritmul de determinare a componentelor astea.

Mie imi da 9.

Merge si fara hash in O(N^2), care ia 100.

P se da in baza 10.

[2933]

Pentru primul test: 2933
Pentru al doilea test: 6250

(obtinute cu sursa mea de 100 de puncte).

Aici puteti discuta despre problema Pp.

Aici puteti discuta despre problema Pkinv.

Aici puteti discuta despre problema Per.

Aici puteti discuta despre problema Mm.

Aici puteti discuta despre problema Maxunice.

Aici puteti discuta despre problema Ksecv.

Aici puteti discuta despre problema G2mm.

Aici puteti discuta despre problema Exit.

Aici puteti discuta despre problema Dictree.

Aici puteti discuta despre problema Rest.

In afara de micile probleme aparute concursul a fost ok. Cand se calculeaza rating-urile?

Nu e corect ce fac utilizatorii andrei-alpha si toni2007 avand in vedere ca au aceleasi dimensiuni la 3 din cele 4 surse de 100 pe care le au amandoi si e foarte probabil sa fie aceleasi surse. Rog un admin sa se uite daca sunt intr-adevar acelasi surse pentru ca aceasta frauda poate afecta negativ ratingurile celorlalti utilizatori. Stiu ca ACM-u e concurs pe echipe dar parca nu e tocmai frumos asa ceva.

De ce nu e corect? Concursul acesta a fost unul fara miza pentru ei doi. Adica oricat de bine faceau, nu se calificau la ACM . Ar fi fost o problema de exemplu daca faceau asta la preONI. Parerea mea e ca e nu e de condamnat, ci chiar dimpotriva. A fost un concurs relaxa(n)t. Poate era mai potriviat sa faca un cont comun, dar nici asa cred ca nu e problema.

Evaluatorul nu ar trebui sa fie pornit?

Undeva prin toamna-iarna. Macedonienii astia nu prea sunt in stare de nimic , cu atat mai putin sa faca ei site.

Pana acum Autumn-Warmup a fost organizat de comunitate. Daca sunt voluntari cu idei bune, se va tine

De asemenea site-ul BOI 2008 va fi creat in urmatoarele zile ("in prima jumatate a lunii august").

Aiurea, au uitat macedonienii astia.

Stai ca nu merge cum spuneam mai sus ca pot fi mai multe diagonale care pleaca din acelasi varf . Cel mai simplu este sa consideri toate diagonalele si la fiecare pas verifici daca poti sau nu sa pui diagonala curenta:

Cod:

#include <stdio.h>

typedef struct { int x, y; } diagonala;

int N;
diagonala D[1024]; int nr_diagonale;

int st[1024]; // st[i] = 1 <=> am selectat diagonala i

int between(int x, int r1, int r2)
{ return (r1 <= x && x <= r2); }

int intersect(int i1, int i2)
{
    return (D[i1].x != D[i2].x && D[i1].x != D[i2].y && D[i1].y != D[i2].x && D[i1].y != D[i2].y &&
            between(D[i1].x, D[i2].x, D[i2].y) + between(D[i1].y, D[i2].x, D[i2].y) == 1);
}

void back(int nivel)
{
    int i;

    if (nivel == nr_diagonale + 1)
    {
        int j = 0;
        for (i = 1; i <= nr_diagonale; ++i)
            j += st[i];
           
        if (j == N-3) // daca am selectat N-3 diagonale afisam
        {
            for (i = 1; i <= nr_diagonale; ++i)
                if (st[i])
                    printf("(%d %d) ", D[i].x, D[i].y);
            printf("\n");
        }
       
        return ;
    }

    st[nivel] = 0; back(nivel+1); // nu selectam diagonala

    // verificam daca putem sa o selectam
    if (st[1] && nivel == 2)
        i = 0;

    for (i = 1; i < nivel; ++i)
        if (st[i] && intersect(i, nivel))
            return ;
    st[nivel] = 1; back(nivel+1);
}

int main(void)
{
    int i, j;

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    scanf("%d", &N);
   
    for (i = 1; i <= N; ++i)
        for (j = i+1; j <= N; ++j)
        {
            if (i+1 == j || (i == 1 && j == N)) continue;
            ++nr_diagonale;
            D[nr_diagonale].x = i;
            D[nr_diagonale].y = j;
        }

    i = intersect(2, 3);
    back(1);
       
    return 0;
}

Sunt multe optimizari care pot fi facute si poti imbunatati programul de mai sus.

Functia valid la care te referi poate fi ceva de genul:

Cod:

int between(int x, int r1, int r2)
{ return (r1 <= x && x <= r2); }

int intersect(int i1, int i2)
{
    return (D[i1].x != D[i2].x && D[i1].x != D[i2].y && D[i1].y != D[i2].x && D[i1].y != D[i2].y &&
            between(D[i1].x, D[i2].x, D[i2].y) + between(D[i1].y, D[i2].x, D[i2].y) == 1);
}

int valid()
{
int i;
for (i = 1; i < nivel; ++i)
   if (st[i] && intersect(i, nivel))
       return 0;
return 1;
}

Poti folosi metoda backtracking.
Poti face asa: consideri un vector st in care st_i reprezinta celalalt capat al diagonalei care contine varful i din poligon sau 0, daca din varful i nu pleaca nicio diagonala. Poti impune i < st_i. Conditia ca 2 diagonale (i st_i) (j st_j) sa nu se intersecteze este ca i <= j, st_j <= st_i sau j <= i, st_i <= st_j.

[H - SVi - SVj + |xj-1-xi| + |xi-xj+1| + |xi-1-xj| + |xj-xi+1|]

Uite o rezolvare O(N log² N):

Sa notam H = |h₁-h₂| + ... + |h_n-1 - h_n| si cu SV_i = |h_i-1-h_i| - |h_i-h_i+1|.
Pentru primul si ultimul pom putem verifica liniar cu care e optim sa le inlocuim: 2 * O(N) = O(N).
Pentru un pom i, 1 < i <  N, trebuie sa aflam care e cel mai bun pom j cu care putem sa il inlocuim. Calculam in O(1) valoarea inlocuirii daca j = 1 sau j = N si acum vrem sa det. 1 < j < N a. i.
H - SV_i - SV_j + |x_j-1-x_i| + |x_i-x_j+1| + |x_i-1-x_j| + |x_j-x_i+1| sa fie minim.

Sa consideram punctele in plan de coordonate (x_j-1, x_j) care sa aiba asociat costul x_j+1. Consideram evenimente pe axa temporala de genul:
* la momentul de timp x_j+1 adaugam punctul (x_j-1, x_j) in plan

Cand inseram punctul (x_i-2, x_i-1) de cost x_i putem afla raspunsul pe care il vrem in log²N, tratand niste cazuri. Putem presupune de ex. ca x_i apartine intervalului [x_j-1, x_j+1] si ca x_i-1 < x_j. Asta determina un dreptunghi in plan si o expresie fixa in functie de j care trebuie minimizata => arbore de intervale 2D cu memorie O(N log N). Mai clar probl se rezuma la:

Ai n puncte in plan si operatii de forma: "pune un punct in plan de cost dat" si "afla intr-un dreptunghi care e costul minim". Poti folosi ideea de la arborele 2D de aici, numai ca tu trebuie sa tii pe fiecare nivel (logN nivele in total) cate un alt arbore de intervale, nu un simplu vector, ca sa poti face si query si update .

E cam jegos de implementat si e destul de incalcita solutia, mai ales ca ai vreo 6 cazuri . S-ar putea sa existe si o solutie mai buna, asta a fost insa prima idee care mi-a venit

CFR are toate sansele