CHEFRES - EDITORIAL

general
, , , , ,
13

#include
#include
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

14

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.

15

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 - //package CodeChef;import java.io.BufferedReader;import java.io.BufferedWr - Pastebin.com

16

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.

17

My [solution][1] during contest got 30 pts with a WA for second test and the same


[2] in practice got AC(100 pts). 
This seems to be a bug as [this comment][3] is also similar and I am getting weird results in other problems too. 

  [1]: https://www.codechef.com/viewsolution/20374448
  [2]: https://www.codechef.com/viewsolution/20442402
  [3]: https://discuss.codechef.com/questions/136251/chefres-editorial/136345
18

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.

19

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

1 Like
20

Solutions will be linked soon.

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

21

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.

22

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

23

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

24

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.

25

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

26

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

27

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

28

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.

29

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

30

Can anyone help me with the code , it is giving runtime

31

Could anyone please check my code why is it not working ? i am getting runtime error.

32

Does anybody know why my code in the second subtask gives a wrong answer((even though it is correct in the first one)? I used Python
https://www.codechef.com/viewsolution/71502253