ADDSQURE - Editorial

best video solution of ADDING SQUARE

I believe that your second point is wrong unless of course, I made a mistake in understanding your formulation.

Consider these y’s
y={6,10}
Consider these sides from x’s that were not matched before
s={2,3}

(a6+a10).(a2 + a-2 + a3 + a-3)
=a3+a4+a7+2a8+a9+a12+a13

Here according to your formulation y=8 will generate 2 different squares, as the coefficient of a8 is 2.
But it generates only 1extra square, corresponding to side=2

There could be cases wherein,
yi+sj == yl+sk, here 2 different y’s end up contributing to the same
exponent in the final result, which could result in cases like above.

1 Like

The editorial is great but I am still not getting how does doing “revHorizontal>>(height - c)” give the distances between the new line and the lines below it (even after watching the editorial video). Can anyone put it in easier words for me?

https://www.codechef.com/viewsolution/38830055
this is a link to my C++ approach to the problem, and it is partially correct.
How do I make it more efficient?

Someone else asked for an example how that shifting works, maybe that helps.

Essentially the horizontal >> c and revHorizontal >> (height-c) achieve the moving the indicated bit to the first (i.e. rightmost) bit.

1 Like

See the “making it faster” section of the editorial

So do I only need to fasten my solution or the approach is wrong?

Yes I got it now, Thanks for a such a lovely explanation!!

The approach is like I described in my editorial, it only needs to be sped up using bitsets (or FFT but that’s much harder).

Good explanation and a good problem … Learnt many things … thanks for the so good editorial…

I am getting WA for last two parts, can someone please check the code? Thanks:)

w,h,n,m=map(int, input().split())
if(1==1 ):
    ai=list(map(int,input().split()))
    bi=list(map(int,input().split()))
    xran=set()
    yran=set()
    for i in ai:
        for j in ai:
            if(i!=j):
                xran.add(abs(i-j))
    for i in bi:
        for j in bi:
            if i!=j:
                yran.add(abs(i-j))
    kran=yran.intersection(xran)
    yran=kran
    maxans=len(xran)
    originall=len(yran)
    for p in range(0,h+1):
        if(originall==maxans):
            break
        else:
            yran1=yran
            flag=0
            for i in bi:
                diff=p-i
                
                if diff==0:
                    flag=1
                else:
                    yran1.add(abs(diff))
            if flag==1:continue
            else:
                newl=len(yran1.intersection(xran))
                if(newl>originall):
                    originall=newl
                if(originall==maxans):
                    break
    print(originall)

Check the following performance evaluation program that compares the execution time of bounded search to the execution time of unbounded search for 100 randomly generated arrays.

https://ideone.com/lUtJUB

Is “revHorizontal >> (height-c)” equivalent to “horizontal<<c” ?

A great problem . Lots of thinking is required.

revHorizontal stores the height =(H-hi);
when u right shift it by (H-c) it gives
{(H-hi)-(H-c)} i.e (c-hi) which is required height below line y=c.I hope it helps.

2 Likes

Learn each and every concept of bitset and this question in detail and in dept in easy language

Best Video Editorial

No, they are not the same.

In an earlier post I gave an example of what the horizontal >> c and revHorizontal >> (height-c) do.

1 Like

Yes, it does. Thanks!!

1 Like

Hello Sir,

I am trying brute force solution for 50 points but it’s failing for 2 test cases.
Please help me to debug this.

Following Code snippet :

#include <bits/stdc++.h>
using namespace std;

int w, h, n, m;
int arr[200009];
int brr[200009];

void solve() {
	set<int>ver, hor;
	for (int i = 0; i < n; i++) {
		for (int j = i+1; j < n; j++) {
			ver.insert(abs(arr[i]-arr[j]));
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = i+1; j < m; j++) {
			hor.insert(abs(brr[i]-brr[j]));
		}
	}
	for (int c = 0; c <= h; c++) {
		for (int i = 0; i < m; i++) {
			hor.insert(abs(c-brr[i]));
		}
	}
	long long cnt = 0;
	for (auto u : ver) {
		for (auto v : hor) {
			if (u == v) cnt++;
		}
	}
	cout << cnt << endl;
}

int main() {
	cin >> w >> h >> n >> m;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 0; i < m; i++) cin >> brr[i];
	solve();
	return 0;
}
1 Like