Snow Boots Silver Question

Problems and Contests
#1

Link to problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=811.
Link to editorial: http://www.usaco.org/current/data/sol_snowboots_silver_feb18.html.

It seems incorrect that the time complexity of the DFS solution is O(N^2 B + B^2 N). Regardless of the N+B neighbors from each call of DFS, we’re still only going to check N tiles and B boots. Isn’t the time complexity O(NB) (in which case the bounds are extremely lenient)?

I tried coding this approach, with the same idea as the editorial.

#include <bits/stdc++.h>

using namespace std;

#define MX 255

struct boot{ int depth, step_size; };

int n, b;
int ans = MX;

boot boots[MX];
int tiles[MX];

bool vis[MX][MX];

void dfs(int tile, int boot){
    // if we are trying index 'boot', # of items discarded so far = boot

    // let's assume that FJ is able to use 'boot' on 'tile'

    if(tile == n-1){
        ans = min(ans, boot);
        return;
    }

    if(vis[tile][boot]) return;
    vis[tile][boot] = true;

    // take a step with the current boot
    for(int i = 1; i <= boots[boot].step_size && tile + i < n; i++){
        if(boots[boot].depth >= tiles[tile + i])
            dfs(tile + i, boot);
    }

    // try to switch to the next boot
    if(boot+1 < b && boots[boot+1].depth >= tiles[tile])
        dfs(tile, boot+1);
    /*
    for(int i = boot+1; i < b; i++){
        if(boots[i].depth >= tiles[tile])
            dfs(tile, i);
    }
    */
}

int main()
{
    freopen("snowboots.in", "r", stdin);
    freopen("snowboots.out", "w", stdout);

    cin >> n >> b;

    for(int i=0; i<n; i++){
        cin >> tiles[i];
    }

    for(int i=0; i<b; i++){
        cin >> boots[i].depth >> boots[i].step_size;
    }

    dfs(0, 0);

    cout << ans << endl;
}

When switching a boot, I only try the topmost boot of the pile. If I apply DFS multiple times and switch for the next boot each time, I think I would visit all states [\text{tile}][\ge \text{boot}] at least once? This should achieve the same purpose as the for loop code (currently commented), where I explicitly iterate through all possible next boots.

My current code (only trying the topmost boot) gives WA on test cases 4 and 9. However, the explicit code (iterating through all next boots) passes all test cases. Can you please explain why my current idea wouldn’t work?

#2

Your code is indeed faster, but misses the condition “Intermediate pairs of boots which he discards without wearing do not need to satisfy this restriction.”

You can optimize away one factor of B like you’re saying by adding another dimension to the state, isSwitching: “is Farmer John in the process of switching boots”.

#3

You could also optimize by creating a matrix of states, such that you don’t visit the same tile with the same boot multiple times.

#4

Thank you for catching my mistake about the “intermediate pairs of boots” condition.

I maintained my approach about switching for only the topmost boot at a time. However, it is no longer the case in the DFS that the current boot works on the current tile. I take care of this by putting the entire for loop for “taking a step with the current boot” under a conditional. In the conditional, I check whether we can even use the current boot to step on the current tile at all. The case about switching boots doesn’t require this extra conditional since we won’t use the current boot on the current tile anyway.

void dfs(int tile, int boot){
    // if we are trying index 'boot', # of items discarded so far = boot

    // it isn't necessarily true that current 'boot' works on current 'tile'

    if(tile == n-1){
        ans = min(ans, boot);
        return;
    }

    if(vis[tile][boot]) return;
    vis[tile][boot] = true;

    // take a step with the current boot if possible
    if(boots[boot].depth >= tiles[tile]){
        for(int i = 1; i <= boots[boot].step_size && tile + i < n; i++){
            if(boots[boot].depth >= tiles[tile + i])
                dfs(tile + i, boot);
        }
    }

    // try to switch to the next boot
    // doesn't require current 'boot' to work on current 'tile'
    if(boot+1 < b) dfs(tile, boot+1);
}

My code happily gets accepted :slight_smile: .Thank you for noticing this. Please share any remarks you may have about the approach.

I do this by creating a visited array for all [\text{tile}][\text{boot}] states.

if(vis[tile][boot]) return;
vis[tile][boot] = true;

I don’t follow this. Why would we choose to add a dimension isSwitching? In the “switching boots” for loop of my previous code, we DFS on a valid [tile][new_boot]. Since the for loop is iterative, my code only tries each pair of boots once, avoiding any switching-boot collisions. In your idea, when would we set isSwitching to be true for a given boot and tile? Can you please elaborate on the purpose of this new dimension?

#5

Nevermind, yes, you don’t need another dimension. But it’s a common technique to add another dimension that tracks what phase you’re in, so that’s what I thought of first.

If you’re in the “isSwitching=true” state you would be able to change boots without regard to their depth, and then you can walk forward after setting “isSwitching=false”. But as you noticed, this is unnecessary.

#6

Ah, I see. isSwitching would just be a placeholder for if(boots[boot].depth < tiles[tile]).