Sunday, June 03, 2012

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

A. Exams

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:

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

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:

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

Because, 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:

1 comment:

Toribio 09-0774 said...

cout << (k >= 3*n ? 0 : n-k%n) << endl;

cout << ((n+1)%4==0 ? n+1 : ((n+1)%2==0 ? 2*n+1 : 4*n+1 ) ) << endl;