Codeforces Round #142

A. Dragons

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

You are crazy about Massively Multiplayer Online role-playing games (MMORPG), recently you are playing one about dragons, the purpose of this game is to defeat \(n\) dragons, each of them have a strength of \(x_{i}\) units, the duel between two opponents is determined by their strength. In other words, the player with the strongest dragon wins the duel.

Every time you defeat a dragon you get a bonus strength of \(y_{i}\) units, you are given a dragon with initial strength of \(s\) units, you are able to fight with any dragon in arbitrary order,  print "YES" if is possible to defeat all the dragons, otherwise print "NO".

This is a really common greedy problem, not too long ago in the Codeforces Round #128 appear a similar problem called Photographer.

The intuition to solved this problem is the following, we want our dragon get stronger as possible in order to be able to face the big (strongest) dragons, this is why we first need him to face the weaker ones and accumulate as much bonus strength points as he can. Just like when you are playing video games you don't go to fight the last boss until you are pretty confident you are at his level...  The following picture illustrate the idea, were the green numbers represent the strength of each dragon:

To accomplish this we sort the dragons by their strength and first fight the ones with lower strength, if we are able to beat all the dragons the answer is "YES", otherwise "NO". The overall time complexity of this solution is \(O(n log n)\).

B. T-primes

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

A T-prime number is a number that has exactly tree positive divisors. For example 4 is an T-prime because its divisors are \(\{1, 2, 4\}\). Given \(n\) numbers your task is to print "YES" if the number is T-prime, "NO" otherwise.

The following website may be useful to spot the pattern Table of Divisors, with this table you just need to look at the numbers with 3 divisors and try to came up with some good conjectures.

To help the reader spot the pattern let's first list a couple of number with 3 divisors:

\(\{4, 9, 25, 49, 121, 169, \cdots\}\)

If we look carefully all this number are perfect squares...

\(\{2^{2}, 3^{2}, 5^{2}, 7^{2}, 11^{2}, 13^{2}, \cdots \}\)

At this point we may feel tempted to conjecture that all the perfect squares has three divisors, but that is totally wrong, a counter-case 4² is 16 and has 5 divisors \(\{1, 2, 4, 8, 16\}\). If we take a closer look seems that the perfect squares of prime numbers do the trick.

Let's try to proof the following statement "The squares of prime numbers has exactly three divisors":

By definition we know that the prime numbers are just divisible by 1 and itself, in other words the set of divisors of any prime number are just \({1, p}\) where \(p\) represent an arbitrary prime number.

If we square any prime number we have a composite number with the following standard prime factorization \(a = p^{2}\), is easy to see that the set of divisors for this new number are always in the form \(\{1, p, p^{2}\}\), which has exactly 3 divisors.

The constraints of the problem establish that the given numbers can be as big as \(10^{12}\), because the T-prime are squares of primes is enough with a list of primes not higher than \(10^{6}\) , this is because \(\sqrt{10^{12}} = 10^{6}\), this list of primes can be constructed using Sieve of Eratosthenes.

The next step, is take this list of primes and square each of them and create a list of T-primes numbers. Once we got the list of t-primes we can use binary search to query each of the numbers in the given list.

C. Shifts

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

You are given a matrix with \(n\) rows and \(m\) columns. You can perform two operations in the rows of the matrix:

(1) cyclically shift right 
Given the row "00111" if we apply the operation we get "10011".

(2) cyclically shift left
Given the row "00111" if we apply the operation we get "01110".

Using the previous operations your task is to print the minimum number of operations that takes to get some column of our matrix full of ones. If this is impossible print -1.

Let's first consider the case when it is impossible to get one of the columns with just ones, is easy to see that just in the cases when at least one row is full of zeros the answer is -1.

We are particular interesting in the minimum amount of shift operations to fill an entry \(a_{ij}\) of our matrix with a 1, to accomplish that we just need to look for the nearest 1 to the entry \(a_{ij}\) in both directions left and right.

For example consider the row #3 "0010" the element in color red belong to our target column, we want to know the minimum amount of shift operations to replace this 0 with a 1. We could make 3 right shifts to get the following row "0100" or we could make 1 left shift and get the same row "0100".

We can calculate this distance by a simple linear search, but, the constraints are too high. We need to pre-calculate a table containing the distance from any entry \(a_{ij}\) to the nearest 1 in the same row (circular distance). For example the table for the previous example look like this:

Once we have this table, the answer is just the minimum sum over all the columns in our matrix. To reduced the complexity of the code I used two distance matrix, but, this could easily merge into one. The overall time complexity of this solution is \(O(n \cdot m)\).

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})\).

ABBYY Cup 2.0 - Easy - virtual participation

A2. Good Matrix Elements

http://www.codeforces.com/contest/177/problem/A2

You are given a \(N\) x \(N\) matrix, where \(N\) is an odd number. A good element of the matrix is defined as follow:

(1) Element of the main diagonal.
(2) Element of the secondary diagonal.
(3) Element of the "middle" row (\(\frac{n}{2}\) row).
(4) Element of the "middle" column (\(\frac{n}{2}\) column).

Your task is to count the number of good elements in the matrix.

The solution of this problem is pretty straightforward, we just need to add up the elements which has one or more of the following properties:

B2. Rectangular Game

http://www.codeforces.com/contest/177/problem/B2

You are playing the following game, initially you have \(n\) pebbles, at each step you arranges them in such way that each row has the same amount of pebbles. Once you have arranges the pebbles, you take back any of the resulting rows (that is, b pebbles) and discards all other pebbles. Keep playing until you end up with exactly one pebble. Your task is to print the maximum possible result of the game.

The first thing to note here is that if you want to distribute certain number \(n\) into \(a\) rows with \(b\) pebbles each, then necessarily \(a | n\) and \(b | n\). Clearly, we going to be dealing with divisors of \(n\) in this problem.

Based on the previous claim the main idea of this problem is keep dividing the number of \(n\) until we reach some point we cannot do it anymore. This reasoning lead us to the question of how to divide in order to maximize the final result.

Le'ts look an example with the number 6, the asterisk represent the pebbles :

The divisors of the number 6 are \(\{1, 2, 3, 6\}\), we can distribute the pebble in four possible ways:

(1) one row of six pebbles  

\(6 / 1 = 6\)

******

(2) two rows of three pebbles  

\(6 / 2 = 3\)

***

*** 

(3) three row of two pebbles  

\(6 / 3 = 2 \)

**

**

**

(4) six rows of one pebble

\(6 / 6 = 1\)

*

*

*

*

*

* 

Looking at this example it seems obvious that we should take the lowest available divisor greater than one at each step. 

To implement this idea we simply iterate over all the factors of \(n\), and for each one of them add up \(\frac{n}{d}\) to the solution. The overall time complexity of this solution is \(O(\sqrt{n})\).

C2. Party

http://www.codeforces.com/contest/177/problem/C2

You are organizing a party, from all of your acquaintances some of them are friends and some of them dislike each other. To make the party a success you came up with the idea of only inviting people that share a friendship relationship. Given the relationship between the acquaintances, your task is to return the maximum number of people that you can invite to the party.

This is a typical graph connectivity problem, it can be solved with DFS, BFS or Disjoint Sets. I solved using Disjoint Set data structure.

The Disjoint Set data structure helps us to divide each of the acquaintances in groups according to their direct or indirect friendship relationship. Initially every person belongs to its own group, using the \(union\_set(u, v)\) operation we unite the people who share a relationship of mutual friendship in a common group. We keep track of the number of people in each of the groups. 

The final step is to check which of those groups has people that dislike each other. Having the Disjoint Set this is a straightforward task, for each pair of people that dislike each other let's called it \((u,v)\) we check if \(find\_set(u) = find\_set(v)\). This means that, if the pair \((u,v)\) belongs to the same group we can not invite any of the people in that group.

UVA 10892 - LCM Cardinality

http://uva.onlinejudge.org/external/108/10892.html

You are given a integer \(N\). Your task is to return the number of different integer pairs with lcm equal to \(N\).

A good start is to first think how to get \(N\) as the \(lcm(a,b)\). In order to do that we first need to identify the different values that \(a\) and \(b\) can take. 

After get your hands dirty with couple of sample cases is not hard to see that \(a\) and \(b\) should be taken from the set of divisors of \(N\). The reason behind this is that the \(lcm(a,b)\) takes the maximum exponent from each prime factor of \(a\) and \(b\). The divisors of a number serves as a building block of the number that they divide. In other words contains fragments of the prime factorization of the given number \(N\). Tried another number that is not a divisor of \(N\) is not going to lead us to the correct result.

Let's clarify this thoughts with an example, the pairs that works for \(N = 12\) are the following:

1. \(lcm(1, 12) = 12\)
2. \(lcm(2, 12) = 12\)
3. \(lcm(3, 12) = 12\)
4. \(lcm(4, 12) = 12\)
5. \(lcm(6, 12) = 12\)
6. \(lcm(12, 12) = 12\)
7. \(lcm(3, 4) = 12\)
8. \(lcm(4,6) = 12\)

All this numbers belongs to the set of divisors of 12 that are the following: \(\{1, 2, 3, 4, 6, 12\}\). Note, that in total there are 21 pairs \(( \frac{6 \cdot 5}{2} + 6 \)  but not for all of them we get 12 as lcm. For example \(lcm(3, 6)\) is not 12.

The solution to this problem is to first calculate all the divisors of a given number \(N\) and stored them in the data structure of your preference. For each different pair of divisors we count the ones that \(lcm(d1, d2) = 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.