Sorry for long testing queues and timeouts. I hope it won't repeat.

Congratulations for the winners — tourist, Petr, Egor, and snuke. They managed to solve all three problems!

Thanks for helping Limak again. What do you think about problems? Feedback will be appreciated.

#### Div2

**250, BearPaints** — Iterate over one side of desired blue rectangle and in constant time calculate maximum possible second side. code

**500, BearDartsDiv2** — Iterate over three numbers. For found value of a*b*c we must know how many times it occurs in some suffix of a sequence. We need an array or a map. code

**1000, BearDestroysDiv2** — Dynamic programming with bitmasks, *O*(2^{W}·*H*·*W*). Iterate over cells in the given order (first row, then second row and so on) and consider all possible state of the next *W* + 1 cells. code

#### Div1

**300, BearCries** — Dynamic programming in *O*(*N*^{3}). *dp*[*i*][*A*][*B*] where *A* is number of started emoticons already with at least one underscore (ready for being closed by second semicolon) and *B* is number of started emoticons with single semicolon only (without underscores). code

**500, BearDarts** — Rewrite given condition as *t*[*a*] / *t*[*b*] = *t*[*d*] / *t*[*c*]. Use map of pairs — irreducible fractions. code

**900, BearDestroys** — Problem would be easier with small *W* and big *H*. But it can be proved that we can consider Limak's walk in some other order, diagonal by diagonal:

```
1247..
358..
69..
```

Now we can use the same technique as in div2hard to get complexity *O*(2^{H}·*H*·*W*). code

Div1Hard is great problem, thanks.

IMO, 500 was easier than 300 in Div1.

As for me, problems were quite standard, though I haven't managed to find all bugs in my div1Hard.

By the way, what problems did happen during the round? I tried to hack the solution of my roommate 3 times, but received "Connection timed out" all three times. Suprisingly, his solution then failed system tests.

In my room was dreemoon, he had the same problem with challenges.

Problems were easy and many people were submitting.

In both d1easy and d2easy intended solutions had running times bigger than 100ms. Usually these two problems have low constraints, like N <= 50, even for

O(N^{3}) complexity. I could have setN≤ 50 in d1easy.But the main load was from d1med and I don't know why.

Maybe because all solutions to it had complexity

O(n^{2}log(n)), and consequently they were not very fast?But examples were small and during a round programs are run on examples only — as long as queue is (almost) empty.

You are not taking into consideration people testing their codes on maxtests during the round.

I personally ran some 4-5 tests with arrays of size 1000 on TC servers. Assuming other people did something similar too it is possible to see why there was heavy load from d1 medium.

y y could not I think of bitmasks in D2 1000 :|

could you explain more about D2 hard? I can only think of DP with complexity O(2^(W) * 2^(W) * W * H), I dont know how to compress them

Errichto btw in div2 500 I used map and I got TLE when I changed map to array I got ACC.

For

Nup to 500 complexity is dangerous indeed. I recommend unordered_map — it's faster.