FCF2P5 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Pritish Priyatosh Nayak

Tester: Sibasish Ghosh

Editorialist: Pritish Priyatosh Nayak

DIFFICULTY:

Simple

PREREQUISITES:

Observation, Dynamic programming

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 A to another position B takes |A-B| units of time.
Process queries which ask you to tell the minimum time needed to go from position Src to position Dest.

EXPLANATION:

Keep the position having value 1 as reference.
Let t[i] denote the time needed to go from position having value 1 to position having value i.
And then time needed to go from Src to Dest is basically abs(t[ value at Src ] - t[ value at Dest ]) .

See setter solution for implementation details.

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];
	int pos[n];
	rep(i,0,n)
	{cin>>a[i];a[i]--;pos[a[i]]=i;}
  	
  	int t[n];
  	t[0]=0;
	rep(i,1,n)
	{
		t[i]=t[i-1]+abs(pos[i-1]-pos[i]);
	}
 
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		x--,y--;
		cout<<abs(t[a[x]]-t[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>
    #define int long long
    using namespace std;
    int32_t main()
    {
       ios_base::sync_with_stdio(false);cin.tie(NULL);    
       int n,q;
       cin>>n>>q;
     
       int a[n];
       int pos[n];
       for (int i = 0; i < n; ++i)
       {
       	cin>>a[i];
       	a[i]--;
       	pos[a[i]]=i;
       }
       int d[n];
       d[0]=0;
       for (int i=1; i < n; ++i )
       {
       	d[i]=d[i-1]+abs(pos[i-1]-pos[i]);
       }
     
       while(q--)
       {
       	int src,dest;
       	cin>>src>>dest;
       	src--,dest--;
       	cout<<(int)(abs(d[a[src]]-d[a[dest]]))<<'\n';
       }
     
     
     
       cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
       return 0;
    }