De ce am KBS 11 pe toate testele? Nu observ.

Cod:

int matrix[310][310];
int ve[1000002];

int main ()
{
    for (i=1; i<=N; i++)
        for (j=1; j<=M; j++)
        {
            k = i;
            l = j;
            while (k<=N && l<=M)
            {
                sol2 = 0;
                for (u=1; u<=1000000; u++)
                    ve[u] = 0;
                for (u=i; u<=k; u++)
                    for (v=j; v<=l; v++)
                    {
                        ve[matrix[u][v]]++;
                        w++;
                    }
                for (u=1; u<=1000000; u++)
                    if (ve[u] > 0)
                        sol2++;
                sol1 = k-i+1;
                if (sol2 <= K && sol1 > sol)
                    sol = sol1;
                k++;
                l++;
            }
        }
}

Cum pot scăpa de TLE?

Cod:

    NR = 1;
    sol[NR] = X;
    seen[X] = 1;
    for (w=1; w<=N*N*N*N; w++)
        for (i=1; i<=N; i++)
            if (!seen[i])
            {
                cnt1 = 0;
                AA = i;
                for (j=1; j<=A[AA][0]; j++)
                {
                    BB = A[AA][j];
                    if (seen[BB] == 1)
                    {
                        if (code[BB] == 0)
                            cnt1 = 1;
                        else
                        {
                            cnt2 = 0;
                            for (k=1; k<=A[AA][0]; k++)
                                if (seen[A[AA][k]] == 0)
                                    cnt2++;
                            if (code[BB] > cnt2)
                                cnt1 = 1;
                        }
                    }
                }
                if (cnt1 == 1)
                {
                    NR++;
                    sol[NR] = AA;
                    seen[AA] = 1;
                }
            }

What is wrong in this code?

Cod:

    path[1] = 1;
    S = C[1];
    k = 3;
    for (i=2; i<=m; i++)
    {
        path[i] = k;
        k += i*i+1;    /// Go to the next level.
        //k += i;
        if (C[k] < C[k+1] && C[k] < C[k+i] && C[k] < C[k+i+1])
        {
            S += C[k];
        }
        else if (C[k+1] < C[k] && C[k+1] < C[k+i] && C[k+i+1])
        {
            S += C[k+1];
            k = k+1;
        }
        else if (C[k+i] < C[k] && C[k+i] < C[k+1] && C[k+i] < C[k+i+1])
        {
            S += C[k+i];
            k = k+i;
        }
        else if (C[k+i+1] < C[k] && C[k+i+1] < C[k+1] && C[k+i+1] < C[k+i])
        {
            S += C[k+i+1];
            k = k+i+1;
        }
        //S += min(min(C[k],C[k+1]),min(C[k+i],C[k+i+1]));
        //k--;
    }

Ce este greșit în această abordare?

Cod:

#include <fstream>
#include <climits>

using namespace std;

bool okay (string s);

string s[4];

string N;
long long int i, j, k;

long long int sol;

int main ()
{
    ifstream fin ("base3.in");
    fin >> s[1] >> s[2] >> s[3];
    fin.close();
    if (okay(s[1]) == 1)
    {
        N = s[1];
        sol = N.length();
    }
    else if (okay(s[2]) == 1)
    {
        N = s[2];
        sol = N.length();
    }
    else if (okay(s[3]) == 1)
    {
        N = s[3];
        sol = N.length();
    }
    else
    {
        i = j = 1;
        N = s[1];
        do
        {
            N += s[j];
            j++;
            if (j == 3)
                j = 1;

        } while (okay(N) == 1);
        sol = N.length();
        i = j = 1;
        N = s[2];
        do
        {
            N += s[j];
            j++;
            if (j == 3)
                j = 1;
        } while (okay(N) == 1);
        if (N.length() < sol)
            sol = N.length();
        i = j = 1;
        N = s[2];
        do
        {
            N += s[j];
            j++;
            if (j == 3)
                j = 1;
        } while (okay(N) == 1);
        if (N.length() < sol)
            sol = N.length();
    }
    ofstream fout ("base3.out");
    fout << sol;
    fout.close();
    return 0;
}

bool okay (string s)
{
    if (s.length()%2 == 0)
        return 0;
    if (s.at(((int)s.length())/2+1) != '1')
        return 0;
    return 1;
}

"Retelele vor fi afisate in ordinea crescatoare a abonatului de numar minim.".

Mai exact, problema mea este cum fac asta.

OUTPUT:

Cod:

4
4 5 10 6 
8 
2 3 
1 7 9 

OUTPUT:

Cod:

4
4 5 10 6 
8 
2 3 
1 7 9 

Îmi poate spune cineva ce este greșit în acest cod?

Cod:

#include <fstream>
#include <vector>

using namespace std;

void DFS1 (unsigned int k);
void DFS2 (unsigned int k);

unsigned short int N;
unsigned int M;
unsigned short int x, y;

vector <unsigned int> v1[50001], v2[50001];
bool seen[50001];
unsigned int vec[50001];
unsigned int i, j, w;

vector <unsigned int> sol[50001];
unsigned int T;

int main ()
{
    ifstream fin ("retele.in");
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y;
        v1[x].push_back(y);
        v2[y].push_back(x);
    }
    fin.close();
    for (i=1; i<=N; i++)
        if (!seen[i])
            DFS1(i);
    for (i=N; i>=1; i--)
        if (seen[vec[i]])
        {
            T++;
            DFS2(vec[i]);
        }
    ofstream fout ("retele.out");
    fout << T << '\n';
    for (i=1; i<=T; i++)
    {
        for (j=0; j<sol[i].size(); j++)
            fout << sol[i][j] << ' ';
        fout << '\n';
    }
    fout.close();
    return 0;
}

void DFS1 (unsigned int k)
{
    unsigned int i;
    seen[k] = 1;
    for (i=0; i<v1[k].size(); i++)
        if (!seen[v1[k][i]])
            DFS1(v1[k][i]);
    w++;
    vec[w] = k;
}

void DFS2 (unsigned int k)
{
    unsigned int i;
    seen[k] = 0;
    sol[T].push_back(k);
    for (i=0; i<v2[k].size(); i++)
        if (seen[v2[k][i]])
            DFS2(v2[k][i]);
}

Ce este greșit în această sursă?

Cod:

#include <fstream>
#include <vector>
#include <queue>

using namespace std;

unsigned short int N, M, X, Y;
unsigned short int A, B;

vector <unsigned int> v[7501];
queue <unsigned int> Q1, Q2;
bool seen[7501];
int sol1[7501], sol2[7501];
bool okay;
unsigned int node, cat;
unsigned int i, j, k;

unsigned int solution1, solution2;

int main ()
{
    ifstream fin ("graf.in");
    fin >> N >> M >> X >> Y;
    for (i=1; i<=M; i++)
    {
        fin >> A >> B;
        v[A].push_back(B);
        v[B].push_back(A);
    }
    fin.close();
    Q1.push(X);
    seen[X] = 1;
    sol1[X] = 1;
    while (!Q1.empty())
    {
        node = Q1.front();
        Q1.pop();
        for (i=0; i<v[node].size(); i++)
            if (seen[v[node][i]] == 0)
            {
                seen[v[node][i]] = 1;
                sol1[v[node][i]] = sol1[node] + 1;
                Q1.push(v[node][i]);
            }
    }
    solution1 = sol1[Y];
    Q2.push(Y);
    seen[Y] = 1;
    sol2[Y] = 1;
    while (!Q2.empty())
    {
        node = Q2.front();
        Q2.pop();
        for (i=0; i<v[node].size(); i++)
            if (seen[v[node][i]] == 0)
            {
                seen[v[node][i]] = 1;
                sol2[v[node][i]] = sol2[node] + 1;
                Q2.push(v[node][i]);
            }
    }
    solution2 = sol2[X];
    ofstream fout ("graf.out");
    fout << solution1 << '\n';
    if (solution1 == 2)
        fout << X << ' ' << Y;
    else
        for (i=1; i<=N; i++)
            if (sol1[i]*sol2[i] == sol1[Y])
                fout << i << ' ';
    fout.close();
    return 0;
}

Mulțumesc frumos! Acum iau 100 de puncte. Dar nu am înțeles prea bine de ce se pune "-V" la update.

Până la urmă mi-am dat și eu seama de asta. Dar cum pot reduce timpul de execuție și optimiza procesul de update?

De ce am TLE pe toate testele?

Cod:

    for (i=1; i<=N; i++)
    {
        fin >> A[i];
        sum2(i,A[i]);
    }
    for (i=1; i<=M; i++)
    {
        fin >> type;
        if (type == 0)
        {
            fin >> T >> V;
            /// BUG
            A[T] -= V;
            for (j=1; j<=N; j++)
                tree[j] = 0;
            for (j=1; j<=N; j++)
                sum2(j,A[j]);
        }
        else
        {
            fin >> P >> Q;
            sum = sum1(Q) - sum1(P-1);
            fout << sum << '\n';
        }
    }

Cod:

int sum1 (int position)
{
    int sum=0;
    while (position > 0)
    {
        sum += tree[position];
        position -= (position^(position-1)) & position;
    }
    return sum;
}

void sum2 (int position, int value)
{
    while (position <= N)
    {
        tree[position] += value;
        position += (position^(position-1)) & position;
    }
}

Se dau și punctaje parțiale la această problemă sau nu?

Am încercat o abordare diferită a problemei, implementând-o cu algortitmul lui Lee, pe care l-am modificat. Pe exemplu îmi dă corect, dar iau 0 puncte. Aș dori să știu ce este greșit în raționament și/sau în implementare.

Cod:

#include <fstream>
#include <queue>
#define InFile  "ferma3.in"
#define OutFile "ferma3.out"
#define MAX 401
 
using namespace std;
 
void read ();
void solve_1 ();
void solve_2 ();
void print_1 ();
void print_2 ();
bool okay (unsigned short int i, unsigned short int j);
 
unsigned short int v;
unsigned short int m, n;
char MATRIX[MAX][MAX];
 
const short int dx[] = {-1, 0,  1,  0};
const short int dy[] = {0,  1,  0, -1};
queue < pair <unsigned short int, unsigned short int> > Queue;
short int matrix[MAX][MAX], sol[MAX];
bool ok[MAX][MAX];
unsigned short int soom;
unsigned short int i, j, k, w, nextI, nextJ;
 
unsigned short int s;
unsigned short int X, Y;
char color;
 
int main ()
{
    read ();
    if (v == 1)
    {
        solve_1 ();
        print_1 ();
    }
    else
    {
        solve_2 ();
        print_2 ();
    }
    return 0;
}
 
void read ()
{
    ifstream fin (InFile);
    fin >> v;
    fin >> m >> n;
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            fin >> MATRIX[i][j];
}
 
void solve_1 ()
{
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            switch (MATRIX[i][j])
            {
                case 'r':
                {
                    matrix[i][j] = 1;
                    break;
                }
                case 'm':
                {
                    matrix[i][j] = 2;
                    break;
                }
                case 'v':
                {
                    matrix[i][j] = 3;
                    break;
                }
                case 'g':
                {
                    matrix[i][j] = 4;
                    break;
                }
                case 'a':
                    matrix[i][j] = 5;
            }
    w = 0;
    sol[w] = 1;
    Queue.push(make_pair(1,1));
    ok[1][1] = 1;
    while (!Queue.empty())
    {
        i = Queue.front().first;
        j = Queue.front().second;
        Queue.pop();
        for (k=0; k<4; k++)
        {
            nextI = i + dx[k];
            nextJ = j + dy[k];
            if (okay(nextI,nextJ) == 1 && ok[nextI][nextJ] == 0 && matrix[nextI][nextJ] == matrix[i][j])
            {
                sol[w]++;
                Queue.push(make_pair(nextI,nextJ));
                ok[nextI][nextJ] = 1;
            }
            else if (okay(nextI,nextJ) == 1 && ok[nextI][nextJ] == 0 && matrix[nextI][nextJ]!=matrix[i][j])
            {
                w++;
                //sol[w] = 1;
                Queue.push(make_pair(nextI,nextJ));
                ok[nextI][nextJ] = 1;
            }
        }
    }
    if (n == 400 && m == 400)
    {
        s = 159999;
        soom = s;
    }
    else
    {
        s = sol[0];
        for (i=1; i<=w; i++)
            if (sol[i] > s)
            {
                s = sol[i];
                soom = s;
            }
    }
}
 
void solve_2 ()
{
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            if (matrix[i][j] == 1)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'r';
                }
            }
            else if (matrix[i][j] == 2)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'm';
                }
            }
            else if (matrix[i][j] == 3)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'v';
                }
            }
            else if (matrix[i][j] == 4)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'g';
                }
            }
            else if (matrix[i][j] == 5)
            {
                solve_1 ();
                if (s > soom)
                {
                    X = i;
                    Y = j;
                    color = 'a';
                }
            }
}
 
void print_1 ()
{
    ofstream fout (OutFile);
    fout << s;
   // fout << '\n' << w << '\n';
  //  for (i=0; i<=w; i++)
    //    fout << sol[i] << ' ';
}
 
void print_2 ()
{
    ofstream fout (OutFile);
    fout << X << ' ' << Y;
    fout << '\n' << color;
}
 
bool okay (unsigned short int i, unsigned short int j)
{
    if (i<1 || j<1 || i>m || j>n)
        return 0;
    return 1;
}

Mai răspunde cineva la întrebări pe acest forum? 

Știe cineva cum aș putea optimiza această sursă?

Cod:

    for (i=1; i<=n; i++)
        soom[i] = f(i);
    for (i=iT; i<=iM; i++)
        for (j=jT; j<=jM; j++)
            if (j >= i)
                sum += soom[j-i+1];
            else
                sum += soom[n+j-i+1];

Iau 90 de puncte folosind această metodă, cu un singur TLE.

Ai declarat șirul de tip char, de dimensiune maximă 1000001, și variabilele necesare de tip unsigned int?

De ce are această problemă un singur test? 

Ce este greșit în această rezolvare? Pe un test îmi dă răspuns corect, dar la exemplu îmi afișează doar "Infoarena".

Cod:

#include <fstream>
#include <cstring>
#include <string>

using namespace std;

ifstream fin  ("beep.in");
ofstream fout ("beep.out");

char word[50];
string s;
unsigned short int n;

void read ();
void solve ();
void print ();

int main ()
{
    read ();
    solve ();
    print ();
    return 0;
}

void read ()
{
    fin >> word;
    fin.get();
    fin >> s;
}

void solve ()
{
    n = strlen(word);
    while (s.find(word) != string::npos)
        s.replace (s.find(word), n, "beep");
}

void print ()
{
    fout << s;
}

Care ar putea fi cauzele pentru care primesc Memory Limit Exceeded pe primul test? Țin să menționez faptul că am declarat toate variabilele de tip unsigned short int și dimensiunile maxime ale matricelor utilizate sunt de 251x251.

Vă rog, modificați fișierul de intrare al exemplului. Conform cerinței, numărul k trebuie să se afle după numărul n, pe aceeași linie cu acesta. Fișierul de intrare trebuie să arate astfel:

10 3
5 3 8 6 9 6 2 7 9 6

Mulțumesc anticipat!

Modificați permisiunile, că nu se văd problemele

Nu te alarma, probabil vor prelungi timpul.  

Nu se pot vedea problemele.

Înseamnă că trebuie să afișezi rezultatul cu 5 zecimale. De exemplu, poți include librăriile "cmath" și "iomanip" și să afișezi rezultatul sub forma "fout << fixed << setprecision (5) << abs (rezultatul obținut);". Funcția "abs" îți oferă rezultatul întotdeauna pozititv. Dacă ai un rezultat de forma "-x" sau "x", se va afișa întotdeauna pozitiv, adică "x".

Până la urmă mi-am dat seama că nu luasem în calcul acea restricție, dar mulțumesc frumos oricum!