[Community Puzzle] Rectangle Partition


#21

Interesting feature - added the hidden tag. Thanks.


#22

My solution is not well optimized. However, I did exactly what you wrote in you hint. (Actually I did it before reading your hint).

spoiler alert

I did two “for” loop to itterate through x dimensions and y dimensions to compute the sub-widths.

And a final double “for” loop to compare each sub-strings and increment a counter value.

I can’t see what I can do to optimize this code, it works in all cases except Hi density cases.

Is anyone has an idea to minimize the for loops ?


#23

Do you really mean sub-strings?
All data are integers. If you have Strings to compare, it is much slower than integer compare.


#24

Same problem here. I’m even using list comprehensions thinking they are more efficient.

I tried with a counter and using sum(x==y) iterated over two lists… still times out.


#25

python? you can pm me your code I’ll try to comprehend it.


#26
Yet another hint if it may help

Recycling the example:

  0___2______5__________10 
  |   |      |          |
  |   |      |          |
 3|___|______|__________|
  |   |      |          |
 5|___|______|__________|

Possible distances:

Horizontal: 2 3 5 5 8 10
            | | |/
Vertical:   2 3 5

=> 4 possible squares.


#27

I made a mistake in my sentence :sweat_smile:

I wanted to say ‘sub-widths’ wich are integers


#28

In some languages, the final double for-loop can be too slow when the list of widths and heights are both very long. There are ways to speed it up. For example, sort it first. Because there can be a lot of duplicate values in the list, you can “skip” the duplicates to shorten the loop.


#29

How can you skip them though? Each duplicate could be another square if it is in the other list…


#30

For example, if you have [1,1,1,1,1,1,1,1,1,1,2] in one list, you can treat it as [1,2] with a count of [10,1]
In another list it could be [1,2,3] with a count of [5,2,1].

The nested loop is reduced to 2x3 comparisons instead of the original 11x8
When list1’s 1 matches list2’s 1, your total count will increment by ??


#31

How to “skip” during nested loop?
Different languages have different syntax and features. The general idea is like that:

pointerX at xList head
pointerY at yList head

loop until pointer reaches end of list
  get x
  get y
  if x==y
    pointerX jumps to x of different value
    pointerY jumps to y of different value
    counter += something_related_to_jumps
  else if x > y
    pointerY++
  else if x < y
    pointerX++

In some languages, the (x==y) compare is slower because it has to fetch data from two different lists. Comparing list[i] with list[j] can be much faster if the values of the same list are stored in memory with known distance to each other. Reducing the number of (x==y) test can enhance performance.
It will also do a significant saving when one list ends much earlier than the other one, we need not continue walking in the other list.


#32

I was finally able to pass all hi desnsity, it was a great puzzle. it allowed me to rethink the solutions in different ways until i was able to found the best solution. thanks


#33

My favorite task so far! Really got me thinking! Recommend everyone to try it.


#34

time out for clojure, but easily pass with same algorithm in python…
So I think the reason is the speed of the language LOL


#36

Finally passed in clojure with your hints, thanks soooo much !!! It is really fun!
And I think it should be put in medium, not easy…


#37

To master a language, one should understand the strength and weakness of the language in use, and knows what design and approach can leverage the strength and counter the weakness.

It is interesting to know how clojure performs in this puzzle.

Also share my result using java. It can pass all tests without any tuning of the algorithm. A direct nested loop works - may be because its List or Collections library is well optimized for this style of operations, or it has a very good cache structure that significantly enhances performance.


#38

Hello,
I have an error at the beginning of my code (line 14) which start by fill the 2 lists x and y with the measurements on each side :

w, h, count_x, count_y = [int(i) for i in input().split()]
j = 0
k = 0
square = 0
for i in input().split():
    x[j] = int(i)
    j += 1
for i in input().split():
    y[k] = int(i)
    k += 1

The console write that x is not defined.
Then, when i add ‘x = []’ it now says me that the list assignment index is out of range although i test it successfully on the Spyder IDE.
Why ?


#39

@nabil.alibou x = [] creates an empty list. You could either:

  • declare x = [None]*count_x to create a list having the proper size;
  • or declare x = [] and use x.append(int(i)) in the loop to add successive inputs at the end of the list;
  • or simply write x = list(map(int, input().split())) or equivalently x = [int(i) for i in input().split()] to create and fill the list at the same time.

#40

I am a beginner, I used a simple way to solve the problem. if you guys have any solutions ,please let me know them.it’s my pleasure. Thanks in advance!! :sweat_smile::sweat_smile:

import java.util.;
import java.io.
;
import java.math.*;

// I seperate w and h into single segments
//example : w = 10,on w we have 2 and 5
// these segments are 2 5 10 5 8 3(arrX)
//like that , with h = 5 , we have 2 5 3 (arrY)
// the result will appear when we compare arrX and arrY
class Solution {

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    int w = in.nextInt();
    int h = in.nextInt();
    int countX = in.nextInt();
    int countY = in.nextInt();
    // initializing two arrays to store value
    int[] arrX = new int[100000]; int nX = 0;
    int[] arrY = new int[100000];int nY = 0;
    
    for (int i = 0; i < countX; i++) {
        int x = in.nextInt();
        arrX[nX++] = x;
    }

    for (int i = 0; i < countY; i++) {
        int y = in.nextInt();
        arrY[nY++] = y;
    }
   // adding w and h into these arrays, they are also segments in these arrays
    arrX[nX++] = w;
    arrY[nY++] = h;
    
    for (int i = countX; i >= 1; i--) {
        for (int j = i - 1; j >= 0; j--) {
            arrX[nX++] = arrX[i] - arrX[j];
        }
    }

    for (int i = countY; i >= 1; i--) {
        for (int j = i - 1; j >= 0; j--) {
            arrY[nY++] = arrY[i] - arrY[j];
        }
    }
    //compare 2 arrays and output the result
  int result = 0 ;
    for(int i = 0 ; i < nX ; i++){
        for(int j = 0 ; j < nY ; j++){
            if(arrX[i] == arrY[j]) result ++ ;
        }
    }
    System.out.println(result);
}

}
;


#41

This was a great puzzle! I started by ‘drawing’ the whole rectangle with the sub-rectangles, passing only the first 3 tests. After thinking about how to do it more efficient, I realized I didn’t need any of that. Like most of the time, I was complicating myself. The lesson learned was: keep things simple!