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

TopCoder SRM 544 - miss the match

DIV 2 250 - ElectionFraudDiv2

http://community.topcoder.com/stat?c=problem_statement&pm=11946

You are given a list of of integers \(\{0, 5, 100\}\) that represent the percentages received by each of the candidates of an election. You are ask to write a program that detect if the election is fraudulent, or if the reported percentages are rounded. In that case, return "YES", otherwise, "NO". For more details of the problem statement please check the link below.

In my opinion this problem was little bit more tricky than a normal DIV 2 250 the 19.10% of success rate confirm my thoughts...

To solve this problem we need to consider the following three cases:

Case #1: The sum of percentages equal to 100%

In this case we assume the elections were not fraudulent. The answer for this case is "NO".

Case #2: The sum of the percentages is greater than 100%

In this case we need to check if the sum is greater than 100% because of a rounded up error. For example if the percentage for a certain candidate is 13% means that the real percentage value (not rounded) of the elections for that candidate is in the range \([12.5\%, 13.49\%]\). To check that occurred a round error we substitute each of the candidate percentage for the minimum value in this range and sum them up. If we get a percentage sum less or equal to 100% means that the results are not fraudulent. The reason is because we can always get 100% with some combination of the rounded up error. In this case we should be careful with 0% is not possible to get 0% as a result of a rounded up error. For example:

3 candidates 

\(A1 = \{34\% , 34\%, 34\%\}\)

\(sum\_percentage = 102% \)

\(A2 = {33.5\%, 33.5\%, 33.5\%}\)

\(sum\_percentage = 100.5%\)

The results of this elections still fraudulent even after fixed the rounded up errors.

Case #3: The sum of the percentages is less than 100%

Similar to case #2 but taking the maximum value of the candidate percentage range.

DIV 2 500 - BoardSplitting

http://community.topcoder.com/stat?c=problem_statement&pm=11951

You are given a unlimited amount of boards of length \(actualLength\) and using those  you need to create \(desiredCount\) boards of length \(desiredLength\). You are allow to glue the boards and also cut them. If there are multiple ways to use the same number of boards, pick the one that perform as few cuts as possible. Return the number of cuts they will perform.

The strategy that I follow to solved this problem was greedy + simulation. As in the previous problem there are also three main cases to consider:

Case #1 desiredLength is equal to actualLength

In this case the answer is 0 because each of the \(actualLength\) boards has the desired length and we have unlimited supply of this boards we just take \(desiredCount\) of them.

Case #2 desiredLength is greater than actualLength

In this case the boards in our supply are smaller that our target. The best possible scenario is when the \(desiredLength\) is a multiple of the actualLength in that case our answer is 0 because we don't need to perform any cut. Otherwise, the optimal strategy is to glue as much boards of length actualLength as we can and after that deal with the remainder. Because the \(desiredLength\) of all the board is the same thus the remainder for each of the boards is going to be the same. However, the cases where the remainder portion of the actualLength is not enough to complete the \(desiredLength\), in this cases we just glue this board and take the missing part for the next board. The following example explain this idea:

\(desiredCount = 159\)
\(actualLength  = 25\)


 


\(desiredLength = 314\)

In this case the remainder of \(desiredLength % actualLength\) is 14. Which means that we first glue 12 boards of \(actualLength\) and what remains is a left over of 14 units length. This left over is the amount that we should complete for each of the \(desiredLength\) boards and the only part that actually require cuts of the board with \(actualLength\). In the pictures bellow we can see that when we cut the board with \(actualLengh = 25\) we end up with a board of 11 units. This board is further use for the next board of \(desiredLength\) we need to complete.

Case #3 desiredLength is less than actualLength

This cases can be reduced to the previous one. The only difference is that the remainder is now the \(desiredLength\).

DIV 1 500 - FlipGame

http://community.topcoder.com/stat?c=problem_statement&pm=11974

Given a binary matrix:

00000000
00100000
01000000
00001000
00000000

You have to toggle the bits of the matrix until all of them become 0s. At each step you are allow to toggle the bits that are below certain shortest path from the upper-left corner to the lower-right corner. They ask you to return the minimum number of steps required to change all bits to 0s.

The strategy to solve this problem is greedy. Let's say that the \(i\)-th element represent the row of the matrix and the \(j\)-th element the columns. For each row we pick the the highest set bit for the \(j\)-th column. If for a certain row the highest set bit is less than one of the predecessor highest set bits we keep the position of the one with greater value of \(j\). The reason to pick the highest set bit is because the problems ask us to pick paths that are shortest paths. This procedure is guaranteed to finish because keep toggle the highest set bits until all the bits become 0s.

Codeforces Round #121 - silly mistake

This was not a good match for me, I got pretty confident after solved the problem A relatively fast. I was careless in the problem B and forgot to consider an important case. I spend the rest of the match looking at problem C.

A. Funky Numbers

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

In this problem we need to tell if a certain number can be expressed as the sum of two triangular numbers. At first the constraint of \(N \leq 10^{9}\) seems kind of scary... The key observation is that there are just 44,720 triangular numbers under the \(10^{9}\). Knowing this we can construct a sorted list of all triangular numbers under \(N\). The only question that remains is how to search efficiently into into this sorted list, the answer is simple binary search. For each number in our list greater or equal to \(N\) we used binary search to look for the number \(N - A[i]\) in the list, if we find a match we are done, which means it's possible to express this number as the sum of two triangular numbers, otherwise, is not. To make things clear let's check an example:

\(N = 256\)

\(T = \{1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 120, 136, 153, 171, \\ 190, 210, 231, 253, 276, ...\}\)

\(X = 256 - T[0] = 256 - 1 = 255\)

\(binary\_search(X)\) 
255 is not in the list; means 1 + 255 is not the sum of two triangular numbers.

\(X = 256 - T[1] = 256 - 3 = 253\)

\(binary\_search(X)\)
253 is in the list; means that 256 can be expressed as the sum of two triangular numbers 256 = 253 +3.

B. Walking in the Rain

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

You are given a one-dimensional grid, each cell of the grid has a threshold of the amount of days can last, you need to move your troops along the grid, from position \(1\) to \(N\). From the \(i\)-th cell your troops are just allowed to move to the cells \(i + 1\) or \(i + 2\) as long as the cell is not destroyed. Output the maximum number of days that your troops can walk along this grid.

My guess is that on purpose the writer kept the constraints low enough to allow \(O(N^{2})\) solution to pass. During the match I was not thinking I tried to simulate the process... I forgot to consider the case where the troops where in the initial position. A better solution was to notice that we can't jump more that two cells at time, this means that  if we get block by two destroyed cells next to each other we are not going to be able to cross them. This means that for each pair of cells we calculate their maximum destroy time threshold and for all this value we stay with the minimum of all the pairs.

Trie Data Structure

In this link you can find an excellent explanation about the Trie Data structure
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

I wanna share with you guys my C++ implementation based on the TopCoder tutorial: