COKE2 - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan

Tester: Teja Vardhan Reddy

Editorialist: Taranpreet Singh

DIFFICULTY:

Easy

PREREQUISITES:

Basic Math, Cases, Segment tree with Lazy Propagation.

PROBLEM:

Given the initial temperature and prices of N cokes and the acceptable range of final temperature [L, R] and the ambient temperature K.

If a can has temperature x at the current minute, then following happens.

  • If x > K+1, x reduces by 1.
  • If x < K-1, x increases by 1.
  • Otherwise x = K

You are required to find the cheapest can for each minute i \in [1, Q] such that after i minutes, its temperature is in the range [L, R].

EXPLANATION

Assuming we are dealing with a can with Temperature C and price P.

First thing, Exactly one of the following three can happen.

  • K < L
    • In this case, if C < L then it never attains any value in range [L, R] since it’s moving away. This coke can never be optimal.
    • In case L \leq C \leq R, then this coke shall be optimal till time x such that C-x >= L which means x \leq C-L, so this coke is valid in time range [0, C-L]
    • In the last case where C > R, then this coke shall enter allowed range at time C-R and remain valid till time C-L. So this coke is valid in time range [C-R, C-L]
  • K > R
    Similar cases can be made as above.
  • L \leq K \leq R.
    Here, once the current temperature of any coke enters range [L, R], cannot leave the range, thus shall remain valid till the end. We only need to find minimum x such that after x minutes. If L \leq C \leq R, then this coke is valid in the time range [1, Q]. If C < L, then this coke is valid in time range [L-C, Q]. Similarly for C > R.

By the above cases, we got a valid time period for each coke, during which we are allowed to choose that can. So, it is not hard to see, that for each minute y, we basically have a set of coke cans, whose time period contains y. Since we are looking for the cheapest can, we shall always take the one with the minimum price.

It is an easy application of the range minimum point query segment tree. Initially, we can set cost for all minutes to some large values. Then for each can with valid time period [st, en], we can update the minimum of range [st, en] by segment tree with lazy propagation.

Some of the nice segment tree blogs are here and here.

Alternate solution:

An alternate solution is also possible, by using priority queues (or maybe even queues) to keep a set of coke cans which are valid at the current minute. We have also added their price to ordered multiset. Moving to next minute, we add new coke cans and their prices and remove all coke cans and their prices from queue and multiset respectively which are no longer valid. For the minimum cost, if the multiset is empty, no can is valid, otherwise, the query to the smallest element would return minimum cost.

TIME COMPLEXITY

The time complexity is O((N+Q)*log(Q)) 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,q,k,l,r;
int C[100100];
int P[100100];

int sm_n=0;
int sm_q=0;

int sgt[400400];

void update(int nd,int l,int r,int s,int e,int val){
	if(s<=l && r<=e ){
		sgt[nd] = min(sgt[nd], val);
		return;
	}
	int mid=(r+l)/2;
	if(s<=mid){
		update(2*nd,l,mid,s,e,min(val,sgt[nd]));
	}
	if(mid+1<=e){
		update(2*nd+1,mid+1,r,s,e,min(val,sgt[nd]));
	}
}

int query(int nd,int l,int r,int ind){
	if(l==r)return sgt[nd];
	int mid=(r+l)/2;
	if(ind<=mid){
		return min(sgt[nd],query(2*nd,l,mid,ind));
	} else {
		return min(sgt[nd],query(2*nd+1,mid+1,r,ind));
	}
}

int main(){
	//freopen("03.txt","r",stdin);
	//freopen("03o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		n=readIntSp(1,100000);
		q=readIntSp(1,100000);
		k=readIntSp(-100000,100000);
		l=readIntSp(-100000,100000);
		r=readIntLn(l,100000);

		sm_n += n;
		sm_q += q;

		assert(sm_n<=1000000);
		assert(sm_q<=1000000);
		for(int i=0;i<=4*q;i++){
			sgt[i]=1<<30;
		}
		for(int i=0;i<n;i++){
			C[i]=readIntSp(-100000,100000);
			P[i]=readIntLn(1,1000000000);
			int ll,rr;
			if(C[i] < l ){
				if(k < l){
					continue;
				} else if(l<=k  && k<=r){
					ll= l - C[i];
					rr= q;
				} else {
					ll = l - C[i];
					rr = r -  C[i] ;
				}
			} else if(l<= C[i] && C[i] <= r){
				if(k < l ){
					ll = 1;
					rr = C[i] - l ;
				} else if(l<= k && k <= r){
					ll= 1;
					rr= q;
				} else {
					ll = 1;
					rr = r  - C[i];
				}
			} else {
				if ( k < l){
					ll = C[i] - r;
					rr = C[i] - l;
				} else if( l<= k && k <= r){
					ll = C[i]  - r;
					rr = q;
				} else {
					continue;
				}
			}
			ll=max(ll,1);
			rr=min(rr,q);
			if( ll <= q && 1<= rr){
				update(1,1,q,ll,rr,P[i]);
			}
		}
		for(int i=1;i<=q;i++){
			int h= query(1,1,q,i);
			if(h ==1<<30){
				cout<<"-1 ";
			} else
			cout<<query(1,1,q,i)<<" ";
		}
		cout<<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];
vector<vi> vec(123456),vec1(123456);

int add(int val,int q,int pr){
	if(val<=q){
		vec[val].pb(pr);
	}
	return 0;
}
int remov(int val,int q,int pr){
	if(val<=q){
		vec1[val].pb(pr);
	}
}
int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,q;
		cin>>n>>q;
		int k,l,r;
		cin>>k>>l>>r;
		int i,j;
		rep(i,n){
			cin>>c[i]>>p[i];
		}
		int tim;
		rep(i,n){
			if(k<l){
				if(c[i]>r){
					add(c[i]-r,q,p[i]);
					remov(c[i]-l+1,q,p[i]);
				}
				else if(c[i]>=l){
					add(0,q,p[i]);
					remov(c[i]-l+1,q,p[i]);
				}
			}
			else if(k>r){
				if(c[i]<l){
					add(l-c[i],q,p[i]);
					remov(r-c[i]+1,q,p[i]);
				}
				else if(c[i]<=r){
					add(0,q,p[i]);
					remov(r-c[i]+1,q,p[i]);
				}
			}
			else{
				tim=0;
				if(c[i]<l){
					tim=l-c[i];
				}
				else if(r<c[i]){
					tim=c[i]-r;
				}
				add(tim,q,p[i]);
			}
		}
		multiset<int> seti;
		rep(i,q+1){
			rep(j,vec[i].size()){
				seti.insert(vec[i][j]);
			}
			rep(j,vec1[i].size()){
				seti.erase(seti.find(vec1[i][j]));
			}
			if(i>0){
				if(seti.empty())
					cout<<-1<<" ";
				else
					cout<<*(seti.begin())<<" ";
			}
			vec[i].clear();
			vec1[i].clear();
		}
		cout<<endl;

	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class COKE2{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni(), q = ni(), k = ni(), l = ni(), r = ni();
	    SegTree t = new SegTree(1+q);
	    for(int i = 0; i< n; i++){
	        int c = ni(), p = ni();
	        int st = 0, en = -1;
	        if(k < l){
	            if(c <= l){}
	            else if(c <= r+1){
	                st = 1;
	                en = c-l;
	            }else{
	                st = c-r;
	                en = c-l;
	            }
	        }else if(k > r){
	            if(c >= r){}
	            else if(c >= l-1){
	                st = 1;
	                en = Math.min(q, r-c);
	            }else{
	                st = l-c;
	                en = Math.min(q, r-c);
	            }
	        }else{
	            if(c < l-1)st = l-c;
	            else if(c > r+1)st = c-r;
	            else st = 1;
	            en = q;
	        }
	        st = Math.max(st, 1);
	        en = Math.min(en, q);
	        if(st <= en)t.update(st, en, p);
	    }
	    for(int i = 1; i<= q; i++){
	        long ans = t.min(i);
	        if(ans == IINF)ans = -1;
	        p(ans+" ");
	    }
	    pn("");
	}
	long IINF = (long)1e18;
	class SegTree{
	    int m = 1;
	    
	    long[] sum, lazy;
	    public SegTree(int n){
	        while(m<=n)m<<=1;
	        lazy = new long[m<<1];
	        sum = new long[m];
	        Arrays.fill(lazy, IINF);
	        Arrays.fill(sum, IINF);
	    }
	    void push(int i, int ll, int rr){
	        if(i >= m)sum[i-m] = Math.min(sum[i-m], lazy[i]);
	        else{
	            lazy[i<<1] = Math.min(lazy[i<<1], lazy[i]);
	            lazy[i<<1|1] = Math.min(lazy[i<<1|1], lazy[i]);
	        }
	        lazy[i] = IINF;
	    }
	    void update(int l, int r, long x){update(l, r, 0, m-1, 1, x);}
	    void update(int l, int r, int ll, int rr, int i, long x){
	        push(i, ll, rr);
	        if(l == ll && r == rr){
	            lazy[i] = x;
	            return;
	        }
	        int mid = (ll+rr)/2;
	        if(r <= mid)update(l, r, ll, mid, i<<1, x);
	        else if(l > mid)update(l, r, mid+1, rr, i<<1|1, x);
	        else{
	            update(l, mid, ll, mid, i<<1, x);
	            update(mid+1, r, mid+1, rr, i<<1|1, x);
	        }
	    }
	    long min(int pos){return min(pos, 0, m-1, 1);}
	    long min(int pos, int ll, int rr, int i){
	        push(i, ll, rr);
	        if(i >= m)return sum[i-m];
	        int mid = (ll+rr)/2;
	        if(pos <= mid)return min(pos, ll, mid, i<<1);
	        return min(pos, mid+1, rr, i<<1|1);
	    }
	}
	//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 COKE2().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:

6 Likes

Instead of using Lazy Propagation, we can simply sort on the basis of Current Temperature and then for each value of m from 1 to q, find the left most and right most index using binary search in the array which satisfy the given requirement and then simple RMQ over that interval using a Segment Tree. But for some reason that approach gives WA in the last TC. I’m guessing it is some sort of corner case. Any help is appreciated.

Solution Link : CodeChef: Practical coding for everyone

@jagreetdg I used the same approach as you with binary search and segment tree RMQ.
Link to my submission: CodeChef: Practical coding for everyone

In my solution I consider 3 cases when I do the binary search. Suppose that you want to find the leftmost index. You compute the final temperature after ‘mid’ minutes and if it is in <l, r> then you take ‘mid’ as a new ‘high’. However if the final temperature is less than l then you must take ‘mid’ as a new ‘low’ because you must find a value that fits in <l, r>. Similarly, if the final temperature is greater than r then you have to look for a smaller value so you must take ‘mid’ as a new ‘high’.

In the same way I look for the rightmost index.

I don’t know about multi set and segment trees. I have used this approach for solving partial cases.
I sorted the 2D array on the basis of coke price and then looped from time 1 to Q for each loop. I was stuck at calculating the temperature for every can for that particular time i. So I used a for loop to calculate temperature.
Here is my partial accepted solution:- Can I improve this somehow?

#include<bits/stdc++.h>
using namespace std;

int newtemp(int ci, int k, int m) {
  for(int i = 0; i<m; i++) {
    if (k-1 <= ci && ci <= k+1) {ci = k;
    break;}
    else if (ci > k+1) ci = ci-1;
    else if (ci < k-1) ci = ci+1;
  }
  return ci;
}
bool sortcol(const vector<int>& v1,
               const vector<int>& v2 ) {
 return v1[1] < v2[1];
}
int main() {
  int t;
  cin>>t;
  while(t--) {
    int n, q, k, l, r;
    cin>>n>>q>>k>>l>>r;
    vector<vector<int>>arr(n, vector<int>(2));
    for(int i = 0; i<n; i++) {
      cin>>arr[i][0]>>arr[i][1];
    }
    sort(arr.begin(), arr.end(), sortcol);
    int temp, minPrice;
    for(int time = 1; time<=q; time++) {
      int flag = 0;
      for(int i =0; i<n; i++) {
        temp = newtemp(arr[i][0], k, time);
        if (temp >= l && temp <= r) {
          minPrice = arr[i][1];
          flag = 1;
          break;
        }
      }
      if (flag == 0) {
        cout<< -1<<" ";
      } else {
        cout<< minPrice<<" ";
      }
    }
    cout<<endl;
  }
  return 0;
}

First sort the temperature .We can simply update the range of ( L , R ) before each queries .
if( L > k ) L++ , R++ :: as decreasing values ( which are greater than k ) by 1 is equivalent to increasing range by 1 .
if( R < k ) L-- , R–
if( L<=k && R>= k ) L-- , R++

Then we just have to find the indexes of the temperature which lies between L to R . Easily done using Binary Search ( Lower_bound , Upper_bound )

Then find the Range minimum in that index by any data structure.

Solution link : CodeChef: Practical coding for everyone

4 Likes

Please tell me good resources to learn segment trees…

links are given in editorials.

1 Like

I am instead building a segment tree for all cans and initializing all values to a large value.
s[i] and t[i] (below)are calculated in the same way as the editorial

for i from 1 to Q
i have a dictionary s[i] denotes the index of the cans which become valid starting from i and t[j] denotes the index of the cans which become invalid starting from j.
If a can becomes valid I change the value of that can in the tree to its cost
if a can becomes invalid I change the value of that in the tree to a large value
then I print the first node of the tree (that is the minimum cost can)

but I am getting tle even though I am making max (2*n) point updates and not even range updates.
Please help

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

edit:language problem again

same solution works in C++ that too in 0.35/1
while in python it doesn’t even work in 5 seconds

@taran_1407 @vijju123 @l_returns @infinitepro

1 Like

Used your approach and some suggestions from this thread too. Instead of using binary search, I used lower_bound and upper_bound, which are implemented on binary search, Here is my solution
https://www.codechef.com/viewsolution/26226616

2 Likes

https://www.codechef.com/viewsolution/26231271
I have implemented the same approach as mentioned in the editorial. I have created a segment tree for storing minimum’s for all segments of 1 to Q. I am not using Lazy Propagation here. I have created three functions : buildTree(), updatetree() and printquery(). Please can anyone tell me why my code is giving WA. It is working fine for sample testcases. Please provide a test case that my code might be failing. PLEASE HELP

1 Like

I solved this problem without using segment tree. I calculated start time and end time (for the coke to be drinkable when chef reaches home) and just pushed them in two different arrays of vectors. Then a simple sweep was required using a multiset to calculate the min for each time considered k such that 1 <= k <= M.

Link : CodeChef: Practical coding for everyone

1 Like

Thank you so much for this helpful post.

PLEASE HELP for the above code. I have been stuck for days now

python is really slow on large arrays i guess, but not much sure about it.