[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.
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↵
[problem:701B]↵
You can just record the number of rows and columns that is not under attack.↵
It's o(m).↵
[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)↵
it goes like that:↵
>>>>>>>>>>>>↵
<<<<<<<<<↵
>>>>>>>>>>>>↵
<<<<<<<<<↵
>>>>>>>>>>>>↵
<<<<<<<<<↵
>>>>>>>>>>>>↵
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]↵
every depth of lca of the 2x schools is at least the depth of y .↵
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?↵
↵
↵
