Hi, I'm really new to Flow algorithms and I'm starting with maximum flow using the EdmondsKarp, I've implemented this version, for the test example extracted from SPOJ FASTFLOW the following test-case has a max-flow of 5, my code answers 3. what would be wrong ? Thanks

Test-Case:

4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3

int max_flow(int source, int sink) {
    int residual[MAXN][MAXN]; memset(residual, 0, sizeof(residual));
    while(1) {
        int prev[MAXN]; memset(prev, -1, sizeof(prev));
        int actual[MAXN]; memset(actual, 0, sizeof(actual));
        prev[source] = source;
        actual[source] = INF;
        queue<int> q; q.push(source);
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(int i = 0; i < graph[u].size(); i++) {
                int v = graph[u][i];
                if(capacity[u][v] - residual[u][v] > 0 && prev[v] == -1) {
                    prev[v] = u;
                    actual[v] = min(actual[u], capacity[u][v] - residual[u][v]);
                    if(v != sink) {
                        q.push(v);
                    } else {
                        while(prev[v] != v) {
                            u = prev[v];
                            residual[u][v] += actual[sink];
                            residual[v][u] -= actual[sink];
                            v = u;
                        }
                        goto end;
                    }
                }
            }
        }
        end:;
        if(prev[sink] == -1) {
            int sum = 0;
            for(int i = 0; i < MAXN; i++) {
                sum += residual[source][i];
            }
            return sum;
        }
    }
}

Hi, I have a problem which gives two mazes, and asks if it possible to travel from some vertex (a, b) to vertex (c, d) in A maze and, go from vertex (i, j) to (k, l) in maze B with the same number of steps(the number of steps in the path).

There's a way to check if it's possible to travel in a per-determined number of steps in a graph ?

Hi, I'm stuck in such a problem who ask's for the given set G of points in a plane, for each point i, how many points s are less than an integer D close to point i.

My fist and naive approach was an O(N^2) solution looking for the distance from all points to points, which didn't got TLE.

What is the better approach ?

Hi, I have the following problem, given a number N between 1 and 1000000, print their last non-zero digit from N!.

The only strategy I've got was try to store the last digits of their fatorial, but this strategy fails when the number N reaches '25'. There's an efficient solution ? since the time limit is strict.

This is my actual strategy, storing in mem[i] the last digit of i!:

    ll fat = 1, last = 1;
    for(int i = 1; i <= 1000010; i++) {
        if(i % 5 == 0 || last % 5 == 0) {
            ll tmp = last * i;
            while(tmp % 10 == 0) tmp /= 10;
            last = tmp % 10;
        } else {
            last = (last * i) % 10;
        }
        mem[i] = last;
    }

Hi, I'm in doubt in how to check if there's cycles in a graph meanwhile I do a topological sort.

The only way to implement a topological sort is this one:

void dfs(int x) {
    vis[x] = true;
    for(int u = 0; u < n; u++) {
        if(!vis[u] && graph[x][u] == 1) {
            dfs(u);
        }
    }
    order.push_back(x);
}

but this implementation doesn't check if there's cycles, which modification can I do to check for cycles ?

Hi, I'm strugglin with the follow problem; Given a N * M rectangle with nums between -500 — 500, return the values of the longest sum of cells from cell (0, 0) to cell (N-1, M-1), you can make the moves (i + 1, j), (i, j + 1) and (i, j — 1), you can only visit a cell one time.

I tried the DP strategy:

//dp[i][j] is the longest sum path until the cell (i, j)
//maze[i][j] value in the cell (i, j)
dp[i][j] = max(maze[i][j], max(dp[i - 1][j] + maze[i][j], max(dp[i][j - 1] + maze[i][j], dp[i][j + 1] + maze[i][j])));

this strategy isn't working due to the test case:

81 28 240 10
40 10 100 240
20 180 110 35

the answer is: 1094 this strategy returns: 724.

what is the optimal strategy ? Thanks.

Hi, I'm failing on test case #31 in the problem Dijkstra? from Codeforces Alpha Round #20 (Codeforces format) Link to the Problem, but I'm not able to test it locally because the test case is too big, it's hidden in the submit link.

There's a way to see this full test ? The problem itself is tricky, asking for a as fast as possible Dijsktra implementation, can you guys see what's wrong with this code ? Code

Hi, Searching for how to find if a give graph _G_is Strongly Connected (There's a path from any vertex to any other vertex) I figured out about Kosajaru's Algorithm and Tarjan's Algorithm, but looking in other solutions for problems involving SCC, I've found an interesting approach which does not fit in any of the two algorithm, but worked for me in a problem in SPOJ-BR:

Mounting the Adjacency Matrix:

It's used 2 Matrices, MA and MB:

If there's a Path from Vertex A -> B: MA[A][B] = true; mark the opposite in matrix MB: MB[B][A] = true;

Then: dfs through them, first in MA, if the number of visited vertexes are equals to the number of vertexes in the graph G, then, the graph is strongly connected, if not, dfs though matrix MB, and again, if the number of visited vertexes is the number of vertexes in the graph G, the graph is strongly connected.

Is it a well known algorithm, it works in any case to look for SCC ?

Thanks in advance.

Hi, Today I've faced an interesting geometry problem, which I don't know yet how to solve without TLE.

I'm not posting the link because it's in portuguese, but summarising, there's two points in the cartesian plan, the statement gives it's cordinates, how many 'crossing' (integer cordinates) this segments passes through ?

My approach (TLE) O(N) being N the number of integer x cordinates. I check the slope the line, and iterate over the integer point in the x axis and go checking if the current y value for the actual x is also an integer.

The correct solution is probably an formula which easiely check this points in O(1), there's exists this formula ? what's the correct approach ?

Thanks in advance.

Hi, today I've experienced the weird fact that I'm unable to see the test case which I failed, and the code of other contestants in the Gym problems, I'm practicing in '2011-2012 Stanford Local Contest, 8 October, 2011' problem B: http://codeforces.com/gym/100015/attachments, I'm pretty sure my code is right, but I'm unable to see even my answer for the first test case, which returns to me 'Wrong Answer', does someone knows what is wrong in my code or what is the possible error ?

EDIT: code moved to: http://pastebin.com/creXK21E

Hello everybody; I've been dealing with this problem about a time, but I can't understand what the pretest 2 stands about. take a Look;

Test 2:

7

10 4 6 3 2 8 15

The problem statement says that the displeasure of the i-th walrus is the number if younger walrus between i and the index of the further walrus who has an age less than the age of the _i_th walrus;

On this example take the walrus with age '4', the furthers walrus which is younger than him is the walrus with age 2; this closed interval is about (0-based) 2-3 which are walrus with age 6 and 3, only the walrus with age 3 is younger than walrus with age for. In my mind this result should be:

4 1 1 0 -1 -1 -1 instead of: 4 2 1 0 -1 -1 -1

can someone help me to figure out what is wrong ?

I was not able to solve the E problem in time of the contest, I'm dealing with a wrong answer in Test 2, In my solution, I'm always looking for the nearest room, I'm wondering if this greedy approach is wrong ?