Блог пользователя cgy4ever

Автор cgy4ever, история, 8 лет назад, По-английски

Topcoder SRM 714

Time: 2:00 pm MSK Sunday, May 7, 2017

At the same time there will be an onsite contest: https://tco17.topcoder.com/regional-events/st-petersburg-russia/. We will share problems for both SRM and this regional contest.

Calendar: https://www.topcoder.com/community/events/ (Note: Still not updated)

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Update: added start time and link to regional contest.

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Contest coming!

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

We will share problems for both SRM and this regional contest.

Will the onsite regional event have div. 2 or div. 1 problemset?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    We need a problemset that are good for both first time player and TCO winner, we will use Div2 Easy, Div1 Easy and Div1 Hard, so hopefully everyone can enjoy it.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Registration open. Update: start time is 2:00 pm instead of 1:30.

»
8 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

Is topcoder down at the moment, I can't enter Arena?

»
8 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

Hard is very nice!

What's the intended solution of Med? Straightforward solution works in O(KlogMAX * memoizationcost), but I struggled a lot with TL.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm extremely sorry if what i'm gonna explain now is wrong, as i am incredibly inexperienced ->
    each time from f(n) we use f(n / 2) and f((n + k) / 2), Look at this tree of states, in each level the difference between the state with minimum number and maximum number is at most k, so that's why we can use an array of size k for each level, that would make the memoization cost O(1), of course please correct me if i'm wrong

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    Since all subtasks we get are in form of "calculate answer on segment [1, n / 2^x + y]", y <= K, n is L or R, memorization can be a simple array lookup. It works fast even in Java.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    My submitted solution was buggy, but I still think it can be solved like this (not sure what are your solutions memoizing, so I don't know how different it is; skipping some +/-1 adjustements): we compute the values for even numbers [L, L+K) directly, as well as for odd numbers in (R-K, R]. The rest of [L, R] can be split into even numbers from [L+K, R], and odd numbers that directly correspond to them. So we can solve recursively for the [(L+K)/2, R/2].

    memoization_cost is then replaced by the cost of directly compuing Klog MAX values, so I guess by log MAX with a low constant.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    No memoization:

    Go from the end, fix finishing number x ≤ K. Now if we look at the tree of numbers generated by going backwards from x, they will be of the form x2p - kq, where 0 ≤ q < 2p - 1 .

    Number of applications of f for such number is simply p + numberOfBits(q). Now it can be easily summed up over numbers from [L, R] if x and p are fixed.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    It seems the only thing I needed to do was to replace a map with unordered_map.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

    Another one, without memoization :

    Let Si = sum of g(i) for [K + 1, i + K]. Then, Si = i + (Si / 2) + (S(i - K) / 2 + i / 2). However, we can naively calculate g(i) in O(lgN) time. So, If we know S(i - K) / 2, we can know Si / 2 in O(KlgN) time. T(N) = O(KlgN) + T(N / 2) = O(K(lgN)2).

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Can you please explain the proof?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Well, what requires proof?

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I'm not quite sure how you derived Si = i + Si / 2 + S(i - K) / 2 + i / 2? Just intuition behind it would be useful. Thanks in advance.

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            That is a recursive definition, try to separate cases for odd / even number in interval, and write what happens next for both numbers.

»
8 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

I was the author of this round except for div1 medium. I hope you enjoyed the round!

After this round, I've got 99 problems on Topcoder.

Here is some of the code and hints for the problems.

div2
div1
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Can we solve RemovingParenthesis in O(n)? Somebody in my room did it using stack.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I know that one of the submitted hard are wrong. For example, on test where we should shuffle for a lot of times: (pos=-1+1000*k,delta=-1),(pos=1000*k,delta=1) for k in [1..100]. Do you have such a test?

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Is TOPCODER Arena Down???