Interesting feature - added the hidden tag. Thanks.
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 ?
Do you really mean sub-strings?
All data are integers. If you have Strings to compare, it is much slower than integer compare.
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.
python? you can pm me your code I’ll try to comprehend it.
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.
4 Likes
I made a mistake in my sentence 
I wanted to say ‘sub-widths’ wich are integers
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.
2 Likes
How can you skip them though? Each duplicate could be another square if it is in the other list…
2 Likes
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 ??
1 Like
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.
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
1 Like
My favorite task so far! Really got me thinking! Recommend everyone to try it.
2 Likes
time out for clojure, but easily pass with same algorithm in python…
So I think the reason is the speed of the language LOL
1 Like
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…
5 Likes
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.
@nabil.alibou x = [] creates an empty list. You could either:
- declare
x = [None]*count_xto create a list having the proper size; - or declare
x = []and usex.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 equivalentlyx = [int(i) for i in input().split()]to create and fill the list at the same time.
1 Like
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!!
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);
}
}
;
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!
2 Likes
This no longer looks like an easy puzzle. 
Рекурсия наше усё …
4 Likes