Tuesday, February 21, 2006 Match summary In division 1 easy and medium problems have a pretty high success rate, but only 6 participants successfully solved the hard. The winner is marek.cygan who is more than 250 points ahead of Per and bmerry. In division 2 medium and hard problems were the same as easy and medium from division 1. Only 9 participants were able to solve the hard contradictory to 124 successful solutions from division 1. The first place got the newcomer mastodonth, followed by oldbig and another newcomer vyxaryx.
The ProblemsFarFromPrimesUsed as: Division Two  Level One:
The solution for this task is pretty straightforward. You just need to loop over all numbers from A to B and check for each if it is far from primes. The main challenge here is to write function which will check if the number is prime or not. Here is the sample implementation of such function: boolean isPrime(int num) { if (num < 2) return false; for (int i = 2; i*i <= num; i++) if (num % i == 0) return false; return true; }Snowflakes Used as: Division Two  Level Two: Used as: Division One  Level One:
There are two different solutions for this problem. You can iterate through all cells of the flared out snowflake and for each cell find where it will be in the folded triangle by modeling the described in the problem statements manipulations. Another way is to simulate unfolding of the folded snowflake by inversing the original manipulations. You can see Eryx's solution as an example for the first way, and Petr's solution for the second. CrazySwitchesUsed as: Division Two  Level Three: Used as: Division One  Level Two:
This task can be solved using graph theory. The graph should be build using following considerations. The vertex of the graph is pair of our current position and state of the light in all rooms. Two vertices are connected with an oriented edge of weight 0, if it is possible to get from the first to the second by turning exactly one switch. Two vertices are connected with an oriented edge of weight 1, if it is possible to get from the first to the second by making exactly one movement. To solve the problem in terms of such graph we need to find a shortest by total weight way from the initial state to the final. It can be done by using slightly modified breadthfirst search. To minimize the number of "1"weight edges, it is necessary to replace queue with deque. After taking the vertex from the head of the deque, the vertices adjusted with "0"weight edge should be added to the head of the deque, and the vertices adjusted with "1"weight edge  to the tail of the deque. StickedWordsUsed as: Division One  Level Three:
Let's define L(c) as the maximal length of the sequence which can be built starting with the letter c. Let's build a graph where vertices are letters and edges are words. Each edge is oriented from the first letter of the corresponding word to the last and has the weight equal to the length of the word minus one. The L(c) can be found by using the FordBellman algorithm on this graph. Note, the L(c) could be infinite, if a cycle can be reached from the corresponding vertex of the graph. We will store the current answer as an array of characters A[i]. For each position in the array A[i] we will store the flag C[i] which is true, if the A[i] is the end of some sequence starting from the beginning of the array and built using the rules from the problem statement. All A[i] at the beginning should be equal to some "empty" character, which should be considered lexicographically later than any other, all C[i] should be equal to false. The following pseudocode shows the algorithm of the solution: for i = 0..len1 { if (i > 0) and (not C[i]) continue; foreach Word in dic { if (i + length(Word) + L(last symbol of Word) < len) continue; if (A[i] is not empty) and (Word[0] != A[i]) continue; S = substring of A starting on the ith position with length equals to the length of Word; if (Word > S) continue; if (Word == S) C[i + length(Word)  1] = true; if (Word < S){ Pos = i + position of the first character which differs in Word and S; for j = pos..index of the last nonempty character of A { C[j] = false; } for j = 0..length(Word)  1 { A[i + j] = Word[j]; } for j = i+length(Word)..index of the last nonempty character of A { A[j] = empty; } C[i + length(Word)  1] = true; } } } The answer will be the part of the A from the beginning to the first i>=len1 for which C[i] is true. 
