Can anyone tell a test case why my
[1] is giving WA.
[1]: https://www.codechef.com/viewsolution/7523518No, it won’t give “possible” since 4 and 8 belong to different segments.
2 Likes
Yeah your approach is correct, so is mine.
@Kostya_by: http://www.codechef.com/viewplaintext/4617643
It’s giving WA on : n = 6, m=2,
2 1 4 3 6 5
1 2
5 6
Giving possible but ans is impossible.
1 Like
My solution link :@p00r >> here is one test case on which your code fails:
4 3
4 3 2 1
1 3
2 2
3 4
P.S: I think there are some other bugs too in your code.
1 Like
no in that case …even for disconnected ranges it may assume that is connected …for example …for query …1 2 2 3 and 4 4…here connected range should be only from 1-3 but in ur case it would considering 1-4 …because 4 will also be updated to 1.
Please check this testcase which is wrong by your logic’
1
4
3
4
3
2
1
1 2
2 3
3 4
1 Like
@apple1 >> your code also fails on the same above test case.
here is the link to your AC solution: 4621504
I have followed the same approach of sorting every range (storing them in a temp array and then updating the original list).
it will take n^2 time, and hence i got time limit exceeded error when i submitted. You might have done some mistake
thanx !! for pointing that out…
Yes, I’ve got what you’re trying to say. But I have not called the update function if both the no’s in the interval are same. So it perfectly runs fine for the case you’ve specified. There is something else which is probably going wrong. Are you able to pinpoint what’s missing?
Thats the only bug. Fixed! Thanks!
yjanin35: it is giving me Impossible, which is correct, it can be done with this approach
Okay, I got it. For example if I query an interval which has the value 0 but if I break the current interval and all the constituent intervals have value 1 then the answer should be “Possible” while my code gives “Impossible”.