CBFEAST, EDGEDIR short Editorial

CBFEAST

First of all notice that constant K which is given (which could differ for each query, if task were different).

Now every update maps to 2K length segment from which we could query -> segment trees.

Now you are updating interval [c-K, c+K] with d, and update means add this to front (you can do operations 1 and 2 separately so they are both adding to front). Query is done for single element c while descending the tree.

This is now done similar to segment trees Assingment on segment.
Also, similar to Dynamic max subarray question, you are keeping maximal subarray, prefix, suffix and sum in each node of implicit “lazy-prop” segtree. Complexity O(QlogK)

If you are able to understand beforementioned similar problems, and implicit segment trees my


[2] should be self-explanatory. Also, notice if $K$ was not constant for each query, range we would be updating might not be contiguous and linear, i.e. i don't know if it would be solvable in $QlogX$ complexity.

**EDGEDIR**

Only works if number of edges is even.

Cut out a random tree with DFS and assign all other edges randomly. Now every node of a tree will be associated with even or odd indegree from currently assigned edges. Now assign the edges of a tree bottom-up from node to his parent (not in that direction but in a way that makes child node even degree). Only the root will be indeterminete degree, but it will have to have even degree since total number of edges is even, and all other nodes have even degree by construction. Here is the 

3.

5 Likes

I did EDGEDIR exactly in this way, I am seeing many solution using MST for some reason. There were no weight on edges, what is that idea all about ?

I just have a question,

line 153: ans = max(ans, query(noder, 1, MAXK, c, 2) + query(nodel, 1, MAXK, c, 2));

I don’t understand why it works, if I’m not mistaken it will be BEST_SUFFIX_LEFT + BEST_PREFIX_RIGHT, no?

PS: The code is great, thanks for sharing!

any spanning tree will work just fine. MST just happens to be one of them.

1 Like

Thanks, so for for example -> ppss|sssppp <-, where you are pushing to p(prefix), and one possible solution is obviously sum of max suffixes left and right then.

Ohhhh got it! It makes sense, I just imagined other representation, but obviously, it is as you said! Thanks again, sorry for the stupid question

No its not stupid, my only bug was exactly what u asked there :slight_smile:

i just have a question, what’s the space complexity for CBFEAST in your code? Thanks in advance.

Same as time complexity (with possibly some redundant nodes)

Can you please provide the link to your EDGEDIR solution?

1 Like

I don’t understand what do you mean by assigning the edges bottom up. I saw a large number of submissions using the same technique but could not understand the “updating edges up to the root” part. (I understand the spanning tree part though)
If we do this:
For every leaf, travel up to the root of the tree assigning the edges correctly, then it will work correctly but will time out.

I am not able to understand how a single DFS (I mean after finding the spanning tree) can accomplish this update. Any help will be highly appreciated. Thanks.

The theory behind solving EDGEDIR is fairly simple:

  1. Create a spanning tree.
  2. DFS to determine the distance of each node from root.
  3. Direct any edges that are not part of the spanning tree however you like.

Now every node at distance d from root has an undirected edge connecting it to a node at distance d-1, and we can always direct that edge in a way that leaves the node at distance d with an even number of indegrees. If we sort the edges and do this with the most distant edges first, the only node that we can’t control is root.

Root will only be wrong if there is an odd number of edges, in which case the problem is unsolvable.

Check out the dfs1 function in the code link i just added.

@upintheair. Consider a directed graph with odd number of edges. Every edge has a tail(source vertex) and a head(destination vertex). Thus, each edge contributes one to the indegree of some vertex and one to the outdegree of some vertex, which implies number of edges are equal to the sum of indegrees of all vertices. If every vertex has to have even indegree then the total indegree of all vertices would also be even. But this wouldn’t be possible if there are odd edges(because then sum of indegree of vertices would be odd.)