TLE '17 Contest 7 P4 - Database - Olympiads Online Judge

TLE '17 Contest 7 P4 - Database

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 2.0s

Python 4.0s

Memory limit: 512M

Author:

Problem type

Fax is about to enter his list into the Cronerian government database.

Fax McClad, Croneria's most skillful bounty hunter, has recently found a list filled with identification strings of various members of the Dankey Kang Gang!

There are $N$ ~N~ strings on this list. Fax notices that the $i^\text{th}$ ~i^\text{th}~ and $(i+1)^\text{th}$ ~(i+1)^\text{th}~ string differ by at most $1$ ~1~ character. The first string of this list will be denoted with $S$ ~S~.

Fax manually inputs all of the strings into a Cronerian government database, which sorts all of the strings by lexicographical order.

Now, Fax needs to make sure that he inputted the strings correctly. He will perform the following query $Q$ ~Q~ times: what is the $j^\text{th}$ ~j^\text{th}~ character of the $i^\text{th}$ ~i^\text{th}~ string in the database?

Can you help Fax to determine what the expected output should be?

Constraints

$1 \le N,Q,|S| \le 2 \times 10^5$ ~1 \le N,Q,|S| \le 2 \times 10^5~

All characters are lowercase characters in the English alphabet.

$1 \le x \le |S|$ ~1 \le x \le |S|~

In each query, $1 \le i \le N$ ~1 \le i \le N~ and $1 \le j \le |S|$ ~1 \le j \le |S|~.

Subtask	Points	Additional constraints
1	15	$1 \le \|S\| \le 20$ ~1 \le \|S\| \le 20~
2	15	$1 \le N,Q,\|S\| \le 500$ ~1 \le N,Q,\|S\| \le 500~
3	50	$1 \le N,Q,\|S\| \le 10^5$ ~1 \le N,Q,\|S\| \le 10^5~
4	20	No additional constraints.

Input Specification

The first line of input will contain $S$ ~S~, the first string of the list.

The next line of input will contain $N$ ~N~, the number of identification strings on the list.

$N-1$ ~N-1~ lines of input follow. The $k^\text{th}$ ~k^\text{th}~ line will contain an integer $x$ ~x~ and a character $c$ ~c~. This denotes that string $k+1$ ~k+1~ is obtained by changing the $x^\text{th}$ ~x^\text{th}~ character of string $k$ ~k~ to $c$ ~c~.

The next line of input will contain $Q$ ~Q~, the number of queries.

$Q$ ~Q~ lines of input follow. Each line will be a query in the form i j.

Output Specification

Output on separate lines the answer to each query.

Sample Input

bbbbb
4
4 c
3 a
2 b
4
3 5
2 3
4 4
3 4

Sample Output

b
a
c
b

Explanation for Sample Output

The strings in the list are initially in the order bbbbb, bbbcb, bbacb, bbacb.

After putting all the strings into the database, their order is bbacb, bbacb, bbbbb, bbbcb.

Comments

1

can definitely solve contest problems in 4 seconds commented on Oct. 29, 2023, 11:53 p.m.

is this problem really tested and pass in python?

1

maxhflow commented on April 4, 2018, 5:02 a.m.

Will there be an editorial for this question? :)

12

r3mark commented on April 5, 2018, 4:30 a.m. ← edited →

I'm not sure whether the author is planning to write an editorial but the author's intended solution is to maintain the hashes of the string with a persistent segment tree.

However, there exists a nice divide and conquer solution. Break $S$ ~S~ into blocks of size $2^i$ ~2^i~ where $i$ ~i~ loops from $1$ ~1~ to $\log_2{|S|}$ ~\log_2{|S|}~. For each block, we want to compute the relative order of the substring in this block among each of the $N$ ~N~ versions of $S$ ~S~. We already have the relative order of the two halves of the block, so we can sort this and find the order of the entire block. It's important to not break ties in this solution (until the end). The time complexity of this is $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~ for each value of $i$ ~i~ since over all the blocks (for a fixed $i$ ~i~), there are at most $N$ ~N~ distinct substrings. So the final time complexity is $\mathcal{O}(N \log N \log |S|+Q)$ ~\mathcal{O}(N \log N \log |S|+Q)~.