Help : ASTRING problem on codechef (MAY LunchTime 36)

Revision en1, by safayet007, 2016-06-04 10:47:30

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English safayet007 2016-06-04 10:47:30 762 Initial revision (published)