PYMID - Editorial

PROBLEM LINK:

Contest

Setter: a0n0k0i0t
Tester: a0n0k0i0t
Editorialist: a0n0k0i0t

DIFFICULTY:

Medium

PREREQUISITES:

Binary Search

QUICK EXPLANATION:

  • Formula for number of sockets required for height x is Soc(x) = x*(x+1)*(x+2)/6
  • Formula for number of sticks required for height y is Sti(y) = (y-1)*(y)*(y+1)
  • Given n , m maximize value of x and y such that:
    n \geq x*(x+1)*(x+2)/6
    m \geq (y-1)*y*(y+1)
  • Use binary search to get max value of x and y satisfying above conditions.
  • Let maximum values of such x be h1 and maximum value of such y be h2
  • h=min(h1,h2)

Explanation:

Observation 1:

The sequence of sockets in each level is
1,3,6,10...
The sequence of sticks in each level is
0,6,18,36,60...

In both the seqences the common difference forms an A.P. having sequence
2,3,4...
6,12,18,24...
Sum of sockets and sticks required for a height x and y respectively can be found using sequence and series mathematics .
n \geq x*(x+1)*(x+2)/6 \hspace{1cm} -(1)
m \geq (y-1)*(y)*(y+1) \hspace{1.2cm} -(2)

Obsevation 2:

1\leq n,m\leq 10^{16}
From equation (1) and (2) its not hard to see that
0 \leq x,y \leq 10^6 \hspace{1cm} (loose upper bound)

Now all that remains is to find maximum values of x and y such that it satisfies above equation.Let that be h1 and h2 respectively.
Maximum height of pyramid h possible h=min(h1,h2)

So, a possible solution is that we can linearly check on values of x,y and stop at the respective maximum.
But this approach has a time complexity of O(T*n^{1/3}) and will result in tle.
To optimise the solution use binary search with l=0 and r=10^6 .

Time complexity : O(T*log(n^{1/3}))

Alternative approach:

Using Observation 2 that
1\leq n,m\leq 10^{16}
We can construct and array beforehand to store all values of sockets and sticks required for height i
Let array A has values for number of sockets required for height 1 to 10^6
A_i = i*(i+1)*(i+2)/6
Let array B has values for number of sticks required for height 1 to 10^6
B_i = (y-1)*(y)*(y+1)
To answer each test case:
Simply find the lower bound of n and m from array A and B respectively and find the minimum.

Time complexity: O(T*(log(n^{1/3}))

SOLUTION

Appraoch 1:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
	ll T;
	cin>>T;
	for(ll _=0;_<T;_++){
	    ll n,m;
	    cin>>n>>m;
	    
	    ll l=0,r=1e6,a1=-1;
	    while(l<=r){
	        ll mid=(l+r)/2;
	        ll x=((mid)*(mid+1)*(mid+2))/6;
	        if(x<=n){
	            l=mid+1;
	        }
	        else{
	            a1=mid;
	            r=mid-1;
	        }
	    }
	    l=0,r=1e6;ll a2=-1;
	     while(l<=r){
	        ll mid=(l+r)/2;
	        ll x=((mid)*(mid+1)*(mid+2));
	        if(x<=m){
	            l=mid+1;
     }
	        else{
	            a2=mid;
	            r=mid-1;
	        }
	    }
	    cout<<min(a1-1,a2)<<"\n";
	}
	return 0;
}

Approach 2:

#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;

int main() {
	// your code goes here
	fastio;
	ll t;
	cin >> t;
	vector<ll>sockets(1000000);
	sockets[0] = 0;
	for(ll i = 1; i < 1000000; i++){
	    ll temp = (i * (i+1LL))/2LL;
	    sockets[i] = sockets[i-1]+temp;
	}
	vector<ll>sticks(1000000);
	vector<ll>valid_tri(1000000);
	sticks[0] = 0;
	sticks[1] = 0;
	for(ll i = 2; i < 1000000; i++){
	    ll triangle = valid_tri[i-1] + (i - 1);
	    ll stk = triangle * 6;
	    sticks[i] = stk + sticks[i - 1];
	    valid_tri[i] = triangle;
	}
	while(t--){
	    ll n, m;
	    cin >> n >> m;
	    if(m == 0){
	        if(n == 1){
	            cout<<1<<endl;
	        }
	        else{
	            cout<<0<<endl;
	        }
	        continue;
	    }
	    int so = lower_bound(sockets.begin(), sockets.end(), n) - sockets.begin();
	    int st = lower_bound(sticks.begin(), sticks.end(), m) - sticks.begin();
	    if(sockets[so] > n){
	        so--;
	    }
	    if(sticks[st] > m){
	        st--;
	    }
	    int ans = min(so, st);
	    cout<<ans<<endl;
	}
	return 0;
}
1 Like