Sequence Equation

See the original problem on HackerRank.

Solutions

This simple problem can be solved by memorizing the inverse of \(p\) into a fast-lookup container like a map/dictionary or even into an array (since the domain spans from \(1\) to \(N\)).

Since all the associations are unique, \(p\) is invertible.

Basically, the key of the map is the value of \(p\) and the value is the index.

Here is a C++ implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int N, y; cin >> N;
unordered_map<int, int> f;
for (auto i=0; i<N; ++i)
{
    cin >> y;
    f[y] = i+1;
}
for (auto i=0; i<N; ++i)
{
    cout << f[f[i+1]] << "\n";        
}

We can even use a vector instead of a map:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int N, y; cin >> N;
vector<int> f(N+1);
for (auto i=0; i<N; ++i)
{
    cin >> y;
    f[y] = i+1;
}
for (auto i=0; i<N; ++i)
{
    cout << f[f[i+1]] << "\n";        
}