Here in this 1073C - Вася и робот my observations are -
1)If (abs(x) + abs(y)) < string_length then ans -1
2)If (abs(x) + abs(y)) > string_length and ((abs(x) + abs(y))-string_length)%2 != 0 then also ans -1
Then I was thinking like, okay only way can be binary approach or any tiring greedy approach. But none of these could not help to proceed. Because If I will use binary search, how can I increase or decrease the length.
Do not put any direct solution. Just hints or just let me know where my thinking is wrong?
I am trying to be very subtle...
Think about what are you binary search-ing exactly?
On length. But,if on length, from where it has to be started?
If you don't know where it has to be started, there are at most O(N) starting positions to be tried
Nice. I have got it. But I thought, checking for each length might cause TLE. Because for each length there would be (n-len) positions to check.
But it won't. Because we might have to check for logn length. And in worst case there might be nlogn complexity . Well I do not know if my calculation of TL is right :3 But I have got the idea. Can you please explain the complexity? And thanks for being subtle <3
You probably got the idea already. It may take O(N) to check for a specific length, therefore we apply binary search to reduce the number of lengths checked from O(N) to O(lg N). The number of lengths we will try is in O(lg N), therefore if we spend O(N) complexity on each length, it will take O(N) * O(lg N) time for all O(lg N) lengths we check.
Though, I guess you still have to figure out how to check for a single answer :)