311A - The Closest Pair
http://codeforces.net/blog/entry/7787
311B - Cats Transport
P.S. I feel very sorry that I thought it was a traditional DP problem with only 800B code and didn't realize some participants were not familiar with such kind of problems, so I said it was easy.
Let a[i] be the distance from hill 1 to hill i, s[i]=a[1]+a[2]+…+a[i].
Firstly, we sort the cats by (Ti-a[i]). Then we can divide the cats into P consecutive parts, and plan a feeder for each part. Dynamic Programming can solve this problem.
Let f[i,j] indicates the minimum sum of waiting time with i feeders and j cats.
f[i,j] = f[i-1,k]+a[j]*(j-k)-s[j]+s[k] = a[j]*j-s[j] + f[i-1,k]+s[k]-a[j]*k
That’s O(PM^2). It’ll get TLE.
Let p>q, if p is "better" than q, then:
f[i-1,p]+s[p]-a[j]*p>f[i-1,q]+s[q]-a[j]*q
(f[i-1,p]+s[p])-(f[i-1,q]+s[q])>a[j]*(p-q)
g[p]-g[q]>a[j]*(p-q)
So we can use Convex hull trick with a queue. Then we get O(MP), which can pass the problem.
311C - Fetch the Treasure
Firstly, we solve such a problem: if we can go exactly k,k1,k2……or kp cells forward each step, what cells can we reach?
We divide the H cells into k groups: Group 0,1……k-1. The i-th cell should be in Group (i mod k).
- If we reach Cell x in Group (x mod k), we can also reach Cell (x+kj , 1<=j<=p) in Group ((x+kj)mod k).
- If we reach Cell x in Group (x mod k), we can also reach Cell (x+k) in the same group.
Let D[i] be the minimum cell we can reach in Group i. Then we can reach all the cells which number are bigger then D[i] in Group i.
Regard the groups as points. Regard k,k1,k2……kp as edges. And use a Shortest-Path Algorithm to calculate all D[i].
Notice that there are at most 20 operations of type 1, we are able to run such an algorithm after each of these operations. The total time complexity is O(20*k*20*log(k)) with Dijkstra.
Secondly, we build a binary-heap to solve operations of type 2 and 3.
- Type1 – If a D[i] becomes smaller, we put the new cells we can reach into the heap.
- Type2 – Decrease a value of a node in the heap, or a cell in the “Treasure Cell” array.
- Type3 – Ask the biggest node in the heap and delete it.
These are basic operations of binary-heap. The time complexity is O(NlogN). In C++, you can also use priority_queue from STL and lazy-tags. So we can solve the whole problem in O(400klogk+NlogN).
311D - Interval Cubing
http://codeforces.net/blog/entry/7787
311E - Biologist
http://codeforces.net/blog/entry/7847
312A - Whose sentence is it?
We only need to find out if “miao.” is a prefix of the sentence, and if “lala.” is a suffix of the sentence. Pay attention to the situation when both conditions are satisfied.
What is slope optimization?
I probably don't know its English name. It's a kind of optimization in DP using the monotonicity of the ratio of adjacent elements in a queue. The problem "Commando" in APIO2010(http://www.apio.olympiad.org/2010/) is an example. But the one in this round is much easier than "Commando".
It's called "Convex hull trick" in English, according to this: http://wcipeg.com/wiki/Convex_hull_trick
Thank you. I've fixed it.
I'm sorry, but I dont understand why "f[i,j] = f[i-1,k]+a[j]*(j-k)-s[j]+s[k] = a[j]*j-s[j] + f[i-1,k]+s[k]-a[j]*k" Can anybody explain me?
It's probably this:
f[i,j] = min{f[i-1,k]+a[j]*(j-k)-s[j]+s[k] | k < j}
This "a[j]*(j-k)-s[j]+s[k]" calculates the total waiting time for those cats between k and j, assuming the (i-1)-th feeder takes care of the k-th cat and the i-th feeder takes care of cats between k and j.
What I found confusing is the usage of a[j], in the above expression, where j represents j cats, whereas a[i] was originally stated to be "Let a[i] the distance from hill 1 to hill i". Also, the usage of "s[i] = a[1]+a[2]+…+a[i]." is not quite clear with the definition of a[i]. What does it represent? Any clarification will be greatly appreciated.
Consider the array that contains values p[i], the prefix sum of height values where p[i] = h[1] + h[2] +... + h[i]. Now consider array
a[i] = T[i] — p[c[i]], where c[i] denotes the hill number ith cat goes to. Sort this array. Now f(i, j) denotes the minimum time taken by i feeders to pick up the first j cats from the array 'a'. Recursion can be written as
f(i, j) = times taken by i-1 feeders to pick up first k cats + time taken by ith feeder to pick up cats from k+1 to j. This can be written as
f(i, j) = min{f(i-1, k) + (j-k)*a[j] — s[j] + s[k]} 1 <= k <= j
As for the s[k] — s[j], you can interpret it like this. Each -a[i] denotes how much time the cat would have to wait, if a feeder starts at time 0. If feeder starts at time x, it will experience a delay of x — a[i]. For cats from k+1 to j, the feeder starts from his position at a[j] (you have to convince yourself this is correct). So the delay experienced by cats from k+1 to j is (a[j] — a[k+1] + a[j] — a[k+2] + .... a[j] — a[j]) = (j-k)*a[j] — (s[j] — s[k]) Correct me if I am wrong.
Thanks you, now its clear for me.
Great explanation. Thanks very much. Just one thing: I suppose it should be 0 <= k < j.
Thanks for such a detailed and articulate explanation. I wish the editorials were written with a similar clarity and rigor.
Hi, I can not understand why the formula given for f[i, j] is correct. Can somebody explain it to me? Thanks
Edit: In the contest I got another formula(suppose b[i] = T[i] — a[h[i]]): f[i — 1, k] + b[i] * (j — k) But I can't understand why these two are the same?
311B / 312D In my view, it will make more sense if we add an additional constraint that all feeders should start at a non-negative time.
Yes, I stand with you.
For 311A, I submitted
Here p[j].x — p[i].x is always negative but the checker gave wrong answer on test 4. Is this the same mistake that you've mentioned?
311B the feeder can actually start at any time including the negatives.
Thank you for pointing that out! it was driving me crazy!