PROBLEM LINK:
Authors: Parth Dhorajiya and Rituj Aryan
DIFFICULTY:
MEDIUM
PREREQUISITES:
Binary Search, Math
PROBLEM:
Cheems have a series of N blocks that he wants to paint. But, he can only paint in steps.
In i^{th} step, he will paint one block and move i blocks forward. (i starts from 1).
For eg, if he starts with first block, he will paint the following blocks :- 1, 2, 4, 7, 11, 16, …… (Lets denote this as one process). But he will miss many blocks in between.
So he has to start again by choosing a different initial block (can be any) and follow the same process till all N blocks are painted. (During each process he will choose an initial block and follow the above given steps).
He is allowed to paint one block one or more times.
Cheems is weak in maths and lazy, so he wants to paint all the boxes in minimum possible processes. Help him!
EXPLANATION:
Most optimal way to do so is to start at 1^{st} block. He will paint 1,2,4,7,11,16…. numbered boxes. Then he will start from 2nd, 3rd, 4th, 5th box … in consecutive processes. This will ensure that every box is painted.
Suppose we paint some boxes at i^{th} process then at (i+1)^{th} process, we will paint all the boxes next to the boxes painted in i^{th} process.
Example:
Starting from box 1 \rarr 1, 2, 4, 7, 11, 16, …
Starting from box 2 \rarr 2, 3, 5, 8, 12, 17, …
Starting from box 3 \rarr 3, 4, 6, 9, 13, 18, …
So by following the given approach we can paint all boxes in minimum no. of processes.
Now the question is how can we find total processes required.
The common observation is that we will find the maximum difference between two consecutive boxes painted in the 1^{st} process because regardless of any process which is starting from a particular box, we can’t paint the boxes that are left out between the consecutive boxes painted in that process.
So, we will need that no of processes which are equal to the maximum no of boxes left after the 1^{st} process applied which is (1 \rarr 2 \rarr 4 \rarr 7…) so that every process will cover one box which is in that maximum difference. And following this approach of covering all the boxes lying in that maximum difference, the boxes that are left out in 1^{st} process but are not lying in maximum difference are also covered.
For eg – if N = 18,
Then we will find the lower bound of N in the array = [1,2,4,7,11,16,22…] (this vector is noting but the indexes of boxes painted in the 1st process) which is 22. So now the maximum difference clearly is between box 11 and box 16 which is 5, so the answer is 5.
But the point here is to note that, if N=21 then lower bound of 21 is 22, and the maximum difference is also 16-11=5 but we can observe that to fill the boxes from 16-21 we would need 6 process. (so observe that where this exception occurs)
ALTERNATE EXPLANATION:
Credits: Himanshu Airan
This question follows a pattern
for n=1, ans = 1
n = 2, ans = 1
n = 3, ans = 2
n = 4, ans = 2
n = 5, ans = 2
n = 6, ans = 3
……
The pattern here is 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, …… (value x will be printed x+1 times).
Now, we are to find N^{th} term of this series, which is \frac{\sqrt {1+8*N} - 1}{2}.
SOLUTIONS:
Setter's Solution - CPP
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define ll long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fo(i,n) for(i=0;i<n;i++)
#define vec vector<ll>
#define mod (ll)(1e9+6282)
int main()
{
fast
vector<ll> v;
ll c=1;
for(ll i=1;c<=mod;i++)
{
v.pb(c);
c+=i;
}
ll t;
cin>>t;
for(ll i=0;i<t;i++)
{
ll n;
cin >> n;
if (n == 0) {
cout<<"0"<<endl;
continue;
}
if(n==1||n==2)
cout<<"1"<<endl;
else{
auto e = lower_bound(v.begin(), v.end(), n);
ll t1=v[e-v.begin()-1];
ll t2=v[e-v.begin()-2];
ll a=max(n-t1,t1-t2);
if(n-t1==t1-t2)
a++;
cout<<a<<endl;
}
}
}
Alternate Solution - Python
from math import sqrt
test = int(input())
for _ in range(test):
n = int(input())
ans = (sqrt(1+8*n)-1)/2
print(int(ans))