PROBLEM LINK:
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 ) . Suggestions are welcomed as always had been.