motatoes's blog

By motatoes, history, 5 years ago, In English

Hello CF!

I'm preparing for the next hashcode by solving the following prev. problem:

Given a pizza of size R x C with cells containing either mushrooms or tomatoes as shown bellow:

We are given 2 parameters: L and H. The goal is to split the pizza into rectangular slices such that each rectangle contains at least L cells of mushrooms and at least L of tomatoes. Furthermore, each split rectangle should contain at most H cells in total. Note that not all of the pizza needs to be contained in the split. The goal is to maximize the number of cells

So in the example above, L=1 and H=6 so in this case The ideal split will be:

So each split contains at least 1 mushroom and at least 1 tomato, and each split contains at most 6 cells. I am not sure how to approach the solution to this problem? Which topics should I read about to understand how to solve such a problem?

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

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

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

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

Psyho's blog, http://psyho.gg/, has some nice write-ups on marathon problems. He is one of the best in the world in this kind of problems, so it is worth checking out. The blog is a bit outdated, though (the last post is two years ago).