July 18, 2018 Problem Of The Week – Beach Umbrellas

The 2018 Facebook Hacker Cup kicked off a few weeks ago, with Round 1 scheduled for the upcoming weekend.
With this in mind, let’s discuss a problem that featured in the 2017 edition of Facebook Hacker Cup – Beach Umbrellas
The summary of the problem statement is that on a line of given length, how many ways exist of placing umbrellas of varying radii in valid points on the line, while ensuring no two umbrellas intersect in area?
Let’s say we generate a combination where all umbrellas are placed. Now, how many possible variations exist, ignoring the ordering of the umbrellas?
If there are X free spaces left and N umbrellas, the number of variations are C(X+N, N)
Therefore after accounting for the order of umbrellas, the number of combinations become N! * C(X+N, N)
So how do we determine X? Well, the free space is determined by the length of the line segment and also the sum of the diameters of all umbrellas.
In other words, X = L – S (where S = sum of 2 * R_i where i iterates from 0 to N-1)
This is when the length of the line segment is L, however and when the umbrella’s areas are bound within this length.
But in actuality, only the centers of the umbrella are bound to this length, as the line only consists of points where the umbrella can be hoisted.
This was because we subtracted the sum of diameters, but the umbrellas on the sides only contribute by 1 radius to the area occupied, and not by 2 radii.
Therefore our available space in actuality, is larger, by the sum of the radii of the umbrellas at both extremities.
There are N^2 possible combinations for the umbrellas in the extremes, and we iterate over them all, while calculating the number of combinations with the remaining umbrellas using the remaining distance.
Ensuring we take modulo during calculations, we can solve the problem.
Below is the implementation of the contestant who ranked #1 in the round –

//start of jonathanirvings' template v3.0.3 (BETA)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;
double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
#ifdef TESTING
#define DEBUG fprintf(stderr,"====TESTING====\n")
#define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define DEBUG
#define VALUE(x)
#define debug(...)
#endif
#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)
inline string IntToString(LL a){
char x[100];
sprintf(x,"%lld",a); string s = x;
return s;
}
inline LL StringToInt(string a){
char x[100]; LL res;
strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
return res;
}
inline string GetString(void){
char x[1000005];
scanf("%s",x); string s = x;
return s;
}
inline string uppercase(string s){
int n = SIZE(s);
REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
return s;
}
inline string lowercase(string s){
int n = SIZE(s);
REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
return s;
}
inline void OPEN (string s) {
freopen ((s + ".in").c_str (), "r", stdin);
freopen ((s + ".out").c_str (), "w", stdout);
}
//end of jonathanirvings' template v3.0.3 (BETA)
#define MAXN 5000000
int T;
int MOD = 1e9 + 7;
int n,m,data[2005];
int fact[MAXN+5];
int invfact[MAXN+5];
map<int,int> dp[5005];
int pow(int a,int b)
{
if (b == 0) return 1;
if (b == 1) return a % MOD;
int temp = pow(a,b/2);
int temp2 = ((LL)temp * temp) % MOD;
if (b % 2 == 0) return temp2;
return ((LL)temp2 * a) % MOD;
}
int C(int a,int b)
{
if (dp[b].count(a)) return dp[b][a];
int ret = invfact[b];
FORN(i,0,b-1)
{
ret = ((LL)ret * (a - i)) % MOD;
}
//debug("%d %d %d\n",a,b,ret);
return dp[b][a] = ret;
}
int main()
{
fact[0] = 1;
FORN(i,1,MAXN)
{
fact[i] = ((LL)fact[i-1] * i) % MOD;
}
invfact[MAXN] = pow(fact[MAXN],MOD-2);
FORD(i,MAXN-1,0)
{
invfact[i] = ((LL)(i + 1) * invfact[i+1]) % MOD;
}
scanf("%d",&T);
REPN(cases,T)
{
printf("Case #%d: ",cases);
scanf("%d %d",&n,&m);
int total = 0;
REP(i,n)
{
scanf("%d",&data[i]);
total += 2 * data[i];
}
if (n == 1)
{
printf("%d\n",m);
continue;
}
int risan = 0;
REP(i,n) REP(j,n) if (i != j)
{
int space = m - 1 + data[i] + data[j];
if (total > space) continue;
int temp = C(space - total + n, n);
temp = ((LL)temp * fact[n - 2]) % MOD;
risan += temp;
if (risan >= MOD) risan -= MOD;
}
printf("%d\n",risan);
}
return 0;
}