SLEEPTECH - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Никита Лазарев
Tester: Nishank Suresh
Editorialist: Taranpreet Singh

DIFFICULTY

Easy-Medium

PREREQUISITES

Difference Arrays, Binary Search.

PROBLEM

There are N problems in the contest. The i-th of them was solved at minute L_i for the first time. This task will stop increasing the joy of everyone around at the minute R_i + 1 (that is, R_i is the last minute when the task increases the joy). In other words, the i-th task increases the joyfulness for everyone by 1 unit from the minute L_i to the minute R_i.

In the anime that Egor watched recently, there are various techniques that can make a person fall asleep. Egor knows techniques that will allow him to sleep for any minutes between A and B minutes, i.e. Egor can sleep for A minutes, A + 1 minutes, …, B minutes. Egor can also combine techniques, i.e. he can choose techniques with different duration and then sleep the total time of all techniques.

Egor wants to combine techniques to wake up in the most joyful moment possible. Your task is to find the maximum joy in which Egor can wake up.

QUICK EXPLANATION

  • Using the intervals [L_i, R_i], we can easily divide the whole number line into at most 2*N+1 blocks, where each block has the same joy value.
  • Considering each block [X, Y], we want to determine if there’s a subset of distinct elements in [A, B] whose sum lies in [X, Y].
  • For that, a binary search on the minimum number of elements is selected. If x elements are selected from [A, B], then the sum we can obtain is in range [x*A + x*(x-1)/2, x*B - x*(x-1)/2].

EXPLANATION

First of all, let us simplify the information we have for our use. We have N intervals, and in order to calculate joy at some moment T, we need to iterate over all intervals and count the number of intervals including position T. We need some kind of preprocessing to answer these kinds of queries faster than iterating over all intervals.

Let’s J(T) denote the joy at moment T. Assuming no interval starts or ends at T or T+1, then we can claim that J(T) = J(T+1) shall hold. This is because the joy level change only when some new interval starts, or some existing interval stops. We can see that there are exactly N start points and exactly N endpoints. So these kinds of positions are at most 2*N, dividing the number line into 2*N+1 parts.

The implication of the above is that we can divide the whole number line into disjoint continuous partitions, such that each continuous partition has the same joy.

For example, consider intervals [1,4], [3,6], [2,10],[8,8], we can write joy levels partitions as follows

  • [-\infin,0] has joy level 0
  • [1,1] has joy level 1
  • [2,2] has joy level 2
  • [3,4] has joy level 3
  • [5,6] has joy level 2
  • [7,7] has joy level 1
  • [8,8] has joy level 2
  • [9,10] has joy level 1
  • [11,\infin] has joy level 0

These intervals can be formed using difference arrays, which can be implemented using ordered maps.t

Now, after forming these intervals, we can forget the original intervals. All we need to do is to iterate over these partitions, and determine if there’s a subset of distinct elements of [A, B] such that Egor can wake up in this partition or not. Among all partitions where Egor can wake up, we compute the maximum.

Reduced problem

We have a set of elements [A, B], from which we can pick any subset. Can we pick a subset of these elements with the sum in the range [X, Y] or not.

Let’s say we pick x elements where 0 \leq x \leq B-A+1. The smallest sum we can get is by picking smallest x elements, i.e. A, A+1, A+2 \ldots A+x-1, whose sum is A*x + x*(x-1)/2. Similarly, the largest sum we can obtain is B*x - x*(x-1)/2.

Claim: By choosing x elements optimally, Egor can wake up at any moment in interval [A*x + x*(x-1)/2, B*x-x*(x+1)/2].
Proof: Let’s start with picking the smallest x elements in a set called S. We aim to obtain a subset with sum T where S lies in the above range. Repeat the following process until the sum of the subset is T.

  • Find the largest element a such that a \in S and (a+1) \notin S.
  • Remove a and add (a+1) to S.

By this process, the sum of S increases by 1 unit after each step. The only time we are unable to select an element a in the first step is when we have chosen the largest x element in [A, B]. The sum of S is B*x-x*(x+1)/2 at this point. Hence, by this process, we are able to obtain subset with each sum in the range [A*x + x*(x-1)/2, B*x-x*(x+1)/2].

Coming back, by choosing x elements, we can check if intersection of range [A*x + x*(x-1)/2, B*x-x*(x+1)/2] and [X, Y] is non-empty or not. If we find it non-empty for any value of x, we have found a subset with the sum in the range [X, Y], so the answer to our reduced problem is yes.

But there can be B-A+1 possible values of x, and we cannot iterate over all of them.

A clever trick here is to binary search for the largest value of x such that A*x + x*(x-1)/2 \leq Y. After finding such x, it is sufficient to compare intersection of range [A*x + x*(x-1)/2, B*x-x*(x+1)/2] and [X, Y] is sufficient to determine the answer to our reduced problem.

For reference, the reduced problem is implemented as a function in Editorialist’s solution section.

TIME COMPLEXITY

The construction of J intervals takes O(N*log(N)) time. There are 2*N intervals and we need to run a binary search which takes O(log(B)) time.

So the overall time complexity is O(N*(log(N)+log(B))

SOLUTIONS

Setter's Solution
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <array>
#include <unordered_set>
#include <list>
#include <cassert>
#include <fstream>
#include <unordered_map>

#define DEBUG
#define pqueue priority_queue
#define pb(x) push_back(x)
#define endl '\n'
#define all(x) x.begin(), x.end()
#define int long long
#define mk(a, b) make_pair(a, b)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<char> vc;

const ll inf = 1e9 + 228;
const ll infll = 1e18;
const ll mod = 1e9 + 7;
//static const int maxn = 1e6 + 228;
const ld eps = 1e-9;
const ll mod2 = 998244353;
const ld PI = atan2l(0, -1);

void fast_io() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    freopen("fishes.in", "r", stdin);
//    freopen("fishes.out", "w", stdout);
}


vpii kek;

int n, a, b;

int check(int pntr) {
    int l = 1, r = (b - a + 1);
    int ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        int mn = a * mid + mid * (mid - 1) / 2;
        if (mn <= pntr) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

bool cmp(pii a, pii b) {
    if (a.first == b.first) {
        return a.second > b.second;
    }
    return a.first < b.first;
}

void solve() {
    cin >> n >> a >> b;
    kek.resize(n);
    for (pii &i:kek)
        cin >> i.first >> i.second;
    vpii lol;
    for (pii i:kek) {
        lol.pb(make_pair(i.first, 1));
        lol.pb(make_pair(i.second , -1));
    }
    lol.pb(make_pair(1e18, 0));
    sort(all(lol), cmp);
    int cnt = 0;
    int ans = 0;
    int lst = -1;
    for (pii i:lol) {
        int an = check(i.first);
        int mx = b * an - an * (an - 1) / 2;
        if(mx >= lst){
            ans = max(ans, cnt);
        }
        cnt += i.second;
        lst = i.first;
    }
    cout << ans << endl;
}


signed main() {
    fast_io();
    srand(time(NULL));
    int q = 1;
    cin >> q;
    while (q--)
        solve();
}
Tester's Solution
#include "bits/stdc++.h"
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long int;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
 
    int t; cin >> t;
    while (t--) {
        int n, a, b; cin >> n >> a >> b;
        map<ll, int> ct;
        for (int i = 0; i < n; ++i) {
            ll l, r; cin >> l >> r;
            ++ct[l]; --ct[r+1];
        }
        int ans = 0, cur = 0;
        ll prev = (*ct.begin()).first;
        for (auto &[x, y] : ct) {
            ll lo = 1, hi = b - a + 1;
            while (lo < hi) {
                ll mid = (lo + hi + 1)/2;
 
                // a + a+1 + a+2 + ... + a+mid-1
                // = mid*a + mid*(mid-1)/2
                ll left = mid*a + mid*(mid-1)/2;
                if (left >= x) hi = mid-1;
                else lo = mid;
            }
            ll right = lo*b - lo*(lo-1)/2;
            ll left = lo*a + lo*(lo-1)/2;
            if (left < x and right >= prev) ans = max(ans, cur);
            
            cur += y;
            prev = x;
        }
        cout << ans << '\n';
    }
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class SLEEPTECH{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        long A = nl(), B = nl();
        TreeMap<Long, Integer> delta = new TreeMap<>();
        for(int i = 0; i< N; i++){
            long L = nl(), R = nl()+1;
            delta.put(L, delta.getOrDefault(L, 0)+1);
            delta.put(R, delta.getOrDefault(R, 0)-1);
        }
        long ans = 0, joy = 0;
        for(Map.Entry<Long, Integer> e:delta.entrySet()){
            long st = e.getKey();
            Long en = delta.higherKey(st);
            if(en == null)break;
            en--;
            joy += e.getValue();
            if(possible(A, B, st, en))ans = Math.max(ans, joy);
        }
        pn(ans);
    }
    boolean possible(long A, long B, long from, long to){
        //Is it possible to wake up in time range [from, to], using techniques within [A, B]
        long lo = 0, hi = B-A+1;
        while(lo < hi){
            long mid = lo + (hi-lo+1)/2;
            long minSleep = sum(A, A+mid-1);//Minimum sleep by picking mid elements from [A, B]
            if(minSleep <= to)lo = mid;
            else hi = mid-1;
        }
        long sleep = sum(B-lo+1, B);
        return sleep >= from;
    }
    long sum(long A, long B){
        //Sum of elements from A to B, both inclusive
        A--;
        return ((B*B+B)-(A*A+A))/2;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    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 SLEEPTECH().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. Suggestions are welcomed as always. :slight_smile:

7 Likes

I tried prefix sum approach using map, where mp[L[i]]++ and mp[R[i]+1]–.
In addition when I took an Example A = 4, B = 8. I found there is always only one sequence and one number I have to care about, like in this case seq = [ 4 … 26 ], and number = 30. these are the only combination made from sleeping techniques. So i added 3 more numbers in map.
mp[4]+=0, mp[26]+=0 and mp[30] += 0 ( for particular these cases ).
then finally using a single loop on map i did prefix sum.

int last = 0, ans = 0 ; 
here m1 = 4, m2 = 26, m3 = 30;
for( auto& x : mp ){
        if( x.ff > m3 ) break ; 
        last = x.ss + last ; 
        if( (m1 <= x.ff && x.ff <= m2) || ( x.ff == m3 ) ){
            ans = max(ans,last) ;
        }
    }

Still its not accepted I don’t have any idea where I’m failing.
Here is my full code, please have a look.

Hey,it would be really helpful,if someone explains the problem clearly.

I tried reading the problem statement over and over ,but unable to break it down and understand.

Thanks.

In this editorial the upper limit is wrong sometimes. i.e.
( B * x - ( x * ( x + 1 ) ) / 2 ) is wrong
( B * x - ( x * ( x - 1 ) ) / 2 ) is right

2 Likes