Centers of circles form a regular polygon with side length 2. Now, consider the formula to find circumradius of a regular polygon and add 1 because you were connecting circle centres, but not their tangent points to the circle.

i also have wa#6

Same here... got stuck in Test-16 .

It can be solved using O(log(n) + log(k)) rows.

Do it like that:

1) put AA right before # to the left. This is 00 written base 26.

2) go right until you encounter -. Put + there and then go left until you hit #. Increase that number (it will become AB). Then go right again.

3) if you encounter # while walking right, go left and compute coordinate of last - mathematically using cells to the left as memory with base-26 2-digit arithmetics. For arbitrary k and n it will be more than 2 of course, that's why it's O(log(k)+log(n)), but not a constant.

4) like in case of 2 run right/left by putting - instead of + until result becomes zero (decrease it with every - set).

5) Find rightmost - and paint everything to the left with +

6) Find - and stop there

Though, I heard in this forum that the checker is wrong as it stops when there are n-1 pluses, but not when invalid state/character pair is met. So, actually you will have to use O(n) states to calculate 'n' and then bring back this value to calculation area inside read/write head :)

My solution for each k output 604 lines.

I don't understand what you mean there.

In fact, the problem asks for an interval [l, r] to find the average cost of a sub-interval.

That is, as for the first test case. After two 'change' queries we have cost(1, 2) = 1; cost(2, 3) = 2, cost(3, 4) = 2. Then we are asked for the average on the interval [2, 4] which is (cost(2, 3) + cost(3, 4) + cost(2, 4)) / 3.



So, given an interval [l, r] you are asked to compute:

int64_t n_of_intervals = 0;
int64_t total_sum = 0;
for (int i = l; i < r; ++i)
   for (int j = i + 1; j <= r; ++j)
      n_of_intervals += 1
      total_sum += cost(i, j)
output total_sum / n_of_intervals

What do you mean under "the method of construction"? For example I solved it using greedy algo. And, as I know, it's very hard to prove that for some fixed n solution doesn't exist. Therefore jury checked a possibility of coloring artists for all n <= MAXN with a help of their own method (maybe, also greedy). According to this time limit and MAXN for this problem were selected.

Эта задача имеет математическое решение. Нам задан граф на N вершинах, причём степень каждой вершины p (нужно самому понять, откуда берётся p). Требуется покрасить вершины так, чтобы смежные имели разный цвет. Утверждение: покраска возможна <=> цветов >=p+1. Необходимость очевидна. А достаточность реализуется по индукции: пусть мы покрасили k<N вершин, так что смежные имеют разный цвет. Возьмём не покрашенную вершину. Её степень <=p, а цветов >=p+1.Тогда покрасим её в любой из оставшихся цветов.

I used fast I/O to get 0.031. There are faster input methods that use fwrite/fread while mine is based on getChar/writeChar. Perhaps using even faster I/O can get you to 0.015

[code deleted]

Edited by author 10.09.2019 14:33

Edited by moderator 24.11.2019 13:26

It's wrong. Because the last leaf of the max heap is not necessarily minimum but you are removing it (v.pop_back();). Your code may remove the median element.

And the sort_heap has no effect.

Решил с грехом пополам, здесь писать не буду. Остались сомнения, что в условии(в тестах) правильно размер массива подсчитан, этот(SIZE) не катит.

Use Segment Trees with lazy propagation

The problem asks: "What is the longest closed path that you can assemble?"

Your examples are not closed loops. The first and last squares, although they are neighbours, they don't match their path endings.

u may try this test:
2
1 2
0 1
0 0

so output should be:
2
0 1
1 2

when WA is
2
1 2
0 1

This test helped me:
10
-5 1
1 14
-5 2
2 3
3 19
0 0

The answer is:
2
-5 1
1 14

Now, let's fight with WA5 :D