Блог пользователя Pulkit3714

Автор Pulkit3714, история, 12 месяцев назад, По-английски

Hi,

I wrote the following solution using monotonic stack and dp, but it is failing for 2 test cases. Can someone help me with this?

Code:

Spoiler

My understanding is: For each element, we should go to the largest left or right element, that is in sight (no larger element in between). It would be great if someone could point a minimal breaking testcase.

Thanks!

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
5
4 1 2 3 3 

Fails for something similar to this.

Best solution : 4 -> 3 -> 2 -> 1

Your solution : 3 -> 2 -> 1

Hope it helps :)

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

this is a really good problem and its solvable without segment trees, unlike what codeforces would lead you to believe. think about the order and you'll probably get it (considering that i was able to), tho your solution is interesting. what if we go to the smallest but still greater left/right element instead?