Python solution (short).
1 Like
@eaugenethomas You don’t check bounds in the loop while(v[f].first){f++;} - f runs beyond the size of the vector.
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…
@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
Whats offline mode???
#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
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.
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
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.
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/136345I 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.
I was amazed by seeing offline mode XD…
Idk how that idea came first to some of you…
1 Like
Solutions will be linked soon.
Until that, I am going to post ideone links for my solutions.
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.
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
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