Match Editorial

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

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;
  }

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)

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.

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)

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.

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.