It Was Almost An AC, Can You Please Help Me?

Here is the problem link https://atcoder.jp/contests/abc167/tasks/abc167_d . I tried solving the problem without using any Graph Theory algorithm by just using a Set as a major tool. Here’s the idea, begin exploring from the first city and store that current city in a set. Now, keep exploring and add the cities that you haven’t explored yet to the set, and simply stop when you encounter a city that is already in the set because you have found a cycle. Store the city where you found the cycle in a variable then start exploring again from the first city till you get to the city where the cycle was found (maybe this could be avoided) and store the number of steps taken. Now reduce these many steps from K. Then find the number of edges in the cycle and reduce K to K mod (edges in cycle). Now simply simulate the process for the [K mod (edges in cycle)] steps and you can find the city you’ll end at.

Using this approach I got an AC in 47 out of 55 test cases. Out of the 8 remaining I got TLE in 3 and WA in 5.

Here’s the code that I used:-

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(int i=a; i<b; i++)
#define ll long long

int main()
{
    FASTIO
    int n;
    ll k;
    cin >> n >> k;
    vector<int> v(n);
    rep(i,0,n)
    {
        cin >> v[i];
        v[i]--;
    }
    set<int> nodes;
    int pos = 0;
    nodes.insert(pos);
    int n_c = 0;
    while(true)
    {
        if(nodes.find(v[pos]) == nodes.end())
        {
            nodes.insert(v[pos]);
            pos = v[pos];
        }
        else
        {
            n_c = v[pos];
            break;
        }
    }
    pos = 0;
    int steps = 0, cycle = 0;
    while(pos != n_c)
    {
        steps++;
        pos = v[pos];
    }
    pos = v[pos];
    cycle++;
    while(pos != n_c)
    {
        pos = v[pos];
        cycle++;
    }
    k -= steps;
    pos = n_c;
    k %= cycle;
    while(k--)
    {
        pos = v[pos];
    }
    cout << pos + 1 << "\n";

    return 0;
}

Now here’s the question. Can I get an AC in the remaining test cases with some simple modifications to the above code?

Yes.

Spoiler

What about small k? Currently your solution assumes that k is large enough that you’ll always be able to reach the “cyclic node”, but this may not always be true.

I think this is also the cause of the TLE. You set k -= steps, possibly making it a negative number, then take it modulo cycle, which may still leave it as a negative number. It will then get stuck in the while(k--) loop.

2 Likes

:smiley: :smiley: :smiley: :smiley: :smiley:
Thank you so much @galencolin !!!

Ohh! I got it in first try
solution

1 Like

Nice :slightly_smiling_face: :+1:

1 Like

Have a look here Another Surprise for Everyone :slightly_smiling_face:

1 Like

Thnx bro, i love recursion

You’re welcome. You may even add some problems on recursion that are your favorite. :slightly_smiling_face:

Sure…

Thanks :smiley: