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.
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