### rng_58's blog

By rng_58, history, 3 years ago, , Let's discuss problems.

Does anyone have an idea for D? Comments (40)
 » How to solve C, H, G, K?
•  » » 3 years ago, # ^ | ← Rev. 2 →   H: The answer is the number of ways we can delete two vertices from the tree so that the size of its maximum matching doesn't change.Compute this by subtree dp: dp[x][u][k][r] is the number of ways to delete r vertices from the subtree of x such that the size of its maximum matching is k smaller than the size of the optimal matching for the subtree of x. If u = 0 then x is not matched and not removed (we can later match it to its parent) and if u = 1 then x is removed or used in the matching.You should count each way of removing vertices only once, so you should fix a strategy to get exactly one maximum matching for each set of removed vertices. One way to do this is to match a vertex to its first child that is not matched or removed.
•  » » 3 years ago, # ^ | ← Rev. 2 →   C: First, I put vertex on each edge. [v1-v2] => [v1-e1-v2] So, this problem can be solved with dominator tree, but I get TLE. So, I rewrite program more faster, faster, faster...., I get AC with 0.999s/1s!!!!(with +14...XD)H: If we know edmond's blossom algorithm, we can convert this problem to "we have forest those vertex colored with red, blue, yellow. count (u, v) with color(u) == red && color(v) == red && path(u, v) have blue vertex." Construct forest and solve this problem are easy, but my poor english can't explain this convert...
•  » » G: choose a root arbitrarily(respecting all the requests), then recursively solve for each connected component of "i want this guy to be my superior"-requests.
•  » » » Wow. before reading your solution I thought my algorithm was wrong. but.... •  » » » I am very suprised it was solved by just 7 teams. It was meant to be one of easier problems. On AE it was solved by ~75 people including some Div2 guys.
•  » » » » Some of this desperated div2 guys like me spent 24 hours on the problem on AE ;)
•  » » 3 years ago, # ^ | ← Rev. 2 →   C : We will disregard all vertices which is not reachable from 1. We calculate DP[i] in topological order, which is If the vertex can be blocked by cutting one edges, we store that edge's index. If there is more than one such edges, we store the one closest to 1. Otherwise, -1 For some vertex v If more than two adjacent vertex have DP[i] = -1, DP[v] = -1; If one adjacent vertex have DP[i] = -1, if there is no other adjacent vertex, store that adjacent edge's index. Otherwise DP[v] = -1. If no adjacent vertex have DP[i] = -1, check if there is more than two distinct value of DP[i]. If there is, DP[i] = -1, otherwise, DP[i] is that common value It's not hard to prove why this works. O(n+m)
•  » » K. Sort the array a. For each i we want to check whether we can distinguish a i and a i + 1. We can distinguish them if there exist x, y such that x is the sum of some subset of {a 1, ..., a i - 1}. y is the sum of some subset of {a i + 2, ..., a N}. We can distinguish x + y + a i and x + y + a i + 1 using the scale. We define dpL[i][j]: the minimum z such that z%C = j and z is the sum of some subset of the first i elements. Similarly define dpR for suffixes. With these DP arrays straightforward checking of the conditions above will work in O(NC 2). It's not hard to improve it to O(NClogC) with priority_queue.
•  » » » Why should we check only a i and a i + 1?
•  » » » » We get 2 N numbers by measuring all subsets. These numbers can be divided into two multisets of size 2 N - 1 by the inclusion of particular item. We can't distinguish two items when this division results in the same pair of multisets, thus this is an equivalence relation.
•  » » » » » 3 years ago, # ^ | ← Rev. 5 →   Why is this true? We also know which elements were for every number in multiset.Upd.: I understand why this is true: a_i is equivalent to a_j if for every subset of {1..n}/{i}/{j} we get the same value. So I got solution using two iterators for 2*n * nc.Upd.2: I proved it from my understanding but still don't understand your prove.
•  » » » » » » Suppose that the multiset corresponding to the subsets with a 1 (call it X) and the multiset corresponding to the subsets with a 2 (call it Y) are the same. In this case, the multiset corresponding to the subsets that contain a 1 and doesn't contain a 2 ( ) and the multiset corresponding to the subsets that contain a 2 and doesn't contain a 1 ( ) are the same. In each of these sets, obviously the numbers are sorted by the part that comes from {a 3, ..., a N}, so for any subset S of {a 3, ..., a N}, the "weight" (shown by the scale) of and the weight of are the same. That means even if someone secretly swaps a 1 and a 2, you can't notice that.
•  » » » » » » » Yes, this proof is easier than mine. Thanks.)
•  » » » "For each i we want to check whether we can distinguish ai and ai + 1" — omg, that's so trivial and brilliant and the same time :o
•  » » » We can improve it to O(NC) by using sliding window with deque.
•  » » 3 years ago, # ^ | ← Rev. 2 →   C. We've got a topological sort of the graph vertices, sorted edges by the left edge vertex according to the topological sort and processed edges. Let's call the vertex that can be reached by two necessary paths "good". Let's process the edge A -> B. If B has not been visited earlier, remember its parent A. Otherwise find LCA(A, parent[B]) and check whether there is the good vertex on the path between LCA(A, parent[B]) and A or between LCA(A, parent[B]) and parent[B] or not. If there is such vertex on either of these paths we call the vertex B "good".
•  » » 3 years ago, # ^ | ← Rev. 2 →   H:Calculate maximum matching bottom-up. For each matching edge color black the parent side vertex of it (all other vertices are white). Cut edges connecting two black vertices. For each black leaf remove it and adjacent white vertex. Remove black vertices has at least three neighbours. Then, we can connect two vertices if and only if they are white vertices from different connected components.
 » 3 years ago, # | ← Rev. 2 →   Problem D:If you sort (ai,bi) by ai, then you need to do this: take maximum element and change all numbers to the right b_j+=a_j (its own adding value) and delete maximum (put -inf). We couldn't understand how to implement it.
 » Where can we find results?
•  » »
 » Explain, please, samples in problems I and O(div 2).
 » How to solve O,E div2?
 » Some ideas for D: you only need to collect from each field at most once (if you collected from it twice you might as well not go the first time) given a set of fields to collect from, we collect them in sorted order of a_i. given an optimal set of k fields, we can construct an optimal set of k+1 fields by adding one field (I'm not sure if it's true but this seemed to match with some small random cases) we can model the process as follows: initially each field starts at value b_i. We take the max value firld, say it has index k. We add max(a_i, a_k) to the value of field i. This gives a simple n^2 solution, but not sure how to optimize it.
•  » » 3 years ago, # ^ | ← Rev. 5 →   Sorry for posting completely wrong stuff
•  » » The problem is pretty similar to Bear and Bowling from one of Errichto's rounds. You can write the DP and optimize with f.ex. splay. You can also write a not-very-nice segtree or sqrt convex hulls (the last thing actually worked for a nonzero number of points of AE, but it's really unlikely to squeeze it for accepted)
•  » » Probably the easiest way: create a trie containing all the binary words describing the correct assignments of the variables x 1, x 2, ..., x n (e.g. if the assignment is okay, we want the trie to contain the word 101). Do it using the following construction: start with a single leaf (no variables). Add the variables in the decreasing index order.When adding a variable x j to the trie T describing the choices on variables x j + 1, ..., x n, we need to take two copies of T and join them with the root (for each possible choice of x j). Then, for each clause starting with x j, remove the appropriate subtree from the trie (e.g. if the clause if , remove the subtree 010 as it fails this clause).Doing it straightforwardly, we'd have an O(2 n + m) algorithm ( m — total length of the clauses). However, instead of copying the tries, we can make them persistent and get the linear runtime.
 » 3 years ago, # | ← Rev. 2 →   Full solution to D:We observe first three observations that lewin noted. Using this we arrive at what -XraY- said. Unfortunately, I don't know any way it can be implemented in an efficient way (Marcin_smu do you know one? I didn't get whether that's what you do).We assume glades are sorted according to a i. Let p 1, ..., p n be optimal order of adding glades to our partial solutions (that means, if we want to get answer for k days we need to collect mushrooms from glades of indices p 1, ..., p k in an ascending order of a values).We need to turn our thinking upside down. Instead of determining firstly p 1, then p 2 and so on for each k we will determine optimal order if we consider only glades with k smallest a i values. Key observation here is that adding $k+1$th glade doesn't affect order of adding previous glades (what follows from what -XraY- said)! So $k+1$th order will be $k$th order with $k+1$th glade inserted somewhere in the middle. Given this we can determine those orders using your favorite balanced binary tree.By the way, I think that third lewin's claim is highly nontrivial. My proof used some augmenting paths-like argument, but I don't remember it now clearly.I like that problem very much, it's sad nobody solved it, but I am not very surprised since it took me 5 hours to come up with solution and 5 hours to code :P (this was my first time I implemented BBST). However on AE ~10 people got full marks (but we were given almost 2 days), so it was not impossible to solve it.
 » 3 years ago, # | ← Rev. 4 →   Our solution for C:Main idea is to track "sources" of single paths to quickly check whether different incoming edges to this vertex are from the same "source".Lets associate with every graph vertex two additional values: paths[i] is amount of paths that lead to vertex with number i from vertex 1. 0 <= paths[i] <= 2. Initially paths[i] = 0 for every i > 1 and paths = 2 source[i] is the pointer to the vertex from where single path that leads to vertex i takes it's "source". (only matters for vertexes that has it's paths set to 1) "Source" of the path is the vertex with paths = 1 and there is an edge that leads from vertex with paths = 2 to this vertex. Algorithm:Lets calculate paths for each vertex in thier topological order.Calculating for vertex i: lets check every edge that leads to vertex i whether this edge give us additional path to this vertex. Lets call j the vertex that is the start of current edge that leads to i. If paths[i] == 0 && paths[j] > 0 then we can add path from j to i and set paths[i] = 1. Now we should set the "source" of this path: if paths[j] == 2 then we create new "source" of single path that starts in vertex i, if paths[j] == 1 then we "push the stream" from some other "source" and save the pointer to it's initial "source" — source[i] = source[j] If paths[i] == 1 then we can only accept another path form another "source" or from the vertex with paths[j] == 2 If paths[i] == 2 already then we cannot change anything and we can skip all other edges to this vertex In the end just print all indexes of 2 in paths array.Complexity: O(N+M)Why does it work: Sources of single is just an end of edge from 2 paths to one: they path spread thier "single stream" to all edges that can be reached from this source and all of them will point to this "source". All the vertexes that can be reached only through this source use edge that created this source — all of them become unreachable if we remove this edge. If the vertex can be reached form multiple sources (or directly of two-pathed vertexes with two edges) it becomes two-pathed itself and can create this own sources. Two-pathed vertexes can create infinite new sources because we need to make only two path and in the end to answer we can choose two for each vertex and find answer.Probably this is the easiest solution to implement: only topological sort is required. And solution code is also pretty short.What do you think about this?