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).
But the contest haven't finished yet.
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
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.
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
Could be, I also didn't see it earlier. Didn't know you could do that.
Yeah, it was posted until the contest was over. It was saved as a draft before that.
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.
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.
Can you please explain the proof? I don't see how the problem corresponds to the longest increasing subsequence problem.
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) .
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
The silver and gold versions of Cow Jog are different (this is a solution to the silver version)
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.
I can offer something easier. Not DFS but backtracking — much more easier.
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...
Problem 3 is the same as one problem in NOIP1999(China) called missile intercepting.
If someone can AC most NOIP/NOI problems dating back to 1999 under contest conditions, they probably should be at USACO camp anyways :-).
http://www.comp.nus.edu.sg/~noi/2012/noi-tasks-2012.pdf
Check out the problem "Walking"
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?
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
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 ?
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).
Thank you.Now i understand it!