DS Question - 1

general
,
1

Q1 : How many strings of length n are there where following m conditons are satisfied.

Each condition has two paramters L and R and it is satisfied when substring [L,R] is a palindrome.

//Also find ‘kth lexicographically smallest’ string which satisfies all those m conditions.

1 <= n,m <= 2*10^5

//1 <= k <= 1e17

1 <= l <= r <= n

P.S. - My solution turned out to be wrong, so I don’t have an AC solution.

2

I have tried creating many such problems with ideas that there is some condition on the range [L, R]. Most of them are hard to solve, unless you have some special properties e.g. if two ranges [L1, R1] intersect with [L2, R2], then the common range also follows that property. e.g. see the problem CLOST on codechef, in this problem, the property is whether the string is balanced or not, for this particular property the above stated intersection condition holds.

You can create some interesting question if you ask whether there exists a situation with given property. e.g. see this problem in which inverse of RMQ problem over a permutation is asked.

Also, I would like to point out one thing, if we have following condition that the if ranges intersect, then one range will lie completely inside the other or they will be disjoint, then we can create a tree like structure in which the desired problem might not be hard to solve. e.g. see one of the problems set by me.

So, overall think about many variations of the above problem, some of them might be feasible to solve others are much harder to solve in general.

1 Like
3

With conditions like ranges wouldn’t intersect, the problems much easier to solve. I intended to create a medium-hard question :open_mouth: . Nevertheless, thanks for advice. Will keep this in mind for future questions.

4

There was a typo in this paragraph

Also, I would like to point out one thing, if we have following condition that the if ranges intersect, then one range will lie completely inside the other or they will be disjoint, then we can create a tree like structure in which the desired problem might not be hard to solve. e.g. see one of the problems set by me.

Please reread this.

5

Sumeet I have an idea, as I am not getting a solution of complexity less than O(n^2).
We can change the constraints such that n <= 3000 and m <= 1e5.

------------------------ Pause here if you are thinking of the solution----------------------

Spoiler -

  1. Find the mid - point of each query (palindrome from l to r) and if there are many queries having same mid - point, then only retain the one with max. length.
  2. This would have reduced the no. of queries to 2 * n at max, since there are 2*n mid-points possible in a string of length n.
  3. Now for each query, run an iterator from its both end, i.e. l and r, and do dsu.
  4. Now sort the dsu’s according to the least element they have, and count the no. of dsu’s.
  5. Convert k to base 26, and now assign each dsu one character in the sorted order.

Here the main variation(trick) would be to observe that max. no of queries to be processed is 2*n.

6

This seems nice for an easy-medium level question. Let’s see what others think.

7

This problem seems a bit similar to hackerrank september 2015 , 101 hack 4th question