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?

P.S. I'm not sure what tags to add for this problem but I will add the appropriate tags and title once I receive guidance.

  • 1
    $\begingroup$ Please try to make a title that is more descriptive of your problem, the current title in fact makes me think this problem is about hash functions, while it isn't. $\endgroup$ – Discrete lizard Feb 26 '18 at 13:50
  • 1
    $\begingroup$ The problem as phrased doesn't clearly fall within a well-known class. I think this is the whole point of the challenge, you're supposed to solve a problem for which there aren't satisfactory solutions yet. So I think the only thing that can help you get started (other than having someone else solve the problem) is general algorithm design techniques and a lot of practice on similar, but easier problems. $\endgroup$ – Discrete lizard Feb 26 '18 at 13:53
  • 1
    $\begingroup$ 'algorithms problem' isn't much more descriptive than the previous title. All questions with the algorithms tags can be described by that. Please make a title for this specific problem. $\endgroup$ – Discrete lizard Feb 26 '18 at 13:56
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Feb 26 '18 at 18:10
  • 1
    $\begingroup$ The way you learn to be an Olympic-level ice dancer isn't by going to a coach and saying "I want to learn how to do a triple-axel jump; how do I do that?" You start by practicing the basics. So, the best way to prepare for the next contest might be studying a variety of basic exercises on algorithms and data structures, rather than trying to solve the previous contest problem with no background. $\endgroup$ – D.W. Feb 26 '18 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.