Codeforces Beta Round #4 - virtual participation

A. Watermelon

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

You and a friend want to divide a Watermelon with \(N\) kilos in two pieces. Because you and your buddy are crazy about even numbers, the division should be made in such way that the weighs of each part of the fruit have a  even number of kilos. Your task is to print "YES" if the division is possible, otherwise "NO".

The solution of this problem is pretty straightforward let's first consider the case where the given number \(N\) is odd. This means that \(N\) can be expressed in the form \(2x + 1\) for some integer \(x\). Is not hard to see that is not possible to split the number in two even parts when \(N\) is odd, because, the remainder of one is going to end up changing one of the Watermelon half weighs into an odd amount. 

We can conjecture then that this split is possible only when \(N\) is even, but hold on a second, how about the case \(N = 2\), is clearly not possible and is an even number... Is this the only exception out there? the answer is yes. Any other even integer greater than 2 can be expressed in the form \(2x + 2y\) where \(x\) and \(y\) are integers greater or equal than one. Knowing this we can conclude that our answer are all the even numbers greater or equal to 4. The overall time complexity of this solution is \(O(1)\).

B. Before an Exam

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

You are are planning on taking a Biology exam. Your parents knows that you hate the subject so they made you study for \(d\) days not less than \(minTime_{i}\) and not more than \(maxTime_{i}\) hours per each \(i\)-th day. Your parents now are asking you the time table of your study sessions, unfortunately, you just wrote down the total sum of time let's called it \(sumTime\). Your task is to print the time table according to your parents constraints, in addition, the total sum of time in each day should be equal to \(sumTime\). If is impossible to build such schedule print "NO".

The strategy to solve this problem is greedy. The first thing to notice is that at each day we should have a least  \(minTime_{i}\) hours, otherwise, our parents constraints will not be satisfied. Once we assign  \(minTime_{i}\) to each day, if the remaining \(sumTime\) is less than zero means that there is not enough time for the given constraints so the answer is "NO". 

The next step is to assign the remaining \(sumTime\) to each \(i\)-th day, taking care that the \(i\)-th day cannot have more than \(maxTime_{i}\) hours. After all of the assignments if the remaining \(sumTime\)  is greater than zero means that there is to much time to be fitted on the current schedule so the answer in this case is also "NO".

Finally, if any of the previous conditions does not hold means we got a solution. We just print any valid schedule. The overall time complexity of this solution is \(O(d)\).

C. Registration system

http://www.codeforces.com/contest/4/problem/C

The administrator of some random website ask for your help to implement a prototype of a new registration system. The system work as follow, when a user register if the username does not exist in the database the system prints "OK", otherwise the system prints usernamei in the following way (username1, username2, ... ) for each registration repetition  using the same username.

This problem shows the importance of a good data-structure in algorithm design. The idea here is to have a map<string,int> which maintains a counter for each name in the database. Every time a name is repeated we just print the name with the current value of our counter. The overall time complexity of this solution is \(O(N logN)\) assuming that each query to our map takes \(logN\) time.

D. Mysterious Present

http://www.codeforces.com/contest/4/problem/D

You want to send a letter to a good friend. Because you are the mysterious type of person you decide to make a chain of envelopes and put the card into them. This chains of envelopes should hold the following condition the width and the height of the \(i\)-th envelope is strictly higher than the width and the height of the \((i-1)\)-th envelope. Given the width and height of the letter and all the envelopes print the maximum chain size of envelopes you can form.

The strategy to solve this problem is Dynamic Programming. To simplify our solution we first discard all the envelopes which our letter can not fit in. Is easy to see that those one would not contribute to the final solution

The DP state of the solution consist in maintain the maximum length of the chain that ends in the index \(i\)-th. We also keep record of the parent of each member of the chain, in that way at the end we can reconstruct the optimal solution. The overall time complexity of this solution is \(O(n^{2})\).