-skyline-'s blog

By -skyline-, history, 8 years ago, In English

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 and poor format.

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

It's 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 '_' 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: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

First,find a way from s to t.

If there is no such way,the answer is 0.

If there is such way,try to stop every edge on it and try to find bridges and upuate the answer.

How to find a bridge?

DFS it with root s,record the depth of every vertex and the least depth it can reach without passing its father.

If the least depth x can reach without passing x's father > the depth of y then (x,y) is a bridge.

Try to stop edges o(n),and finding bridges o(m).

It's o(nm).

My o(nm) solution:19462368

Other solutions are welcomed.

If you find any mistakes,tell me.

UPD1:solution to problem F

Full text and comments »

  • Vote: I like it
  • +85
  • Vote: I do not like it