You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFRES - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Maps, Binary search or ordering queries would do fine.

PROBLEM:

Given $N$ disjoint intervals $[L_i, R_i)$ and $M$ query times $P_i$, we need to print the minimum waiting time from query point to any time belonging to any interval, at or after query time.

SUPER QUICK EXPLANATION

  • Sort intervals as well as query time, maintain two pointers and for every interval, iterate from earliest query time $X$ and answer is $L_i - T_i$ if query time is before interval, otherwise $0$ for every query time such that $R_{i-1} \leq X < R_i$.
  • Alternate online solution is for every query $X$, to use binary search to find earliest interval such that $X < R_i$. If query time lies in interval, Wait time is zero, else $L_i-X$.
  • Query times at or after $R_n$ will wait forever (if possible without food :D)

EXPLANATION

Since intervals are disjoint, every query point can belong to at most one interval, which we need to find, in order to find out the waiting time. Suppose we know that for query time $X$, the required interval is $[L, R)$. How to calculate waiting time?

See the secret box.

View Content

This is enough to solve sub task 1, since we can check for every query time, waiting time for all intervals ending after query time and print the minimum of all waiting times, but this results in $O(N*M)$ complexity, which is too slow for sub task 2.

We need to find this interval fast. We know that the interval we are seeking is in fact the earliest interval which ends after query time.

It is ideal to sort the intervals, whenever we need to find such earliest, first, last intervals. Sorting is almost used in every problem which involves intervals.

Anyways, after sorting, if interval j is required interval, we know that either $j==1$ of $R_{j-1} \leq X < R_j$. This can be used as condition for binary search, since all interval before jth interval has $R_i \leq X$ and all intervals after jth interval has $R_i < X$.

Otherwise, we can sort the query points and use two pointers, one for query points and one for interval index. For every interval, assign minimum times to all query points which are before $R_i$, not assigned answer yet.

In case answer is not assigned to query, customer has to survive without food forever.

Time Complexity

For binary search solution, Time complexity is $O((M+N)*logN)$.
For Offline solution, Time complexity is $O(N*logN +M*logM)$.

Proving complexity is not hard for this problem, though may be referred in secret box.

View Content

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution
Tester's solution
Editorialist's solution

Edit: Until above links are not working, You may refer solution here.

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)

This question is marked "community wiki".

asked 30 Sep '18, 01:05

taran_1407's gravatar image

6★taran_1407
3.9k2895
accept rate: 22%

edited 30 Sep '18, 11:16

For a binary search solution, you may refer any solution in practice using binary search. I found this solution, doing binary search using lower_bound function.

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

(30 Sep '18, 21:40) taran_14076★

Can't see the solutions - shows html with "Access denied" message.

link

answered 30 Sep '18, 04:01

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

Solutions will be linked soon.

Until that, I am going to post ideone links for my solutions.

(30 Sep '18, 10:59) taran_14076★

Python solution (short).

link

answered 30 Sep '18, 07:53

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

Why does this question have line sweep tag?? I didn't participate in the contest. But as soon as I have seen this tag I wanted to upvote. But now I'm reserving it for some other day.

Comment on editorial - I upsolved it using offline mode. But was amazed by seeing binary search approach. :)

link

answered 30 Sep '18, 04:58

aryanc403's gravatar image

5★aryanc403
2.6k1516
accept rate: 10%

1

I was amazed by seeing offline mode XD....
Idk how that idea came first to some of you....

(30 Sep '18, 09:28) l_returns5★

Actually i just saw i referred to it by offline solution only. Didn't realize this until i posted the editorial, that i have not named the offline solution.

(30 Sep '18, 11:00) taran_14076★

@eaugenethomas You don't check bounds in the loop while(v[f].first){f++;} - f runs beyond the size of the vector.

link

answered 30 Sep '18, 09:55

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

edited 30 Sep '18, 09:59

@eugalt Thanks for pointing out. Now it works fine https://www.codechef.com/viewsolution/20400880

link

answered 30 Sep '18, 10:07

eaugenethomas's gravatar image

4★eaugenethomas
32
accept rate: 0%

can i get the test cases that u have been uploaded for this?? please, i need to check it out where i made my program to do mistake.. thanks in advance....

link

answered 30 Sep '18, 10:45

sathvikrijo's gravatar image

1★sathvikrijo
1
accept rate: 0%

No, Test cases cannot be shared, as per codechef rules. You can see detailed discussion or put forward your views if you wish to, at link below.

https://discuss.codechef.com/questions/7509/link-to-test-cases-after-contests

(30 Sep '18, 11:03) taran_14076★

@taran_1407 ,I applied binary search but it is showing tle.Could u explain? https://ide.geeksforgeeks.org/XgWvSXyZqX

link

answered 30 Sep '18, 12:10

utchinu's gravatar image

3★utchinu
01
accept rate: 0%

You're passing the vector by value in your binary search. That by itself is $O(n)$. Pass it by reference.

(03 Oct '18, 17:33) algmyr7★

@taran_1407 , can you please check my code for this problem ,because i dont understand that why i got only 30 point and WA for rest of test cases.

link of my solution : https://www.codechef.com/viewsolution/20395523

link

answered 30 Sep '18, 12:53

vishalm2017's gravatar image

4★vishalm2017
01
accept rate: 0%

edited 30 Sep '18, 13:00

I submitted your code in practice, and it got AC. This is a known problem.

https://discuss.codechef.com/questions/136250/wa-in-contest-ac-in-practice

(30 Sep '18, 21:18) eugalt3★

So why my solution got WA for rest of 70 points during the contest.

(03 Oct '18, 07:53) vishalm20174★

why am i getting tle? please help!!

link to my solution is: https://www.codechef.com/viewsolution/20407310

link

answered 30 Sep '18, 20:05

sourav_sikaria's gravatar image

2★sourav_sikaria
1
accept rate: 0%

Your solution tries to iterate over range of size up to 1e9, which cannot be completed in one second. Assume 1e7 iteration can be done in one second.

(30 Sep '18, 21:36) taran_14076★

Whats offline mode???

link

answered 01 Oct '18, 03:10

zeph1yr's gravatar image

1★zeph1yr
1
accept rate: 0%

Offline mode means we read all queries first, answering them in some specific order and printing answers according to their order in input.

(01 Oct '18, 03:26) taran_14076★

Can anyone help me I have used Binary search, but it gives me TLE? link: Ideone

link

answered 01 Oct '18, 10:10

apoorvsaxena's gravatar image

3★apoorvsaxena
1
accept rate: 0%

include<iostream>

include<algorithm>

using namespace std;

struct Interval { int start=-1, end=-1; };

bool compareInterval(Interval i1, Interval i2) { return (i1.start < i2.start); }

int main() { int t; cin>>t; while(t--) { int n,m; cin>>n>>m; Interval ta[n+1]={{-1,-1}}; int ta_len=1; for(int i=1;i<n+1;i++) {="" int="" x,y;="" cin="">>x>>y; ta[i].start=x;ta[i].end=y; ta_len++; } sort(ta, ta+ta_len, compareInterval);

    int ca[m+1]={-1};
    int new_ca[m+1]={-1};
    int maxv=-1;
    int ca_len=1;
    for(int i=1;i<m+1;i++)
    {
        int temp;
        cin>>temp;
        if (maxv<temp)
            maxv=temp;
        ca[i]=temp;
        new_ca[i]=temp;
        ca_len++;
    }

    sort(new_ca,new_ca+ca_len);

    ca_len--;
    int sol[maxv+1]={0};
    int j=1;
    int i=1;
    while(i<ta_len)
    {
        if (ta[i].start <= new_ca[j] && new_ca[j] < ta[i].end)
        {
            sol[new_ca[j]]=0;
            j++;
        }
        else if(ta[i-1].end <= new_ca[j] && new_ca[j] < ta[i].start)
        {
            sol[new_ca[j]]=ta[i].start-new_ca[j];
            j++;
        }
        else if(new_ca[j]>=ta[i].end)
            i++;
    }

    if (j<ca_len+1)
    {
        for(int i=j;i<ca_len+1;i++)
        {
            sol[new_ca[j]]=-1;
            j++;
        }
    }

    for(int i=1;i<=ca_len;i++)
        cout<<sol[ca[i]]<<endl;
}

}

what is wrong with my code? it's complexity is nlogn (I think so) so why it is giving TLE

link

answered 01 Oct '18, 16:17

siddhant02's gravatar image

3★siddhant02
1
accept rate: 0%

why my binary approach solution is giving tle. i think it's complexity is nlogn. Also,please suggest some cases for which my code is giving WA.

link

answered 01 Oct '18, 18:00

humblejumbo's gravatar image

3★humblejumbo
22
accept rate: 0%

You're passing on the vector in int binarysearch(vector<pair<ll,ll> > v1,ll l,ll r,ll key) by value, so you copy a vector of pairs for every single call to binary search. Make that a reference int binarysearch(vector<pair<ll,ll> > &v1,ll l,ll r,ll key) and you should get decent running times.

(03 Oct '18, 16:33) algmyr7★

Can anyone tell me why my BS approach gives TLE but sorting queries approach does not. Both solutions have the same complexity. Both solutions here - BS - https://pastebin.com/PyhCsSj0 Sorting queries - https://pastebin.com/D5QV9TJH

link

answered 01 Oct '18, 18:38

archit940's gravatar image

2★archit940
1
accept rate: 0%

Hey. So this question i had solved in java on the contest day, and the submission from that day is here. And today, after fruitlessly racking my brain for where the NZEC could have arised, i submitted the same code, and you know it, it showed full AC. Today's code is here. So what did actually transpire by on the contest day? I am totally perplexed and an answer would be so satisfying.

link

answered 02 Oct '18, 01:00

ajs_code_96's gravatar image

3★ajs_code_96
1
accept rate: 0%

My solution during contest got 30 pts with a WA for second test and the same code in practice got AC(100 pts). This seems to be a bug as this comment is also similar and I am getting weird results in other problems too.

link

answered 03 Oct '18, 03:12

siddhant22's gravatar image

5★siddhant22
121
accept rate: 0%

I am using binary search and also pass my vector by reference, still got tle. Please help me, what could i do to decrease the time? Here is my solution link - https://www.codechef.com/submit/complete/20938161. Please help.

link

answered 17 Oct '18, 15:54

sagar2405's gravatar image

4★sagar2405
01
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,770
×1,041
×651
×78
×47
×10

question asked: 30 Sep '18, 01:05

question was seen: 2,926 times

last updated: 17 Oct '18, 15:54