padfoot1717's blog

Need help for an atcoder problem
By padfoot1717, history, 4 years ago, In English

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.

  • Vote: I like it
  • -24
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by padfoot1717 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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),

      → Reply