informal EDITORIAL for Codeforces Round #364 (Div. 2)

Правка en1, от -skyline-, 2016-07-24 18:29:33

Codeforces Round 364 (Div. 2) There is still no formal EDITORIAL for Codeforces Round #364 (Div. 2) yet ,so I write a informal one. Sorry for my poor English. 701A - Cards You can calculate the sum (x) of a pair of cards x=2*(a1+a2+...+an)/n for every card ai,find a card ak which ai+ak=x and k is not used the n is small,so you can simplely write a o(n*n) solution(also there is a o(n) one,o(n*n) is enough) my o(n*n) solution[submission:19328905] 701B - Cells Not Under Attack You can just record the number of rows and columns that is not under attack if r rows and c columns is not under attack there is r*c cells that is not under attack o(m) my o(m) solution:19330540 701C - They Are Everywhere You can just use two pointers There are x types of Pokemon if [i,dp[i]-1] has x-1 types of Pokemon and [i,dp[i]] has x types of Pokemon dp[i+1]>=dp[i] so it's o(n) my o(xlogx+n) solution:19332828 701D - As Fast As Possible It's a math problem let d=ceil(n/k) just look at the bus it goes like that:

<<<<<<<<< >>>>>>>>>>>> <<<<<<<<< >>>>>>>>>>>> <<<<<<<<< >>>>>>>>>>>> the long lengths are the same(x) and goes to right the short lengths are the same(y) and goes to left it goes to right and put the old students down and does to left and welcome new students so x+y:x-y=v2:v1 it goes for d xs and (d-1) ys so: 1:d*x-(d-1)*y=l 2:x+y:x-y=v2:v1 3:ans=(d*x+(d-1)*y)/v2 so ans=l/v2*((d*2-1)*v2+v1)/(v2+(d*2-1)*v1) o(1) my o(1) solution:19334768 701E - Connecting Universities let's take 1 as the root of the tree record the depth of every vertex(depth of 1 is 0) record the number of schools of the subtree of every vertex the sum of the depth of the lca of every pair of school should as small as possible consider 2x schools of the subtree of vertex y(may be 2x is not the number of all the schools of the subtree of vertex y) every depth of lca of the 2x schools is at least the depth of y if a subtree of the son of y has k schools in the 2x schools(not in all the schools) 1:if the k of every son is always mink<=x you can match the schools to make every lca y 2:if for son z,mink>x match (2x-mink) schools of the subtree of z with the schools not in the subtree of z but in the subtree of y just look at z like look at y so,it's o(n) my o(n) solution:19344918 701F - Break Up Any solution?

other solutions are welcomed if you find any mistakes,tell me

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский -skyline- 2016-07-28 16:45:33 573
en7 Английский -skyline- 2016-07-24 18:45:44 7
en6 Английский -skyline- 2016-07-24 18:44:44 177
en5 Английский -skyline- 2016-07-24 18:41:38 110
en4 Английский -skyline- 2016-07-24 18:38:59 107
en3 Английский -skyline- 2016-07-24 18:35:49 47
en2 Английский -skyline- 2016-07-24 18:33:11 65
en1 Английский -skyline- 2016-07-24 18:29:33 2508 Initial revision (published)