Petr's blog

Russia vs China match commentary
By Petr, 12 years ago, In English

http://petr-mitrichev.blogspot.ru/2013/05/ural-championship-day-1-russia-vs-china.html

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

Comments Comments (15)
| Write comment?
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Can we submit the problems after the contest ?

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

How to solve B? Especially interesting that "Shanghai Jiao Tong U" has solved it on the 10th minute after the start:

_Problem B: given a sequence of Ws and Ls, find a set of segments of maximum total length such that each segment has more Ws than Ls._

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

    Interesting problem ,anyone know how to solve it ?

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

      EDIT: totally wrong, as shown by reply below. Thanks for the counterexample!

      I haven't tested this yet, but I think it might work. Warning: like most of the algorithms I thought of.. they sounded good in my head, but might turn out to be crap/nonsense in reality, but read on to disprove/ if you think this might inspire a solution.

      From the given example, WLWLLLWWLWLWLLWL,

      create an array that stores the current elevation after reading k characters, where reading a W gives you a +1 elevation, and L a -1 elevation. From the example, we will get [0 1 0 1 0 -1 -2 -1 0 -1 , etc] So now the problem is, find the maximum set of intervals where each interval.endElevation > interval.startElevation

      Then, for each index of the elevation array, find the rightmost index in the elevation array that is greater than elevation[index]. We create an interval object out of this, with start time = index, end time = right most index with elevation > current elevation.

      Now the problem is just interval scheduling, and total runtime is O(n log n).

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

        Interval scheduling maximizes number of tasks, not total duration of them.

        Nevertheless it is not always optimal to find the rightmost index.

        For WLLLWWWLLWLLW optimal solution is W, WWWLLWLLW, not WLLLWWW, W, W

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

    Think how you would solve this using DP in O(n^2) time. Then make it O(n log n) using a tree structure. Maybe there's a greedy that works, but I'm not aware of one.

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

      There are several options how to solve this problem using DP in O(n2).

      For example, state can be:

      • dp[i] — best answer for prefix [0..i] or
      • dp[i][lastsum] — best answer for prefix [0..i] with last segment ending at position i and having sum equal to lastsum.

      What DP-solution do you talk about?

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

        Well, which one do you think you can make faster? :)

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          • dp[i] = max( dp[i-1], max(dp[j] + i-j | sum[0..i] > sum[0..j]) )
          • dp[i][lastsum + a[i]] = dp[i-1][lastsum] + 1

            dp[i][0] = max(dp[i-1][sum] | sum > 0)

          The first one looks more promising, but the second is also not very difficult. It is not obvious how n * log(n)-speed-up can be made.

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

            what about dp[i] = max(dp[i-1], dp[i-value[i]] + value[i])? value[i] is the maximum length of the valid segment ending at i. We can precompute value[i] first. If value[i] == 0, dp[i] = dp[i-1].

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

              It is not always optimal to take longest segments.

              For example WLLWLLWWWLWLLLW. In optimal solution last W is not connected to anything.

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

            The first formula is nice. Now observe that the second maximum is equal to i + max(dp[j]-j over j such that sum[0..j] > sum[0..i]). So for every j store a pair (dp[j]-j, sum[0..j]) and then on every step you need to take a maximum of the first coordinate over all pairs where the second coordinate is big enough. All you need is a tree allowing to take maximums over segments and to change elements.

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

    :) 10 minutes is enough to code a dp with fenwich tree

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

I think that D is the similar problem as SPOJ SUBLEX, which is solvable by using a Suffix Automaton.

→ Reply