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 ?
This was the hardest problem in Northern Subregional of NEERC in season 2016-2017. https://codeforces.com/gym/101142/attachments , problem H.
Probably there are no known polynomial solutions.