informal EDITORIAL for  Codeforces Round #364 (Div. 2)
Difference between en1 and en2, changed 65 character(s)
[contest:701]↵
There is still no formal EDITORIAL for  Codeforces Round #364 (Div. 2) yet ,so I write a informal one.↵
Sorry for my poor English.↵
[problem:701A]↵
You can calculate the sum (x) of a pair of cards
.
x=2*(a1+a2+...+an)/n↵
fFor every card ai,find a card ak which ai+ak=x and k is not used.
tThe 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).
mMy o(n*n) solution[submission:19328905]↵
[problem:701B]↵
You can just record the number of rows and columns that is not under attack
.
iIf r rows and c columns is not under attack there is r*c cells that is not under attack.
It's o(m).
mMy o(m) solution:[submission:19330540]↵
[problem:701C]↵
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:[submission:19332828]↵
[problem:701D]↵
It's a math problem
.
let d=ceil(n/k)↵
jJust look at the bus.
it goes like that:↵
>>>>>>>>>>>>↵
   <<<<<<<<<↵
   >>>>>>>>>>>>↵
      <<<<<<<<<↵
      >>>>>>>>>>>>↵
         <<<<<<<<<↵
         >>>>>>>>>>>>↵
tThe long lengths are the same(x) and goes to right.
tThe short lengths are the same(y) and goes to left.
iIt 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)↵
It's o(1).
my o(1) solution:[submission:19334768]↵
[problem:701E]↵
lLet's take 1 as the root of the tree.
rRecord the depth of every vertex(depth of 1 is 0).
rRecord the number of schools of the subtree of every vertex.
tThe sum of the depth of the lca of every pair of school should as small as possible.
cConsider 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 
.
iIf 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:[submission:19344918]↵
[problem:701F]↵
Any solution?↵


oOther solutions are welcomed.
iIf you find any mistakes,tell me.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English -skyline- 2016-07-28 16:45:33 573
en7 English -skyline- 2016-07-24 18:45:44 7
en6 English -skyline- 2016-07-24 18:44:44 177
en5 English -skyline- 2016-07-24 18:41:38 110
en4 English -skyline- 2016-07-24 18:38:59 107
en3 English -skyline- 2016-07-24 18:35:49 47
en2 English -skyline- 2016-07-24 18:33:11 65
en1 English -skyline- 2016-07-24 18:29:33 2508 Initial revision (published)