[Community Puzzle] Rectangle Partition

Finally I could solve it with mapping. It was really hard for me. I’m learning C++ and it was the first problem I solved with that language. I don’t know what data structures are more efficiently for each kind of problem in that language.

1 Like

I did it!
I replaced all my fancy containers and iterators with good old pointers and dynamic arrays to finally pass the High density tests…

but still… I wonder how can I get to pass the High density tests with a more modern C++ like solution rather than an almost C one?

EDIT: nevermind I can actually access the solutions since I passed 100% :stuck_out_tongue:


Hello ! :grinning:

I thank the author for this puzzle and you guys who posted. I’m doing it with Java.

I only pass the 3 first tests : simple, squarish and bigger 1, and validators 1,2,3,6

I do nested loops to store x and y gaps and then compare them. I saw that it is what it is just advised by the author in his hidden hint.

I specify that I don’t have time out issue but lower square detection

Please help !

More gems to discover. A few more messages about enhancing efficiency were posted below the hidden hints.

I had the same problem.
There is a big difference between ‘==’ and ‘equals’ in Java.

1 Like

LeifTerry : Thank you very much, I was still thinking, reading the thread but found no idea to solve my problem. With your hint I pass 3 more tests (the 6 firsts) and time out for the 3 others. I’m very surprised about that difference between == and .equals()

OK I passed all tests and validators with no efficiency enhancing at all. The last problem was a debug code that increased time. Once I deleted this code, I passed everything. (JAVA)

Thank you !

I think this puzzle should be at difficulty medium. I wasn’t able to pass all test without using maps. But maybe it’s due to the fact that i’m kind of new to c++. But still, it seems a hard for an “easy” puzzle. Take me few hours when I expected to finish in one.

Hi, everybody. I could pass all the tests cases with language BASH, but I can not pass the Validator 6.

Anyone knows what makes this validator?? Thank you in advance!!!

Improved some test cases so that your bug, if any, is more likely to reveal. Try again.

1 Like

Thank you for the reply. I will try again!! Finally I got it!!!

Hi there! I spent a few hours on this test and I don’t understand why I fail on validator 3 (the others are successful)
I’ve rewritten my code several times and read the different tips but I can’t find the solution.
Could someone help me understand what type of test is missing for validator 3 please?

I’s ok, I got it.

I am not able to get the Hi-density 2. My code is getting time out, any ideas? I think it is because I am using nested loops, but how to overcome it?

You should read this topic, hints have already been provided to other users with similar issue.

1 Like

I got time out for 7 and 8. The helpful hint is the == comparison sign. Printed out the time taken to compare, and oh my, I now know why it took so long.

Optimizing that one line helps a lot.

Thanks for the hints!
Using dict instead of list (Python) made me pass the Hi-Density tests.

Hi guys! I was having trouble with the high density problems, these were the methods:

At first I was creating a list of all the possible rectangles coordinates like “(0,0) (0,1) (1,1) (1,0)” and then comparing the sizes of each rectangle edge, if the edges had equal size, it was a match. This method took 5+ minutes to solve.

The second method I used was: instead of compairing the coordinates values, I could actually store all the edge sizes in a list, and then compare all the edge sides, one by one. This one, reduced the time to 21 seconds, but it’s still not enought to pass high density cases.

The third method, and the one that solved in less than 1sec, is based in the use dictionaries to optmize the comparison of the lenghts that match in x and y. I hope it helps! :slight_smile:

1 Like

To all the poor souls trying to pass Validators 7,8,9 using C++, you need maps to do it.


It was a fun challenge. Resolving it was quite easy. The problem was optimizing it.