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(2W·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(N3). 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(2H·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(N3) complexity. I could have set N ≤ 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(n2log(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 N up to 500 complexity
is dangerous indeed. I recommend unordered_map — it's faster.