[Community Puzzle] Rectangle Partition

I somehow got confused by the measurements thing, thinking they instead were the size of the intervals. “But why are they provided sorted, it can change the result?”. Until it finally dawned on me. Then solving the puzzle was not a problem. Maybe it would help to have a picture (rather than ASCII art) of a graph with graduated axes to illustrate what the input really is?

1 Like

Unfortunately the present CG platform does not allow images in puzzles. Having the ascii diagram is the best that can be done.

1 Like

I have exactly the same problem: Sames Errors at Bigger-2, Hi-density 1 and Imbalance, and may code is in javascript too… Did you find a solution ?

Easy? Huh…

Try to split the problem into smaller ones.
The problem would be easier if you were given the dimensions of all the small rectangles right ?

So first step, compute these dimensions and store them somewhere.

Then all you need to do is: iterate over these dimensions, compare, conclude.

1 Like

Having O(n^2) you get what you get: people timing out left and right. I’m not saying it’s hard, it’s just not so easy. And I have no idea how not to timeout with N=5000. Well, I kinda have, but… here is what I found.

I was playing with worse case scenarios for first few Ns and w=h=N+1 (so for N=1 the answer is 5, for 2 its 14 and so on…) and guess what? We got square pyramidal numbers here!

https://oeis.org/A000330

And the formula is pretty simple: a(n) = n*(n+1)(2n+1) / 6

Try for yourself for N=501 and you’ll get the magic 42042751 number people got few posts above (see Jan 2 post).

It’s funny how worse case gives you an instant answer.
Now the only question remains what if we have not the worse case scenario but very close to it… :thinking:

Some members said above they use java and do not need any optimization just a double nested for-loop it will pass all tests. Java plays its magic to optimize itself!

Other than this special language case, use a map structure. It has been mentioned many times above of this very standard skill that everyone should learn.

1 Like

You don’t need to store rectangles one by one, all you need to know is how many rectangles of each width/height there are.

The basic structure for that in C++ is an unordered map (note that a normal map would work too). It has other names in other languages : dict in Python (or even better, defaultdict), Hash in ruby, etc.
Depending of the implementation, it will be O(N log N) or O(N).

1 Like

Hey thanks for the puzzle and for this hint. The hint absolutely saved me!
Since you mentioned, I’ve been thinking about solving this with DP.

I think the base problem can be easily solved,

  • Given width and height
  • if width == height, return 1
  • else, return 0

and then somehow add all the results. But I’m stuck on how to divide width and height measurement lists into base problems. Any ideas?

Edit: I got a working algorithm, which I implemented in Dart and it timed out on HighDensity test. Pseudo code:

  • foo(width sub-measurements, height sub-measurements)
  • if both list contains single and same element, count++ // Base case.
  • if first list has more than one elements, call foo(each element of first list, second list)
  • else, call foo(first list, each element of second list) // using a loop to pass each element

The way I did it : for each line at y1 loop through all the points x1, then for each following point x2 on the same line, look if there’s a point at y1 + (x2 - x1), in which case you know you have a square. The only data structures you need are a list for the xs and ys given as part of the inputs.
That covers all possible squares quickly enough.

1 Like

Hi,

Out of curiosity, how can I actually test my solution with this one in the codingame debugger?

P.S. : I’m trying to get my way into C++ after coming from Python, and your problem made me think and learn A LOT in a little more than 2 hours. Thanks a lot for the way you created it, it’s really cool.

You have to activate the expert mode in the settings. Then you can use the Custom button:


Screenshot 2020-09-26 134937

3 Likes

I’m confused, this was exactly my solution, yet i fail on the hi-density because takes too long

Hi, j’avais exactement le même problème ! Je pense qu’il faut utiliser .equals() à la place de == pour compter les carrés.
Ça m’as permis de validé tout les tests… mais j’avoue ne pas totalement comprendre pourquoi étant donné que l’on compare des Integers…
Bon courage :slight_smile:

1 Like

Hello! I don’t know what to do about the Hi-Density stuff. ): My code is written in C# and I use 6 for-loops: 2-2 for input and 2 for calculating the result. Is that too much? Or could the problem be somewhere else?

Consider using a map structure. See the much earlier posts in this thread.

1 Like

I really enjoyed solving this challenge, thank you!

The problem looked like a quick easy solve, and then alas I stumbled at the high density cases.
Code wise it was simple, but the logical insight was not. For that it felt like a medium problem.
Thanks OP for a great experience.
I had fun finding ways to change the algorithm down to O(n^2) 100%, and I felt humbled.

Can someone help me? I dint understand this puzzle.
I understand it this way. I have sheet of paper, and now I get task to cut it to squares of length of centimeters.
sheet of paper is 10, 5.
First square I can cut and I left with 5, 5. 1-square.
another sheet of paper is 5, 5.
second square i cut 3, 3 and I left with second square.
another sheet of paper is 2, 3.
I cut last square 2, 2. and left with 1, 2.
Then why I need have 4 squares if I cut out only 3 peaces?

Another way is to divide it by 2 to get how many I can get squares. And then I can get in total 5 squares.

Also I am understanding that I cant use square which I need to cut it in smaller peaces. Also I cant cut more then one peace square even if last available peace 5, 2 I can get 2 extra squares of 2, 2.

Not sure I understand your post, maybe this will help you :
Sans titre

With the given rectangle and coordinates you can form one 2x2 square (green), one 3x3 (blue) and two 5x5 (red).

1 Like