### lydrainbowcat's blog

By lydrainbowcat, 7 years ago, ,

#### 311A - The Closest Pair

http://codeforces.com/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.com/blog/entry/7787

#### 311E - Biologist

http://codeforces.com/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.

#### 312B - Archer

http://codeforces.com/blog/entry/7847

• +6

 » 7 years ago, # |   +1 What is slope optimization?
•  » » 7 years ago, # ^ |   +9 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".
•  » » » 7 years ago, # ^ |   +14 It's called "Convex hull trick" in English, according to this: http://wcipeg.com/wiki/Convex_hull_trick
•  » » » » 7 years ago, # ^ |   +6 Thank you. I've fixed it.
 » 7 years ago, # |   +7 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?
•  » » 7 years ago, # ^ |   +8 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.
•  » » » 7 years ago, # ^ |   +3 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.
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   +20 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.
•  » » » » » 7 years ago, # ^ |   0 Thanks you, now its clear for me.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Great explanation. Thanks very much. Just one thing: I suppose it should be 0 <= k < j.
•  » » » » » 7 years ago, # ^ |   +11 Thanks for such a detailed and articulate explanation. I wish the editorials were written with a similar clarity and rigor.
 » 7 years ago, # | ← Rev. 2 →   +2 Hi, I can not understand why the formula given for f[i, j] is correct. Can somebody explain it to me? ThanksEdit: 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?
 » 7 years ago, # |   -14 I don't think there are 10 lines in this test case ??10,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ ,.._ miao.miao.miao. lala.lala.lala. lala.miao....
 » 7 years ago, # |   0 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.
 » 2 years ago, # | ← Rev. 2 →   0 Can someone please tell why my code is getting WA at test 3? Link Thanks in Advance!EDIT: Was able to find the problem — Need to declare a new convex hull for each iteration of feeder — Link
 » 10 months ago, # |   0 For 311A, I submitted FOR i from 1 to n PRINT (n-i,0) 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?
 » 8 months ago, # |   0 311B the feeder can actually start at any time including the negatives.
•  » » 7 months ago, # ^ |   0 Thank you for pointing that out! it was driving me crazy!
 » 8 months ago, # | ← Rev. 2 →   +5