Painters Partition problem

#1

code link: https://ide.codingblocks.com/s/358657

please check my code and suggest changes as it failed to pass two test cases.

#2

Hey @shivanshu12800 which test cases were you failing?

#3

@mr.encoder the test case 3 and 5 are failing

#4

Hey @shivanshu12800 you forgot to sort it, you have let your s=arr[n-1] without sorting. Might be these test cases aren’t in sorted order. Try this and let me know did it get accepted or not :slight_smile:

#5

i tried sorting the array but then it gave wrong answer for test 0, 2, 4

#6

But sorting is necessary m okay do one thing. Instead of doing sorting . Find the maximum element in the array and initialise start with that maximum element. If it works then let me know.

#7

https://ide.codingblocks.com/s/358657 see I just calculated the Max element in the function and with this it passed all the TCs but when I do sorting , it failed the TCs…why so?

#8

This problem works on two approach either you chose sorting or find maximum element in an array and start with it. Your approach was ideal for finding the maximum element and then preceding to further problem.
There’s a dedicated editorial here : https://www.geeksforgeeks.org/painters-partition-problem-set-2/
Check it out and it will clear your all queries :grinning: