358A - Dima and Continuous Line

Author — Berezin

If our line has self-intersections, that some pair of semi-circles exists, which intersect each other.
Let points x₁ < x₂ are connected with a semi-circle and points x₃ < x₄ are connected with another semi-circle. Then this semis-circles intersect if one of the conditions is true:

1). x₁ < x₃ < x₂ < x₄
2). x₃ < x₁ < x₄ < x₂

Let’s iterate trough all pairs of semi-circles, and check if the semi-circles intersect each other. So, the solution will have complexity O(N²) what satisfied the constrains.

358B - Dima and Text Messages

Author — Berezin

It’s clear, that adding new random symbols means, that we can simply omit them, they don’t change the structure of the phrase:  < 3word₁ < 3word₂ < 3... word_N < 3. Let’s determine the phrase before inserting random elements: s = " < 3" + word1 + " < 3" + ... + " < 3" + wordN + " < 3". Lets i —is an index in s, we are waiting for. At the beginning i = 0; we will iterate though the sms and when we will meet the symbol which equals to s_i we will simply increment i.

if at some moment |s| ≤ I we found all needed symbols and answer is yes, otherwise – no.

358C - Dima and Containers

Author — Berezin

We know all the numbers at the beginning, so, it’s clear, that we want pop three maximums. We can “precalculate “ maximums with finding next zero and iterating through all numbers between two zeroes.
We should do pops from different containers, so let’s save maximums in the top of the stack, in the beginning of the queue and on the beginning of the dek. (you can do this in some other way) We should determine, where will be stored the 1st, 2nd and 3rd maximum. For example, the first(the biggest one) – in the stack, second – in queue, and the third – in dek. “trash” – other numbers we can save into the end of the dek.
Also you need to catch cases, when two or less numbers are between zeroes.

358D - Dima and Hares

Author — Sereja

Let’s look at the first hare: we chose them befoe second, or after. If it is chosen after the second, than the solution from the 2nd hare to the last doesn’t depend on the first one, otherwise, we will receive the same but before the second hair will be obviously the feed hair. So, we have two dinamics:
1). d0i — answer for suffix as a separate task.
2). d1i — answer for suffix if the previous hair for this suffix is feed already.
Movements:
d0n  =  an
d1n  =  bn
d0i  =  max(ai  +  d1i  +  1,  bi  +  d0i  +  1)
d1i  =  max(bi  +  d1i  +  1,  ci  +  d0i  +  1)
answer is d01;

358E - Dima and Kicks

Author — Sereja

The first thing to understand is that the answer is the divisor of maximal-length sequence of standing one by one ones. (1111…11)
Let’s iterate trough this number. Now we should check the table knowing the value of K. Let’s find the most left of ones, and choose from them the most top. Let it be (X, Y). then after each step Dima can appear inly in cells which look like: (X + K * a, Y + K * b). Let such cells are the vertexes of the graph. And sequences of ones – the ribs. We will build the graph. We should check that there are no additional ones in table. We should also check if the graph is connected and has en Euler’s path. The value of K is the next answer under the all conditions. The correct implementation will have the complexity O(N * N * log(N)). In reality it will be never achieved.