E gresita abordarea inversa. Mergand de la stanga la dreapta (i=1..N/2), tu practic stergi cifrele din capat (baab -> aa). Din pacate, asta face ca, avand o cifra k, sa poti sa ajungi din restul curent in mai multe resturi diferite cu acelasi cost.

Cel mai simplu test pe care l-am putut gasi este:
1 0 0 0 0 0 0 0 0 0
5015
5

Raspunsul corect e 5115 iar in varianta ta da 5005.

Asta fiindca daca adaugi la margine cifra 5, numarul devine 5xx5. Indiferent daca adaugi 5-ul la restul 0 sau 1, obtii tot restul 0. In general, j * 10 % K poate da valori egale pentru j-uri diferite. N-ai de unde sa stii care rest e cel bun.

In schimb, in varianta corecta j-ul nu se inmulteste cu nimic si, deci, pentru fiecare new_rest si o cifra k ai un unic j.

Interesant

Acum inteleg de unde vine. Formula din codul tau e ((j + 10^N-2i+1 * k) * 10 + k) % K.
In cod adaugi invers cifrele. Deci, in exemplul tau ar trebui sa adaugi b * 10², fiindca exista doar aa deocamdata.

Nu iese matematic ce ai scris acolo. Cum ai dedus acea formula?

Este doar o altă alternativă de scriere pentru lista de adiacență?

Da, te scuteste de implementarea manuala.

Prima data aplici a treia regula: T = t₁ + t₂, unde t₁ = () si t₂ = (()).
t₁ e corecta datorita primei reguli.
La t₂ aplici regula a doua: t₂ = '(' + t₃ + ')', unde t₃ = ().
t₃ e corecta datorita primei reguli.

Nu stiu care e rostul vectorului drum, dar oricum depasesti limitele vectorului (din cauza lui u) si scrii peste tot in memorie si suprascrii multe valori de care ai nevoie.

Banuiesc ca voia ca la marginea matricei sa fie INFINIT. Tipuri de date: http://www.tutorialspoint.com/cplusplus/cpp_data_types.htm

Da, ordinea e de la dreapta la stanga.

Bitii nu fac decat sa scrie mai simplu o valoare mare, dar poti scrie si manual un miliard. Trebuie sa fie o valoare mare astfel incat cand faci min(INFINIT, alta_valoare) sa se ia tot timpul alta_valoare.
Al doilea return din functie e un fel de else implicit. Daca intra la if se iese din functie iar daca nu se merge la celalalt return. E echivalent cu abs().
Matricea sol o calculezi cu programare dinamica, nu are legatura cu bitii.

Solutia oficiala foloseste int iar tu long long. Deci, solutia ta e mult mai inceata.

Ok, posibil sa ma fi exprimat gresit. Prin query ma refeream la operatii. N operatii (la tine) = M query-uri (la mine).

Solutia mea tine cont de asta.

E destul de ciudat enuntul, sper ca am inteles bine problema. Presupun ca daca A il mosteneste pe B si B pe C atunci si A pe C.

O solutie mai buna ar fi sa imparti cele M query-uri in bucati de sqrt(M). Pentru fiecare bucata, calculezi vectorul S[i] = stramosul cu nivelul minim pe care il mosteneste (cel mai de sus). Apoi, operatiile se fac astfel:

2. O(1), pur si simplu marchezi.
1. O(1), marchezi la nodul x ca la query-ul cu indexul i i s-a atribuit valoarea y.
3. Ai lista L de noduri ale caror valoare s-a schimbat (maxim sqrt(M)). Mergi din x pana in stramosul cu nivelul minim (posibil diferit de S[i]) in maxim sqrt(M) pasi si de fiecare data cand treci pe langa un nod din L vezi cu ce valoare a contribuit la x.

Iese complexitatea O(N*sqrt(M) + M*sqrt(M)).

Codul tau e gresit, nu garanteaza raspunsul optim. Nu se poate fara programare dinamica.

Nu faci bine parcurgerea. Introduci de prea multe ori elementul in coada, de asta iei MLE/TLE. Incearca sa inveti http://www.infoarena.ro/problema/bfs si http://www.infoarena.ro/problema/bellmanford. Acestea fiind zise, rezolvarea ta nu e corecta. Vezi ce s-a scris prin acest topic.

Lol, nu ma bagati in seama. VMAX e defapt lungimea maxima a intervalelor, care = n. 

@Ozturk Arif: Daca nu se precizeaza atunci nu. (Asta e presupunerea pe care o poti face in general)

La Sarac sau Rege nu e O(n * log VMAX + m) timpul?

P.S.: La acest concurs e incurajata colaborarea intre participanti?

A fost data la ceva olimpiada straina si a fost explicata la finala Algoritmiadei 2013.

Ciclu2: Puteti sa definiti, va rog, un ciclu simplu? Nu mi-e clar raspunsul la a doua intrebare.

O greseala e ca faci l-- in ultimul while. In rest, am schimbat putin while-urile. Spor.

Cod:

#include <iostream>
#include <fstream>

using namespace std;

int main()
{
    ifstream f("turist.in");
    int a[10][10],n,m,i,j,l=0,v=0,gresit,Sminima=3200,nrlinie,nrcoloana,doarS;
    f>>n>>m;
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)f>>a[i][j];
    for(i=2;i<n;i++){for(j=2;j<m;j++)
    {
    l=i;v=j;gresit=0;doarS=0;
    if(a[i][j]<0)
    {
    	v--;
        while(v>=1&&gresit==0)       //orizonatal stanga
        {
            if(a[l][v]<0)gresit=1;
            else doarS+=a[l][v];
            v--;
        } 
        if(gresit==0&&doarS<Sminima)
        {
            Sminima=doarS;nrcoloana=j;nrlinie=i;
        }
       l=i;v=j; doarS=0;gresit=0;

		v++;
        while(v<=m&&gresit==0)              //orizontal dreapta
        {
            if(a[l][v]<0)gresit=1;
            else doarS+=a[l][v];
            v++;
        }
        if(gresit==0&&doarS<Sminima)
        {
            Sminima=doarS;nrcoloana = j;nrlinie=i;
        }
        l=i;v=j; doarS=0;gresit=0;

		l--;
        while(l>=1&&gresit==0)           // vertical in jos
        {
            if(a[l][v]<0)gresit=1;
            else doarS+=a[l][v];
            l--;
        }
        if(gresit==0&&doarS<Sminima)
        {
            Sminima=doarS;nrcoloana = j;nrlinie=i;

        }
            l=i;v=j; doarS=0;gresit=0;
		l++;
        while(l<=n&&gresit==0)                 // vertical in sus
        {
            if(a[l][v]<0)gresit=1;
            else doarS+=a[l][v];
            l++;
        }
        if(gresit==0&&doarS<Sminima)
        {
            Sminima=doarS;nrcoloana = j;nrlinie=i;

        }
    }
}}
ofstream g("turist.out");
g<<Sminima<<endl<<nrlinie<<endl<<nrcoloana;

}

Ce nu merge? Daca vrei sa verifici si elementele de pe margine poti pur si simplu... sa o faci. for i:=1->n, for j:=1->m. Clarifica putin.

Ti-as sugera sa te obisnuiesti sa scrii cod mai frumos.

P.S. Am si eu o curiozitate: voi cum verificati in evaluator la Fenrir ca graful nostru sa nu aiba lant hamilton fara sa bagati ceva foarte costisitor ca timp?

Dinamica O(2^N * M).

Nu.

Pai nu iti merge nici macar pe exemplu. Functia de comparare a stringurilor nu e buna. Gandeste-te ce se intampla daca str1 e prefix al lui str2.