# ADDSQURE - Editorial

**URL:** <https://discuss.codechef.com/t/addsqure-editorial/79023>\
**Category:** editorial\
**Tags:** bitset, editorial, medium, oct20\
**Created:** [October 5, 2020, 3:08pm UTC](https://discuss.codechef.com/t/addsqure-editorial/79023 "2020-10-05T15:08:17Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![spaanse](https://discuss.codechef.com/user_avatar/discuss.codechef.com/spaanse/32/214887_2.png) [@spaanse](https://discuss.codechef.com/u/spaanse)\
**Post date:** [October 5, 2020, 3:08pm UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/1 "2020-10-05T15:08:17Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/ADDSQURE)  
[Div-2 Contest](https://www.codechef.com/OCT20B/problems/ADSQURE)  
[Div-1 Contest](https://www.codechef.com/OCT20A/problems/ADSQURE)

_Author:_ [Aleksandr Abelyan](https://www.codechef.com/users/abelyan)  
_Tester:_ [Radoslav Dimitrov](https://www.codechef.com/users/radoslav192)  
_Editorialist:_ [Jelmer Firet](https://www.codechef.com/users/spaanse)

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

[Bitwise operations](https://en.wikipedia.org/wiki/Bitwise_operation)  
Setter’s solution: [Fast Fourier Transform](https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm)

# PROBLEM:

You are given N vertical lines and M horizontal lines. You may add one more horizontal line. Give the maximum number of squares you can form with different areas?

# QUICK EXPLANATION:

Use bitsets to speed up the following \mathcal{O}(n^2) solution. Determine which distances between pairs of horizontal and vertical lines already exist. For each possible new line (temporarily) update the distances between horizontal pairs. Then count how many k are both the distance between two horizontal lines and the distance between two vertical lines.

# EXPLANATION:

Before I start my explanation, I want to mention that I start explaining the idea behind the algorithm. The code given in this part is used to support the idea, but would give a TLE because it is too slow. In the section after that I will discuss how the code can be sped up using bitsets.

## Idea of the algorithm

Note that a square is a rectangle with equal side lengths. Furthermore the area of a square is entirely defined by the side length. So the problem could have been rephrased as finding the maximum possible number of squares with different side lengths. A square with side length k is formed by the lines only if there are a pair of vertical lines k units apart; and a pair of horizontal lines k units apart.

 ![addsqure1](https://s3.amazonaws.com/discourseproduction/original/3X/f/3/f3ddc381400a9a58e7cf3d01fcded72d2c570b7a.png)

Because we are not allowed to add vertical lines, all possible square sizes are already determined by the given vertical lines. Therefore it will be handy to figure out for each k if there are two vertical lines that are k units apart. We will also determine for which k there are two horizontal lines k units apart. We can find these distances between pairs of lines with the following bit of code:

```c++
// vertical[i] is true if there is a line x=i, reason for boolean array comes later
vector<bool> vertical;
//verDiff[k] is going to be true if there is a pair of vertical lines k apart
vector<bool> verDiff(width+1);
for (int i = 0; i <= width; i++) if (vertical[i]) { // lines x=i
	for (int j = i; j <= width; j++) if (vertical[j]) { // lines x=j
		verDiff[j-i] = true;
	}
}
// do the same for horizontal lines

```

Now we have two boolean arrays `verDiff` and `horDiff` that hold whether the vertical or horizontal lines would allow a square of size k to exist. If we want to count the number of different sized squares we loop trough both arrays and count how often `verDiff[k] = horDiff[k] = true`. But we can still add a line to increase the number of squares.

A quick modification that allows us to calculate the answer is to consider every possible line y=c, temporarily add it and calculate the number of squares we end up with. However this would become way too slow, because now we have three nested loops (over x\_1, x\_2 and c). To get back to quadratic complexity we notice that a lot of things don’t need to be recalculated. For example `verDiff` doesn’t depend on the newly added line. Furthermore at most M of the values in `horDiff` change when you add the new line, so we can just determine which these are.

So the algorithm we have consists of the following steps

1. Calculate `verDiff` for the vertical lines
2. Calculate `horDiff` for the original horizontal lines
3. Consider each horizontal line `y=c`
  1. Determine which items in `horDiff` will additionally be set to true (named `newHorDiff`)
  2. Determine the number of squares by looping trough `verDiff`, `horDiff` and `newHorDiff`

This is done in the following snippet:

```c++
// calculate verDiff and horDiff
int maxSquare = 0;
for (int c = 0; c <= height; c++) { // consider y=c
	vector<bool> newHorDiff; // the distances from the new line to the others
	for (int i = 0; i <= height; i++) if (horizontal[i]) { // lines y=i
		newHorDiff[abs(i-c)] = true;
	}
	int numSquare = 0;
	for (int i = 0; i <= height; i++) {
		if (verDiff[i] and (horDiff[i] or newHorDiff[i]) ) {
			numSquare++;
		}
	}
	maxSquare = max(maxSquare, numSquare);
}
// print maxSquare-1 to ignore the 0-area square

```

## Making it faster

Now that we have got the idea of the algorithm, there is still an issue: it’s too slow. In my explanatory snippets there are nested for loops, each of which can be executed up to 10^5 times. This means the algorithm is \mathcal{O}(n^2), where we take n the largest of W,H,N,M. Using the estimate of 10^9 operations per second, it seems that this algorithm is not feasible. However, we can do more in a single operation. Let’s introduce bitwise operations.

Bitwise operations are like the familiar boolean operations, but they work on 64 bits at a time (maybe 32 based on OS and hardware). There are also two additional bitwise operations: left-shift and right-shift. You can read up on these on [Wikipedia](https://en.wikipedia.org/wiki/Bitwise_operation) if you are not familiar with them.

To make use of bitwise operations we will store the boolean arrays in a `bitset` instead. `bitset` is a datastructure from the C++ standard that allow us to use bitwise operations on more than 64 bits. Other programming languages might have similar structures predefined. Now we just need to transform the snippets to use bitsets.

For the first snippet we are going to replace the inner for loop with bitwise operations. First we can replace the assignment of `true` by an or operation with the condition of `if(vertical[x2])`, so we will get `verDiff[x2-x1] |= vertical[x2]`. Next we will increase both indices to get `verDiff[x2] |= vertical[x2+x1]`. And finally turn the for-loop into a bitwise operations using, where you replace the `+x1` in the index with a left-shift. We then turned the snippet into the following code:

```c++
// vertical[i] is true if there is a line x=i, reason for boolean array comes later
bitset<mx> vertical;
//verDiff[k] is going to be true if there is a pair of vertical lines k apart
bitset<mx> verDiff;
for (int i = 0; i <= width; i++) if (vertical[i]) {
	verDiff |= (vertical >> i)
}
// repeat the same for the horizontal lines

```

For the second segment I need to introduce a new bitset. This will be `revHorizontal`, which is the reverse of `horizontal`. So `revHorizontal[i]` is set if there is a horizontal line y=\text{height}-i. We need this new bitset because it also allows us to update distances to lines below the new line quickly. `horizontal` and `revHorizontal` will be shifted by y and \text{height}-y respectively, so that after shifting `horizontal[k]` is set if there is a line at y=c+k, and similarly `revHorizontal[k]` will be set if there is a line at y=c-k.  
Next we need to calculate for how many squares we can form. We can just translate the boolean operations of the snippet into bitwise operations to get a bitset where bit k is set if there is a square with side-length k. The C++ `bitset` contains a function `count` that counts how many bits are set, so the number of squares. The second snippet transforms into the following snippet:

```c++
// calculate verDiff and horDiff
int maxSquare = 0;
for (int c = 0; c <= height; c++) {
	bitset<mx> newHorDiff;
	newHorDiff |= (horizontal >> c);
	newHorDiff |= (revHorizontal >> (height-c));
	int numSquare = (verDiff & (horDiff | newHorDiff)).count();
	maxSquare = max(maxSquare, numSquare);
}
// print maxSquare-1 to ignore the 0-area square.

```

Now that all inner for loops have been replaced by bitwise operations the algorithm is fast enough to pass the time limit. Intuitively by using bitsets we turned an algorithm that used \mathcal{O}(n^2) operations into an algorithm that uses \mathcal{O}(\frac{n^2}{64}) operations. (Though note that because of the definition of big O the algorithm using bitsets is still \mathcal{O}(n^2))

You can look at my full code below which has a lot more comments.

# ALTERNATE SOLUTIONS:

The setter (Aleksandr) used Fast Fourier Transfrom (FFT) to determine the already existing distances between pairs of horizontal or vertical lines. This is a method that uses some complex (literally) mathematics to determine for multiply frequencies how strong an input array “resonates” with that frequency. In terms of this problem, that would happen if there is a pair of lines that frequency apart. [3blue1brown](https://www.youtube.com/watch?v=spUNpyF58BY) has a good video that explains what a Fourier Transform is. In practice I have not yet encountered a problem for which a FFT is required for the solution. If any of you do, please tell me about it in the comments.

The tester (Radoslav) used the same approach as me. However he constructed the `revHorizontal` on the fly instead of beforehand.

# SOLUTIONS:

> **Setter's Solution**
>
> ```c++
> #include <bits/stdc++.h>
> using namespace std;
> 
> typedef long long ll;
> typedef unsigned long long ull;
> typedef long double ld;
> 
> //#pragma GCC target("avx2")
> //#pragma GCC optimization("unroll-loops")
> //#pragma GCC optimize("O2")
> //#pragma GCC optimize("O3")
> 
> #define FOR(i,a) for (int i=0;i<(a);++i)
> #define FORD(i,a) for (int i=(a)-1;i>=0;i--)
> #define FORT(i,a,b) for (int i=(a);i<=(b);++i)
> #define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
> #define trav(i,v) for (auto i : v)
> #define all(v) v.begin(),v.end()
> #define ad push_back
> #define fr first
> #define sc second
> #define mpr(a,b) make_pair(a,b)
> #define pir pair<int,int>
> #define make_unique(v) v.erase(unique(all(v)),v.end())
> #define fastio ios_base::sync_with_stdio(false); cin.tie(0); //cout.tie(0);
> #define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
> #define y1 EsiHancagorcRepa
> const int N=1e5+4; 
> const ll MOD=1e9+7;
> const ll MX=1e16;
> 
> using cd = complex<ld>;
> using vcd = vector<complex<ld> >;
> 
> const ld PI = acos((ld)-1);
> 
> int rev[3 * N];
> cd roots[3 * N];
> 
> void fft(vcd& a)
> {
> int n = a.size();
> for (int i = 0; i < n; ++i)
> if (i < rev[i])
> swap(a[i], a[rev[i]]);
> for (int len = 1, step = n / 2; len < n; len <<= 1, step >>= 1)
> for (int st = 0; st < n; st += len + len)
> for (int i = 0, root = 0; i < len; ++i, root += step)
> {
> cd u = a[st + i], v = roots[root] * a[st + len + i];
> a[st + i] = u + v;
> a[st + i + len] = u - v;
> }
> }
> void inv(vcd& a)
> {
> fft(a);
> reverse(a.begin() + 1, a.end());
> for (cd& x : a)
> x /= a.size();
> }
> void conv(vcd& a, vcd& b)
> {
> int n = 1, h = 0;
> while (n < a.size() + b.size())
> n *= 2, ++h;
> while (a.size() < n) a.push_back(0);
> while (b.size() < n) b.push_back(0);
> rev[0] = 0;
> for (int i = 1, high = -1; i < n; ++i) {
> high += !(i & (i - 1));
> rev[i] = rev[i ^ (1 << high)] | (1 << (h - high - 1));
> }
> ld sector = 2. * PI / n;
> for (int i = 0; i < n; ++i) {
> roots[i] = cd(cos(sector * i), sin(sector * i));
> }
> fft(a); fft(b);
> for (int i = 0; i < n; ++i)
> a[i] *= b[i];
> inv(a);
> }
> bitset<N> tv,tn,unused;
> int x[N],y[N];
> 
> int main(){
> srng;
> fastio;
> int w,h,n,m;
> cin>>w>>h>>n>>m;
> vcd xx(w+1,0),yy(h+1,0),xxr(w+1,0),yyr(h+1,0);
> FOR(i,n){
> cin>>x[i];
> 		
> xx[x[i]]=1;
> xxr[w-x[i]]=1;
> 		
> }
> 
> conv(xx,xxr);
> 	
> FORT(i,w+1,xx.size()-1){
> 
> if ((int)(xx[i].real()+0.5)){
> 			
> unused[i-w]=1;
> }
> }
> FOR(i,m){
> cin>>y[i];
> tv[y[i]]=1;
> yy[y[i]]=1;
> yyr[h-y[i]]=1;
> }
> conv(yy,yyr);
> int ans=0;
> FORT(i,h+1,yy.size()-1){ 
> if ((int)(yy[i].real()+0.5)){
> if (unused[i-h])ans++;
> unused[i-h]=0;
> }
> }
> int pat=0;
> FOR(i,h+1){
> 		
> if (!tv[0]){
> pat=max(pat,int((unused&(tv|tn)).count()));
> 			
> tv=tv>>1;
> tn=tn<<1;
> }
> else{
> tv=tv>>1;
> tn=tn<<1;
> tn[1]=1;
> }
> }
> cout<<ans+pat<<endl;
> return 0;
> }
> 
> ```

> **Tester's Solution**
>
> ```c++
> #include <bits/stdc++.h>
> 
> using namespace std;
> template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
> const int MAXN = (int)1e5 + 42;
> 
> int w, h, n, m;
> int a[MAXN], b[MAXN];
> bitset<MAXN> hor, ver, emp;
> 
> void read() {
> cin >> w >> h >> n >> m;
> for(int i = 0; i < n; i++) {
> cin >> a[i];
> hor[a[i]] = 1;
> }
> 
> for(int i = 0; i < m; i++) {
> cin >> b[i];
> ver[b[i]] = 1;
> }
> }
> 
> void solve() {
> bitset<MAXN> dp1 = emp, dp2 = emp;
> 	
> // Can be replaced with FFT.
> for(int i = 0; i < n; i++) {
> dp1 |= hor >> a[i]; 
> }
> 	
> // Can be replaced with FFT.
> for(int i = 0; i < m; i++) {
> dp2 |= ver >> b[i]; 
> }
> 	
> bitset<MAXN> available = dp1 & dp2;
> bitset<MAXN> pref, suff = ver; 
> pref[0] = ver[0];
> 
> int ans = available.count();
> for(int i = 0; i <= h; i++) {
> if(!ver[i]) {
> chkmax(ans, (available | ((pref | suff) & dp1)).count());
> }
> 
> pref <<= 1;
> suff >>= 1;
> pref[0] = ver[i + 1];
> }
> 
> // -1 cause len=0 isn't a square
> cout << ans - 1 << endl;
> }
> 
> int main() {
> ios_base::sync_with_stdio(false);
> cin.tie(nullptr);
> 
> read();
> solve();
> return 0;
> }
> 
> ```

> **Editorialist's Solution**
>
> ```c++
> #include <iostream>
> #include <vector>
> #include <utility>
> #include <tuple>
> #include <algorithm>
> #include <bitset>
> using namespace std;
> 
> typedef vector<int> vi;
> typedef vector<vi> vvi;
> 
> const int mx = 100001;
> 
> int main() {
> int width, height, numVer, numHor;
> cin >> width >> height >> numVer >> numHor;
> // bitsets for vertical and horizontal lines
> // vertical[i] is set if there is a line y=i
> // horizontal[i] is set if there is a line x=i
> // revHorizontal[i] is set if there is a line x=height-i
> bitset<mx> vertical, horizontal, revHorizontal;
> 
> // read in x-coordinates of vertical lines and store in bitset
> for (int i = 0; i < numVer; i++) {
> int verLine;
> cin >> verLine;
> vertical.set(verLine);
> }
> // read in y-coordinates of horizontal lines and store in bitset
> for (int i = 0; i < numHor; i++) {
> int horLine;
> cin >> horLine;
> horizontal.set(horLine);
> revHorizontal.set(height-horLine);
> }
> bitset<mx> verDiff, horDiff;
> 
> // iterate over each of the vertical lines (x=i)
> for (int i = 0; i<= width; i++) if (vertical[i]) {
> // and for each line (at x=j) to the right of it set bit j-i of verDiff
> verDiff |= (vertical >> i);
> }
> // iterate over each of the horizontal lines (y=i)
> for (int i = 0; i<= width; i++) if (horizontal[i]) {
> // and for each line (at y=j) above it set bit j-i of horDiff
> horDiff |= (horizontal >> i);
> }
> 
> int maxSquare = 0;
> // loop over all possible y-coordinates of the new line
> for (int c = 0; c <= height; c++) {
> // newHorDiff will store the newly formed distances, 
> bitset<mx> newHorDiff;
> // update the distances between the new line and those above it
> newHorDiff |= (horizontal >> c);
> // update the distances between the new line and those below it
> newHorDiff |= (revHorizontal >> (height-c));
> // calculate how many squares can be created
> // there is a square of a particular side-length if that side-length
> // is the distance between two horizontal lines, 
> // and the distance between two vertical lines
> int numSquare = (verDiff & (horDiff | newHorDiff)).count();
> maxSquare = max(maxSquare, numSquare);
> }
> 
> // -1 to ignore a 0-area square.
> cout << maxSquare-1 << endl;
> 
> return 0;
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![sksama](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sksama](https://discuss.codechef.com/u/sksama)\
**Post date:** [October 12, 2020, 9:34am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/2 "2020-10-12T09:34:42Z")

</div>

Great contest

If any one wants explanation on how Bitset was used to solve this question in Hindi- [LINK](https://www.youtube.com/watch?v=p4zN1FHruTg)

[![](https://img.youtube.com/vi/p4zN1FHruTg/maxresdefault.jpg "Adding Squares : CodeChef October Long Challenge 2020 | Explanation in Hindi | BitSet | sKSama") ](https://www.youtube.com/watch?v=p4zN1FHruTg)

---

<div class="post-metadata">

**Author:** ![ameybhavsar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ameybhavsar/32/26566_2.png) [@ameybhavsar](https://discuss.codechef.com/u/ameybhavsar)\
**Post date:** [October 12, 2020, 9:44am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/3 "2020-10-12T09:44:58Z")

</div>

NIce problem!

---

<div class="post-metadata">

**Author:** ![rdxvijay](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rdxvijay/32/21383_2.png) [@rdxvijay](https://discuss.codechef.com/u/rdxvijay)\
**Post date:** [October 12, 2020, 9:54am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/4 "2020-10-12T09:54:03Z")

</div>

This was a great problems.  
After trying for 2 days i was able to solve it.

---

<div class="post-metadata">

**Author:** ![sarthak\_jain29](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sarthak_jain29/32/65440_2.png) [@sarthak\_jain29](https://discuss.codechef.com/u/sarthak_jain29)\
**Post date:** [October 12, 2020, 10:18am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/5 "2020-10-12T10:18:17Z")

</div>

i solved this for 50 marks (3sec time) still i got TLE for 2 subtasks

#include  
#include\<bits/stdc++.h\>  
using namespace std;  
#include  
#define ll long long

int main(void) {

ios\_base::sync\_with\_stdio(false);  
cin.tie(NULL);

ll w,h,n,m,temp,final\_max=0;  
cin\>\>w\>\>h\>\>n\>\>m;  
vectorall\_x,all\_y;

for(ll i=0;i\<n;i++)  
{  
cin\>\>temp;  
all\_x.push\_back(temp);  
}

for(ll i=0;i\<m;i++)  
{  
cin\>\>temp;  
all\_y.push\_back(temp);  
}

vectornbi;  
for(ll j=0;j\<=h;j++)  
{  
bool flag=false;  
for(ll i=0;i\<m;i++)  
{  
if(all\_y[i]==j)  
{  
flag=true;  
break;  
}  
}  
if(flag!=true)  
{  
nbi.push\_back(j);  
}  
}

sets,s2,s3;  
for(ll i=0;i\<n;i++)  
{  
for(ll j=i+1;j\<n;j++)  
{  
s.insert(abs(all\_x[i]-all\_x[j]));  
}  
}

for(ll i=0;i\<m;i++)  
{  
for(ll j=i+1;j\<m;j++)  
{  
s3.insert(abs(all\_y[i]-all\_y[j]));  
}  
}  
// ---------------------------------------------------------------COMPULSARY-----------------------------------------------------------------------

ll count=0,max1=0,pos=0;

ll f=nbi.size();

for(ll j=0;j\<f;j++)  
{  
count=0;  
sets1,s4;

for(ll i=0;i\<m;i++)  
{  
s1=s;  
s4=s3;  
s1.insert(abs(all\_y[i]-nbi[j]));  
ll k1=s1.size(),m1=s.size();  
if(k1==m1)  
{  
s4.insert(abs(all\_y[i]-nbi[j]));  
ll k2=s3.size(),m2=s4.size();  
if(k2\<m2)  
{  
count++;  
}  
}  
}  
if(count\>=max1)  
{  
max1=count;  
pos=nbi[j];  
}  
}

// \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_  
ll max2=0;

set :: iterator itr;

```
for (itr = s.begin(); itr != s.end(); ++itr) 
{ 
   set<ll>tv;
   tv=s3;
   tv.insert(*itr);
   if(tv.size()==s3.size())
   {
   	max2++;
   }

```

}

cout\<\<max1+max2\<\<endl;

}

can you check

---

<div class="post-metadata">

**Author:** ![spaanse](https://discuss.codechef.com/user_avatar/discuss.codechef.com/spaanse/32/214887_2.png) [@spaanse](https://discuss.codechef.com/u/spaanse)\
**Post date:** [October 12, 2020, 10:23am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/6 "2020-10-12T10:23:51Z")

</div>

Can you [format your code](https://discuss.codechef.com/t/tutorial-formatting-in-codechef-discuss/72834) or link your submission. I suggest you look into the “making it faster” section of my editorial

---

<div class="post-metadata">

**Author:** ![anon58388457](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon58388457](https://discuss.codechef.com/u/anon58388457)\
**Post date:** [October 12, 2020, 10:31am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/7 "2020-10-12T10:31:04Z")

</div>

I don’t understand How every unique difference is calculated in O(n). For example 8,32,1777,2345566.  
Here there will be 3+2+1=6 unique differences right? i.e n\*(n-1)/2  
How can it be calculated in O(n) ??

---

<div class="post-metadata">

**Author:** ![user109](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@user109](https://discuss.codechef.com/u/user109)\
**Post date:** [October 12, 2020, 10:32am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/8 "2020-10-12T10:32:46Z")

</div>

Thanks for editorial !!

---

<div class="post-metadata">

**Author:** ![spaanse](https://discuss.codechef.com/user_avatar/discuss.codechef.com/spaanse/32/214887_2.png) [@spaanse](https://discuss.codechef.com/u/spaanse)\
**Post date:** [October 12, 2020, 10:42am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/9 "2020-10-12T10:42:39Z")

</div>

It’s not done in \mathcal{O}(n), but in \mathcal{O}(n^2). It is only fast enough because it is sped up using bitwise operations.

---

<div class="post-metadata">

**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\
**Post date:** [October 12, 2020, 10:42am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/10 "2020-10-12T10:42:51Z")

</div>

Read the editorial

---

<div class="post-metadata">

**Author:** ![paliya\_64](https://discuss.codechef.com/user_avatar/discuss.codechef.com/paliya_64/32/104114_2.png) [@paliya\_64](https://discuss.codechef.com/u/paliya_64)\
**Post date:** [October 12, 2020, 10:43am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/11 "2020-10-12T10:43:13Z")

</div>

put your code in between 2 signs ``` and format it or either paste code link, its not readable,

---

<div class="post-metadata">

**Author:** ![rupinderg00](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rupinderg00/32/24644_2.png) [@rupinderg00](https://discuss.codechef.com/u/rupinderg00)\
**Post date:** [October 12, 2020, 10:44am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/12 "2020-10-12T10:44:27Z")

</div>

Nice explanation!!

---

<div class="post-metadata">

**Author:** ![anon58388457](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon58388457](https://discuss.codechef.com/u/anon58388457)\
**Post date:** [October 12, 2020, 10:44am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/13 "2020-10-12T10:44:49Z")

</div>

My bad 🙇‍♂️

---

<div class="post-metadata">

**Author:** ![tamo11](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tamo11/32/90787_2.png) [@tamo11](https://discuss.codechef.com/u/tamo11)\
**Post date:** [October 12, 2020, 11:12am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/14 "2020-10-12T11:12:42Z")

</div>

I wrote a simple modified brute force logic O(n^2) with no bitsets and FFT, and yet my code turned out to be the fastest AC submission in the contest (Java DIV 1)  
Were the test cases a bit _weak_?

---

<div class="post-metadata">

**Author:** ![spaanse](https://discuss.codechef.com/user_avatar/discuss.codechef.com/spaanse/32/214887_2.png) [@spaanse](https://discuss.codechef.com/u/spaanse)\
**Post date:** [October 12, 2020, 11:29am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/15 "2020-10-12T11:29:40Z")

</div>

There were only three 100pt JAVA submissions in div1, so being the fastest of those is not really surprising. I don’t know if testcases could have been constructed to prevent really optimized algorithms that didn’t use bitsets, because they run in almost the same time.

---

<div class="post-metadata">

**Author:** ![tamo11](https://discuss.codechef.com/user_avatar/discuss.codechef.com/tamo11/32/90787_2.png) [@tamo11](https://discuss.codechef.com/u/tamo11)\
**Post date:** [October 12, 2020, 11:35am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/16 "2020-10-12T11:35:34Z")

</div>

ok thanks!  
i had no idea that there were only 3 submissions btw

---

<div class="post-metadata">

**Author:** ![dinesh\_b\_s](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dinesh_b_s/32/28176_2.png) [@dinesh\_b\_s](https://discuss.codechef.com/u/dinesh_b_s)\
**Post date:** [October 12, 2020, 11:47am UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/17 "2020-10-12T11:47:04Z")

</div>

Does bitset count() function have a time complexity of O(N) where N is the length of the bitset?

---

<div class="post-metadata">

**Author:** ![rath772k](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rath772k/32/269267_2.png) [@rath772k](https://discuss.codechef.com/u/rath772k)\
**Post date:** [October 12, 2020, 12:01pm UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/18 "2020-10-12T12:01:09Z")

</div>

Asymptotic complexity is O(N) but you’d get a 32 times or 64 times speed up depending on the machine you are working on.

---

<div class="post-metadata">

**Author:** ![satyam\_patidar](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@satyam\_patidar](https://discuss.codechef.com/u/satyam_patidar)\
**Post date:** [October 12, 2020, 12:02pm UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/19 "2020-10-12T12:02:55Z")

</div>

thanks ,  
i thought i should make it to O(n) only which is not possible,  
i don’t know using bitwise O(n2) algo can also be possible

---

<div class="post-metadata">

**Author:** ![dinesh\_b\_s](https://discuss.codechef.com/user_avatar/discuss.codechef.com/dinesh_b_s/32/28176_2.png) [@dinesh\_b\_s](https://discuss.codechef.com/u/dinesh_b_s)\
**Post date:** [October 12, 2020, 12:12pm UTC](https://discuss.codechef.com/t/addsqure-editorial/79023/20 "2020-10-12T12:12:29Z")

</div>

Even though bitset count function can be 64 times faster than O(N), the total number of operations per second in the worst case can be ((2 x 10^5)^2)/64 **≈** 1.6 x 10^8. As the time limit is 3 sec, (1.6 x 10^8)/3 **≈** 5.3 x 10^7 are the total number of operations per second for this logic. Is this a very tight bound for the compiler to accept? It seems so to me. Correct me if I’m wrong.

[Next page](https://discuss.codechef.com/t/addsqure-editorial/79023.md?page=2)