В Е любой диаметр подходит для вычисления ответа?

Thank you all for the nice problem set!

I'm not sure what is the complexity of your solution for D, but it can be solved it O(t).

Problem B is just that?

For problem D how do you prove that x = the minimum number such that freq[num] != (num<<2) ?

There is a much shorter (and arguably easier) solution for E.

Let us do a binary search for the answer. Then we have to check, for fixed A, if there is a k-path such that every other vertex is at distance at most A from the path. But if any vertex cannot reach this imagined path, then also some leaf cannot. So, informally, we place a pawn on every leaf, and have all the pawns walk a distance A up a tree, cutting all the vertices that are left behind from the tree. If all that is left is a short path, then A was good enough.

More formally: we prune the leaves one-by-one. As long as the tree is not a path, we seek for a leaf x in a tree with a parent y such that the distance D[x] already covered by x satisfies D[x] + weight(x, y) ≤ A. We then cut x from a tree and increase D[y] to D[x] + weight(x, y), if needed. We repeat it until the tree reduces to a path shorter than k (which means A is good enough, we detect it by keeping track of vertices with degree  ≥ 3), or until we run out of leaves that can be pruned, in which case A is too small.

Worked like a charm and makes for a quite short code: 40004166. Either this is good, or the tests missed it :)

"Note, that it is always optimal to use roses in even positions and lilies in odd positions. That is, the string 01010101010 is always optimal"

What is bad in 101010101 ? :D

arsijo Can you share your code for D ? Also what's the time complexity ?

For problem D, the only thing you are checking is max value and n, m. U also need to check for having 2 0-s, having more than enough appearances of 1, or 2.. etc

My solution for Problem D:

Let m be the greatest number that has frequency of 4m. Then, the height (i.e. the distance between opposite corners) of the rhombus is 2m + 1. This means that smaller side of the rectangle must be greater or equal to 2m + 1. This can also be used to prune the search space. Another important usage of this fact is that the horizontal or vertical distance from zero-cell to sides can not be smaller than m. The minimum of horizontal and vertical distances to sides can not be greater than m, as we assumed m is the largest rhombus side that fits in the rectangle (*).

Now, because the rectangle is symmetric, we can assume that the zero cell is on the top-left quarter and thus the max number is at the bottom-right cell, and row <= column. Let b be the maximum of the numbers. Then the potential locations for zero-cell is the line r + c = n + m - b. Out of those points (r, c), using (*), we can see that it's sufficient to check just two points, one with row equals to m, and the one with column equals to m.

Code

I just happened to print 0101... But printing 1010.. would have been okay too right?

Solution for E:

Just try to prove that some segment of diameter of length less than or equal to k would be the optimal answer. First, try to prove for a more particular case, k=n.

Implementation details: http://codeforces.me/contest/1004/submission/40027676

Can anyone tell me what is wrong with this submission? http://codeforces.me/contest/1004/submission/40022548

In problem D "If we know n,m,x, and b" But, why you know b?

Problem E can be solved in N * log(C) time without hard math :)

Do binary search on the answer, let d be the value we have to check.

Let 0 vertex be the root of the tree. Call vertex 'sad' if it needs a "chosen" vertex in its subtree (back_edge_length + max_distance_to_vertex_in_subtree > d).

'Sad' vertexes form a subtree of our tree. Call vertex a 'sad kid' if it is a sad vertex without sad chldren.

If there are > 2 sad kids, one path can't go into all of their subtrees, binary search answer is NO.

If there are exactly 2 sad kids, its easy to see that answer is YES <=> path between this two kids fits (length < k and distance to each vertex <= d).

If there is only 1 sad kid, answer is YES <=> the path from the kid to the root (but not longer than k) fits (distance to each vertex <= d).

If there are no sad kids, answer is YES (you can choose root alone).

So, binary search checking can be done in O(n): find sad kids with dfs; check paths for distance to vertexes with bfs; find path between two vertexes with dfs.

for F problem: I think we can maintain 2 segment tree. The first one computes the sum-OR.

the second one computes sum of f(i) where i is in range [l,r] and f(i) is the left-most position that the sum-OR of range [i,f(i)] >= x.

With 2 above Segment Tree, we can have a nlog^3(n) solution:

• For the first type of query, assume that the current position being considered is p(initially, p = i). We find the right-most position p' that the sum-OR in [p',i] is different with the sum-OR in [p,i]. p' can be easy to find by binary-search.
• It's easy to see that if sum-OR in [p',i — 1] <= x then the function f in range [p',p — 1] will be unique. We can find this position by binary-search. After updating, we let p = p'.
• This process will be repeated no more than 20 times. Because after a step, the sumOR in [p,i] will contain more than at least 1 bit.

• For the second one, it's easy to see that function f is a non-decreasing array. So we find the right-most postion r' that f(r') <= r. And the answer is (r' — l + 1) * (r + 1) — sum(f(i)) where i is in range [l,r'].

I think we can get a nlog^2(n) solution by using a Segment Tree to maintain the position where the sum-OR changes in both 2 directs. I need help for this part. Thank you.

Thanks for reading my comment despite my bad English.

For problem D how to check if matrix is valid in faster than O(t)?

Is there O(1) way?

When will the editorial for F be released?

Can someone please explain question B, why 010101... or 101010... are optimal solutions. How to deduce this idea from the question ? I get that for every segment of length even , even_no/2 should be the count of lilies and roses and for segments of length odd, no/2 and no/2+1 would be the best. Thanks

It is possible to solve problem E with a greedy algorithm: find the center of the tree (which we know must be part of the path) and run a DFS from it, storing the greatest distance to the root appearing in each node's subtree. Now we can increment the path greedily by storing the greatest distance to the path in each node's subtree in a priority queue, and adding to the path the node with greatest such value. The children of the center node are initially added to the queue, and, whenever we add a node to the path, we add its children to the priority queue. When adding the children of node k to the queue, the greatest distance to the path in their subtree is simply [greatest distance to the root in the subtree] — [distance root->k]. We must also take care to keep the solution as a simple path; this can be done by, when adding node k to the solution, erasing from the priority queue all its siblings (except for when adding a child of the center node, since the center can have 2 of its children on the solution). Complexity is O(N*log N). Code: http://codeforces.me/contest/1004/submission/40096868

Problem D， why we should find the minimum i that the number of occurrences of i in the list is not equal to 4*i?

Solution of F,please.I've tried my best but still can't solve it

Where's the code???

please help in problem E getting WA on test case 12

Ципко топ))0)

?detaR tI sI

Alternate easy solution for problem E:

Root the tree at node 1. Now the optimal path will be either have two ends such that no node in its subtree(except itself) is part of the path (when path is bent at lca of two ends), or it will have only one end(when it is a straight path in which one end is an ancestor of the other).

Binary search on the answer, and each time, do a dfs, and greedily select nodes which have no other nodes selected in their subtrees, and not selecting them would violate that answer.

If greater than 2 nodes are selected, then answer doesn't exist. Otherwise, just build the path between the two selected nodes, and check if the answer is satisfied.

Why is this problem rated 2400 lol