CHDF - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest
Practice

Author: Aniket Sood,Arihant Jain
Tester: Aniket Sood
Editorialist: Arihant Jain

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Greedy, DP

PROBLEM:

Given fuel F and a point P on a highway (F,P), we can stop at points (F,P+F), (F-1,P+F-1) and (F+1,P+F+1) there are potholes on the highway at some points we have to find whether or not Chef can stop at the runway within its bounds without ever stopping on a position with a pothole.

QUICK EXPLANATION:

Apply DP and memoization to the recursive solution as we encounter the same subproblems which, without memoization, are computed repeatedly.

EXPLANATION:

Subtask #1:

Run a recursive loop over the 2 states of P and F.

Subtask #2:

It depends on the type of implementation. The iterative implementation will only pass Subtask 1 and 2, but not 3.

Subtask #3:

Proper solution is as follows:

  1. By Identifying the changing parameters and determining the number of subproblems.

  2. The two parameters that change for every subproblem are: Array position, P and Fuel, F.

  3. Figure out that the recurrence relation exists and you specify the problems in terms of parameters. Because you can adjust your speed by up to 1 before jumping to the next position, there are only 3 possible speeds, and therefore 3 spots in which we could be next.

  4. If fuel is F, position P, we could go from (F, P) to:
    ( a ) (F,P+F); if we do not change the speed
    ( b ) (F-1,P+F-1); if we change the speed by -1
    ( c ) (F+1,P+F+1); if we change the speed by +1

  5. If we find a way to stop in any of the subproblems above, then we can also stop from (S,P). This is because we can transition from (S,P) to any of the above three options. Let’s call a function that we’re trying to compute canStop. Then:
    canStop(S,P) = canStop(S,P+S) || canStop(S-1,P+S-1) || canStop(S+1,P+S+1)
    It is the recurrence relation.

  6. Add memoization. This means that you should store your function result into your memory before every return statement.

  7. Look up the memory for the function result before you start doing any other computation.

    Going through this implementation, using recursion with memoization, the tightest upper bound on the time complexity will be O(L*sqrt(L)).

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
#define int long long

bool canStop(map<pair<int, int>, int> &vis, set<int> &vec, string highway, int n, 
int initFuel, int startIndex)
{
    if (vis.count({startIndex, initFuel}))
    {
        return vis[{startIndex, initFuel}];
    }
    if (startIndex >= n || startIndex < 0 || initFuel < 0 || !(highway[startIndex] - '0'))
    {
        vis[{startIndex, initFuel}] = 0;
        return false;
    }
    if (initFuel == 0)
    {
        vis[{startIndex, initFuel}] = 1;
        return true;
    }
    int c[] = {initFuel, initFuel - 1, initFuel + 1};
    for (auto fuel : c)
    {
        if (canStop(vis, vec, highway, n, fuel, startIndex + fuel))
        {
            vis[{startIndex, initFuel}] = 1;
            return true;
        }
    }
    vis[{startIndex, initFuel}] = 0;
    return false;
}
int32_t main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n, fuel;
        cin >> n >> fuel;
        string highway;
        cin>>highway;
        set<int> a;
        map<pair<int, int>, int> vis;
        if (canStop(vis, a, highway, n, fuel, 0))
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }
}
Editorialist's Solution 
def insertIntoMemo(memo, startIndex, initFuel, exp):
    memo.setdefault(startIndex,{})[initFuel] = exp


def canStopRecursionWithMemo(runway, initFuel, startIndex=0, memo=None):
    if memo == None:
        memo = {}
    if startIndex in memo and initFuel in memo[startIndex]:
        return memo[startIndex][initFuel]
    if(startIndex >= len(runway) or startIndex < 0 or initFuel < 0 or not 
runway[startIndex]):
        insertIntoMemo(memo, startIndex, initFuel, False)
        return False
    if initFuel == 0:
        insertIntoMemo(memo, startIndex, initFuel, True)
        return True
    for adjustedFuel in [initFuel, initFuel-1, initFuel+1]:
        if canStopRecursionWithMemo(runway, adjustedFuel, 
startIndex+adjustedFuel, memo):
            insertIntoMemo(memo, startIndex, initFuel, True)
            return True
    insertIntoMemo(memo, startIndex, initFuel, False)
    return False

def Convert(string):
    list1 = []
    list1[:0] = string
    return list1

if __name__ == "__main__":
    t = int(input())
    while (t > 0):
        t = t - 1
        n, fuel = [int(X) for X in input().split()]
        highway = input()
        high = Convert(highway)
        for i in range(0, len(high)):
            high[i] = int(high[i])
        if(canStopRecursionWithMemo(high, fuel, 0)):
            print("YES")
        else:
            print("NO")
2 Likes