Hello,

I've tried to solve Jumping in Gyms --> ACM ECPC16 but I always get WA ... it seems that my approach to solve the problem is wrong...if anyone can give me hints how it can be solved or you can give me test cases that my code fails... http://codeforces.com/gym/101147/problem/E

Here is my attempt:

#include <bits/stdc++.h>
using namespace std;
int N;
int arr[100009];
int dp[100009];
bool vis[100009];
int dfs(int ind, int steps)
{
    if(ind == N-1)
        return 0;

    int &ret = dp[ind];
    if(ret != -1)
        return ret;

    ret = 1e9;

    if(ind - arr[ind] > -1 && ind + arr[ind] < N && !vis[ind] && !vis[ind])
    {
        vis[ind] = 1;
        ret = min(ret, dfs(ind + arr[ind], steps+1)+1);
        ret = min(ret, dfs(ind - arr[ind], steps+1)+1);
        vis[ind] = 0;
    }
    else if(ind - arr[ind] > -1 && !vis[ind])
    {
        vis[ind] = 1;
        ret = min(ret, dfs(ind - arr[ind], steps+1)+1);
        vis[ind] = 0;
    }
    else if(ind + arr[ind] < N && !vis[ind])
    {
        vis[ind] = 1;
        ret = min(ret, dfs(ind + arr[ind], steps+1)+1);
        vis[ind] = 1;
    }
return ret;
}
int main()
{
    //freopen("jumping.in", "r", stdin);
    int T, x;
    cin>>T;
    while(T--)
    {
        memset(vis, 0, sizeof(vis));
        memset(dp, -1, sizeof(dp));
        cin>>N;
        for(int i=0; i<N; i++)
        {
            scanf("%d", &arr[i]);
        }
        for(int i=0; i<N; i++)
        {
            int res = dfs(i, 0);
            if(res <= 1e5)
                printf("%d\n", res);
            else
                cout<<"-1\n";
        }
    }
return 0;
}

Thanks in advance

I tried to solve it using DP which has parameter (current vertex (s) — No. of vertices that I've passed by (cnt) ) and it equals to minimum time takes to dp[s][cnt] but I get TLE in test case #33 ... I've read the editorial and I think I'm following the same approach .

#include<bits/stdc++.h>
using namespace std;
pair <int, int> arr[5001][1001];
vector <int> res2;
vector <int> res3;
int n, maxi = 0, T;
int dp[5001][5001], sz[5001];

int fun(int s, int cnt, int time)
{
    int &ret = dp[s][cnt];
        if(ret!=-1 && ret < time){res2.pop_back();return ret;}
    ret = 2e9;
    if(time > T)
    {
        res2.pop_back();
        return 2e9;
    }

    if(s == n)
    {
        if(maxi < cnt)
        {
            maxi = cnt;
            res3 = res2;
        }
        ret = time;
        res2.pop_back();
        return 0;
    }

    for(int i=0; i<sz[s];i++)
    {
        ret = time;
        res2.push_back(arr[s][i].first);
        fun(arr[s][i].first, cnt+1, time+arr[s][i].second);
    }
res2.pop_back();
return ret;
}
int main()
{
    memset(dp, -1, sizeof(dp));
    int m, f, t, v, mm;
    scanf("%d%d%d", &n, &m, &T);mm=m;
    arr[0][0] = make_pair(1, 0);sz[0]=1;
    while(m--)
    {
        scanf("%d%d%d", &f, &t, &v);
        arr[f][sz[f]] = (make_pair(t, v));sz[f]++;
    }
    fun(0, 0, 0);
    printf("%d\n", maxi);
    for(int i=0; i<res3.size(); i++)
        printf("%d ",res3[i]);
    cout<<endl;
return 0;
}

I've found a comment saying that it can be solved using Bellman Ford Algorithm but I still don't know how it can be used ?

Thanks in advance

I've tried to figure out the reason for RTE on test case 2 but no way I got stuck. Please, if any coach can submit the solution to tell me which test case gives RTE or if anyone can offer help it will be appreciated.

#include<bits/stdc++.h>
using namespace std;
vector <int> arr[30];
vector <bool> ans;
int main()
{
    freopen("mahdi.in", "r", stdin);
    int t, len, mult, add, n, fir;
    char fir1;

    cin>>t;
    for(int tt=1;tt<=t;tt++)
    {
        ans.erase(ans.begin(), ans.end());
        for(int i=0;i<26;i++)arr[i].erase(arr[i].begin(), arr[i].end());
        cin>>fir1>>len>>mult>>add;
        fir = (fir1 - 97) % 26;
        arr[fir].push_back(0);
        for(int i=1; i<len; i++)
        {
            fir = (fir * mult + i * add) % 26;
            arr[fir].push_back(i);
        }
        cin>>n;
        while(n--)
        {
            cin>>fir1>>len>>mult>>add;
            //if(fir1 < 97)cout<<"dog";
            fir = (fir1 - 97) % 26;
            bool check = 1;
            int pos = -1;
            if(arr[fir].size())
            {
                pos = arr[fir][0];
            }
            if(pos !=-1)
            {
                for(int i=1; i<len; i++)
                {
                    check = 0;
                    fir = (fir * mult + i * add) % 26;
                    int s = 0, e = arr[fir].size(), mid;
                    if(!e) break;
                    while(s < e)
                    {
                        mid = s + (e-s-1)/2;
                        if(pos <= arr[fir][mid])
                        {
                            e = mid;
                        }
                        else if(pos > arr[fir][mid])
                        {
                            s = mid+1;
                        }
                    }
                    if(arr[fir][s] > pos)
                    {
                        pos = arr[fir][s];check=1;
                    }
                    /*for(int j=0; j<arr[fir].size(); j++)
                    {
                        if(arr[fir][j] > pos)
                        {
                            check = 1;
                            pos = arr[fir][j];
                            break;
                        }
                    }*/
                    if(!check)break;
                }
            }
            if(pos == -1 || !check)
                ans.push_back(0);
            else
                ans.push_back(1);
        }
        cout << "Case " << tt << ":\n";
        for(int i=0;i<ans.size();i++)
        {
            if(ans[i]) cout<<"BRAVO\n";
            else cout<<"REPEAT\n";
        }
    }
return 0;
}

Thanks in advance