Pow Pow - SPOJ
Posted on May 29, 2015

Link to problem

Overview: The problem asks us to calculate the following expression: where , , and . The three integers are given as input.

A naive solution is clearly infeasible, so in order to make the problem simpler we need to think about how to manage the sum of squares of the binomial coefficients. Doing a couple of modifications to we can get:

Now, we can give a meaning to this last expression as “the sum of the number of ways to have elements from a first group of elements and to have elements from a second group of elements”. Interestingly, this is equal to “choose elements from a group of elements”. So we reduced to be equal to . At this point the problem is not solved yet, we need a couple of additional insights.

So far what we have to calculate has reduced to , here we need to realize that is prime and therefore we can make use of Fermat’s little theorem to get the answer. Applying Fermat’s little theorem will result in calculating where:

To calculate we might want to use Fermat’s theorem again; however, is no longer a prime number.

Continue reading...

Codeforces Round 293 - Problem D
Posted on March 12, 2015

Link to problem

Overview: There are \(n\) people waiting in a queue to enter a escalator. At each second the person in front of the queue either enters the escalator with probability \(p\) or doesn’t move with probability \(1-p\), making the whole queue wait behind him. The problem asks to find the expected value of the number of people standing on the escalator after \(t\) seconds. The input consists of a line with three numbers \(n, p, t\) \((1 \le n, t \le 2000, 0 \le p \le 1)\). Numbers \(n\) and \(t\) are integers, number \(p\) is real, given with exactly two digits after the decimal point.

The solution becomes simpler by using the dynamic programming paradigm. The most straightforward random variable to get the answer would be \( \mathrm{X_t} = \) the number of people in the escalator after t seconds. And the expected value would be \( \mathrm{E[X_{t}]} = \sum_{i=1}^{n}{i*\mathrm{Pr[X_{t}}=i\mathrm{]}} \). Where \( \mathrm{Pr[X_{t}}=i\mathrm{]} \) is the probability that \( i \) people are in the escalator after \( t \) seconds.

Now to calculate the probability, we need to be careful with the dependency of the \(i^{th}\) person on the \((i-1)^{th}\) person in the queue. However, if we think about it, to reach that state at \( j\) seconds we have to make it through whatever the states are at \(j-1\) seconds. And not surprisingly, there are only two possible states at \(j-1\) seconds. Either there are \(i-1\) people in the escalator, which is \( \mathrm{Pr[X_{j-1}}=i-1\mathrm{]} \), or there are already \(i\) people in the escalator, which is \( \mathrm{Pr[X_{j-1}}=i\mathrm{]} \).

Combining them we can easily calculate the state where there are \(i\) people after \(j\) seconds. If there are \(i-1\) people at \(j-1\) seconds, then in the next second, person \(i\) enters with probability \(p\). And if there are already \(i\) people at \(j-1\) seconds, then in the next second, person \(i+1\) does not move with probability \(1-p\). Therefore, we have:

Continue reading...