### Errichto's blog

By Errichto, 3 years ago, ,

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

•
• +115
•

 » 3 years ago, # |   +24 Div1Hard is great problem, thanks.
 » 3 years ago, # |   +50 IMO, 500 was easier than 300 in Div1.
 » 3 years ago, # |   +26 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.
•  » » 3 years ago, # ^ |   0 In my room was dreemoon, he had the same problem with challenges.
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   +1 Maybe because all solutions to it had complexity O(n2log(n)), and consequently they were not very fast?
•  » » » » 3 years ago, # ^ |   0 But examples were small and during a round programs are run on examples only — as long as queue is (almost) empty.
•  » » » » » 3 years ago, # ^ |   +8 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.
 » 3 years ago, # |   0 y y could not I think of bitmasks in D2 1000 :|
 » 3 years ago, # |   0 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
 » 3 years ago, # |   0 Errichto btw in div2 500 I used map and I got TLE when I changed map to array I got ACC.
•  » » 3 years ago, # ^ |   +6 For N up to 500 complexity is dangerous indeed. I recommend unordered_map — it's faster.