PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Aleksandr Abelyan
Tester: Radoslav Dimitrov
Editorialist: Jelmer Firet
DIFFICULTY:
MEDIUM
PREREQUISITES:
Bitwise operations
Setter’s solution: Fast Fourier Transform
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.
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:
// 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
- Calculate
verDifffor the vertical lines - Calculate
horDifffor the original horizontal lines - Consider each horizontal line
y=c- Determine which items in
horDiffwill additionally be set to true (namednewHorDiff) - Determine the number of squares by looping trough
verDiff,horDiffandnewHorDiff
- Determine which items in
This is done in the following snippet:
// 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 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:
// 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:
// 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 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
#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
#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
#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;
}
