Kindly try this problem and provide a detailed algorithm for solving it, i will be extremely thankfull. Link to the problem Edit-Seems to be extremely strange, that people rather than helping are delibrately downvoting just for the sake of fun.

# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 200 |

2 | antontrygubO_o | 191 |

3 | pikmike | 188 |

4 | Monogon | 184 |

4 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 179 |

8 | Radewoosh | 173 |

9 | SecondThread | 172 |

10 | McDic | 161 |

Kindly try this problem and provide a detailed algorithm for solving it, i will be extremely thankfull. Link to the problem Edit-Seems to be extremely strange, that people rather than helping are delibrately downvoting just for the sake of fun.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/07/2020 07:16:16 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by saurav1717 (previous revision, new revision, compare).Consider the one-dimensional version of this problem(i.e., h = 1) . Here you can see that a greedy solution would work where you'll make a cut only when the number of 1's in the current segment exceeds k.

Coming to the original problem, since h <= 10 thus you could brute force the number of horizontal cuts(i.e., try every possible combination of horizontal cuts) and for each combination calculate greedily the number of vertical cuts required to ensure that each component has <= k 1's (just like the one-dimensional counterpart of this problem).

Thanks.

Can you please further elaborate that after chosing a particular combination of horizontal cuts, how am i going to decide greedily where to make vertical cuts.

Just like in the one-dimensional counterpart we can use prefix sums here. Simply create the prefix sums for every row. For checking whether a vertical cut is required at the current position we can simply check the maximum number of chocolates that are present at any of the blocks enclosed between the previous vertical cut(or the left boundary in case no cut has been made) and the current position which we are considering.

Coming to the part where you need to check the maximum, consider its 1-D counterpart where you are given a boolean array and the positions where it is partitioned. To find the maximum number of 1s in this case, the most trivial way is to check for each segment(brute force). Coming back to the problem since h <= 10 brute force can also work here. However, instead of blindly checking for each segment we can use prefix sums to reduce the complexity of this task from O(hw) to O(h),

Ok, i got it.