lydrainbowcat's blog

By lydrainbowcat, 11 years ago, In English

311A - Ближайшая пара

http://codeforces.net/blog/entry/7787

311B - Транспортировка кошек

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 - Достать сокровище

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 - Куб на отрезке

http://codeforces.net/blog/entry/7787

311E - Биолог

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

312A - Чье это предложение?

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 - Лучники

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

Full text and comments »

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

By lydrainbowcat, 12 years ago, In English

Hello,everyone!

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. http://codeforces.net/blog/entry/7773#comment-134702 .

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: http://codeforces.net/blog/entry/7785

Contest is over. Congratulations to the winners.

Div.1

  1. zfmdhy786 (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.

Div.2

  1. ymxlkAc
  2. sasha.sochka
  3. bohuss

Full text and comments »

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