wsrstf's blog

By wsrstf, history, 5 weeks ago, In English,

When I was participating Round #475 Div.2 I looked at this problem and found it very interesting. However, I couldn't come up with any good solution at that time('cause there was only 30 mins left and I thought Problem D would be easier to solve(though I didn't solve that either, T T)). Today I reviewed this problem, but couldn't understand what the tutorial means, so after an hour's thought I got an idea by myself.

It's not very difficult to find that although there exist many ways to cut such a rectangle, all those of same type can be moved to gather around. This can lead to the fact that we only need to consider the cases when each type of smaller rectangles are gathered together, forming a bigger rectangle with area c. So now our problem is organizing n distinct rectangles properly such that the finally shape consist of these n rectangles IS A RECTANGLE. We know every component rectangle's area, which equals to the number c of input(here we translate 'number' to 'area' to better understand what we are doing). Say the new shape consists of such n different rectangles is a rectangle iff we can organize these n rectangles in such a way that if we consider each component of different types of rectangles as a small point, then all n points are formed as a matrix, that is every row has exactly the same number of points, so as to every column. If we translate points to small rectangles, then we are getting close to the answer. Difference between points and rectangles is that points are 0-dimentional, yet rectangles are 2-dimentional. So now what we need to do is reshape the small rectangles such that they can properly form the final rectangle. I will omit the rest of the solution because I think my idea has been explained clearly above. (Though I have referred to others' codes to implement this efficiently)


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

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