You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFTRE - Editorial

(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Sergey Kulik
Editorialist: Xellos

DIFFICULTY:

HARD

PREREQUISITES:

heavy-light decomposition, hashing, segment trees

PROBLEM:

Just another problem with queries on a tree. The queries are: reverse values on a path, copy values from a path, check if two paths contain the same sequence of values.

QUICK EXPLANATION:

Comparing paths = comparing hashes. Reversal queries are irrelevant. Use HLD to reduce the problem to subarray copy / compute hash queries, which can be solved using persistent DS, e.g. persistent segment trees.

EXPLANATION:

Queries of type 1 are just copying a path $u\rightarrow v$ to the path $v\rightarrow u$, so we can just deal with them the same way as with type 2 queries.

This problem combines many advanced concepts. The first and probably most basic one is using heavy-light decomposition of the tree (rooted at e.g. $0$) to split any path to $O(\log{N})$ paths, where each path goes towards or away from the root. When we have two paths of equal lengths, we can put them side by side and split each of them also at the same positions where the other is split; that gives still $O(\log{N})$ pairs of paths $p_{1i},p_{2i}$ of equal lengths such that we need to copy the values in $p_{1i}$ to $p_{2i}$ for each $i$ or check if they're equal for each $i$.

The benefit of this splitting is that each path in the HLD is a linear structure - the copy/check operations are now on subarrays/segments (of possibly different arrays or the same array) instead of arbitrary paths in a tree.

SEGMENT OPERATIONS

First of all, checking subarrays/segments for equality directly is slow. We need some way to compare two segments in constant time, and the common choice for this is hashing. Let's use a polynomial hash $H(s)=\sum s_i q^i \% p$ for $p=10^9+7$ and some number $q$. If two segments have equal hashes, then they're equal and if we know the lengths and hashes of two segments, we can compute their hash in constant time using precomputed powers of $q$. Let's also not forget that the paths in the tree and therefore also segments here can be directed, so we need to store both forward and reverse hashes.

Let's now build the typical data structure for segment operations: a segment tree which supports copying a segment (possibly from a different segment tree) and computing a segment's hash. Most of the implementation is the same as for any other segment tree: if the current vertex doesn't correspond to the current segment, split into sons and merge their hashes into the current vertex's hash, return the hash of the current vertex when asked for it. The problem is the copy operation: what to do when a segment corresponding to some vertex $v_1$ has to be copied to another segment corresponding to some vertex $v_2$?

This trick is what persistent structures are based on: we simply replace the edge to $v_1$ from its parent (the vertex we got into it from) by an edge from that parent to $v_2$. Of course, when copying something into the subtree of such a vertex, we have to be careful: that vertex is shared by multiple segment trees, but we're only modifying it in one of them. The solution is to create a copy of it with the same sons and only one parent - the one from the currently modified subtree. (Note that a vertex can technically have multiple parents, but they belong to different trees; this procedure also ensures that only the currently processed vertex can have multiple parents and not any vertices above it, since they're the copies created here. We don't have to remember the parents; they're given implicitly when we go down a tree.)

In order to avoid having to reverse whole subtrees, we can mark vertices as "reverse this when necessary"; when processing such a vertex (after the above mentioned copying), we just swap its sons, mark them the same way and swap the forward/reverse hash. Also, two reversals cancel out.

We have everything necessary now. The total time complexity of any operation on such a segment tree is still $O(\log{N})$, since we're only doing $O(1)$ operations per vertex; with $O(\log{N})$ operations per query, the total time complexity is $O(N+Q\log^2{N})$. However, we're adding $O(\log{N})$ vertices in each operation, so the memory complexity is also $O(N+Q\log^2{N})$.

AUTHOR'S AND TESTER'S SOLUTIONS:

The author's solution can be found here.
The tester's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 20 Sep '16, 02:38

xellos0's gravatar image

7★xellos0
5.9k54394
accept rate: 10%

edited 23 Sep '16, 01:13

admin's gravatar image

0★admin ♦♦
19.8k350498541


Answer is hidden as author is suspended. Click here to view.

answered 23 Sep '16, 03:30

sarvagya3943's gravatar image

4★sarvagya3943
(suspended)
accept rate: 36%

Sure, it's just another type of tree. A bit less balanced.

The real power of treaps is the ability to support much uglier operations and many of them at once (e.g. insert/erase/range updates/queries). In this case, you can use a persistent treap in exactly the same way as a persistent segment tree, since you don't have those ugly operations.

(25 Sep '16, 05:33) xellos07★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,768
×1,359
×81
×60
×55
×6

question asked: 20 Sep '16, 02:38

question was seen: 1,913 times

last updated: 25 Sep '16, 05:33