Intended Solution for Snow Boots Gold?

Problems and Contests
#1

Link: Snow Boots

So I’ve been looking at this problem for the past hour, and I can’t figure out what the intended solution is. The module is “More Operations on Ordered Sets,” and I still don’t understand what data structures / operations you would use on this problem. I took a look at the editorial, but it describes a solution using two pointers and a doubly-linked list.

I understand fully what the question is asking, but I can’t figure out how / why it corresponds to this certain module. Can somebody link me a solution, or give me an idea on how to start this problem? Thank you!

#2

Yeah- I don’t really see how it corresponds to “More Operations on Ordered Sets”.

#3

You can use an ordered set in place of a linked list. Instead of nxt and pre you would use next() and prev() on iterators.

#4

Since you’re putting this problem in this section, could provide an internal solution so people don’t get confused as to why this solution is on the “More Operations on Ordered Sets”?

#5
#6

Thank you so much Benq! I solved the problem today with next() and prev() instead of maintaining a linked list. I probably should have looked more into alternate data structures for a linked list.