FAPF - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Farhod
Tester: Joud Zouzou
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Partial sums and Observation.

PROBLEM:

There are N cities on a straight line, each city having an associated value given in array V. The cost to move from city x to city y is f(x, y) = |V_y -V_x|+y-x. Cost of a path a_1, a_2 \ldots a_k of length k is \sum_{i=1}^{k-1} f(a_i, a_{i+1}). You have to answer Q queries, each query giving two cities and we have to find the minimum cost of the path between the given pair of cities.

QUICK EXPLANATION

  • Let us sort cities in the non-decreasing order of V_i. Now, f(x, y) becomes V_y-V_x +y-x for y \geq x.
  • Expanding \sum_{i=1}^{k-1} f(a_i, a_{i+1}) with a_1 = x and a_k = y, we get V_y-V_x+y-x as the cost of path from x to y as all the remaining terms cancel out.
  • Now, in order to maximize k, we visit all cities z if V_x \leq V_z \leq V_y since visiting them in non-decreasing order do not affect the cost of path. All these cities lie between city x and city y in sorted list.

EXPLANATION

Let’s analyze the function f(x, y). Calculating cost of path from x to z which passes through y, we get f(x, y) + f(y, z) expanding which, we get |V_y-V_x|+ |V_z-V_y| + y-x+z-y = |V_y-V_x|+ |V_z-V_y| + z-x. If we can assume we visit cities in either ascending or descending order of V_i, we get V_y-V_x+V_z-V_y + z-x which is V_z-V_x + z-x = f(x, z) (assumed V_z \geq V_x) which is dependant only upon the start and end city.

Now, we have found the cost of a path, we need to maximize the number of cities visited. Visiting the cities in non-sorted order is not allowed as it will increase the cost. So, if V_x \leq V_y, we can visit all cities z such that V_x \leq V_z \leq V_y is held. Similarly, if V_x \geq V_y, we can visit all cities z such that V_x \geq V_z \geq V_y is held.

This is it. After that, we just need to implement it which can be done using maps, which you may refer below.

Hint for using maps. You may store mappings $(x, v)$ such that there are $v$ cities with $V_i \leq x$.

TIME COMPLEXITY

The time complexity is O(N*logN) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 200200;
const long long mod = 998244353;

using namespace std;

int n;
int q;
int a[N];

void solve()
{
	    scanf("%d%d", &n, &q);
	    vector < int > v;
	    for(int i = 1; i <= n; i++){
	            scanf("%d", &a[i]);
	            v.push_back(a[i]);
	    }

	    sort(v.begin(), v.end());

	    for(int i = 1; i <= q; i++){
	            int s, t;
	            scanf("%d%d", &s, &t);

	            int cost = abs(a[s] - a[t]) + t - s;
	            int length = upper_bound(v.begin(), v.end(), max(a[s], a[t])) - v.begin();
	            length -= lower_bound(v.begin(), v.end(), min(a[s], a[t])) - v.begin();

	            printf("%d %d\n", cost, length);
	    }
}

int main()
{
	    ios_base::sync_with_stdio(0);

	    int T;
	    scanf("%d", &T);
	    while(T--){
	            solve();
	    }
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int id[1000000];
map<int,int> mn,mx;
pair<int,int> v[1000000];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
	    mn.clear();
	    mx.clear();
	    int n,q;
	    cin>>n>>q;
	    for (int i=1;i<=n;i++)
	        cin>>v[i].first,v[i].second=i;
	    sort(v+1,v+n+1);
	    for (int i=1;i<=n;i++)
	    {
	        id[v[i].second] = i;
	        mx[v[i].first]=i;
	        if (mn[v[i].first]==0)mn[v[i].first]=i;
	    }
	    while(q--)
	    {
	        int x,y;
	        cin>>x>>y;
	        cout<<abs(v[id[x]].first-v[id[y]].first)+y-x<<' ';
	        if (v[id[x]].first<v[id[y]].first)swap(x,y);
	        cout<<abs(mx[v[id[x]].first]-mn[v[id[y]].first])+1<<endl;
	    }
	}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
//Solution Credits: Taranpreet Singh
public class Main{
	//SOLUTION BEGIN
	//This code is not meant for understanding, proceed with caution
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), q = ni();
	    int[][] p = new int[1+n][];
	    for(int i = 1; i<= n; i++)p[i] = new int[]{i, ni()};
	    Arrays.sort(p, 1,n+1,(int[] i1, int[] i2) -> Integer.compare(i1[1], i2[1]));
	    int[] pos = new int[1+n];
	    for(int i = 1; i<= n; i++)pos[p[i][0]] = i;
	    TreeMap<Integer, Integer> map = new TreeMap<>();
	    map.put(-1, 0);
	    for(int i = 1; i<= n; i++)map.put(p[i][1], i);
	    while(q-->0){
	        int u = ni(), v = ni();
	        int pu = pos[u], pv = pos[v];
	        int ans = v-u+Math.abs(p[pu][1]-p[pv][1]);
	        if(p[pu][1]>p[pv][1]){
	            int t = pu;pu=pv;pv=t;
	        }
	        int a2 = map.floorEntry(p[pv][1]).getValue()-map.floorEntry(p[pu][1]-1).getValue();
	        pn(ans+" "+a2);
	    }
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	long mod = (long)1e9+7, IINF = (long)1e18;
	final int INF = (int)1e9, MX = (int)1e6+1;
	DecimalFormat df = new DecimalFormat("0.0000000");
	double PI = 3.1415926535897932384626433832792884197169399375105820974944, eps = 1e-8;
	static boolean multipleTC = true, memory = false;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    int T = (multipleTC)?ni():1;
//        Solution Credits: Taranpreet Singh
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
	    else new Main().run();
	}
	long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
	int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}   

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

3 Likes

can someone please explain editorial in detail , like why are why doing a perticular step

1 Like

Could you please explain how did you deduce this fact? It’s not given in the problem that the cities are in straight line

3 Likes

My solution gives Run time error for large second set of test cases. Can any one explain me the reason behind the Run time Error.

My Solution: https://www.codechef.com/viewsolution/24111054

" There are N cities (numbered 1 through N) on this planet; let’s denote the value of city i by vi"
i think from this line in problem

1 Like

I think a bit of an error in the 2nd last para, where the 2nd relation is Vx >= Vy, the inequality Vx<=Vz<=Vy is incorrect, it should be Vx>=Vz>=Vy.

1 Like

Since we have a single value associated with each city and the only computation involved is the distance between cities, we can visualize them to be in a straight line.

1 Like

Corrected. Thanks for pointing out.

Good explanation.Thank you.

1 Like