USACO 2018 February: Snow Boots (Part 2)
USACO 2018 February: Snow Boots (Part 2) Using a Monotone Deque! Problem It's winter on the farm, and that means snow! There are N N tiles on the path from the farmhouse to the barn, conveniently numbered 1 … N 1 … N , and tile i i is covered in f i f i feet of snow. In his farmhouse cellar, Farmer John has B B pairs of boots, numbered 1 … B 1 … B . Some pairs are more heavy-duty than others, and some pairs are more agile than others. In particular, pair i i lets FJ step in snow at most s i s i feet deep, and lets FJ move at most d i d i forward in each step. Farmer John starts off on tile 1 1 and must reach tile N N to wake up the cows. Tile 1 1 is sheltered by the farmhouse roof, and tile N N is sheltered by the barn roof, so neither of these tiles has any snow. Help Farmer John determine which pairs of snow boots will allow him to make t...