Hi,

I'm having a hard time trying to figure out an efficient solution to problem J — Jimi Hendrix from Petrozavodsk Winter Training Camp 2016.

Do you guys have any tips ?

Thanks

Hi, I took part in HackerEarth's Star Wars the Code Wars last Sunday, and there's is a problem that is not solved by anyone yet Link.

My idea was to incrementally obstruct the vertexes that appears the most in the counting of shortest paths, but it doesn't work. Do someone have an optimal idea ?

Thanks

Hi CF,

I'd like to know if there's a platform where it's possible to simulate old ICPC regional contests with teams that participated in the regional in the score (similar to Codeforces Gym ghosts).

Currently, we train creating contests in a2oj, which is fine, but without feedback from which problems other teams are solving, the contest dynamic is way different.

Thanks

Hi,

I've just learned about how to calculate probabilities of certain problems (usually with cyclic states) using systems of linear equations (LIM.

Now, facing a harder problem, I have to calculate an expected value in the same fashion. To calculate simple probabilities, I assume that every variable in the system is the probability of some event (in LIM above, I supposed that an variable x[i] is the probability to go from node i to node 300).

How to build a system of equations to get an expected value ?

Link to the problem

Thank you

Hi,

I've just realized that SGU is not working. Is it on maintenance or it's gone ?

Link

As I posted in the official thread, I don't think it's a good decision, actually, I think it one more step for TopCoder fall.

Hello,

I recently solved problem RSA. But one detail confused me. One of the needs of the problem is to find the modular inverse of one number A module MOD. I always computed this operation with Euler's theorem stated here Theorem. But in this problem, surprisingly, it doesn't work, and I had to compute this modular inverse though the Extended GCD algorithm. Is there any cases which Euler's theorem doesn't work ?

Euler's theorem Code (I've used this code in dozens of problems without trouble)

Extended GCD Code

Hi.

I'm trying to solve this problem from Live Archive Link.

I'm receiving Wrong Answer and the test data isn't available online. To briefly explain my solution, I pre-process the hashing function for the whole string, and them take the hash of the slices I want from this array and apply it's inverse module to normalize the prime powers. Is there something wrong with this approach ?

My Code

Thanks in advance.

Hey.

Brazil's first phase of ICPC 2014/2015 Regional will happen this next Saturday (09/13/2014). The contest will happen in the same time in the UVA system.

Link

Hello, I'm currently learning how to use matrix exponentiation to solve linear recurrence relations, and I'm in doubt on how to build transformation matrices, for example.

Let f(n) = 2 * f(n - 1) + 2 * (f - 2) + 2 * f(n - 3) + f(n - 4)

With f(1) = a, f(2) = b, f(3) = c, f(4) = d

The vector v with the initial values should be

How to build it's transformation matrix ?

Hello, today I've found an interesting problem in Live Archive Link. Suddenly I noticed that it's very similar to an old problem form the brazilian version of spoj Link which I also never managed to solve.

My first solution for the first problem is a simple brute-force (with a low constraint 'N <= 10') I thought it was feasible. But this full brute-force O(N!*6^N) clearly exceeded the time limits.

Explaining my brute-force solution, I try all possible permutations orders for the prisms and then, backtrack on it's biggest pyramid possible (trying all it's faces)

Could you give me some ideas on how to solve it in time ?

Hi, I'm trying to solve this problem: Link

I know how to solve it in O(N * M) per query (using bfs or dfs) to find the components in the matrix obeying the constraints, but this problem asks for a faster approach (matrix can be 1000 * 1000, and 10^5 queries), how to do it ?

Hello, I'm trying to solve this problem from Polish Olympiad of Informatics Link. The problem seems to be straight forward, but I'm not able to figure out the optimal strategy. Currently, I think the optimal strategy is to always let Alice to take only the biggest card, an then, Bob take all the other cards, this, due to the first example which seems that points are not cumulative. Do you have any other clue to the 'optimal' strategy ?

Hello.

I'm trying to solve Palindromic Paths Link. Given a graph with letters in the edges, find longest and smallest palindrome from vertex 0 to vertex N — 1. My current solution based on a backtracked dfs easily exceed the time limits, do someone know a faster way to find it ?

Hi, the South American ICPC regional phase took part yesterday. I wasn't able to solve the problem Link. Some contestants said to me that it's solved by max flow, do someone know another solution or have a clue on how to build the flow graph ? Thanks in advance.

Hi, I've been in trouble trying to solve: Link. It's a version of the equipment-replacement problem, but it also asks for show the 'equipment change' decisions.

I already have a dynamic programming solution working to find which is the best cost, but my attempts to store the path as well aren't even close to right results.

I've already tried to store this info with the cost updates inside the recursion, but it didn't worked though.

Code

Hello, I'm trying to solve this problem Link. The problem statement is available in LiveArchive in English.

In the Brazilian SPOJ, the time-limit is quite strict, as the problem resumes to a grid shortest path, I choose the A* algorithm, which generally is faster than Djikstra and it's heuristics fits perfectly in 2-dimensional grids, but my solution isn't fast enough. How can I optimize more the A* ? The current code is:

struct MyLess {
    bool operator () (int x, int y) {
        return f[x] > f[y];
    }
};

int func (void) {
    int i, j;

    dist[conv(RF,CF)] = 0;
    vis[conv(RF,CF)] = 0;

    priority_queue<int, vector<int>, MyLess> q;

    q.push(conv(RF, CF));

    for ( ; !q.empty(); ) {
        int now = q.top(); q.pop();

        if (vis[now]) {
            continue;
        }

        vis[now] = 1;

        if (now == conv(RT, CT)) return dist[now];

        pair<int, int> od = rev(now);

        for (i = 0; i < 24; i++) {
            int ni = od.first + dx[i];
            int nj = od.second + dy[i];

            int next = conv(ni, nj);

            if (ni <= 0 || nj <= 0 || ni > R || nj > C || graph[next] == 1 || vis[next]) continue;

            if (next >= 0 && next < R * C) {
                int next_cost = dist[now] + ct[i];
                int heuristic = abs(ni - RT) + abs(nj - CT);

                if (next_cost < dist[next]) {
                    dist[next] = next_cost;
                    f[next] = heuristic + next_cost;
                    q.push(next);
                }

            }
        }
    }
    return dist[conv(RT,CT)];
}

Hi, as a curiosity, and to propose an 'recreational' thread in Codeforces, let's discuss here your coding environment. Which languages and ide do you use, Which OS, Why do you use them ?

Hello, I'm trying to solve the problem Tax;

In a first glance, it looks like a little modified Dijksta algorithm, using the weight as the max value of the last weight edge weight and the current weight, like the code I did here.

But unfortunately this idea only work for 3 test cases, can you point what is wrong with this code, or the right idea for tackle this problem ?

Thanks in advance.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <memory>
#include <iomanip>
#include <numeric>
#include <functional>
#include <new>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <cctype>
#include <ctime>

#define REP(i, n) for(int (i) = 0; i < n; i++)
#define FOR(i, a, n) for(int (i) = a; i < n; i++)
#define FORR(i, a, n) for(int (i) = a; i <= n; i++)
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
#define sz(n) n.size()
#define pb(n) push_back(n)
#define all(n) n.begin(), n.end()

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

using namespace std;

typedef long long ll;
typedef long double ld;

const ll INF = 1000010100980980LL;
const int MAXN = 100009;
int N, M, a, b, c;
vector<pair<int, int> > graph[MAXN];
ll dist[MAXN];

ll func(int hashiri, int saigo) {
    for(int i = 0; i <= N; i++) dist[i] = INF;

    dist[hashiri] = 0LL;
    priority_queue<pair<int, int> > q;

    //Last bigger, index;
    q.push(make_pair(0, hashiri));

    while(!q.empty()) {
        int last = q.top().first, index = q.top().second; q.pop();

        for(int i = 0; i < graph[index].size(); i++) {
            int next = graph[index][i].first, cost = graph[index][i].second;
            int real_cost = max(cost, last);

            if(next == saigo) real_cost += cost;

            if(dist[index] + real_cost < dist[next]) {
                dist[next] = dist[index] + real_cost;
                q.push(make_pair(cost, next));
                printf("%d %d\n", index, next);
            }
        }
    }

    return dist[saigo];
}

int main(void) {
    scanf("%d%d", &N, &M);

    REP(i, M) {
        scanf("%d%d%d", &a, &b, &c);
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    printf("%lld\n", func(1, N));

    return 0;
}

Hello, I'm getting WA in Test 3 in Codeforces Round 146 — B — Easy Number Challenge, In my computer (Windows 7 Professional — JDK 1.7.9) my Code gives the right answer (3076687) in both Eclipse and IDEA IntelliJ, and I tried submissions in both Java 6 and Java 7. Does someone know what's wrong ? Thanks in advance.

Submission Link 1 Submission Link 2

Hello, I'm trying to solve ZOJ — Fire Net problem, reading the statement, it looks like a backtracking for all the possible locations for the guns, I'm doing int, check all possible combination of valid locations for the guns. I'm getting the right answers for the example case, but WA in the submission. Is this the right approach ?

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <memory>
#include <iomanip>
#include <functional>
#include <new>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <climits>
#include <cctype>
#include <ctime>

#define REP(i, n) for((i) = 0; i < n; i++)
#define FOR(i, a, n) for((i) = a; i < n; i++)
#define FORR(i, a, n) for((i) = a; i <= n; i++)
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++)
#define sz(n) n.size()
#define pb(n) push_back(n)
#define all(n) n.begin(), n.end()

using namespace std;

typedef long long ll;
typedef long double ld;

int a, b, i, j, k, n, ans;
char maze[10][10];

int rec(int i, int j, int now) {
    maze[i][j] = 'U';
    for(k = i + 1; k < n && maze[k][j] != 'X'; k++) maze[k][j] = 'P';
    for(k = i - 1; k >= 0 && maze[k][j] != 'X'; k--) maze[k][j] = 'P';
    for(k = j + 1; k < n && maze[i][k] != 'X'; k++) maze[i][k] = 'P';
    for(k = j - 1; k >= 0 && maze[i][k] != 'X'; k--) maze[i][k] = 'P';

    if(now > ans) {
        ans = now;
    }

    for(a = 0; a < n; a++) for(b = 0; b < n; b++) {
        if(maze[a][b] == '.') rec(a, b, now + 1);
    }

}

int main(void) {
    //freopen("i.in", "r", stdin);
    while(scanf("%d", &n) == 1 && n != 0) {
        REP(i, n) {
            scanf("%s", maze[i]);
        }
        ans = 0;
        REP(i, n) REP(j, n) {
            if(maze[i][j] == '.') {
                rec(i, j, 1);
            }
            REP(a, n) REP(b, n) if(maze[a][b] != 'X') maze[a][b] = '.';
        }
        printf("%d\n", ans);
    }
    return 0;
}

Hello, I'm dealing with a persistent wrong answer in this problem Link As the statement says, you have to calculate the flow from vertex 1 to N, and you an only go to down vertexes(ie. vertexes with lower values), in my code I check the flow from 1 to N and print in, does someone already solved this problem ? Could you point where's the mistake in my code. Thanks in advance.

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <utility>
#include <functional>
#include <valarray>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>

using namespace std;

#define REP(i, n) for(i = 0; i < (n); i++)
#define FOR(i, a, n) for(i = a; i < n; i++)
#define REV(i, a, n) for(i = a; i > n; i--)

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

typedef long long ll;
typedef long double ld;

#define MAXN 210
#define INF 100000

int i, j, test, n, m, next, capacity[MAXN][MAXN];
vector<int> graph[MAXN];

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 ans = 0;
            for(int i = 1; i <= n; i++) {
                ans += residual[source][i];
            }
            return ans;
        }
    }
    return 0;
}

int main(void) {
    scanf("%d", &test);
    for(; test-- > 0; ) {
        scanf("%d", &n);
        REP(i, MAXN) {
            graph[i].clear();
        }
        memset(capacity, 0, sizeof(capacity));
        REP(i, n-1) {
            scanf("%d", &m);
            REP(j, m) {
                scanf("%d", &next);
                graph[i+1].push_back(next);
                graph[next].push_back(i+1);
                capacity[i+1][next] += 1;
                capacity[next][i+1] += 1;
            }
        }
        printf("%d\n", max_flow(1, n));
    }
    return 0;
}

Hello, I'm a pretty beginner with segment trees and I'm in doubt on this problem, I can build the tree but the queries for look for the right interval with the biggest sum is wrong, can someone point out what is wrong with my method func. Thanks in advance.

Problem Statement

#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <utility>
#include <functional>
#include <valarray>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <climits>

using namespace std;

#define REP(i, n) for(i = 0; i < (n); i++)
#define FOR(i, a, n) for(i = a; i < n; i++)
#define REV(i, a, n) for(i = a; i > n; i--)

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

typedef long long ll;
typedef long double ld;

#define MAXN 5000010
#define INF 1000001000

int n, a[MAXN], t[4*MAXN];
int b, c, i, m, tmp, x;

void build (int a[], int v, int tl, int tr) {
    if (tl == tr)
        t[v] = a[tl];
    else {
        int tm = (tl + tr) / 2;
        build (a, v*2, tl, tm);
        build (a, v*2+1, tm+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

int func(int v, int tl, int tr, int l, int r) {
    if(l > tr || r < tl) {
        return -INF;
    }
    if(tl >= l && tr <= r) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    int p1 = func(2 * v, tl, (tl + tr) / 2, l, r);
    int p2 = func(2 * v + 1, ((tl + tr) / 2) + 1, tr, l, r);

    if(p1 > p2) return p1;
    else return p2;
}
int main(void) {
    freopen("i.in", "r", stdin);
    scanf("%d", &x);
    REP(i, x) {
        scanf("%d", &a[i+1]);
    }
    build(a, 1, 1, x+1);    
    scanf("%d", &m);
    REP(i, m) {
        scanf("%d%d", &b, &c);
        printf("%d\n", func(1, 1, x+1, b, c));
    }
    return 0;
}

Hi, I've just learning the algorithm to find bridges in a graph, it's a modification of an dfs Code

But now I'm facing an problem, how do I check for 'bridges' connecting to 1 pre-determined vertex(example: being a the vertex I want to check for bridges to it, if the edge n is removed, there won't be a path to some vertex 'x' to the main vertex a).

I've tried to use the simple approach to look for bridges, but it clearly don't work, which'd be the right approach ?

by the way, the problem is this one: Link

Hi, is it possible to check if there's a path with size from a node 'a' to a node 'b' with size 'N' ? I've tried an BFS approach, using the 'visited' array with integer with a limit in the number 'N', but this strategy didn't worked.

Do you have any idea, or there's a well known algorithm for this ? (I seached, but didn't found anything)