codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

312.md (3399B)


      1 Source: https://codeforces.com/blog/entry/7785
      2 
      3 #### [311A - The Closest Pair](/contest/311/problem/A "Codeforces Round 185 (Div. 1)")
      4 
      5 [http://codeforces.com/blog/entry/7787](//codeforces.com/blog/entry/7787)
      6 
      7 #### [311B - Cats Transport](/contest/311/problem/B "Codeforces Round 185 (Div. 1)")
      8 
      9 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.
     10 
     11 Let a[i] be the distance from hill 1 to hill i, s[i]=a[1]+a[2]+…+a[i].
     12 
     13 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.
     14 
     15 Let f[i,j] indicates the minimum sum of waiting time with i feeders and j cats.
     16 
     17 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
     18 
     19 That’s O(PM^2). It’ll get TLE.
     20 
     21 Let p>q, if p is "better" than q, then:
     22 
     23 f[i-1,p]+s[p]-a[j]*p>f[i-1,q]+s[q]-a[j]*q
     24 
     25 (f[i-1,p]+s[p])-(f[i-1,q]+s[q])>a[j]*(p-q)
     26 
     27 g[p]-g[q]>a[j]*(p-q)
     28 
     29 So we can use **Convex hull trick** with a queue. Then we get O(MP), which can pass the problem.
     30 
     31 #### [311C - Fetch the Treasure](/contest/311/problem/C "Codeforces Round 185 (Div. 1)")
     32 
     33 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?
     34 
     35 We divide the H cells into k groups: Group 0,1……k-1. The i-th cell should be in Group (i mod k).
     36 
     37 * 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).
     38 * If we reach Cell x in Group (x mod k), we can also reach Cell (x+k) in the same group.
     39 
     40 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.
     41 
     42 Regard the groups as points. Regard k,k1,k2……kp as edges. And use a Shortest-Path Algorithm to calculate all D[i].
     43 
     44 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.
     45 
     46 Secondly, we build a binary-heap to solve operations of type 2 and 3.
     47 
     48 * Type1 – If a D[i] becomes smaller, we put the new cells we can reach into the heap.
     49 * Type2 – Decrease a value of a node in the heap, or a cell in the “Treasure Cell” array.
     50 * Type3 – Ask the biggest node in the heap and delete it.
     51 
     52 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).
     53 
     54 #### [311D - Interval Cubing](/contest/311/problem/D "Codeforces Round 185 (Div. 1)")
     55 
     56 [http://codeforces.com/blog/entry/7787](//codeforces.com/blog/entry/7787)
     57 
     58 #### [311E - Biologist](/contest/311/problem/E "Codeforces Round 185 (Div. 1)")
     59 
     60 [http://codeforces.com/blog/entry/7847](//codeforces.com/blog/entry/7847)
     61 
     62 #### [312A - Whose sentence is it?](/contest/312/problem/A "Codeforces Round 185 (Div. 2)")
     63 
     64 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.
     65 
     66 #### [312B - Archer](/contest/312/problem/B "Codeforces Round 185 (Div. 2)")
     67 
     68 [http://codeforces.com/blog/entry/7847](//codeforces.com/blog/entry/7847)