COKE - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic math

PROBLEM:

Given temperatures and prices of N coke cans. You want to drink the cheapest coke which quenches your thirst. You know a coke shall quench your thirst if it’s temperature if within the range [L, R]. All these cokes lie at distance M and the normal temperature is K. For every second, if the current temperature of coke is x, it changes as follows.

  • If x > K, x reduces by 1.
  • If x < K, x increases by 1.
  • If x == K, x remains same.

EXPLANATION

It can be seen that we can consider each coke separately. For each coke, we need to determine whether after M seconds, whether it’s temperature is within the acceptable range, and for all cokes, we can take the one with minimum cost. If no coke satisfies, the answer is -1.

Now, what shall be the temperature of coke after M seconds. If Initial temperature is more than K, then every second, the temperature reduces, until it reaches K. Once it reaches K, it remains K. So, the final temperature can be written as max(K, C_i-M)

In other case, temperature increases every second till it reaches K. So, the final temperature can be written as min(K, C_i+M) (as we want to stop as soon as it reaches temperature K).

Hence, we can check for each code whether it is within the range [L, R] and take minimum cost.

TIME COMPLEXITY

Time complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
		
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}

int T;
int n,m,k,l,r;


int main(){
	//freopen("00.txt","r",stdin);
	//freopen("00o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		n=readIntSp(1,100);
		m=readIntSp(1,100);
		k=readIntSp(-50,50);
		l=readIntSp(-50,50);
		r=readIntLn(l,50);
		int best = 10000000;
		for(int i=0;i<n;i++){
			int c,p;
			c=readIntSp(-50,50);
			p=readIntLn(1,1000000);
			for(int j=0;j<m;j++){
				if(c > k){
					c--;
				} else if( c< k){
					c++;
				}
			}
			if(l <= c && c<= r){
				best=min(best,p);
			}
		}
		if(best == 10000000){
			cout<<-1<<endl; 
		} else {
			cout<<best<<endl;
		}
	
	}
	assert(getchar()==-1);
}
Tester's Solution
//teja349
#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); 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 flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

int c[123456],p[123456];
int main(){
	//std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,m,k,l,r;
		cin>>n>>m>>k>>l>>r;
		int i;
		int mini=inf;
		rep(i,n){
			cin>>c[i]>>p[i];
			if(abs(c[i]-k)<=m){
				c[i]=k;
			}
			else if(c[i]>k){
				c[i]-=m;
			}
			else{
				c[i]+=m;
			}
			if(l<=c[i] && c[i]<=r){
				mini=min(mini,p[i]);
			}
		}
		if(mini==inf)
			mini=-1;
		cout<<mini<<endl;
	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class COKE{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), m = ni(), k = ni(), l = ni(), r = ni();
	    int ans = (int)1e8;
	    for(int i = 0; i< n; i++){
	        int c = ni(), p = ni();
	        if(c > k)c = Math.max(c-m, k);
	        else if(c < k)c = Math.min(c+m, k);
	        if(l <= c && c <= r)ans = Math.min(ans, p);
	    }
	    if(ans > 1e7)ans = -1;
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new COKE().run();
	}
	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 you want to. (even if its same :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

2 Likes

Can anyone help me out.
In the question it has clearly stated that when the temp>k+1, then it will decrease by one and when temp<k-1
then it will increase by one, then why are we checking temp>k instead of temp>k+1

Because it’s the same thing. Checking for t > k will include t > k + 1 which will be better as both of them will become either k (if m allows for values t > k + 1)

I have a problem.
My solution: https://www.codechef.com/viewsolution/26000460
I sorted the pair of price and temperatures according to their non-decreasing prices, and checked the temperature range for every element. Where did I go wrong?

Your code is reduntant try this approach
https://www.codechef.com/viewsolution/26020556

Simple understandable solution
https://www.codechef.com/viewsolution/25992763

Of course my code is redundant lol. O(nlogn) complexity unnecessarily. I wish to know why this is wrong instead of time consuming.

https://www.codechef.com/viewsolution/26023538
can anyone figure out why TLE even though complexity is O(n*t)

this post was deleted.

1 Like

Can anyone help me to find why my answer is wrong https://www.codechef.com/viewsolution/26028837

https://www.codechef.com/viewsolution/25998924
Here’s my approach.

// now just dry run with temp as 5 and ambtemp as 4

if(temp>ambtemp){
ans=Math.max(ambtemp,temp-minut);
}
else if(temp<ambtemp){
ans=Math.min(ambtemp,temp+minut);
}
else {
ans=ambtemp;
}

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int main(){
int t;
cin>>t;
while(t–){
ll n,m,k,l,r,price=23463456;
cin>>n>>m>>k>>l>>r;
ll c,p;
for(ll i=0;i<n;i++){
cin>>c>>p;

        if(c<k-1){
            if(c+m >= k-1)
                c=k;
            else
                c+=m;
        }   
        else if(c>k+1){
            if(c-m <= k+1)
                c=k;
            else
                c-=m;
        }
        else if(c>=k-1 && c<=k+1){
            c=k;
        }
        
        if(c>=l && c<=r){
            if(price>p)
                price=p;
        }
            
    }
    if(price==23463456)
        cout<<"-1\n";
    else
        cout<<price<<endl;
    
}

please tell me why this code is not working.
Showing Wrong Answer!!!

#include<bits/stdc++.h>
using namespace std;
#define d(str) cout<<#str<<" : “<<str<<”\n"
#define p(str) cout<<#str
#define o(str) cout<<str
#define nl printf("\n");
#define mem(a,b) memset(a,b,sizeof(a))

int main()
{
int t,n,m,l,r,k;
cin>>t;
while(t–)
{
cin>>n>>m>>k>>l>>r;
int var1,var2,i,j;
map<int,int>mp;
bool flag=1;
for(i=0;i<n;i++)
{
cin>>var1>>var2;
mp[var2]=var1;
}
/*
for(auto it=mp.begin();it!=mp.end();it++)
cout<fir<<" --> "<sec<<endl;
*/
for(auto it=mp.begin();it!=mp.end();it++)
{
if(it->second<=l&&l-it->second<=m)
{
cout<first;
flag=0;
break;
}
else if(it->second>=r&&it->second-r<=m)
{
cout<first;
flag=0;
break;
}
else if(it->second>=l&&it->second<=r)
{
cout<first;
flag=0;
break;
}
}
if(flag)
cout<<-1;
nl;
}
return 0;
}

Why am i getting WA in this??
Suggest me a changes or testcase at which my code is being wrong…

Please mention the link to your code…don’t write the whole code.

https://www.codechef.com/viewsolution/26003147

Can anyone help me find why is my code giving WA?

import operator

for _ in range(int(input())):
    n, m, k, l, r = map(int, input().split())
    ls = dict()
    
    for i in range(n):
        c, p = map(int, input().split())
        ls[c] = p 
        
    sorted_x = sorted(ls.items(), key=operator.itemgetter(1))
    
    ans = -1

    for i in sorted_x:
        temp = i[0]
        if(i[0] != k):
            if(i[0] > k):
                if(i[0]-m <= k):
                    temp = k
                else:
                    temp = i[0] - m 
                
            else:
                if(i[0]+m >= k):
                    temp = k
                else:
                    temp = i[0] + m
                    
        
        if(temp in range(l,r+1)):
            ans = i[1]
            break
        
    print(ans)

simple problem for a cookoff competation

since in the problem statement, if t>k+1 then we have to decrement t by 1 and if t<k-1 then we have to increment t by 1, then why in the solution, we are just comparing t and k instead of k+1 or k-1. Can anyone tell me something about this (the reason about which I am not able to think…) ?

https://www.codechef.com/viewsolution/26048904
what the problem?