safayet007's blog

By safayet007, history, 8 years ago, In English

Problem Link: https://www.codechef.com/LTIME36/problems/ASTRING This problem can be solved using a segment tree RMQ. But I'm thinking of an alternative greedy approach which isn't working. I'm getting constant WA.

The idea is : since we need to take a substring of length k we need to perform (n — k) remove operations. So I'm removing the largest character in the string starting from the minimum index and this is supposed to ensure the lexicographically smallest substring. This approach gets WA. Anyone with bug in my approach or any counter example will be appreciated. Thanks.

Segment tree code : http://pastebin.com/gkx44cTP

My greedy code : http://pastebin.com/gEV1chkC

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all we need to find the lexicographically smallest subsequence and not a substring

I solved this problem using this approach

create a array of ordered set of length of size 26 (one for each character)

  • store the position of each character in the string in their respective sets

  • let curr_index be the index of last used character in the answer string

  • initialize curr_index to -1

  • let rem be the remaining number of characters to fill in the subsequence , initially rem = len

now for k times :
In the array of sets , find the first character for which it has a index ceil such that
ceil is smallest index strictly greater than curr_index and (len — ceil) >= rem (This ensures that there are enough characters for the next iteration)
if the above condition holds then do rem-- , store the character in the answer string and break

My submission (Java) : code

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your code fails on this case:

1

sgxrsmolwnmkesfjnskcyqatlyrltaanjxedluqihcunuz

21