informal EDITORIAL for Codeforces Round #364 (Div. 2)
Difference between en6 and en7, changed 7 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 and poor format.↵




[problem:701A]↵

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]↵


[problem:701B]↵

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.↵

It's o(m).↵

My 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)↵

Just look at the bus.↵

it goes like that:↵

>>>>>>>>>>>>↵

___<<<<<<<<<↵

___>>>>>>>>>>>>↵

______<<<<<<<<<↵

_____>>>>>>>>>>>>↵

_>>>>>>>>>>>>↵

____<<<<<<<<<↵

____>>>>>>>>>>>>↵

_______<<<<<<<<<↵

_______>>>>>>>>>>>>↵

_
_________<<<<<<<<<↵

_
_________>>>>>>>>>>>>↵

The '_' means empty(I cannot format it).↵

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)↵

It's o(1).↵

my o(1) solution:[submission:19334768]↵


[problem:701E]↵

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:[submission:19344918]↵


[problem:701F]↵

Any solution?↵

[cut]↵

Other solutions are welcomed.↵

If you find any mistakes,tell me.↵

[cut]↵

Sorry I don't know how to use format.Can you tell me how to do that?

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)