PALINDR - Editorial

editorial
, , , , ,
1

Problem Link:

Practice

Contest

Difficulty:

Easy-Medium

Pre-requisites:

Treap, Combinatorics

Explanation:

The constraints in the first sub task are very small, so a simple brute force will be enough in order to get a nonzero score at
this problem.

In general case, let’s consider the following problem: you are given the number of each symbol’s occurences and now
you’re asked to calculate the number of different palindromes that one can obtain by permutting all these letters in some way.
Let’s consider that the i-th alphabet letter occurs A[i] times, i.e. ‘a’ occurs A[1] times, ‘b’ occurs A[2] times, and so on.
Then, we can make some observations. At first, if A[] contains more than one odd number (i.e. there are two letters that occurs
odd number of times), then it’s impossible to create a palindrome at all. So, in this case the answer if zero. Otherwise, if there
is one such letter, then this letter will be the “center” of the palindrome, so we place it in the center and decrease the number
of these letters. Now, A[] contains only even numbers. It’s a well known fact that knowing the length of the palindrome, let’s call
it K, and the first (K+1)/2 letters of it, it’s trivial to reconstruct it. Also, it’s not hard to see that the number of occurrences
of each letter in the left half of a palindrome string equals to the number of occurences of each letter in the right half of a
palindrome string. Based on this, we just have to calculate the number of different ways to place (K+1)/2 letters of 10 types
(i.e. ‘a’ to ‘i’), where the amount of letter of every type if known. It’s a well known combinatorial problem and the answer will
be ((K+1)/2)!/((A[1]/2)! * (A[2]/2)! * … * (A[10]/2)!). It is asked to output the result modulo a prime number, so you can use a well
known modular multiplicative inverse calculation trick in order to calculate the answer. With a proper implementation, overall
complexity of a single such a query will be O(alphabet).

So now, in the second subtask you can perform all the operations in a simple way. When you need to reverse the string, you can
do it in O(N) time. To answer the queries of another type, you can calculate the array A[] and then solve the problem in O(alphabet)
complexity, which is in fact very fast. So, this way we get O(M * N * alphabet) solution.

In order to pass the last sub task, you need to use some advanced data structure. Writer’s solution uses treap, which seems the
easiest way to solve the problem. The queries treap should maintain are quite standard for this structure - namely reversing the
segment and counting the number of some letter’s occurences, so it shouldn’t cause any problem.

Setter’s solution:

Can be found here

Tester’s solution:

Can be found here

1 Like
2

So what is the time complexity of the solution passing all the test cases? O(M * log(N) * alphabet) ?

There is another simple solution with an O((M + N) * sqrt(M) * alphabet) time complexity, but I am not sure it would fit within the time limit for all the test cases. In case anyone is interested, the idea of this solution is as follows. Let’s choose a number Q. Then we will perform all the operations (queries and updates) in chunks of Q operations. Before the start of each chunk we know the full state of the string. After each operation, the string will consists of a number of pieces. Each piece consists of an interval of consecutive positions from the string from the beginning of the chunk (the interval of positions can be either in normal order or in reverse order). Then, when we need to perform an operation, we locate the pieces which contain its endpoints and split these pieces - this way, each operation will refer to an interval of pieces. Splitting a piece in two can be performed in O(alphabet) time (by having prefix sums computed for each character and each position of the string from the beginning of the chunk). Then an update simply reverses the order of an interval of pieces (and also changes their state: from normal order to reverse order or the other way around) and a query simply traverses all the pieces within its interval in order to compute the number of times each letter of the alphabet occurs. Each operation creates at most 2 new pieces and at the beginning of the chunk we had only 1 piece. Thus, we end up with O(Q) pieces and each operation takes O(Q * alphabet) time. After performing all the Q operations we will reconstruct the string and have it ready for the next chunk of operations. Reconstructing the string can be performed in O(N) time by traversing the pieces and adding the characters of the piece (in normal or reverse order, depending on the state of the piece). But we also need to compute prefix sums for each character of the alphabet, which takes O(N * alphabet) time. Thus, the overall time complexity is O(M * Q * alphabet + N * (M / Q) * alphabet). By choosing Q=O(sqrt(M)) we obtain the stated time complexity.

6 Likes
3

Please explain how the treaps are used in reversing the string. I have gone through the writer’s solution but unable to understand it properly.

4

Please explain how the treaps are used in reversing the string. I have gone through the writer’s solution but unable to understand it properly.

2 Likes