Magical Strings - Editorial

PROBLEM LINK:

Practice

Contest

Author: Sumeet Verma

Tester: Aman Kedia

Editorialist: Sidhant Bansal

Prerequisites - Pigeon Hole Principle, Disjoint Set Union

Difficulty : Easy - Medium

Expected Complexity: O(N*N)

Editorial -

  1. Find the mid-point of each range (query) and if there are many queries having the same mid-point then only retain that query whose length is max, i.e (where r - l is maxm)
  2. This would have reduced the number of queries to 2*N at max, since there are 2*N number of mid-points in a string of length N.
  3. Now for each query do dsu union of element l with r, (l + 1) with (r - 1), (l + 2) with (r - 2) and so on. We do this because the character which would be put on the index l would be same as the one we put on index r. Extending this logic to all queries we need to maintain dsu. So basically all the elements of one component of dsu should have the same letter on them.
  4. After processing all the queries, let the number of dsu components be x, then the answer is 26x

Complexity Analysis: O(N * N) because we do an O(N) iteration for each query and total number of queries can be 2N, therefore O(2N*N). Here I have ignored the constant of union-find for simplicity.

2 Likes

Can anyone explain how a string of length N can have 2*N midpoints ?

2 Likes

Hi, the following is my code: http://ideone.com/1ElezS (I couldn’t get the inline code function to work, sorry for the external link).

When I submit however, I’m getting TLE. Can you please point out any errors? My approach is basically DSU.

Thanks :slight_smile:

1 Like

Can anyone please explain it in simple terms.
Thnaks.

N for odd length ranges and N for even. :slight_smile:

3 Likes

Yeah !! Thats what I even thought of :slight_smile: Thanks a lot

Sumeet Verma Can you give an example of this problem?

basically for every query [L,R] to be a palindrome we know that s[L]=s[R] && s[L+1]=s[R-1] …and so on (till (L+x)=(R-x) (x is any random number) ). so what u can do instead of using the above mid-point concept ( given in editorial), u can check if we had processed for that range or not. if not then process it otherwise come out of that query.Since if we had a query [L,R] then at first we will process the query for all the palindromes present in that range [L,R] ( i.e. range [L,R] then range [L+1,R-1] … and so on) and update all this ranges as they had been processed. So if now we had another query that is a subquery for the [L,R] (i.e [L+1,R-1] or any other) then we will not process as we had already processed it.
For ex:
consider this test case:
1
6 4
1 5
5 6
1 6
2 5

Here at first we will combine (1,5) and then (2,4) and then (3,3) and we will update all this range that we had processed it.
for next query we will combine (5,6) and update the range
for next query we will combine (1,6) ,(2,5),(3,4) and update the ranges.
for next query we will see that [2,5] we had already processed so we do not need to process it .

so there will be now only one unique set so the answer is 26^1=26;

here is my solution:
https://www.codechef.com/viewsolution/35243020

and here is what the editorial meant to say:
https://www.codechef.com/viewsolution/18978743