Hi, I wanted to try this contest at the Gym because the description says the statements are available in english, but none of the PDFs is in Enligsh. Does someone have the english statements? Thanks

Hi everyone, I've been trying this problem: http://main.edu.pl/en/archive/oi/19/okr

I'm getting 67/100 using hashing, and the fact that the hash of a string of the form xxx..xx (repetead K times) can be calculated in O(lgK) once you have the hash for x.

But I don't know how to improve to get 100 points. Any hint?

Hi everyone,

I'm trying to solve this problem.

I recently solved problem "2361-Areas" at ZOJ, for an explanation you could see my post here.

Now I think problem CIRUT from SPOJ could be solved in a similar way since areas covered by more than one circle are convex. I still haven't thought about how to solve it for areas covered by only one circle.

The problem is that since there area about N^2 areas if I test in O(n) how many circles cover it I would get TLE. So how could I do this faster? or is there another approach to the problem?

Hi everyone, I'm trying to solve this problem however I get TLE. The problem asks for points such that gcd(x,y,z) = 1 inside of 0 <= x < L, 0 <= y < H, 0 <= z < W.

I'm using inclusion-exclusion with the mobius function to find the answer.

First I wrote a version going through all i from 1 to X: http://pastebin.com/UsShb6zF but I got TLE.

So I thought of optimizing it by going only through square free numbers, because in these numbers the value of the mobius function is different from zero, but I still get TLE.

Any idea about how to optimize it further?

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 1000000

int mu[MAXN + 1],factor[MAXN + 1];
int sqfree[MAXN + 1],sz = 0;

long long visible(int X, int Y){
    long long ret = 0;
    
    for(int i = 0;i < sz && sqfree[i] <= X;++i){
        int cur = sqfree[i];
        ret += mu[cur] * (long long)(X / cur) * (Y / cur);
    }
    
    return ret;
}

long long visible(int X, int Y, int Z){
    long long ret = 0;
    
    for(int i = 0;i < sz && sqfree[i] <= X;++i){
        int cur = sqfree[i];
        ret += mu[cur] * (long long)(X / cur) * (Y / cur) * (Z / cur);
    }
    
    return ret;
}

int main(){
    memset(factor,-1,sizeof factor);
    mu[1] = 1;
    sqfree[sz++] = 1;
    
    for(int i = 2;i <= MAXN;++i){
        if(factor[i] == -1){
            mu[i] = -1;
            
            if(i <= MAXN / i)
                for(int j = i*i;j <= MAXN;j += i)
                    factor[j] = i;
        }else{
            int cont = 0,aux = i,p = factor[i];
            
            while(aux % p == 0 && cont < 2){
                aux /= p;
                ++cont;
            }
            
            if(cont == 2) mu[i] = 0;
            else mu[i] = -mu[i / p];
        }
        
        if(mu[i] != 0) sqfree[sz++] = i;
    }
    
    int X,Y,Z;
    
    while(scanf("%d %d %d",&X,&Y,&Z) == 3){
        --X; --Y; --Z;
        
        long long ans = visible(X,Y,Z) + visible(X,Y) + visible(Y,Z) + visible(Z,X);
        
        if(X >= 1) ++ans;
        if(Y >= 1) ++ans;
        if(Z >= 1) ++ans;
        
        printf("%lld\n",ans);
    }
    
    return 0;
}

Hi everyone, I've been trying this problem, my approach was using sweep line after ordering the queries by its ending and considering only the last ocurrence of a number. However it fails for cases like:

N = 4

4 -2 3 -2

Q = 1

1 4

where the answer is 4,-2,3 which contains a -2 that isn't the last one, hence I return 7, but the correct answer is 5.

Any ideas on how to solve the problem?

My code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 100000
#define MAXQ 100000

int a[MAXN],b[MAXN],pos[MAXN];
long long pref[4 * MAXN],suff[4 * MAXN],sum[4 * MAXN],best[4 * MAXN];
long long best_suff;

long long query(int node, int l, int r, int x, int y){
    if(r < x || l > y) return 0;
    
    if(x <= l && r <= y){
        long long ret = max(best[node],best_suff + pref[node]);
        best_suff = max(suff[node],best_suff + sum[node]);
        return ret;
    }else{
        int mi = (l + r) >> 1;
        long long ret1 = query(2 * node + 1,l,mi,x,y);
        long long ret2 = query(2 * node + 2,mi + 1,r,x,y);
        return max(ret1,ret2);
    }
}

void update(int node, int l, int r, int x, int val){
    if(r < x || l > x) return;
    
    if(l == r){
        pref[node] = suff[node] = best[node] = max(0,val);
        sum[node] = val;
    }else{
        int mi = (l + r) >> 1;
        
        update(2 * node + 1,l,mi,x,val);
        update(2 * node + 2,mi + 1,r,x,val);
        
        pref[node] = max(pref[2 * node + 1],sum[2 * node + 1] + pref[2 * node + 2]);
        suff[node] = max(suff[2 * node + 2],sum[2 * node + 2] + suff[2 * node + 1]);
        sum[node] = sum[2 * node + 1] + sum[2 * node + 2];
        best[node] = max(suff[2 * node + 1] + pref[2 * node + 2],max(best[2 * node + 1],best[2 * node + 2]));
    }
}

vector<int> q[MAXN],id[MAXN];
long long ans[MAXQ];

int main(){
    int N;
    scanf("%d",&N);
    
    for(int i = 0;i < N;++i){
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    
    sort(b,b + N);
    int m = unique(b,b + N) - b;
    memset(pos,-1,sizeof pos);
    
    
    int Q;
    scanf("%d",&Q);
    
    for(int i = 0,l,r;i < Q;++i){
        scanf("%d %d",&l,&r);
        q[r - 1].push_back(l - 1);
        id[r - 1].push_back(i);
    }
    
    for(int i = 0;i < N;++i){
        update(0,0,N - 1,i,a[i]);
        
        int ind = lower_bound(b,b + m,a[i]) - b;
        
        if(pos[ind] != -1)
            update(0,0,N - 1,pos[ind],0);
        
        pos[ind] = i;
        
        for(int j = q[i].size() - 1;j >= 0;--j){
            best_suff = 0;
            ans[ id[i][j] ] = query(0,0,N - 1,q[i][j],i);
        }
    }
    
    for(int i = 0;i < Q;++i)
        printf("%lld\n",ans[i]);
    
    return 0;
}

Could anyone give me a hint on how to solve this problem?

I solved POJ 3167 in which the problem was based using a modified KMP, but i couldn't come up with anything that solves UNTITLED.

Hi everyone, today I solved this problem using Dynamic Programming, the state is easy to get (n,c1,c2,c3) and a useful observation is to notice that if you have n,c1 and c2 then c3 can be found, so it isn't necessary for it to be part of the state. With this and some prunning it is enough to get AC (I though I would get TLE). I see solutions that are much faster, how can this be done?

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MOD 100000000000000000LL

int r[125];
long long memo[126][126][126];

long long solve(int pos, int c1, int c2, int c3){
    if(pos == -1){
        if(c1 || c2 || c3) return 0;
        return 1;
    }
    
    long long &ret = memo[pos][c1][c2];
    
    if(ret == -1){
        ret = 0;
        
        for(int i = 0;i <= c1;++i){
            for(int j = max(0,r[pos] - i - c3);j <= c2 && i + j <= r[pos];++j){
                int k = r[pos] - i - j;
                
                ret += solve(pos - 1,c1 - i,c2 - j,c3 - k);
                if(ret >= MOD) ret -= MOD;
            }
        }
    }
    
    return ret;
}

int main(){
    int n,c1,c2,c3;
    
    scanf("%d %d %d %d",&n,&c1,&c2,&c3);
    
    int diff = c1 + c2 + c3;
    
    for(int i = 0;i < n;++i){
        scanf("%d",&r[i]);
        diff -= r[i];
    }
    
    if(diff != 0) printf("0\n");
    else{
        memset(memo,-1,sizeof memo);
        printf("%lld\n",solve(n - 1,c1,c2,c3));
    }
    
    return 0;
}

Hi everyone, I'm getting TLE in this problem, I'm trying and offline approach (I was getting RE doing it online), solving only for values of v that are given in the queries, I find the adjacents groups of numbers >= v in O(n) using 2 pointers.

The complexity is O(N x (#different values of v) + QlgQ).

Could someone suggest me an optimization or different approach? Thanks :)

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int a[100000];
long long cont[100001];
long long ans[100000];

struct query{
    int v,a,b,id;
    
    query(){}
    
    bool operator < (query X)const{
        return v < X.v;
    }
}q[100000];

int main(){
    int N,Q;
    
    scanf("%d %d",&N,&Q);
    
    for(int i = 0;i < N;++i)
        scanf("%d",&a[i]);
    
    for(int i = 0;i < Q;++i){
        scanf("%d %d %d",&q[i].v,&q[i].a,&q[i].b);
        q[i].b = min(q[i].b,N);
        q[i].id = i;
    }
    
    sort(q,q + Q);
    
    for(int i = 0;i < Q;){
        int e = i;
        
        while(e < Q && q[e].v == q[i].v) ++e;
        
        int v = q[i].v;
        memset(cont,0,sizeof cont);
        
        for(int j = 0;j < N;){
            if(a[j] < v) ++j;
            else{
                int e2 = j;
                
                while(e2 < N && a[e2] >= v) ++e2;
                
                int m = e2 - j;
                
                for(int k = 1;k <= m;++k)
                    cont[k] += m + 1 - k;
                
                j = e2;
            }
        }
        
        for(int j = 1;j <= N;++j)
            cont[j] += cont[j - 1];
        
        for(int j = i;j < e;++j)
            ans[ q[j].id ] = (q[j].a <= q[j].b? cont[ q[j].b ]- cont[ q[j].a - 1 ] : 0);
        
        i = e;
    }
    
    for(int i = 0;i < Q;++i)
        printf("%lld\n",ans[i]);
    
    return 0;
}

Hi everyone, could someone help me find my mistake in this problem. Basically what I do is improve the obvious DP approach (with state : position, last color, and how many consecutives carpets were equal) by considering only important indexes in the interval [1,L] (these are 1,L,all s_i, and all e_i + 1).

Code: http://pastebin.com/X2uYYFNH

As the title says, in a graph where the distance of going between two nodes is the concatenation of the strings in the edges along the path between this two verticesm, and we want to find the lexicographically shortest distance, what distance function and which algorithm can we use to solve this kind of problems?

I was trying to solve this problem, and implement a code which uses the Floyd-Warshall algorithm, but there is a problem with cases like this:

V = 3, E = 3, s = 0, e = 2 0 -> 1 a 0 -> 1 ab 1 -> 2 c

The code returns "ac", but the right answear is "abc".

Link

Does someone know a special fact about this conjecture that could help to get a complexity lower than O(180*n), which is the one you get using a dp approach, I tried these two codes:

http://ideone.com/XN4td http://ideone.com/cWhNR (tried to use pointers to speed it up)

but both give me TLE.

Hi everyone, so I found this problem today, and it seems like a really obvious bipartite matching, but I've been getting TLE in it. Is there some faster way to solve it?

Hi everyone, I found this problem today, the small n suggested to use a bitmask, so I tried a DP with complexity O(L·n·2ⁿ) plus some preprocessing using KMP algorithm to find matches.

You can see my code here.

At first I got TLE, I wask doing a for loop to go through all bits of the mask at the dp part, I changed that to use __builtin_ctz in order to access only position with a bit set to 1 in every iteration, that should have cut down the time to the half, since it goes from n·2ⁿ combinations to n·2^n - 1, and that gave me an AC.

But I see really faster solutions, is there some additional optimization? or maybe another approach?

Link

Hi everyone, today i saw this problem, and since i'm usually not good with 3D geometry, i tried to turn it into a linear algebra problem using barycentric coordinates. So if the vertices of the first triangle are A1, B1, C1 and the vertices of the second triangle are A2, B2, C2, we can represent points inside the first triangle like: A1*w1 + B1*w2 + C1*w3, such that w1+w2+w3 = 1, and we can get a similar equation for points inside the second one: A2*w4 + B2*w5 + C2*w6, such that w4+w5+w6 = 1. We also need 0 <= wi <= 1, for every 1 <= i <= 6. Now we can make an equation for the common points:

A1*w1 + B1*w2 + C1*w3 = A2*w4 + B2*w5 + C2*w6

which is actually two equations, one for X's and another for Y's.

Now we could work with 4 equations and maybe reach some conclusion by looking at the rank of the system of equations. But I don't have and idea about how to deal with the inequalities 0 <= wi <= 1.

Can the problem be solved this way? Anyways I would also be interested in another way to solve, or other problems where barycentric coordinates can be used.

Although I didn't passed this problem during the contest, I really enjoyed it.

The reason is I never I hadn't thought before about solving "point in a polygon" queries in a more efficient way other than using O(n) algorithm for every query.

But after getting hacked, and trying to optimize my code, I noticed something nice. If we use the ray tracing algorithm for one point inside a convex polygon, then we worry bout at most four sides of the polygon every time (I assume we are using the Ray casting algorithm), and this combines really nicelly with a sweep line approach, in which you only keep the interesting sides, and discard them when they can't be intersected by the points that follow.

Implementation : 1398412

Link

I'm trying to understand when there is a solution (even though it may have more than 500 moves).

It can't always be done with one divisor, for example A = 4, B = 9 (4->6->9), but I think it can always be done with two divisors, a proof of this would be related somehow to Bezout's identity. Say we pick d1 divisor of A, and d2 divisor of B then we can find integers x,y such that

d1 * x + d2 * y = B - A

since the gcd of d1 and d2 divides B — A, the thing is that one of x and y could be negative. Is there a way to make both positive?

I've tried submitting a solution to problem 120J - Minimum Sum : 1350678, 1350695

But I get Idleness limit exceeded on test 1, I tested my code using Custom Test, but it seems to be working Ok, how can I fix this?

Link

I've been solving some problem about DFS applications, this is the first one I do working with directed graphs. First I established that the following conditions should be enough for a graph to be a cactus, after doing a DFS and getting the DFS tree:

• DFS tree should contain all node
• There are no cross edges or forward edges
• No edge is a bridge, so every edge in the tree, has a back edge covering it
• Back edges don't intersect (no edge is covered by two back edges) and they don't overlap.
• Every node with two or more sons (except the root) should have a back edge starting in it.
• Previous conditions are enough for the graph to be Strongly connected.

However I'm getting WA, could it be an implementation mistake? or some error in the conditions I've assumed?

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAXN 10000
#define MAXE 10000

int E,to[MAXE],nxt[MAXE],last[MAXN];

void add_edge(int u, int v){
    to[E] = v; nxt[E] = last[u]; last[u] = E++;
}

int n,cont,parent[MAXN],level[MAXN],sons[MAXN],back[MAXN];
bool done[MAXN],forward,cross;

void dfs(int pos, int lvl){
    level[pos] = lvl;
    sons[pos] = 0;
    ++cont;
    
    for(int e = last[pos];e != -1;e = nxt[e]){
        int x = to[e];
        
        if(done[x]) cross = true;
        else if(parent[x] != -1){
            if(level[x] > level[pos]) forward = true;
            else back[pos] = (back[pos] == -1? level[x] : -2);
        }else{
            parent[x] = pos;
            ++sons[pos];
            
            dfs(x,lvl + 1);
        }
    }
    
    done[pos] = true;
}

bool is_cactus(){
    if(cont < n || forward || cross) return false;
    
    for(int i = 0;i < n;++i)
        if(back[i] == -2) return false;
    
    for(int i = 0;i < n;++i)
        if(i != 0 && sons[i] > 1 && back[i] == -1)
            return false;
    
    for(int i = 0;i < n;++i){
        if(sons[i] == 0){
            int e = level[i],pos = i;
            
            while(pos != 0){
                if(level[pos] == e){
                    if(back[pos] == -1) return false;
                    e = back[pos];
                }else if(back[pos] != -1) return false;
                
                pos = parent[pos];
            }
        }
    }
    
    return true;
}

int main(){
    int T,m;
    
    scanf("%d",&T);
    
    while(T--){
        scanf("%d %d",&n,&m);
        
        memset(last,-1,sizeof last);
        E = 0;
        
        for(int i = 0,u,v;i < m;++i){
            scanf("%d %d",&u,&v);
            add_edge(u,v);
        }
        
        memset(back,-1,sizeof back);
        memset(parent,-1,sizeof parent);
        memset(done,false,sizeof done);
        forward = cross = false;
        parent[0] = -2;
        cont = 0;
        
        dfs(0,0);
        
        puts(is_cactus()? "YES" : "NO");
    }
    
    return 0;
}

For this problem, first I tried an O(mn) approach (http://ideone.com/rDWvZ) which gave me TLE at pretests.

Then I tried to search for a way to use data structures to speed up the process, but didn't get to anything that could work. Then I noticed that if I precalculated the answer for some groups, the minimum, and the maximum in those groups, I would have enough information to join those pieces and get answers for intervals. So with this, I speed up my solution to O(m * sqrt(n)) which should pass in time: http://ideone.com/y2kEV

Right now I'm getting WA 4, but the case is too big to debug it. Could someone please tell me why it fails?

Cartesian tree (Treap):

Implicit Cartesian Tree:

Hi, I've solved this problem before with O(N^2 lgN) algorithm. For example: http://pastie.org/3129354

But today I got to this problem: http://www.spoj.pl/problems/CHASE/
I got TLE with O(N^2 lgN) algorithm, and a O(N^2) algorithm is mentioned in comments, could someone explain how it works.

N means the number of points given.

Hi, I was trying to solve this problem : http://livearchive.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=2065

However I get TLE, the complexity of my algorithm is O(n^2 lg n) which I think is enough. So I was wondering if using atan2 to order points by polar angle is slow?

Code : http://pastie.org/3105825