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

×

TASUFFIX - Editorial

4
2

Problem Link:

Practice
Contest

Difficulty:

Hard

Pre-requisites:

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

utkarsh_lath's gravatar image

5★utkarsh_lath ♦♦
255385251
accept rate: 0%

edited 22 Jul '13, 00:20

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

Tags:

×10,459
×727
×32
×8
×1
×1

Asked: 22 Jul '13, 00:00

Seen: 2,269 times

Last updated: 22 Jul '13, 00:20