Codeforces Round #124 - upsolving

A. Plate Game

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

You are given a rectangular with width \(a\) and height \(b\). Two players play the following game: take turns to puts plates on the table. The plates can't lie on each other (but the plates can touch each other) and the plates has to be located on the table (within the table border). If both players play optimally determine which player wins.

This problem at first looks kind of challenging. Definitely start to put plates under some weird heuristic may lead to a not so clean implementation. A good way to attack this kind of problems is to think what is the best possible move to make your opponent miserable and guarantee your victory; more formally the optimal strategy. Is not hard to see that play in the middle at each step has this effect. The following example shows an example of two players playing the plate game:

Because of symmetry every time the player 2 has a move the player 1 also has a move as well. Which means the player 1 just lose in the situation when initially there is not a move from him, in other words when \(2r\) is greater than \(a\) or \(b\).

 

B. Limit

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

You are given two polynomials of the form:

$$\\ P(x) = a_{0}x^{n} + a_{1}x^{n-1} + \cdots + a_{n-1}x + a_{n} \\ Q(x) = b_{0}x^{m} + b_{1}x^{m-1} + \cdots + b_{m-1}x + b_{m}$$ Calculate limit: $$\lim_{x\to +\infty}\frac{P(x)}{Q(x)}$$

This problem looks like a pre-calculus exercise to me. I think for further contest authors should avoid this kind of task. The reason why is because give some advantage to people that are more familiar with this concepts. The easier way to came out with a solution is getting your hands dirty and solve some of the sample cases.

$$\\ \lim_{x\to +\infty}\frac{x^{2} + x + 1}{2x + 5} \\ \\ = \lim_{x\to +\infty}\frac{x^{2}(1 + \frac{1}{x} + \frac{1}{x^{2}})}{x(2 + \frac{5}{x})} \\ \\ = \lim_{x\to +\infty}\frac{x^{2}}{x} \cdot \lim_{x\to +\infty}\frac{1 + \frac{1}{x} + \frac{1}{x^{2}}}{2 + \frac{5}{x}} \\ \\ = \lim_{x\to +\infty}x \cdot \lim_{x\to +\infty}\frac{1 + \frac{1}{x} + \frac{1}{x^{2}}}{2 + \frac{5}{x}} \\ \\ = \infty \cdot \frac{1}{2} \\ \\ = \infty$$

As we can see from the previous example the term with maximum exponent for each polynomial (or the degree of the polynomial) determine the value of the limit. From this fact we can generalize three possible cases:

1) \(n\) is equal to \(m\)

In this case the \(x\) get cancel from \(P(x)\) and \(Q(x)\) and the answer become a fraction formed by the coefficients of the highest degree term of each equation. Because, the problem ask you to return a irreducible fraction we divide each coefficient \(a\) and \(b\) by the \(gcd(a,b)\).

2) \(n\) is greater than \(m\)

This case is the same as the previous example, the answer can be +\(\infty\) or -\(\infty\) depending if for each polynomial the product of the term with highest degree is positive or negative.

3) \(n\) is less than \(m\)

In this case the answer is always 0.

C. Lexicographically Maximum Subsequence

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

You are given a string s consisting of only lowercase letters. You need to find its lexicographically maximum subsequence. For more details please check the problem statement.

The strategy to solve this problem is greedy. Let's first consider the following sample case abbcbccacbbcbaaba where the answer is cccccbba. If we construct an adjacency list with the positions where each letter appear we got the following:

 

We start from the letter with the highest lexicographical value and add all the members of the list to our string. In the second step the greedy algorithm follow the same strategy, pick the next letter with the highest lexicographical value but with one exception; we can not pick letters that precede the ones that are already in our string. To deal with this issue we just takes the ones that has greater position that the last letter pick from the previous step. After applied this strategy we end selecting the letters on the positions inside the red rectangles that is the desire lexicographically maximum subsequence: