Official editorial coming soon
Video link: LAZERTST Solution - CodeChef March Long Challenge 2020 - YouTube
4 Likes
I have just one question. I did exactly what’s given in the editorial, but I got a lot more wrong answers.
It took me 40 attempts to get AC.
Have i done some implementation mistake?
https://www.codechef.com/viewsolution/30257273
Edit: I just rechecked my program because it should have gotten accepted on first try and realised ans[q] is initialised without inputting q.
Did you submit the same program each time? I thought that the array and the queries were fixed.
Yes, at least 35 of my submissions was this.
Can somebody explain why those “simple” solutions work?
It seems that resonse to the queries is never -2.
Why?
I include the proof in the video
Sorry, I am not able to listen to the video.
For K = 10, we went for M/2
Why can’t we do the same for when K = 3? Why go for M-1?
I think you got a little confused… For k=3, 2<=m<=10 which is so small for r-l>=1000 that there is very less probability that maximum height(i.e ans) is less than m-1(maximum possible height). So we are answering the maximum height for every query.
Whereas for k=10, we are questioning taking height of m/2 with x1=l, x2=y(these are the same as query) e.g. if query is from 10 to 200, we ask the same question using x1=10, x2=200 but y=m/2 so that there is maximum probability of hitting maximum segment
Proof of this is explained beautifully in the video.
can someone help with this code? I have used the logic in the video explanation.
codechef.com/viewsolution/30598025
Also when we are trying to query the range sum shouldn’t we reduce the left index by one to make it inclusive of the left and right index? (in the code from given in the description).