Codeforces Round #127 - really slow or really sleepy?

Even when I end up loosing points in this match I found the problem set very nice and fun. I couldn't fix the problem B during the match and as usual, after the time finish just took me couples of minutes to find my mistake, lucky me :)

A. LLPS

http://codeforces.com/contest/202/problem/A

You are given a lowercase string. Find the lexicographically Largest Palindromic Subsequence.

The strategy to solve this problem was greedy. Let's solve it for an example first to spot the pattern. Given the string yzyaucyarzy our answer is the subsequence zz. Because we are looking the lexicographically largest string is a good idea start with the values that has highest lexicographical value in the string. In addition, because we pick a multiple instances of the same letter that string is without doubt is a palindrome. Once we are done with the z's the question is there another way to add more letters to this palindrome subsequence and get a lexicographically larger palindrome? the answer is no. Imagine now we are trying to add the y's to our subsequence. Because is a palindrome subsequence we can not simply add them to the end, that will make the string non-palindrome (e.g. zzyy) to maintain the palindrome constraints we need to add more letters into the middle of the subsequence. Is easy to see that all the string's that are valid palindromes using the previous mention strategy are not lexicographically larger than the string zz, some examples are {zyyz, zyz, zyryz}. This lead us to the conclusion of just pick the letters with the highest lexicographically value in the given string as our answer.

The constraints of this problems were really small, the largest string has at most 10 characters. The brute force approach is to generate all the possible subsequences of the string which is analogous to generate all the possible subsets of characters. Given the constraints all the possibles subset upperbound is at most \(2^{10} = 1024\) iterations which is really low. For each subsequence (or subset) we keep the lexicographically largest palindrome that we find.

B. Brand New Easy Problem

http://codeforces.com/contest/202/problem/B

You are given the work as a judge in a programming contest. Your task is to classify a problem as new or similar to an old one. If the problem is similar to a previous problem founded in the contest archive you should measure the similarity according to the following metric:

$$\text{p} = \frac{n(n-1)}{2} - x + 1$$

Where \(n\) is the number of words in the original problem, \(x\) is the number of inversions between the original problem and a permutation subsequence of the original problem founded in a problem of the contest archive.

This problem can be solved with brute force. A good strategy to have in mind for any problem is to always exploit the lower constraint. For this problem the really low \(n = 4\) open that possibility. The idea is for each problem that belongs to the problem archive we compare it with all the possible permutations of the problem that we are evaluating. If we find a permutation that is a subsequence of a problem of the archive we calculate the similarity and keep record of the most similar problem so far. The only thing left to explain is how to calculate the inversions of a given subsequence? a simple way is to have a map<string,int> that give us the position of a word in the original problem. Once we have this for any given permutation of the original problem we can normally calculate the inversions using the values in the map.

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:

Codeforces Round #123 - hmmm

A. Let's Watch Football

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

You are downloading a streaming video from the internet. Because your internet connection is kind of slow the video may stop. To avoid this problem you decided to pause the video for certain amount of time and let it load. Your task is to return the minimum amount of time required to watch the video without pauses.

I found this problem really interesting, because, I been dealing with this kind of issues really often... Let's first define the variables given to us:

\(a\) denotes the size of data needed to watch one second of the video.

\(b\) denotes the size of data you can download from the network per second. 

\(c\) denotes the video's length in seconds.

We can further define the total size in units of the video as \(a \cdot c\). For each second waiting we subtract from the total size the amount of data we download after \(t\) seconds \(t \cdot b\). For the remaining data \((a \cdot c) - (t \cdot b)\) we check if it can be downloaded in less or equal  than \(c \cdot b\) seconds.

B. After Training

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

You are given \(n\) balls and \(m\) baskets. You need to put the \(n\) balls into the \(m\) baskets with the following constraints:

(1) Each new ball in the basket with the least number of balls.

(2) If we got several basket with the same number of balls, we choose the basket which stands closer to the middle.

This problem has two main approaches:

1) Sorting.

2) Generate the sequence following certain pattern rules.

I took the second one. Let's first consider the example when \(n = 4\) and \(m =3\), the following graphic illustrate the final configuration after arranged all the balls in the baskets:

Is easy to see that when m is odd we start to move from the center in a zigzag motion from left to right. At Each step we try to put the next ball as near as possible from the center without violating the least number of ball constraint. Note that in the odd case the second move (if is possible) is always to the left. In the even case is necessary to first visit the another center and then continue in zigzag fashion.

To implement this idea I used two pointers that represent the movements to the left and the right. The overall time complexity of this solution is \(O(n)\).

UVA 10622 - Perfect Pth Powers

http://uva.onlinejudge.org/external/106/10622.html

We say that x is a perfect square if, for some integer \(b\), \(x = b^{2}\). The perfect pth power for a given number \(x\) is defined as  \(x = b^{p}\). You need to determine the largest \(p\) such that \(x\) is a perfect pth power. 

This problem main idea is based on the understanding of the prime factors exponents divisibility. Let's begin with a proof that is going to help us  understand this concepts. Theorem: all the powers in the prime factorization of an integer \(n\) are even if and only if \(n\) is a perfect square, proof:

$$\\\\ n = p_{1}^{k_{1}}p_{2}^{k_{2}} \cdots p_{t}^{k_{t}} \\\\ m = n^{2} \\\\ m = (p_{1}^{k_{1}}p_{1}^{k_{1}})(p_{2}^{k_{2}}p_{2}^{k_{2}}) \cdots (p_{t}^{k_{t}}p_{t}^{k_{t}}) \\\\ m = p_{1}^{k_{1} + k_{1}}p_{2}^{k_{2}+k_{2}} \cdots p_{t}^{k_{t}+k_{t}} \\\\ m = p_{1}^{2k_{1}}p_{2}^{2k_{2}} \cdots p_{t}^{2k_{t}}$$

Because all the exponents of m are even we can conclude that is perfect square.We can easily extend the previous proof to powers of 3, 4, ..., all the way to \(n\). This means that if all the exponents in the prime factorization of a certain number \(x\) are divisible by a certain number \(p\) we can express this number as a pth power. To implement this idea we factorize the number in his standard prime factorization, and, for each factor frequency check the divisibility against certain number pth. If all the number pass the test we got our pth power, is guarantee to always get an answer because of the 1th powers.

The only thing left to consider is the cases when the number \(x\) is less than zero. Let's consider the following example \(4096 = 2^{12}\) but, -4096 is not \((-2)^{12}\). In order to get a negative number as a result of repeated multiplication of the same number, we need to multiply that number odd times. Which means that in the case of negative number we stay with the biggest odd pth exponent as it shows in the following expression:

$$-4096 \Rightarrow (-2)^{12} \Rightarrow (-2)^{3\cdot 4} \Rightarrow (-16)^{3}$$

UVA 10407 - Simple division

http://uva.onlinejudge.org/external/104/10407.html

Given a list of \(n\) numbers \(2 \leq n \leq 1000\).  You need to return the largest integer which when divided into each of the input integers leaves the same remainder.

Let's call our list of numbers \(x\), the following expression explain the given situation:

$$\\ x_{1} = q_{1}d + r \\ x_{2} = q_{2}d + r \\ ... \\ x_{j} = q_{j}d + r$$

As we can see from the previous expressions all the numbers on the list when we divided them by \(d\) leaves the same remainder \(r\). We are interesting in the largest \(d\) that has that property. To understand this problem it may be useful first to prove the following theorem if \(a \equiv b (mod \,\, d)\) then \(d | (a - b)\):

$$\\ a = q_{1}d + r \\ b = q_{2}d + r \\ a = q_{1}d + (b-q_{2}d) \\ a - b = q_{1}d - q_{2}d \\ a - b = d(q_{1} - q_{2})$$

Because \(a - b\) can be expressed as the product of \(d\) by some integer without any remainder, we conclude that \(d | (a - b)\). Enough math for the day :) let's focus in the task. Knowing this we take an arbitrary integer from our set of numbers and subtract this amount to all the numbers in our list. To obtain our result (\(d\)) we just calculate the greatest common divisor over the whole list.

UVA 10680 - LCM

http://uva.onlinejudge.org/external/106/10680.html

This problem ask you to calculate the last non-zero digit of the \(LCM(1...n)\), where \(n\) is between 1 <= n <= 10^6.

The LCM of two integers \(a\) and \(b\)  is the smallest positive integer that is a multiple of both \(a\) and \(b\).

$$\operatorname{lcm}(a,b)=\frac{|a\cdot b|}{\operatorname{gcd}(a,b)}$$

Another way to define the LCM between two integers \(a\) and \(b\) is from their respective standard prime factorization. For each prime factor of \(a\) and \(b\) we take the maximum exponent.

$$\operatorname{lcm}(a,b) = \prod_p p^{\max(a_p, b_p)}$$

I solved this problem using the second definition of LCM. The idea is simple if we want to calculate the LCM for the numbers of \(1, 2, 3, \cdots, n\) we first list all the prime factors between \([1, n]\). For each factor in that list we need the maximum exponent such that \(p^{x} \leq n\). In other words, let's say that \(n = 20\) we want to know the highest power of 2 in the \(LCM(1, 2, \cdots, 20)\) we can try the following:

\(2^{1} \leq 20\) (true)

\(2^{2} \leq 20\) (true)

\(2^{3} \leq 20\) (true)

\(2^{4} \leq 20\) (true)

\(2^{5} \leq 20\) (false)

So the largest power of 2 in the \(LCM(1, 2, \cdots, 20)\) is \(2^{4}\).

 

We repeat this process for the other prime factor in the range \([1,n]\). After that for each prime factor we calculate the answer mod 10. To avoid getting 0's at the end we subtract the \(cnt2 - cnt5\), because between \(1, 2, 3, \cdots, n\) always there is going to be more factors of two than factors of five, this subtraction is always going to be greater than 0. In addition, To speed-up the algorithm the prime factors are pre-calculated using Sieve of Eratosthenes.

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}$$