LIFTME - Editorial

PROBLEM LINK:

Contest

Author: Ayush Ranjan
Tester: Raja Vardhan Reddy
Editorialist: Rajarshi Basu

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation

PROBLEM:

Given are 1 \leq Q \leq 10^6 requests. Initially the lift is at floor 0. In each request a lift first moves to floor F_i from its last location, and then moves to floor D_i. Finally, the lift can be at any floor. Find total number of floors traversed. F_i, D_i\leq N \leq 10^6.

QUICK EXPLANATION:

Simulate the process!

EXPLANATION:

No really, let’s just simulate what we are being told. Let us say we store where we are presently at (BEFORE the current query) by curr. Obviously, curr = 0 initially.

  1. Let the total number of floors travelled be totalCount.
  2. Now, when we first go to floor F_i, number of floors are we travelling = |F_i - curr|.
  3. Next, we go to D_i. Number of floors travelled = |D_i - F_i|
  4. We just need to add this to totalCount, and set curr = D_i and voila, we can process the next request.

And… we are done!

PS: Don’t forget to use long long int, since totalCount can go up to N * Q = 10^6 * 10^5 = 10^{11}

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		ll ans = 0;
		int n, q, lst = 0, floor, dest;
		scanf("%d%d", &n, &q);
		while(q--)
			scanf("%d%d", &floor, &dest), ans += abs(floor - lst) + abs(dest - floor), lst = dest;
		printf("%lld\n", ans);
	}
} 
Tester's Solution
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
 
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,q,i,ans=0,cur_floor;
		cin>>n>>q;
		cur_floor=0;
		for(i=0;i<q;i++){
			int s,d;
			cin>>s>>d;
			ans+=abs(cur_floor-s);
			ans+=abs(s-d);
			cur_floor=d;
		}
		cout<<ans<<endl;
	}
	return 0;
} 
	 
Editorialist's Solution
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define vv vector
 
using namespace std;
 
const int INF = 1e9;
const int MAXN = 1e3+5;
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n,q;
		cin >> n >> q;
		ll sum = 0;
		ll lst = 0;
		while(q--){	
			int a,b;cin >> a >> b;
			sum += abs(a-lst) + abs(b-a);
			lst = b;
		}
		cout << sum << endl;
	}
 
	return 0;
} 

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

3 Likes

Why was even N is given in the probelm :thinking:

6 Likes

Ooh thank you so much @rajarshi_basu for mentioning the data type of the answer…only because of that I didn’t get the green tick.

4 Likes

Can someone tell me what’s wrong with my solution
https://www.codechef.com/viewsolution/32105013

I am getting correct answer with another approach …But when i am trying this approach in my local editor I am getting correct answer but when compiled here I am getting wrong answer…Can someone please help me to figure out where i am going wrong.

This is the link - https://www.codechef.com/viewsolution/32104510

I’m using this approach of storing a variable to store current floor, and getting the correct answer , but the answer is not accepted. Is this a wrong approach. Also can someone tell me where did i go wrong ?

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.RoundingMode;  
import java.lang.Math;


	
class LiftMe
{
		
	
    	public static void main (String[] args) throws java.lang.Exception
	{		   
		LiftMe obj = new LiftMe();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());		
		
		while(t-- > 0) {	
			    	StringTokenizer st = new StringTokenizer(br.readLine());
			    	int Fi = Integer.parseInt(st.nextToken());
		    		int Di = Integer.parseInt(st.nextToken());

				int floor_count = 0;
				int current_floor = 0;
				while(Di -- > 0) {
	  			     StringTokenizer sc = new StringTokenizer(br.readLine());
				     int f = Integer.parseInt(sc.nextToken());
				     int d = Integer.parseInt(sc.nextToken());
		    	
					floor_count += Math.abs(current_floor - f);
					current_floor = f;
					floor_count +=  Math.abs(current_floor - d);

				}	
				System.out.println(floor_count);

		
		}		
	}
}

For N=4
Q=1
F = 4, D = 2

Your answer is 2
Correct answer is 6 ( 4 up 2 down )

You are considering that lift will always go up in first query but it can move up and then down too in a single query.

1 Like

I don’t think it matters

Please anyone help me to find my fault , I’m new in programming. Help me;
#include <stdio.h>

int main()
{
int T,j;
scanf("%d",&T);
for(j=0;j<T;j++){
int N,Q,i;
int f,d,sum=0,g,k=0,h;
scanf("%d %d",&N,&Q);
for(i=0;i<Q;i++){
scanf("%d %d",&f,&d);
g=d-f;
if(g<0){
g=-1g;
}
h=k-f;
if(h<0){
h=-1
h;
}
k=d;
sum=sum+g+h;
}
printf("%d\n",sum);
}
return 0;
}

Please anyone give the answer in c language,

your code has some logical error
variable g has to be zero initially always
then, the value of g will be the value of d.

In shaa Allah
you can check it.
https://paste.ubuntu.com/p/PkBdNFMnNM/

Can someone please let me know what is wrong with my solution ?
Link : https://www.codechef.com/viewsolution/32041764.

Thanks in advance !!

Brother please give me the answer in c language

1 Like

Thank You So Much for your help

1 Like

Please anyone give the answer in c language

Assalamu Alaikum

brother i’ve checked your code. there are so many logical errors. so, read the question again carefully

if you can’t get the idea, you can check it

In shaa Allah
all the best

link: https://paste.ubuntu.com/p/55JHSrygJc/

the 30th line of your code is not needed

In shaa Allah

you can check it
link: https://paste.ubuntu.com/p/7kKDqS84R2/

Thank you ,brother.

1 Like

can someone pls tell me whats wrong in my code. Its working fine on text editor but here I’m getting wrong ans.
https://www.codechef.com/viewsolution/32118555
thank u so much

The datatype is the problem here. you should use long instead of integer.