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

Автор diego_v1, 10 лет назад, По-английски

Problem 1 — Guard Mark:

The "2 ≤ N ≤ 20" constraint immediately suggests a DP + Bitmask solution. Let DP[m] be the maximum safety factor we can achieve with mask m. The transition will be as follows: DP[m + 2b] = min(Str[b], DP[m] - W[b]), where Str[b] and W[b] are the strength and weight of cow b, respectively, and b is a bit that's off in the current mask m. Initially, DP[0] = INF and DP[i] =  - INF for all i in the range [1, 2N - 1]. Our answer will be the maximum among all DP[m] such that the sum of heights of all the cows included in mask m is  ≥ H.

Problem 2 — Marathon:

Let D[i] be the distance to go from checkpoint i - 1 to checkpoint i, and S[i] be the distance we save by skipping checkpoint i (that is, go from checkpoint i - 1 to checkpoint i + 1, skipping i). Naturally, D[1] will be zero, as well as S[1] and S[N].

Let querydist(l, r) be the sum of all D[i] in the range [l, r], and querysave(l, r) be the maximum among all S[i] in the range [l, r], then to answer a "Q L R" query, we would do querydist(l + 1, r) - querysave(l + 1, r - 1). We can manage these queries with a segment tree with two satellite data in each node.

Finally, when we receive an update query to checkpoint i, we would need to properly update data for checkpoints i - 1 through i + 1.

Problem 3 — Cow Jog:

The first thing we must think about is "When do two cows cross each other if they are on the same lane?". They will cross when one cow's starting point is behind the other cow's, but its finishing point is farther than the other cow's. That is, if we represent the cows' covered points with a segment, one cow's segment will be completely contained within the other cow's segment.

Now, how do we know exactly how many lanes we will need? Well, let L[i] be the lane that cow i runs in. Initially, we set all L[i] to 0 and then we process all cows by starting point in the following way: Suppose we're currently processing cow c and the current cow's segment is completely contained within some other cows' segments. Among all those other cows, let m be the maximum of all L[i]. Then L[c] = m + 1. If the current cow's segment is not contained in any other segment, then m will be zero.

Another thing we must deal with is how to calculate those values efficiently. We can do it with a BIT or a Segment Tree after compressing the finishing points of all cows (BIT is probably the easiest way). Since the cows will be processed by starting point, when we process cow c, we know that all segments we've encountered so far, will have a starting point lower than the current cow's segment, so all we need to worry about is their ending points and the lanes they are assigned. We can have a Range Maximum Query using a BIT that stores the maximum lane number for each segment ending point. Let query(x) be the maximum lane number for all segments which have an ending point equal or higher than x, and update(x, l) be the update routine to set ending point x to lane l in the BIT. Then to process a certain cow c, all we must do is update(r, query(r) + 1).

Finally, our answer will be query(1).

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

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

But the contest haven't finished yet.

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

    From the Contest page:

    "You can take the contest during any 4-hour block of time you want, as long as you start during the larger contest window starting the morning of Dec 12 and ending Dec 16 at 23:59 UTC-12 time."

    4 hours after Dec 16 at 23:59 UTC-12 time ended about 15 minutes ago.

    http://www.timeanddate.com/worldclock/timezone/utc-12

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

      Yes, the contest is now officially over (though this was written well before it was). Future contests will resume ending on Monday; there were two different end dates written on different parts of the site so we went with the later one for this contest.

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

        I was thinking that this post was written earlier, but not made visible until just now, since I hadn't seen this earlier. If this was visible earlier, I agree it was too early.

        EDIT: I'm not sure either, but I thought I saw something about it earlier on the forums

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

          Could be, I also didn't see it earlier. Didn't know you could do that.

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

          It wasn't visible earlier. I wrote the blog entry, saved it as a draft and published it only after 4 hours had passed since the contest deadline.

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

Shorter answer for problem 3 :

Let pi and vi be the initial position and the speed of cow number i and ai =  - pi - t × vi .

Answer = LIS(a1, a2, ..., an) which LIS is Longest Increasing Subsequence.It is easy to prove.

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

    Can you please explain the proof? I don't see how the problem corresponds to the longest increasing subsequence problem.

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

      First of all, consider a graph G which its vertices are 1, 2, ..., n and there is an edge between vertices i and j (i < j) if and only if ai ≤ aj .

      Obviously, answer = χ(G) and ω(G) = LIS(a1, a2, ..., an) .

      We know that ω(G) ≤ χ(G) .So, we should just prove that χ(G) ≤ ω(G). Proof:

      Just assign color f(i) to vertex number i (f(i) = size of the longest increasing subsequence of sequence a1, a2, ..., an ending at i).

      So, if there is an edge between vertices i and j (i < j), f(i) < f(j) .So this is a valid coloring.So, χ(G) ≤ ω(G).

      χ(G) ≤ ω(G) and ω(G) ≤ χ(G), so answer = χ(G) = ω(G) = LIS(a1, a2, ..., an) .

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

Linear solution for the problem 3. Let a[i] = t * v[i] + x[i] Answer is number of i, such that a[i] < min(a[i+1] .. a[n]). code

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

    The silver and gold versions of Cow Jog are different (this is a solution to the silver version)

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

With the following observation, Guard Mark can be solved with a better complexity than O(N·2N): For cows i and j, if weighti + strengthi > weightj + strengthj, then cow i is always below cow j in the ordering with maximum safety. (This can be easily proved if you think of weighti + strengthi as the maximum weight that can be placed on top of the cow that cow i is standing on.)

Thus we can sort the cows by weight + strength, and run a DFS to solve the problem in O(2N). Here is my code.

We can also solve the problem in O(N·2N / 2) with meet-in-the-middle: Split the cows into two halves after sorting, and for each subset in each half, calculate the height, weight and maximum safety. Then we can sort the subsets by height and use two pointers to find the answer.

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

    I can offer something easier. Not DFS but backtracking — much more easier.

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

    And I finally got around to coding up the meet-in-the-middle using a treap here. Not sure if there is a nicer way to do this that doesn't involve implementing your own BBST...

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

Problem 3 is the same as one problem in NOIP1999(China) called missile intercepting.

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

I don't understand solution to the first problem(Guard Mark) clearly:can anyone explain to me what did we store in array DP and how we build dynamic?

P.S.can anyone give me his code?

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

    In DP[m] we store the maximum safety factor we can obtain for the given set of cows m, where m is a bitmask. For example, if m = 25, then that set corresponds to cows number 0, 3 and 4, since 25 is written as 10011 in reverse binary, which is how we work with bitmasks. When we use bitmasks, it's easier to number stuff starting from 0.

    The code is here: C++ Code

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

      1)What do you save in next_mask ?

      2)As i understand solution we choose m and we calculate maximum value of strenght(if h>j),but you didn't clear Rem after each m.Why we are safe from not taking any cow 2times ?

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

        1) I use next_mask for simplicity only. It's the variable where I store the next bitmask (the current set of cows plus the one I'm adding).

        2) I don't have to clear the array Rem. I initialize it to infinity and then try to minimize the value for each set of cows. We're not taking any cow 2 times because I choose the cow to take only from the '0' bits in the bitmask (the cows currently NOT in the set).