FCF2P4 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Sibasish Ghosh

Editorialist: Pritish Priyatosh Nayak

DIFFICULTY:

Cakewalk

PREREQUISITES:

Observation

PROBLEM:

You’re given a permutation of 1 to N.
In the permutation the position having value x is linked with the position having value x+1.
And moving from one position to another takes 1 unit of time.
Process queries which ask you to tell the minimum time needed to go from position Src to position Dest.

EXPLANATION:

Because of the fact that position having value x is linked with the position having value x+1, we can go from position having value y to position having value y+k or y-k in k units of time.
So to process the queries, we can simply check what value is at position Src and at position Dest.
The difference between those values will be the answer.

See setter solution for implementation.

SOLUTIONS:

Setter's/Editorialist's Solution 
#include<bits/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--) 
#define mod 1000000007
using namespace std;
 
void Onigiri()
{
	int n,q;
	cin>>n>>q;
	int a[n];
	rep(i,0,n)
	{cin>>a[i];a[i]--;}
 
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		x--,y--;
		cout<<abs(a[x]-a[y])<<'\n';
	}
}
signed main()
{
   ios_base::sync_with_stdio(false);cin.tie(NULL);
   #ifdef Zoro
   freopen("sampletest", "r", stdin);
   freopen("sampleout", "w", stdout);
   #endif  
 
   int t=1; 
   //cin>>t;
 
   while(t--)
   {Onigiri();cout<<"\n";}
 
   cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
   return 0;
}
Tester's Solution 
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
       ios_base::sync_with_stdio(false);cin.tie(NULL);
      
       int n,q;
       cin>>n>>q;
     
       int a[n];
       for (int i = 0; i < n; ++i)
       {
       	cin>>a[i];
       	a[i]--;
       }
     
       while(q--)
       {
       	int src,dest;
       	cin>>src>>dest;
       	src--,dest--;
       	cout<<int(abs(a[src]-a[dest]))<<'\n';
       }
     
     
     
       cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
       return 0;
    }