SRM 626: Not a math person

Another SRM.

Div1 250: The one with dice

Alice throws `a` dice with `b` faces each (Numbered 1 to `b`, all equally likely). Bob throws `c` dice with `d` faces each (same). The score is the sum of all the dice rools each player gets. Return the expected value of Alice score IN CASES SHE WINS. If it is impossible for Alice to win, return -1. All `a,b,c,d` are at least 1 and at most 50

Okay... For each die, can you calculate the probability to get `X` as the total result? Well, yes. This is an `O(a^2 b^2)` dynamic programming thing. Possibly other good methods too. The thing is that we can precalculate two lists that give us the probability Alice gets `X` and the probability Bob gets `Y`.

Then for each pair `(X,Y)` it is easy to get the probability that Alice gets X AND Bob gets Y. So consider only the cases `(X > Y)` and find the probability Alice wins. If the probability is 0, return -1.

Once again, for each pair `(X,Y)`, find its probability, if Alice wins in this case, then the probability that Alice gets that score, provided Alice wins the whole game is `P_A(X) * P_B(Y) / P_"Alice wins"`. The sum of these probabilities multiplied by `X` is the expected value.

My first instinct was to use Bayes theorem , maybe there is a way to simplify things with it?

Total complexity is `O(a^2 b^2 + c^2 d^2 + abcd)`, so around 3* 2500 * 2500 in the worst case :)

vector<double> findProbabilities(int a, int b)
{
    double dp[51][2501];
    
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1.0;
    
    for (int n = 1; n <= a; n++) {
        
        for (int y = 1; y <= n*b; y++) {
            dp[n][y] = 0.0;
            for (int x = 1; x <= b && x <= y; x++) {
                dp[n][y] += dp[n-1][y - x] / b;
            }
        }
    }

    
    vector<double> res(a*b + 1, 0.0);
    for (int i = 0; i <= a*b; i++) {
        res[i] = dp[a][i];
    }
    return res;
}

double getExpectation(int a, int b, int c, int d)
{
    vector<double> Alice,Bob;
    
    Alice = findProbabilities(a,b);
    Bob   = findProbabilities(c,d);
    
    double pw = 0;
    for (int A = a; A <= a*b; A++) {
        for (int B = c; B <= c*d; B++) {
            if (A > B) {
                pw += Alice[A] * Bob[B];
            }
        }
    }
    
    if (pw <= 0.0) {
        return -1.0;
    }
    
    double ew = 0;
    for (int A = a; A <= a*b; A++) {
        for (int B = c; B <= c*d; B++) {
            if (A > B) {
                double p = Alice[A] * Bob[B]; //probability this happens
                ew += A * (p / pw);
            }
        }
    }
    return ew;
}
};

Div1 medium the one with negative edges

A directed graph, possibly with multiple edges and loops and cycles. Find the minimum cost to move from a vertex to another.... EXCEPT that you have at most `X` opportunities to make the cost of an edge negative when you use it. `X` can be is obscenely large.

Okay, no idea.

Div1 hard: The one with mirrors

There is a rectangle with mirror sides of some dimensions. Find each angle from which you can cast a ray from the bottom-left corner in such a way that the ray of light bounces exactly `b` times before touching any corner and finally reaches the top-right corner. `b` is at most 1000000000. For each of those angles, add the total distance traveled by the ray before hitting the corner. Calculate all that modulo 1000000007

I thought I had a good chance to solve this problem. Because of the old codejam problem Hall of mirrors I knew a lot of properties about these rectangles of mirror sides. For example, we could imagine that a bounce is the same as moving around a grid made of rectangles of those mirrors. I would have more luck explaining this if I had time to inkscape....

The thing is that if you imagine a grid of mirrors and make the coordinates in each of these mirror corners `(x,y)` . Then moving from the origin to this coordinate is valid if and only if: `(x,y)` are coprime and also the coordinates should share a diagonal with `(1,1 + b)`. In addition, `b` must be even.

Unfortunately, because `b` can be very large, just knowing that isn't enough. It needs some mathematical trick to avoid doing an `O(b)` loop.

The following passes examples 0 o 3.

const int MOD = 1000000007;

long gcd(long a, long b)
{
    while (b != 0) {
        tie(a,b) = make_tuple(b, a%b);
    }
    return a;
}

int findSum(int sideA, int sideB, int bounces)
{
    if (bounces % 2 == 1) {
        return 0;
    }
    long y = 1 + bounces;
    long x = 1;
    
    // find solutions to this:
    // 1 <= y - p <= y
    // gcd(y - p, 1 + p) = 1
    
    long sx = 0, sy = 0;
    while (y >= 1) {
        if (gcd(x,y) == 1) {
            sx += (x*x) % MOD;
            sy += (y*y) % MOD;
        }
        y--;
        x++;
    }
    sx = ( ((sx * sideA) % MOD) * sideA) % MOD;
    sy = ( ((sy * sideB) % MOD) * sideB) % MOD;
    return (sx + sy) % MOD;
}

I submitted it just for fun, it will time out with slightly large `b`. No one dares to challenge it so far.