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

×

CUBTOWER - Editorial

0
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

This question is marked "community wiki".

asked 19 Jun '16, 15:18

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 22 Jun '16, 10:47

admin's gravatar image

0★admin ♦♦
19.7k350498541


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?

link

answered 13 Dec '17, 19:30

chari407's gravatar image

2★chari407
44727
accept rate: 0%

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 <mokia> in some year's BOI.

Total complexity: Qlog(Q)log(W)

link

answered 15 Oct '18, 19:16

ratingoverflow's gravatar image

0★ratingoverflow
262
accept rate: 50%

edited 16 Oct '18, 19:17

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,492
×1,237
×105
×31
×4

question asked: 19 Jun '16, 15:18

question was seen: 2,121 times

last updated: 16 Oct '18, 19:17