machinepainter's blog

By machinepainter, history, 6 years ago, In English

I was going through the following question

Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.

I tried writing a dp and a greedy solution for this problem, but none of them worked. Unfortunately the site from where I am practising this question also does not have a correct solution. Can someone please suggest a solution to this problem or is this also NP-hard like polygon partition ?

Complete Problem Statement

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

This was the hardest problem in Northern Subregional of NEERC in season 2016-2017. https://codeforces.net/gym/101142/attachments , problem H.

Probably there are no known polynomial solutions.