Lets say we have some equation ax+by = gcd(a,b) . I know that there are infinite number of tuples (x0,y0) such that a*x0 + b*y0 = gcd(a,b). But what is the upper bound on the values of x0 and y0 we get from the Extended Euclidean Algo?

The Extended Euclidean algo i am talking about is

int gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1;
    int d = gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

problem link 339C - Ксюша и гири

The editorial of this problem tells us to make a graph of nodes where each node is a tuple (i,j,k). And after making this node we have to find a path from (0,0,1) to some node (x,y,m). Now according to the question, this graph is acyclic and directed. And each node can have 9 outdegree (there are 10 weights to select from but we cant select the previous weight). And the length of the path is m<=1000. Now i cant find a way to find the path from (0,0,1) to (x,y,m). Because i think there can be 9^(1000) possible paths. How to prove that the number of paths we have to check will actually be less so that we dont get a TLE. Please Help!!

Can you guys share some programming competitions that are open for all? i.e it is not necessary to be a college student to participate in them. I just want to know because I dont want to give up CP after college I want to continue after college also.
So i found out that google code jam doesn't require the participant to be a college student. And also Facebook hacker cup. Can you list some more?

Suppose we have 2 arrays of size n (say A and B) and we have to select k indices i1,i2,i3....ik, such that all are valid indices (i.e all belong to [0,n-1) ) .And let valA = $$$\sum_{j=1}^{k} A_{ij}$$$ and let valB = $$$\sum_{j=1}^{k} B_{ij}$$$. Then min(valA,valB) should be maximum. How to solve this? I tried using dp but couldnt figure out how to move from dp[i-1] to dp[i].
Is there any other way to think about it?

Problem link — https://mirror.codeforces.com/problemset/problem/1355/D

I was able to prove that if S>=2*n, then Petya can always win (same logic which is given in the tutorial). But I am not able to prove that if S<2*n then Petya will always lose. How to prove that?