Help needed in Partitions (ARRP)

general
1

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

1 Like
2

I followed an approach similar to yours. You can refer to it.
Here is the link to my code :- solution

1 Like
3

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 :slight_smile:

4

@debjitdbb , your approach is similar to mine. Can you please show me where my code is going wrong ?

@aryanc403 , here is the approach :-

  1. Compute the prefix sums.

  2. 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]

  3. If it is true then decrement the number of partitions else the partition
    is not possible for that (i).

  4. If the condition holds true until (number of partitions == 0) then the
    partition is possible for that (i).

5

@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 :slight_smile:

1 Like
6

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!

1 Like
7

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

8

https://www.codechef.com/viewsolution/18029066
Click here for magic xD

1 Like
9

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!