Zlobober's blog

Topcoder SRM #607
By Zlobober, 11 years ago, translation, In English

Round starts in 10 minutes.

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

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

What was the problem with DIV1 Medium? I couldn't get a solution but so many people failed the system tests or were hacked (I guess their codes TLE'd)

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

    I guess their solutions used wrong assumptions, which leads to wrong solutions, which can be easily challenged with big random tests.

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

    It's not that surprising — the first thing to expect is a greedy strategy, and many such strategies can be invented, but it doesn't actually work.

    Firstly, only relative positions of corresponding rings of the lock matter, so you can replace pairs of (original,target) positions by just their differences D0[i]. You can add a correctly placed ring to the left of the lock and transform the sequence of differences to a new one: D[i] = D0[i] - D0[i - 1] (mod 10). In this case, an operation is just adding 1 to D[i] and subtracting 1 from D[j] for any pair (i, j), or just adding/subtracting 1 from D[i] (that corresponds to rotating several rings at the right side of the lock).

    We want to convert the array D to all zeroes using a sequence of operations; the order of operations doesn't matter. If we'd add 1 to D[i] and subtract 1 from D[k] (or from no D[k]), and at some other time subtract 1 from D[i] and add 1 to D[j] (or to no D[j]), it can be replaced by one operation, for example (D[j], D[k]). That means we only rotate each ring in 1 direction.

    Let's sum up D[i] of rings which are rotated up, and sum up 10 - D[i] of those rotated down; denote them as x and y. The answer is obviously , and x - y is constant (), so if we could find all possible x, we could obtain the result quite easily. And x < 10N, so it's now clear that a DP works. Let dp[i][j] be  > 0 if j is a subset sum from the first i entries of array D, 0 otherwise; dp[i + 1][j + D[i]] = dp[i][j + D[i]] + dp[i][j].

    The time required for this is O(10N2); it can be cut down by half if we're not interested in j + D[i] for j > 5N (because then we just have y > x, and we don't want even larger y); it can also be cut down on memory to O(10N) if we only remember the last 2 rows of the array. I haven't coded it during the contest, but it should pass.

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

The actual input of the first problem is one string , making the input is two vectors of strings was very confusing!!! I wasted time until I realized that this has nothing to do with the solution.

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

    That's normal on topcoder, they can't make the input string too big because challenges are not like codeforces where you can upload a generator or something

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

      Oh thanks for information! I'm new on topcoder.

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

        Yeah, it usually is confusing for the first time. When I did my first div1 contest on TC, the 250pt problem was also partly about parsing strings (but even worse than this time), and it left me really annoyed that "the problems are not about algorithms, but string parsing". I only found out later that such formats of input are not so common.

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

      I think I was lucky coz I took few times to make a large input and then hacked 3/4 TLE codes :p. It was an awesome feelings because TLE hacks are hard to get :p.

      → Reply