UVA 11548 - Blackboard Bonanza

http://uva.onlinejudge.org/external/115/11548.html

This problem statement tried to mislead you with some weird game between two characters Alice and Bob. Let's not put to much attention in that and focus in the the real task:

Given \(n (2 \leqslant n \leqslant 70) \) strings, you need to return the length of the best vertical alignment between an arbitrary pair of strings \(S_{i}\), \(S_{j}\) where \(i \neq j\). What exactly does that mean? Let's take a look to an example to clear out some obscures points of this statement:

The following two pictures shows two possible alignments for the strings "ABCD" and "ADC", among them the second one is the best alignment which include the letters A and C for a total length of 2.

The constraints of this problem are not to high, to solve it we can simply iterate over all the possible pair of strings, and for each of them calculate all the possible alignments and keep the length of the best one.

The hardest part perhaps is the procedure to calculate the best alignment for a given pair of strings. In order to do that, we just need to take one of the string as point of reference, let's call this string \(S\) and the another string \(P\), at each step we start to compare each character of \(S\) with each character of \(P\), once we are done we repeat the process but now, beginning in the next letter of the string \(S\). During this process if one the string reach it's last letter we restart the counter of matches, and start to count again from the current position, which is equivalent to begin another alignment.

This may sound a little bit confusing let's take a look to an example:
 

The previous picture simulates the idea of the algorithm as we can see using this method we consider all the possible alignments between "ABCD" and "ADC".

The overall time complexity of this solution is \(O(N^{4})\).

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