CUBTOWER - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Sergey Kulik
Testers: Vasya Antoniuk and Kevin Atienza
Translators: Vasya Antoniuk (Russian), Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Medium-hard

PREREQUISITES:

String hashing, range tree queries

PROBLEM:

There are N initially empty towers of letters. There are also M favorite words. There are three types of queries:

  • 0 X C: put the letter C to the top of the X th tower.
  • 1 L R P: find the number of towers in the range [L, R] which contain the P th favorite word.
  • 2 L R P: find the number of occurrences of the P th favorite word across all towers in the range [L, R].

You need to process Q queries.

QUICK EXPLANATION:

We can compare whether two strings are equal by comparing their hashes. For this problem, we can use polynomial hashing so we can compute the hash of any substring easily.

There are only O(\sqrt{S}) distinct lengths in the favorite words, where S is the sum of the lengths of the favorite words. So during a type 0 query, we can compute O(\sqrt{S}) hashes of suffixes, one for each distinct length.

Before processing any type 1 or 2 query, process all type 0 queries beforehand so that you know where each favorite word will appear in the future. Then we process the queries for each favorite word separately. Specifically, when processing the P th favorite word:

  • Consider only type 1 and 2 queries with this P, and
  • Consider only type 0 queries that yield a new occurrence of the P th favorite word.

For a fixed P, each of these constitutes a range sum with point updates, so a Fenwick tree can answer them quickly. For an asymptotically faster solution, use sqrt decomposition instead of a Fenwick tree.

EXPLANATION:

Coming soon.

Time Complexity:

O(N + Q (\sqrt{N} + \sqrt{S})) where S is the sum of the lengths of the favorite words.

AUTHOR’S AND TESTER’S SOLUTIONS:

setter
tester
editorialist

2

There are only O(S−−√)O(S) distinct lengths in the favorite words, where SS is the sum of the lengths of the favorite words. — Can some one explain the meaning of this line and also how this inference is made?

3

Seems that there is a faster solution, both theoretically and practically.
Submission: https://www.codechef.com/viewsolution/20850365
(Second fastest submission among all accepted ones)

Assume that any of favourite strings is not another one’s prefix, and we can see that the total number of occurences is less than sigma|Wi|. So for each favourite string we maintain a dynamic segment tree storing its occurrence, and we are done.

When our assumption is wrong, we first reverse the favourite strings, then build an AC-Automata and get the tree formed by its fail links. Easy to see that, if a node represent string S, its ancestors represent suffix-es of S.

Then, when we attach a char to the end of some string, we find the maximal favourite suffix of the resulting string, get its corresponding node, and add counting variables in its ancestors by one. This can be done by maintain a segment tree of euler tour order.

However, as there are more than one tower, the problem is actually 2-D. So we can use Divide and Conquer + Fenwick Tree to solve it, in the same way as problem in some year’s BOI.

Total complexity: Qlog(Q)log(W)

4

There are only O(S−−√)O(S) distinct lengths in the favorite words, where SS is the sum of the lengths of the favorite words. — Can some one explain the meaning of this line and also how this inference is made?

Suppose sum of all string would not increase 10^5
then their is no more than sqrt(10^5) different length string

like if sum is <=5
then distinct string would be of length (3,2) (1,2) (1,4) In every case their is not more than 2 distinct length string