ALG1705-Editorial

PROBLEM LINK:

Practice

Contest

Author: Vivek Kumar

DIFFICULTY:

HARD

EXPLANATION:

This problem is pure implementation problem.

To solve this problem, Please go through this wonderful editorial of this problem.

Now, suppose you know how to find the number of different substrings of a given string. So, to get Kth character in the concatenation of all substrings, You need to count the number of characters while calculating the length of LCP o ith and (i+1)th suffix in sorted order. Suppose length of the LCP is some L, and it was L’ between (i-1)th suffix and ith suffix. then ith suffix will contribute to strings having length L’+1, L’+2…L. and we will keep adding all the length in this manner unless we get length upto k.

The main issue in this problem is not the algorithm, but implementation :slight_smile:

AUTHOR SOLUTION:

Author’s solution can be found here.

//