Errichto's blog

By Errichto, 8 years ago, In English

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

  • Vote: I like it
  • +115
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Div1Hard is great problem, thanks.

»
8 years ago, # |
  Vote: I like it +50 Vote: I do not like it

IMO, 500 was easier than 300 in Div1.

»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Maybe because all solutions to it had complexity O(n2log(n)), and consequently they were not very fast?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But examples were small and during a round programs are run on examples only — as long as queue is (almost) empty.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    For N up to 500 complexity is dangerous indeed. I recommend unordered_map — it's faster.