lydrainbowcat's blog

By lydrainbowcat, 8 years ago, In English

311A - The Closest Pair

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:




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

311E - Biologist

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

Read more »

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

By lydrainbowcat, 8 years ago, In English


Codeforces Round #185 will take place on Sunday, May 26th at 19:30MSK (23:30CST).

This round is initiated by zanoes, and here are the problem setters:

  • Div.1E & Div.2B —— zanoes (**Zhang Gaoxiang**)
  • Div.1D & Div.1A —— liouzhou_101 (**Wang Qisheng**)
  • Div.1C & Div.1B & Div.2A —— lydrainbowcat (**Li Yudong**)

Testers are roosephu(Luo Yuping), FredaShi(Shi Haoyue), sjynoi(Sun Jiayu), sevenkplus(Gu Yuzhou), MinakoKojima(Tang Feihu) and Riatre.

Especially thanks Gerald for helping us to prepare the round, MikeMirzayanov for the great platform and Delinur for translation.

Score will be standard, 500-1000-1500-2000-2500 in both divisions. In our opinion, problems are easier than the past several rounds prepared by Chinese)

This is our first Codeforces round, I hope you can enjoy it. Wish you high rating and good luck!

UPD: We feel really sorry about the mistake we made. The following words were written by Div.1A (Div.2C)setter, liouzhou_101. .

Meanwhile, It's also zanoes's and my fault that we didn't check his checker carefully, even brought troubles to Codeforces flat. I beg your forgive for liouzhou_101, for he also tried to prepare the round well these days.

UPD2: The round will be unrated.

Editorials will come out soon. Now you can find some of the editorials here:

Contest is over. Congratulations to the winners.


  1. roosaphu (I promise it's someone who pretends to be roosephu, and I've known who he is.)
  2. cp12321
  3. RAD
  4. ACMonster
  5. kAc

And ryz , cgy4ever, who passed problem E in the contest.


  1. ymxlkAc
  2. sasha.sochka
  3. bohuss

Read more »

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