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

×

Hard

Splay Trees

# Problem:

Given a suffix array, find the number of strings that correpond to it. The suffix array can be obtained by applying some operations(see problem for details).

# Explanation:

The problem can be broken into two parts:

• Constructing the suffix array from queries.
• Given the suffix array, find the number of strings that correspond to it.

We will first solve the easy part, finding number of strings.

## Given a Suffix Array find number of strings

Let the suffix array be a1, a2, ... an. Let S be an arbitrary string corresponding to the given suffix array.
Let
S[i] = ith character of the string
Suffix[i] = suffix of S starting from ith character.

We must have

S[a1] ≤ S[a2] ≤ S[a3] ... ≤ S[an]          -  (1)

Also, by our definition of "string", if S[ai] < S[ai+1], then S[ai+1] = S[ai] + 1.

Therefore, if we replace each '≤' by exactly one out of '=' and '<', we will get a unique string.

Also, if each '≤' had full "freedom" of choosing exactly one out of '<' and '=', then number of strings for a given suffix array would be 2n-1.

However, world is not such a nice place. Any '≤' can always be replaced by '<', but it might not possible to replace it by '='. So lets try to see when a '≤' cannot be replaced by '='.

Consider an arbitrary '≤', S[ai] ≤ S[ai+1], and lets see what happens when we replace it by '='.

By suffix array condition, we have

Suffix[ai] < Suffix[ai+1].
But                        S[ai] = S[ai+1]
So, we should have Suffix[ai+1] < Suffix[ai+1+1]

Therefore, the '≤' between S[ai] and S[ai+1] can be replaced by '=' iff ai+1 appears before ai+1+1 in the suffix array. The answer will be 2k where
k = no of positions i such that ai+1 appears before ai+1+1 in the suffix array

• To handle the case where ai = N or ai+1 = N, we can append(conceptually) '0' to the of string, and rewrite the suffix array as
n+1, a1, a2, ... an

• Since the suffix array is very large, we will actually obtain it in the form:
(x1, y1), (x2, y2), ... (xk, yk)
Where each (xi, yi) represents an AP starting at xi, ending at yi, with common difference ±1.
It can be verified if both ai and ai+1 are not boundary of some contiguous segment(i.e. do not belong to the set { x1, y1, x2, y2, ... xk, yk }), then ai+1 appears before ai+1+1. So, we have to only check at boundaries of segments, which are O(k) in number.
It is non trivial to find the position of ai+1 's. However, to check the order of two arbitrary elements in suffix array, we only need to check

• If they belong to same contiguous segment, then what is their order in the segment.
• If they belong to different segments, then what is the order of those segments.

This can be done using STL's map data structure as m[xi] = m[yi] = i, and using lower_bound to locate the relative position of segments in which they lie.

## Obtaining the suffix array

We need to implement the two operations : flip ranges and move ranges to front.
This can be done using balanced binary trees(splay trees). Each node in the tree will store a range of consecutive numbers from u to v (u may larger than v).
At the beginning our tree contains only single node which is (1, n). At any time, the nodes of the tree form a disjoin partition of the range (1,n).
Every node has:

• int u, v: indicate the range(u, v).
• int num: the subtree rooted at this node has total of num array elements.
• bool flip: the entire subtree rooted at this node is flipped. This will be propagated down in lazy manner.

A flip-range, or move-range-to-front operation may need to split at most 2 nodes(for beginning and end of operation's range), so do that first.
Use splay operation to obtain a subtree that corresponds to the given range.

1. Flip operation: Flip that range by updating flip flag on the node.
2. Move the range to front: Can be done by shuffling O(1) nodes of the tree.

# Setter's Solution:

Can be found here

# Tester's Solution:

Can be found here

This question is marked "community wiki".

asked 22 Jul '13, 00:00

255385251
accept rate: 0%

 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,875
×1,359
×40
×8
×1
×1

question asked: 22 Jul '13, 00:00

question was seen: 2,804 times

last updated: 22 Jul '13, 00:20