Codeforces Round #122 - re-submits are killing me!

A. Exams

http://www.codeforces.com/contest/194/problem/A

You are given the grades of n exams. All the grades belongs to the set of integers {2, 3, 4, 5}. The grade 2 means failed exam. The author of the exams is interesting in knowing for a certain sum k of grades what is the minimum amount of failed exams.

Recently Beijing is hot as hell... I think my brain is suffering from overheating :) or maybe this is just another silly excuse to justify a bad match... Well, I notice that brute force was enough for the given constraints. We just need to iterate over all possible combinations of the multiples of the set {2, 3, 4, 5} in the following way:

$$\\ x, y, z, w \ \epsilon \ [0,50] \\ \text{if } x + y + z + w = n \text{ and } 2w + 3x + 4y + 5z = k \text{ then } \\ ans = min(ans, w)$$ The running time of the algorithm is \(O(n^{4})\) that in the worst case scenario is about 6,250,000 iterations, which under the 2 second time limit is alright.

B. Square

http://www.codeforces.com/contest/194/problem/B

There is a square of side equals n meters. You walk along the perimeter of the square in clockwise direction. Every time you walk n + 1 meters you should  mark it with a cross. Return the number of steps required to mark the lower left corner of the square with two crosses.

The constraints were too high for a simulation, this confirmed my thoughts about a mathematical solution. We need to reach the point 4n, at each step with make jumps of length (n + 1) meters. You need to figure it out where this two amounts are going to finally synchronized? the answer is in the lcm(n + 1, 4n) but wait a minute... we are not interesting in the value of the lcm instead in the number of crosses that were marked along the way. This is why we need to divide by (n + 1). The resulting expression is the following:

$$\frac{lcm(n + 1, 4n)}{(n + 1)} + 1$$

I was discussing the problems with my friend cjtoribio and he came with a really interesting simplication of the previous expression.

$$\frac{lcm(n + 1, 4n)}{(n+1)} + 1 \\\\\\\\\\\\\\\\ \frac{4n(n+1)}{gcd(n + 1, 4n)(n+1)} + 1 \\\\\\\\\\\\\\\\ \frac{4n}{gcd(n + 1, 4n)} + 1$$ Because, $$gcd(n, n + 1) = 1$$ We can say that n + 1 just has factors in common with the 4, so gcd(n + 1, 4) has 3 possible values 1, 2 or 4. There exist then 3 possibles solutions: $$f(n) = \begin{cases} & \frac{4n}{4} + 1 = n + 1 \text{ if } n + 1 \equiv 0 \text{ (mod 4)} \\\\\\\\ & \frac{4n}{2} + 1 = 2n + 1 \text{ if } n + 1 \equiv 0 \text{ (mod 2)} \\\\\\\\ & \frac{4n}{1} + 1 = 4n + 1 \text{ otherwise } \end{cases}$$