Painter's partition problem

#1

My code is failing 3 out of 6 test cases.

#2

The code you have shared is written in C++. Are you enrolled in C++ course or Java? If you are enrolled in Java course, then please share java code for the question so that I can help you

#3

Java
I was just checking my logic.

#4

Since I’m a Java course TA, I’m not very familiar with C++. Please share Java code and I’ll help you out.

#6

Here’s the code in java :

#7

I went through your approach, it seems it a bit complicated and I am not able to understand what exactly you’re trying to do. It seems like your approach is not generalized for all kinds of testcases. This question can be solved simply using binary search. As it is given that it takes 1 unit of time to paint 1 unit of a board, in the worst case the total time taken would always be equal to the total area of all boards. So, you need to try for every value of time to see if it is possible to paint the boards in that amount of time, and keep decreasing the time to see if it can further be minimized. Instead of trying for every value of time, you can use binary search for optimization. So, now essentially what you need to do is write a function which given the number of boards, painters and time, will check if such a combination is possible.

#8

So what i am basically doing is
1.Sorting the dimensions
2. giving the n largest dimensions to the n painters(array r[n])
3.Distributing the remaining by comparing for each value the minimum of the second arrary
4.Finding the max value of r
Though i get my approach is not efficient I’d like to know where I went wrong logically if possible. :slight_smile:

#9

It is given in the question that Every painter can paint only contiguous segments of boards. Have you taken care of that condition?

Your code is giving wrong output for test cases like : 2 4
10 20 30 40
Correct output : 60
Your code output : 50 (which would be the output if above condition is not taken into account)

#10

Okay got it.Thanks a lot.

1 Like
#11

If you have any further queries then let me know! Otherwise, please mark the doubt as resolved :slight_smile:

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.