Codeforces Round #268 Editorial

Codeforces Round #268 Editorial

By MiracleFaFa, 7 years ago,

I'll upload my example solutions and will post links to them as soon as it becomes possible.

All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :)

My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments.

469A - I Wanna Be the Guy

I Wanna Be the Guy is an interesting game. I strongly recommend it to you.

The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y.

7894174

469B - Chat Online

This problem is not hard. Just iterator over all possible t, and check if the schedule of Little X and Little Z will overlap.

7894252

Bonus:

1. p, q ≤ 50, l, r ≤ 109
2. p, q, l, r ≤ 105

468A - 24 Game

Solution 1:

If n ≤ 3, it's easy to find that it's impossible to make 24, because the maximal number they can form is 9.

If n > 5, we can simply add n - (n - 1) = 1, 24 * 1 = 24 at the end of the solution to the number n - 2.

So we can find the solution of 4, 5 by hand. 1 * 2 * 3 * 4 = 24, (5 - 3) * 4 * (2 + 1) = 24

7894267

Solution 2:

We can find the pattern like that n + (n + 3) - (n + 1) - (n + 2) = 0, and find the solution of 4, 5, 6, 7 by hand or brute forces.

Solution 3:

A knapsack-like solution.

7894283

468B - Two Sets

Solution 1:

If we have number x and a - x, they should be in the same set. If , it's obvious that . The contraposition of it is , that means if , a - x should in the set B. Same as the number x, b - x.

So we can use Disjoint Set Union to merge the number that should be in the same set.

If a - x doesn't exist, x can not be in the set A. If b - x doesn't exist, b can not be in the set B.

Then check if there are any conflicts among numbers which should be in the same set.

There are many other solutions to solve this problem based on the fact that x, a - x, b - x should be in the same set, like greedy, BFS and 2-SAT.

7894313

Solution 2:

If a = b, it's easy to find the solution.

We regards every number as a node. Every number x links to number a - x and number b - x.

The degree of every node is at most 2. So this graph consists of a lot of chains and cycles, and some node may have self loop.

We only need to check if the lengths of all the chains are even or the chain ends with a self loop.

7894323

Bonus:

Prove there is no cycle in the graph described in the solution 2.

Divided all the numbers from [0, n - 1] into two sets that have parameters a, b. Can you solved it in O(1)?

468C - Hack it!

Define . , so we should find a pair of number a, b that

Solution 1:

First we choose x randomly. Then we can use binary search to find the minimal d that .

So is very small, between 0 and . If , after choosing x atmost 9 * len + 2 times, we can definitely find a pair that

7894341

Solution 2:

We can use binary search to find the minimal d that g(d) ≥ a, g(d) ≥ 2a, ...

This solution is similar to the first one.

7894452

Solution 3:

We can use binary search to find the minimal d that g(d) ≥ a. And we use two pointers to maintain an interval [l, r] that until we find .

I can't prove the correctness of this algorithm, but it performs well in practice.

7894356

Solution 4:

Thanks ZhouYuChen for his talented idea.

If x < 1018, we can get f(1018 + x) = f(x) + 1. That means if we shift the interval [x + 1, x + 1018] by 1, the result will be increase by 1 too. And it also not hard to find that g(10x) = 45 * x * 10x - 1. So if , [a - x, a - x + 1018 - 1] is the answer.

It's easy to see that upper bound of the answer is a, because of pigeonhole principle (among g(0), g(1), ..., g(a) at least two are equal). So big integer is not required in this problem.

If solution 3 is correct, the upper bound of the answer can be 2 * 1016.

7878473

Bonus:

Prove or disprove that solution 3 is correct.

468D - Tree

I am sorry that this problem coincides with that one.

d(u, v) = depu + depv - 2 * depLCA(u, v), so the answer is:

depi there means the distance between node i and root.

We choose centroid of tree as root (let's denote it u), so we can make every pair (i, pi) are in different subtrees, that means depLCA(i, pi) = 0.

So the answer is .

The next part of this problem is find the lexicographically smallest solution.

We regards it as finding the lexicographically smallest matching in a bipartite graph.

For a subtree, if the amount of nodes in this subtree in the left part > the amount of nodes not in this subtree in the right part, the perfect matching doesn't exist. So the amount of nodes in this subtree in the left part + the amount of nodes in this subtree in the right part should be no more than the amount of nodes unmatched, while the root is an exception.

We can use a segment tree to maintain it easily. We determined the minimum possible pi from 1 to n. If there is a subtree that the amount of nodes in this subtree in the left and right part is equal to the amount of nodes unmatched, we must select a node from it, so pi equal to the node in this subtree with the minimum id. Otherwise, we can choose a node with the minimum id that is not in the same subtree with i.

7894417

468E - Permanent

The permanent can be obtained as follows: for each (e1, e2, ..., et) such that x1, xe2..., xet are distinct and ye1, ye2, ..., yet are distinct, add to the answer.

It can be proved by the formula :

,

where s and t are subsets of the same size of {1, 2, ..., n} and , are their respective complements in that set.

Construct a undirected graph G with 2n vertices v1, v2, ..., v2n, where the edge weight between vertex vi, vn + j is Ai, j - 1. We only need to know the sum of weight of all matchings that we choose t edges. The weight of matching is the product of all edge weights in the matching.

We only need to know the sum of the weights that we choose x edges in the each connected components.

The number of nodes in a connected component is s and the number of edges in this connected component is t.

Algorithm 1:

Because it's a bipartite graph, so the number of vertices in one part is at most s / 2. So we can use state compressed dp to calculate the ways to choose x edges in this connected component. The complexity is O(2s / 2 * s2).

Algorithm 2:

We can choose a spanning tree. The number of edges in spanning tree of these vertices is s - 1, and the number of non-tree edges is t - s + 1. So we can enumerate all the non-tree edge, use tree dp to calculate the ways. The complexity is O(2t - s * s2).

Combined with these two algorithm, the complexity is O(min(2s / 2, 2k - s) * s2)) = O(2k / 3 * k2).