I counted 15 possibilities of checking pieces if it is a square or not. All of that I did on piece of paper.
i think I start understanding how I should look for squares.
But build nested loop will be difficult. That mean, that I will need create all possibilities of rectangles at any possible way and then check if it is a square.
Yes you understood it correctly. You really need to check all these 15 rectangles. The most obvious approach is to do it in nested loops.
But no, the nested loops are not the main difficulty. Simple nested loops can handle simple test cases but likely to time out in bigger test cases. You need to optimize it to pass all tests.
But anyway writing a simple nested loop solution as your first step is a worthwhile effort for proof of concept or base for incremental improvement.
And yes I admit this puzzle is relatively harder than others in the same group. No one (as far as I know) regretted having taken this challenge. Wish you enjoy it too.
I use array Xstring[countX] and Ystring[countY]. This is the fastest way to read data, then why I still have error if List is slower anyway.
I use vectors, but was to slow. I have 4 loops and they are checking all possible solutions. Maybe this is wrong way of thinking?
I cant find solution. I see that I need all 4 loops in nested way, but other users are saying that they reduce amount of loops.
My idea gows like this :
ā¦
for ( int k = 0; k <= countX; k++){
xk = xcut[k];
for ( int i = 1 + k; i <= countX+1; i++){x = xcut[i] - xk; //(x - y) ? -1 : answare++; if ( x == y ){ answare++; } } }ā¦
I even try to use :
(x - y) ? -1 : answare++;
Still I canāt brake Hi-density test.
PS. its part of code, but y look this same way like x
Add a counter to your code to do a counting: how many times have you gone through the above subtraction statement in processing one simple test case? (100 or 1000?)
How many different values of x are actually appearing in your test case? (10?)
Get your count result and think about it. Why your CPU was so busy?
1 Like
O my God, I try some options, and I figureout that when I am checking y against X, and if i dont find square y == x, and if y < x, then loop is brake. There is no sense to look for other reactangles. I begin from y be bigger then X, And If I dont find X equal, thenā¦ Yeah.
22281 <- found answares
202<-loop1 25048<-loop2 2542372<-loop3 75703691<-loop4
I notice that there are more then 75 milions itterations to do 
With break function, I save few thousand itterations. But still I canāt pass Hi-density2 
Hi-Dencity2 have 90 371 073. How make this lower?
That line I use to break the loop, But I notice that brake make its job.
{UPDATE}
YEAH! 
After I make Submit I gett 100%. But still in my game, testcase show timeout. I wonder whyā¦
My problem with this program is that I tried to find some sort of pattern I can form in order to construct the program over itā¦
So I started to find a relation between data input ( width, height, no. of vertical and horizontal lines, and their points on x and y)ā¦
First, I formed two arrays, one for points on x-axis ( i.e. 0, 2, 5, 10) another for y-axis (0, 3, 5)ā¦
Second, from previously obtained arrays, created another two contains widths and heights for possible created shapes (rectangles or squares) from partitioningā¦
The length of each array = 1 + 2ā¦+(n-1) where n is the length of axis arrayā¦
Then widths and heights arrays from looping through axis arrays to subtract higher order elements from lower ones (i.e. widthArray = [(10-0), (10-2), (10-5), (5-0), (5-2), (2-0)])ā¦
Last step to sort each array and test widths arrayās elements for match with heights arrayās elements using two loops (where heights array is the inner loop), and whenever match occurs thatās a square!
Fortunately worked like a charm with all iterations 
1 Like
Hi c:
Is there a specific thing that happens in bigger 2 (and validator 3) but not elsewhere? My code works on all other tests and validators but on this one iām one short (get 35 instead of 36 in test 04). Iām suspecting thereās some niche scenario iām not covering with my code but canāt for the life of me figure out what it is.
My method is storing the distance to all lines already existing on the x axis for each new line added to x, resulting in a list where a lines distance to all other lines is stored exactly once. Then count the amount of times the height of the rectangle appers in this list
Then for each new line added to y i check the list of x distances for abs(new_y - old_y) for each already existing y value, and count the occurences
The list for x values starts as [0,w] where each new value is appended after their check against old values, and the same goes for [0,h] and y. i also check if h==w
Hopefully youāll see an issue with this method that i donāt.
Regardless, thank you for the puzzle. Really enjoyed it:)
I lost few hours trying to solve it using dynamic data structures etc., but answer was simple array, just long array. C language.
If you are calculating each y value dynamically and repeatedly, it might be less than desirable. Why need to use abs() in y axis? Are you also using it in x axis? Can it be not used at all?
Why not handle all y values the same way as the x values?
Get the full lists of all x and y and their counts, keep them in a structure (or 2 structures) before looking for match of length.
1 Like
the abs() is just to get the distance without any negatives (since both 0 and h/w are in the lists from the start thereās bound do be at least one negative for each new line since 0-y<0 and y-h < 0). I did the same for the x values, just explained it poorly. Iāll give making separate lists before comparing a try though, thanks for the tip:)
Now I understand why you are using abs(). It adds a little overhead but should be fine for finding out all different lengths of w and h. Store all length info in two maps (or similar structures), one for w and one for h. The map records relationships.
e.g. in the width side, there are 5 sections of line of length 1; 2 sections of length 3, etc
Finally compare the two map structures to find out the count of w == h
Thank you for this puzzle, I really enjoyed it (I enjoyed it so much that I decided to post for my first comment on cg). I was quickly blocked by the high density validators. I understood that my program was repeating calculations already done. Using two maps has you mentioned and compare them was realy usefull solution for me. Thank again 
2 Likes
I canāt pass āHi density 2ā donāt know what wrong with my code , you said store the result ? how ?
some hint please ?
update !
Itās ok I did it but so many line of code, I avoided nested for loop by susing array_count_value and others helpfull function so happy
Last test not passing and i donāt know whyā¦
My code look for each combination if the hight and the width of the square is good, but it looking it 4 times more, so i divided it by 4, every test were good but not the last, someone can help ?
Everything can be explained. Try to find out the root cause of the ā4 times moreā problem and fix it. The ādivide by 4ā approach is a dirty patch that conceals a bug.
1 Like
i fix the divide by 4 by checking if - when i want to have the length of the hight or the width - the first number is below than the second, but i still have 15 square and the last test want 36 squares
I am really stuck . I can`t for the life in me make this algorithm more optimal . this is my code :
string[] inputs;
inputs = Console.ReadLine().Split(' ');
int w = int.Parse(inputs[0]);
int h = int.Parse(inputs[1]);
int countX = int.Parse(inputs[2]);
int countY = int.Parse(inputs[3]);
List<int> listX = new List<int>();
List<int> listY = new List<int>();
int[] inputsX = new int[countX + 1];
int[] inputsY = new int[countY + 1];
inputs = Console.ReadLine().Split(' ');
for (int i = 0; i < countX; i++)
{
inputsX[i] = int.Parse(inputs[i]);
}
inputs = Console.ReadLine().Split(' ');
for (int i = 0; i < countY; i++)
{
inputsY[i] = int.Parse(inputs[i]);
}
inputsX[inputsX.Length - 1] = w;
inputsY[inputsY.Length - 1] = h;
for (int i = inputsX.Length - 1; i >= 0; i--)
{
int x = i;
listX.Add(inputsX[i]);
while (x > 0)
{
listX.Add(inputsX[i] - inputsX[x - 1]);
x--; ;
}
}
for (int i = inputsY.Length - 1; i >= 0; i--)
{
int x = i;
listY.Add(inputsY[i]);
while (x > 0)
{
listY.Add(inputsY[i] - inputsY[x - 1]);
x--; ;
}
}
int contor = 0;
var grouped = listX.GroupBy(x=> x);
foreach( var i in grouped){
contor = contor + listY.Count(c => c == i.Key) * i.Count();
}
Console.WriteLine(contor);