Whistleroosh's blog

Creating square from smaller squares
By Whistleroosh, history, 5 years ago, In English

Hey,

recently I came across a problem which is described below. I've been struggling with it for a while. Could You please help me by giving some hints?

You are given n squares of certain sizes and have to create a larger square using all of those smaller squares. By that I mean that you can connect these squares however you want, so that it results in one large square. Input looks in the following way: first line contains n (it was not explicitly stated what is the max value of n, but it is something in range <30, 90>) and second line contains n integers (each of value from 1 to 50) each describes size of i-th square. As output you have to write either "YES" if it is possible to create a square from all the smaller squares or "NO" if it is impossible.

At first I thought that it's some kind of dynamic programming, but I believe that it'd be hard to keep track of squares which where used to create some state in DP. I'm also not convinced about some greedy approach, like take largest square which haven't been used and place it in first empty position, because that would be to easy and I know that these kind of tasks require more thinking. So I'm thinking that maybe some backtracking approach would be the right choice, though I'm not sure about that. Could You please help me with this task?

Example tests:

INPUT

6
1 1 1 2 1 1

OUTPUT

YES

INPUT

3
5 5 5

OUTPUT

NO

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

»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Maybe, think about how you could form a square.

(1) If you have 4 squares with same side length, you can easily create a bigger square.

(2) If you have 3 squares of side length N, and 4 of side length N/2, we form a bigger square. But, the four squares of side N/2 already form a bigger square as per case (1).

(3) If you have 3 squares of side N, and one of side N-K, and 5 of side K / 2, we form a bigger square. But, the 4 of 5 squares of K/2 already form a bigger square as per case (1).

and so on.... all of them will at least involve 4 smaller squares of same side length.

I don't know if I'm missing something but I guess finding at least 4 values that are the same will do the work. This can be done simply by sorting and then counting for 4 same occurrences.

Would you mind sharing the problem link so I can try?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You try to create bigger squares from smaller but I don't think it'll work. Look at pictures from this site. Sometimes these constructions are quite irregular.

    But here is the link to task, though it is Polish site so you have to use some translator.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah, you're right. It's more complicated than my initial interpretation, now that I think of it. Nonetheless, the problem seems to be very interesting and I'll give it a shot and try coming up with a solution. I was looking up some stuff on google and happened to have found the same Wiki link you shared, but thanks anyway.

      I like -is-this-fft-'s comments on various problems and his way of explaining things so it'd be great to have him share an idea maybe.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know how to solve the problem above (it seems very hard) but the linked problem doesn't seem to be the same one at all. Is it the correct link?

        Anyway the linked problem seems to be "count the number of times a substring appears in a string" except "string" and "substring" are 2-dimensional. I believe it can be solved with hashing in a similar way to the 1D case.

        → Reply