Can anyone help me in finding where my code is going wrong for the problem Partitions? My Code is failing in one test case.
I used binary search to solve the problem.
Here is the link to my code :-
solution
Can anyone help me in finding where my code is going wrong for the problem Partitions? My Code is failing in one test case.
I used binary search to solve the problem.
Here is the link to my code :-
solution
I followed an approach similar to yours. You can refer to it.
Here is the link to my code :- solution
@aryanc403, I followed an approach similar to yours. But I did a bit different thing while doing the binary search. First of all I would do this binary search and all only if the total_sum of the array is divisible by the kth partition required to be performed. Now I go on to do the binary search setting my low pointer to 0 and high pointer to n-1 . Then I perform binary search on the prefix_sum array to search only sum/k, with a small trick that each time I check the number on this array , I decrement the index by a variable x, which is firstly initialised to 0 and further when I do binary search, it gets updated by the current searched element in the prefix_sum array.Low pointer gets updated at each search by index+1 , where index= the index returned by the binary search.
Also one more condition, if at any operation of the binary search you get an index returned -1, then that means k partitions cannot be performed and we stop performing a further binary search. Also for each search I set a counter and increment it by 1. Now at the end of all the operations, I would simply check if this counter was = k .If yes then k partitions was possible in this array.
You can have look at my soln: https://goo.gl/TkND6E
Hope it helps
Well you can even use an unordered_map(in C++) or HashMap(in Java) to store the prefix sums as key. You won’t need to binary search here as you can just check whether the required sum is present or not from HashMap in a heavy O(1) operation.
This would reduce the time complexity by an additional log(n) factor. But I guess binary search too wouldn’t give TLE. Link to my solution using unordered_map.
P.S : I know the aim of this forum was not to ask an efficient solution, but I felt like sharing my approach. Hope you like it!
here a solution we are getting TLE can any one please help me
here is the link to the solution: https://www.codechef.com/viewsolution/18027093
Since, I am not familiar with java can you @onkarnandedkar @debjitdbb please please elaborate your approaches. I knew other approach but I want to know this approach also
@debjitdbb , your approach is similar to mine. Can you please show me where my code is going wrong ?
@aryanc403 , here is the approach :-
Compute the prefix sums.
For each number of partitions from i=2 to n do a binary search on the
prefix sums to check if
(sums[mid]-sums[low-1]) * (number of partitions-1) == sums[n-1] -sums[mid]
If it is true then decrement the number of partitions else the partition
is not possible for that (i).
If the condition holds true until (number of partitions == 0) then the
partition is possible for that (i).
Well just in case you didn’t figure out the change, I just changed map in your code with unordered_map. It passes well within the time limit this way!