Unofficial editorial for KILLKTH problem from JAN18

#[Killjee and k-th letter][1]

Difficulty:Medium

Prerequisite: None

Problem:

Given a string s, answer queries regarding Kth character of Special String generated from given string. You have to answer queries online.

Special String is formed by sorting all sub-strings of given string and concatenating them.

Solution:

Main issue: We have to somehow save the concatenated string. But storing it in a string variable will naturally exceed the memory limit and well as Time Limit for string length upto 10^5.

So, what I did was, I divided the output string into a vector(v) of nodes.

Node struct consist of:

  1. boolean x: 0 for string repeatation,1 for all substrings
  2. int l: total length of node
  3. String s: string to be repeated
  4. int sp: start point for type 1,no.of times to repeat for type 0.
  5. int skip: no.of chacters to skip for type 1.

At first, I made an array(a) of lists having the position(s) of each character in the string.

a[0]={all position where ‘a’ occur in given string}

block_a=all substring starting with an ‘a’.

a[1]={all position where ‘b’ occurs in given string}

block_b=all substring starting with a ‘b’.

Now, let’s consider block_a. Let the length of a[0] be l.

It’s guaranteed that there will be at least l ‘a’ in the beginning of string.So, in v[0] we will save this info.(x=0,l=l,s=“a”,sp=l).

Now, the first substring of block b will come after the last substring of block_a.

If we move to the next index for each element in a[0], We are, in a recursive way, left with the same problem(i.e. we need to sort all substring starting from an index in a[0] and all these substrings will have ‘a’ as a prefix(ps)).

Hence, we will go for recursion until the length of the vector passed is reduced to 1.When the length is 1, we will have to print all string starting from that index with prefix(ps).This info. can be stored in a node of type 1(x=1).

Example, say string is “abc”. Then length of a[0] is 1 and a[0][0]=0; This means now all substrings starting from s[0] , i.e. “a” , “ab” , “abc” will have to be appended. This info is now stored only in a single node of type1.
(here, I used the test function to print the final string and check for some inputs).

Now, we can have vector(psum) for the prefix sum of lengths of node.
For, a value of k we can apply binary search to get the node to which it belongs.And within that node, the character can be found easily.

If you have better solution or if you have any doubts feel free to leave a comment below :slight_smile:

Link to my


[2]

Side Note: I did expect TLE for some test cases.I know a test case where my code won't work, don't know how it got passed. :D


  [1]: https://www.codechef.com/problems/KILLKTH
  [2]: https://www.codechef.com/viewsolution/16779700
3 Likes

The code gives TLE when there is a large string (of > 2*10^4 length) , and all characters are same. Many other submitted solutions too give RE or TLE :frowning:

4 Likes

Are there any alternative solutions using string Suffix structures? I tried comprehending it but can’t come up with a full solution :frowning:

2 Likes

Did u see the suffix tree solution? Thats probably the most simple solution. Just require 2 dfs,and binary Search.

See this solution, a simple brute force in python still gives 20 points. While the same solution gives TLE in C++.

But anyways, there has already been a lot of criticism regarding this problem. :slight_smile: