JOIN
 Match Editorial
SRM 291
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 Problems

FarFromPrimes
Used as: Division Two - Level One:
 Value 250 Submission Rate 402 / 488 (82.38%) Success Rate 255 / 402 (63.43%) High Score fpavetic for 248.21 points (2 mins 24 secs) Average Score 190.97 (for 255 correct submissions)

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:
 Value 500 Submission Rate 232 / 493 (47.06%) Success Rate 214 / 232 (92.24%) High Score raalveco for 485.64 points (4 mins 54 secs) Average Score 297.84 (for 214 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 376 / 392 (95.92%) Success Rate 366 / 376 (97.34%) High Score Eryx for 247.72 points (2 mins 43 secs) Average Score 190.45 (for 366 correct submissions)

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.

CrazySwitches
Used as: Division Two - Level Three:
 Value 1000 Submission Rate 33 / 488 (6.76%) Success Rate 9 / 33 (27.27%) High Score mastodonth for 821.93 points (13 mins 51 secs) Average Score 567.83 (for 9 correct submissions)
Used as: Division One - Level Two:
 Value 500 Submission Rate 229 / 390 (58.72%) Success Rate 123 / 229 (53.71%) High Score Ulan for 461.49 points (8 mins 20 secs) Average Score 312.44 (for 123 correct submissions)

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 breadth-first 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.

StickedWords
Used as: Division One - Level Three:
 Value 1000 Submission Rate 88 / 392 (22.45%) Success Rate 6 / 88 (6.82%) High Score marek.cygan for 747.85 points (17 mins 48 secs) Average Score 515.55 (for 6 correct submissions)

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 Ford-Bellman 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 pseudo-code shows the algorithm of the solution:

```  for i = 0..len-1 {
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 i-th 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 non-empty 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 non-empty 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>=len-1 for which C[i] is true.

By Andrew_Lazarev
TopCoder Member