chrome's blog

Topcoder Open Algorithm Round 2D 2015
By chrome, history, 9 years ago, translation, In English

Hi there!

Tomorrow at 09:30 MSK will be held TCO15 Round 2D.

Some information about Topcoder Open is here.

It is the last change to advance to the next stage.

The max. number of competitors is 2500. 40 of them advances to next stage.

Let's discuss problems after contest.

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

»
9 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Are you really going to tell me that n^3 is sufficient to pass 250 :|?

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

    It would be rather strange

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

      And it got AC... Do I have to mention that I tried hacking it and got -25? (solution of sekiye)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it -37 Vote: I do not like it

        O(N(N + 1)(2N + 1) / 6) = O(N3) ( ͡° ͜ʖ ͡°)

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

        Well, this is very fast N^3. Everything is in cache and so on

        → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Did anyone have an intelligent solution for the medium problem? I solved it with a very stupid one :(

→ Reply
»
9 years ago, # |
  Vote: I like it -31 Vote: I do not like it

OK, I'm generally trying not to whine that much after every contest, but this is so hilarious :P.

In the beginning of my function in medium problem I had:

    if (n >= 10 * k) {
      int div = n / k;
      int nic = div - 5;
      return nic + maxTurns(n - k * nic, k);
    }

After that I had a tailored inequality n>=3k-1, but here I put those 5 and 10 because f&*( me. And since k may be up to 1e18 this causes overflow and changing 10 to 9 results in AC :>.

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

    Yeah, I always laugh at myself when I submit a solution that turns out to be wrong and it can be corrected after the contest by a few key strokes.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you share your solution idea?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Equivalent problem: X is a positive integer between 1 and N-K+1, and you want to guess it. In each turn you choose up to K numbers and ask whether X is in the chosen set.

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How do you solve the 250-pointer in O(n^2)?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    For fixed left end of interval x let's create two pointers y (balance point) and z (right end of interval). We iterate over z and slowly increase y (while side x - y is heavier than side y - z).

    Alternative solution. For interval x - z check if t[x] + 2 * t[x + 1] + 3 * t[x + 2] + ... is divisible by t[x] + t[x + 1] + t[x + 2] + ....

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

      Yes, I saw some solutions using the alternative solution you mentioned. But I did not understand it. Can you please explain that one?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Interval [1, 4] is balanced when 0 = 0·t1 + 1·t2 + 2·t3 + 3·t4 or 0 =  - 1·t1 + 0·t2 + 1·t3 + 2·t4 or 0 =  - 2·t1 + ... or 0 =  - 3·t1 + .... All these equations could be written as 0 = t1 + 2t2 + 3t3 + 4t4 + k·(t1 + t2 + t3 + t4) for some k. So the question is: is this equation true for some k?

        Another explanation. Moving balance point by one changes sum of distance*weight by exactly tx + tx + 1 + ... + tz.

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

    You can loop over all balance points.

    Calculate accumulative sum of moment to the left and to the right of that balance point. Match sum of moment to the left with equal sum of moment to the right.

    The problem with that solution is that substrings consisting of zeros only get calculated multiple times because they have multiple balance points (if the substring is of length x, it will be calculated x times).

    You can compensate this by counting the number of zero substrings and decreasing length(substring) — 1 from the total answer.

    → Reply
»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Screencast

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Confused about 1000... Here's what I thought:

Let pi be probability to succeed in level i, vi value of level i, Pi probability to succeed in all levels before i, Si sum of all boxes up to but not including i.

I'll assume every time we die we are forced to grab the gold we dropped, otherwise it would be equivalent to starting over. Chance of you failing level i and returning to it is qi = (1 - pi) * Pi.

Let Ei be the expected value when you reach level i for the first time.To go from i to i+1, you will grab the chest in i once, plus the chests in 1...i-1 everytime you fail i and come back. This would give .

In challenge phase I realized this is actually pretty close to being correct. Right formula is . Can anyone say where I went wrong or explain how to reach the correct solution?

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

    I actually had a similar solution at first. As a bit of a background, I came up with this problem after watching my friend play Dark Souls. The deaths in that game work similarly, in that you can go back to your corpse to collect dropped items, but there can only be at most one corpse in the game.

    Anyways, back on topic, I had a completely different approach to solve. I'm not entirely sure how to interpret your correct equation. I first define fi(x) to be the expected value we'll end up with given there is a pile of gold at the beginning of level i. We want to find f0(0), and we can also note that f0(0) = f1(0) = ... = fn - 1(0).

    Now, the key observation is that fi(x) is a linear function of x for all i, so fi(x) = ai·x + b (where b is the same for all i). Additionally, we can write the equations for all i. This gives a system of equations. You can solve this naively in O(n^3) with Gaussian elimination, but you can reduce to O(n^2) or O(n) by looking at the structure of the equations.

    I know this solution is a bit complicated, though the main reason I present this is because it can generalize to the harder version of this problem where you can have at most k piles of gold lying around.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Btw what is funny is that I came up with an idea of 500 problem two weeks ago when I saw this title of problem 567D - One-Dimensional Battle Ships :). I didn't read it, but in few secs I imagined a possible statement. We are playing battleships and we have a grip 1xn and somewhere there is a battleship 1xk and we have to find its exact location using least possible amount of guesses :P. So sad, that I haven't given it a thought longer than few secs, because I was at work :P.

→ Reply