cgy4ever's blog

By cgy4ever, history, 7 years ago, In English

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)

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

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Update: added start time and link to regional contest.

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Contest coming!

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

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

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

    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.

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

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

»
7 years ago, # |
  Vote: I like it +61 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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.

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

    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

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

    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.

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

    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.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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.

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

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

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    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).

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Can you please explain the proof?

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

        Well, what requires proof?

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

          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.

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

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

»
7 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

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

      Yes, see ParenthesisRemoval from div1.

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

    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?

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Is TOPCODER Arena Down???

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Works now, but active contests are gone :D

    edit: back now :)