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