chef and matrix division

hi… please give editorial for https://www.codechef.com/SEPT16/problems/CHMTDV or give good approach because
i solved this type of problem(challenger) first time…

I solved this problem considering rows and columns as separate entities. So, I maintained a row sum and column sum. Then the problem reduced to 1-D version where given an array, we need to partition it into p parts such that maximum sum of any given part is minimised. This 1-D problem is available on Spoj by the name of copying books. Just one change is there, if many solutions exists, there they minimise the sum in the initial part. This may be bad in this case as there may be some correlation between rows and columns. So what I did here was just, after doing initial partition, if the number of partitions I made was less than required, I find the largest partition of size >= 2, which can be split further, (in the code, see the “while” loop). I got TLE initially though. So I limited the number operations. Even after doing this, if I get less partitions, I randomly assign the partitions, in this case the first few unmarked partitions.

Although this is not the best solution as there will be some correlation between rows and columns but since the test cases were randomly generated, it gives a good score of around 80 points. Had it been set by the setter, I guess it may give some less points and perform badly on some cases as well.

For more details, you can refer to my code at https://www.codechef.com/viewsolution/11504012

Most of my code is commented and names are self explanatory. If anything is not clear, you can ask below.

1 Like

Let S = The sum of whole matrix

S=S/p

For row_sum try to place p-1 divisors with each section having sum approximately equal to S

For col_sum try to place p-1 divisors with each section having sum approximately equal to S

This method gives about 75

Another method is to solve the problem for 1D version(for row_sum and col_sum independently) using Binary_search or using Dynamic programming.This method gives a few more points

I solved it with Dynamic Programming , Initially , calculating the sum of all columns , and divide that array into P - 1 blocks , I solve it with dp[i][j] = maximum sum block produce till , ith element
using jth division at index i where dp[i][j] = min(dp[i][j] , max(dp[k][j-1] , presum[i] - presum[k]), where presum[i] = array[1] + array[2]… array[i] ( cumulative sum ) and 1 < k < i .
In this way I am able to find the vertical division. Then with the help of vertical division , i found the horizontal division with the same dp approach and this time i divide it by considering the whole matrix not just the single dimensional array .
Through this approach i got 93 score , and on increasing the number of trials , i am able to score 97 , where trials means , after calculating the vertical division , and take them as a input , and with the help of horizontal division I found new updated vertical division , then again horizontal and so on… up to 8-10 trials.
My solution complexity is O( N * (N-1)/2 * P ) approx.

2 Likes

If you find the solution as correct, please mark the answer as accepted as well :stuck_out_tongue:

i solved with s/p method but give me 5 pt… my code is wrong no my approach
thank you for guidance

if you now submit your code in practice problem get 26pt!