Continuing solving USACO

It is embarrassing, but I haven't finished USACO training pages. Even though I have started doing them a while ago. I decided to be done with all of the problems by the end of the August, 2009.

The problem that I finally finished was Primes (prime3). This problem is from IOI 94 and once you know what to do it just takes time to implement. My solution is over 230 lines of actual code. In this problem you are always given a field 5 x 5 you need to fill with digits such that all rows, columns and both diagonals when concatenated each would be a five digit prime number and also the sum of the digits of those primes have to equal to the given sum. Also the digit at the cell (1, 1) is also given.

It's a brute-force problem with optimizations. You have to carefully optimize your solution in order to pass time limit. I submitted many solutions which got TLE. I eventually understood how to solve the problem after reading nice post by ar2rd. The most important optimization is the order in which you fill out the table. Here is the "magic" order:
Fill out main diagonal and then secondary diagonal.
Next fill the first row.
Then second and forth columns.
Next compute the third digit of the fifth row.
Then do the second column.
Finally do the rows two, three and four.
At the end just check if the column one and five are correct (are primes and sum of digits is equal to the given) then memorize the solution.
Also, the other optimization that I did was to precompute all five digit primes with the sum of digits equal to the given and then I used them when I was fill out the table.
That's it!

KRSU Open Contest 2009

Late at night when I was almost going to bed my Google calendar suddenly reminded me about this contest. And I decided to participate in it :) Sometimes programming competitions "are more important than sleep"... The contest wasn't very hard. Although I solved only four out of six problems. Further I will describe my solutions.

Problem A. Attack
It was the easiest problem. "Do what they ask".

Problem B. Big Pyramid
This one was a so tricky that I didn't see the trick. (Thanks to Ulan Degenbaev for such a nice problem!) I submitted this problem seven times and didn't get AC :) I was so mad, that I eventually gave up and went to bed. I solved this problem today though. The problem asked to find the largest pyramid given the elevation map on the area. Area was dived into H by W cells and for each cell they give us how many blocks can possibly stand on it. Pyramid of height N is defined the following way: in the very center there is one block of size 1x1x1, under this block there is another set of 9 blocks, i.e. 3x3, finally on the Nth level of the pyramid there are 2*N-1 x 2*N-1 blocks. The trick was that some cells are possibly covered with "sand". Which means if the elevation area looks like this:
3 3 3
3 2 3
3 3 3
We still know there is a pyramid of height two with the center located at cell (1,1), i.e. the actual pyramid is like this:
1 1 1
1 2 1
1 1 1
The excess is the SAND on the pyramid!
So, keeping that in mind we can easily design O(H^2*W^2) algorithm to find largest pyramid of the area. Consider all possible centers of the pyramid and then try to expand from that center. It's easy to code, I wish I did it during the contest.

Edit: Thanks to the dfyz, as he pointed out there is a better O(H*W*max(H,W)) solution. I was able to improve my previous O(H^2*W^2) solution to run in O(H*W*max(H,W)) time as well. That was possible because my "expand" method was based on finding minimum element on the certain interval of a row or a column. So, pre-computation of those values reduces the running time to the desired

Problem C. Coloring Palette
This was an implementation problem. Especially easy to code if you know STL and how to write your own compare function for the STL's sort method.

Problem D. Draw Rectangles
This is a well-known problem. First we draw red rectangles on the plane. Then we draw blue rectangles on the plane. As usual rectangles can intersect overlap, etc. So the problem asks to find area of the red rectangles. It can be solved in many ways. One approach is to do sweep algorithm.

Problem E. Elementary Algebra
Nice problem. Each letter is a node in the graph. First we merge all nodes that appear in the X=Y expressions. The we say there is an edge from X to Y if there is an expression X>Y, also there is an edge from Y to X if there is an expression X<Y. then can be reduced to transitive closure problem or figuring out whether exists in the if there a cycle answer is "NO" otherwise "YES".

Problem F. Find Strings
I didn't figure out the problem during contest. I knew it was an easy DP, I just didn't see it right away. Basically given two strings (say A and B) you have to find how many strings of minimal length contain both of the given strings as substrings. The DP is the following:
1) Let D[i][j] - be the length of the minimal string that contains strings A[1...i] and B[1..j];
2) Let B[i][j] - be the number of such strings.

If you're interested in how to compute those values read next paragraph:

D[i][j] = D[i-1][j-1], if A[i] is equals to B[j], otherwise D[i][j]=min(D[i-1][j],D[i][j-1])+1.

Similarly B[i][j]=B[i-1][j-1], if A[i]==B[j],
otherwise let best=min(D[i-1][j],D[i][j-1]),
if D[i-1][j]==best then we add B[i-1][j] to B[i][j],
If best==D[i][j-1] then we also add B[i][j-1] to B[i][j].

Finally, I guess it's obvious to figure out where the answer to the problem would be.

Problems by the end of finals week

1019. A Line painting.
Sweep algorithm. Simple geometry.

1010. Discrete Function.
Simple ad-hoc problem.

1026. Questions and answers.
Radix sort.

1025. Democracy in danger.
Simple ad-hoc problem.

1024. Permutations.
Cycle lengths of permutation. LCM and GCD.

1023. Buttons.
Simple math and simple game theory.

1022. Genealogical tree.
Just do topological sort of the directed graph.

Continue solving problems at the hotel :)

1020. Rope (timus.ru)
This problem was a subproblem of one of the questions during last World Finals 2009 in Stockholm. The solution here is simple - the length of the rope is sum of the segments lengths and 2*PI*R because you're doing full circle.

1021. Sacrament of the sum (timus.ru)
You just assume "perfect" hashing in this problem (since there are only at most 50,000 integers in one of the lists) So, you hash the first list A, and then go through the second list B and check if 10000-B[i] is present.

Row of simple problems from acm.timus.ru

1007. Code words.
Simple ad-hoc problem.

1008. Image encoding.
Problem is easily solvable using BFS. The only trick is that you problem statement doesn't really specify which (one of two) input format is going to be used... :)

1009. K-based numbers.
1012. K-based numbers v.2.
1013. K-based number v.3.
The three upper mentioned problems are solved using the exact same DP: dp[i][j] - number of valid K-based numbers of length i and last digit j. The only difference is the latter two have to be implemented using long arithmetic or java's BigInteger class.

1014. The product of Digits.
Simple math problem. There should be formula for it, but I solved using iterations, because given input is specified up to two decimal points...

1015. Test the Difference!
The problem requires to be able to generate all possible rotated states of the die and then determine dice are same. Pretty straightforward.

1017. The staircase.
Classical DP problem. Asks to find number of ways to represent a given integer N as an increasing sum of at least two integers. You have to use long arithmetics again or BigInteger, since N can be up to 500.

Simple Case of Directed Steiner Network Problem.

3570 - Routing (acm icpc live archive).
I was amazed how beautiful and simple solution to this problem actually is. I got stuck on this problem, even though at the first sight it seems easy. Then I asked Prof Mikhail Atallah (our spiritual coach) for help and he pointed out this paper, which explains the solution to this problem and even describes an algorithm for a more general case. I was reading this paper during my flight from Indianapolis to Boston and after I understood it, I was excited to do the actual implementation :-) So, I did implement it and got AC from the first attempt.

The problem is reduced to constructing another graph and finding minimum path in it. You have to use Dijkstra's algorithm with priority queue, because number of nodes in the new graph can be up to 10,000.

Solving problems between finals :-)

This week is a dead week in our university. There is a policy that restricts professors from giving quizes or midterms during this week. So, instead they just give a lot of homeworks and you are overloaded with deadlines. Some of the homeworks are boring and so, I entertain myself by solving problems in between.
Here are the problems for today:
1004. Sightseeing trip
Given undirected weighted graph, the problem asks to find simple cycle (you can visit vertex only once) with minimum weight . At the beginning it seems you have to consider all possible cycles and choose the one with minimum weight. You can use Dijsktra's algorithm here though. Just try to delete every possible edge and then find minimum path between nodes of the deleted edge. The cost of such cycle is the weight of minimum path + cost_of_deleted_edge. That was enough to get AC.

1014. The Product of Digits
Simple number-theoretic problem. :-) First, realize that if prime factorization of the integer N has any prime that is bigger than 7, then answer is "-1". Otherwise do simple prime factorization and figure out the degrees of 2, 3, 5 and 7. Suppose these numbers are K2, K3, K5 and K7 respectively. Observe that in order to find the smallest integer it has to be as short (in terms of number of digits) as possible. So, we will be constructing our answer from the end in the following way:
first put K3/2 nines in the end and set K3=K3%2,
next put K2/3 eights before nines and set K2=K2%3,
next put K7 sevens before eights,
next if K2>0 and K3>0 put single six before sevens and set K2=K2-1 and K3=K3-1,
next put K5 fives before in the similar way,
next if K2=2 put single four,
next if K3>0 put single three,
finally if K2=1 put single one.
Also need to handle special case when N=0 or N=1.
That's it.