Help : ASTRING problem on codechef (MAY LunchTime 36)

Правка en1, от 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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский safayet007 2016-06-04 10:47:30 762 Initial revision (published)