NOKIA - Editorial

[mkagenius]

Note the following is not a proof:
Yet it can give some intuition,
f(n) = n+1 + f(n-x) + f(x), will have minima at x = n/2, u can find this by assuming f(n) to a polynomial function, and taking the derivative.
and f(n) is maximum at other two ends, that is either x = 1 or x = n-1, due to increasing both arms of parabola. (assuming the degree of polynomial f(n) is 2 ), again this is intuitive since the dip is at x=n/2.

f(n) starts decreasing as x increasing from 1 to n/2, reaches its minima when x = n/2, then again starts increasing.

[shubh09]

@mkagenius - the equation in the first line of your explanation should be f(n)=(n+1)+f(x)+f(n-x-1).
Further, the statement “For maximum, we just need to place in the order {1,2,3…N}” seems fairly intuitive to me. (n*(n+3))/2 is easily derivable as being equal to ((n+1)+…+2).
Regarding the one regarding minLen[n], I also am having trouble finding a satisfactory proof for it. It is no doubt intuitive, but it would be great if someone could come up with a concrete proof for the same.

[mkagenius]

@shubh09, yes, you are right. it should be, f(n)=(n+1)+f(x)+f(n-x-1).
The rest of the things still hold.
But

"For maximum, we just need to place in the order {1,2,3...N}"

is not at all intuitive to me, the sum ((n+1)+ .. + 2) surely equals n*(n+3)/2, but is it intuitive that it will be maximum ? I am not sure.

[shubh09]

Let me put it this way - if the length of the wire to connect the ith soldier (meaning i-1 soldiers have already been stationed on the wall) be denoted by len[i], then one can easily see that len[i]>len[i+1]. Now, we know that len[1]=n+1. Hence, we can easily deduce that the max value for len[2] is n. Going on this way, the statement in question is evident.

[mkagenius]

len[i]>len[i+1]

, i think you already assumed that best placement permutation to be (1,2,3..,N) but that is the question, whether this particular permutation is best one or not.(or why do you think that to get maximum, that condition should be satisfied?).

[sai16vicky]

See the constraints say that N<=30. Till N<=10, we can actually simulate the give procedure and display the different lengths we can incur. If we check that, we will come to know that all values will be taken. I mean it is an assumption but as 1/3 rd of the cases are going to satisfy it, we can give it a shot.

[tick]

please prove that all values between min and maximum are possible in this problem

[vijju123]

Can you please elaborate your doubt of Also, ( min[a+1]+min[n-a-2] ≤ max[a]+max[n-a-1] ) is false for n=4, since ( 8+0 <= 5+2 ) is false. ?

For the possible values, I think it has got to do something with having sequences of permuation sorted lexicographically.

[sarthakmanna]

Better to write ‘lg(n+1)’ (‘log’ base 2).

[losing_coder]

I don’t understand why this is in “Simple” category. It is so discouraging for people who started coding.

[psdudeman39]

Thanks for sharing this approach

[sanchit2812]

#include<bits/stdc++.h>
using namespace std;
#define IOS() ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ll long long

ll solve(ll l, ll r){
if(l<=r){
ll mid = (r+l)/2;
return (r-l +2) + solve(l,mid-1) + solve(mid+1,r);
}
return 0;
}

int main(){
IOS();
int t;
cin>>t;
while(t–){
int n,m;
cin>>n>>m;
ll cnt = 0, l=1 , r = n;
ll mx = 0;
mx = (n+1)*(n+2);
mx/=2;
mx–;
cnt = solve(l, r);
// cout<<cnt<<" “;
if(cnt > m) cout<<”-1"<<endl;
else if(m > mx) cout<<m - mx<<endl;
else cout<<0<<endl;
}
return 0;
}

[sh16011993]

Thanks for the explanation. Still I am not getting how we are taking O(n^2) for individual subproblem? Can you help with this please. Thanks.

[nagesh_reddy]

I am writing this for those who still not able to understand : why do we need sub problems to find min value. (Try using pen and paper)

For minimum, its always better to try partitioning the problem into two equal subproblems.
minLen[n] = (n+1) + minLen[n/2] + minLen[n-1-n/2]

Based on the above statement we have to divide each sub-problem into 2 parts every-time for that we need recursion, you can check how the flow goes in the following diagram

In the above diagram our N=5, we divide it into 2 sub-problems every-time (For this reason we need recursion)

For maximum, we just need to place in the order {1,2,3…N}
maxLen[n] = (n+1) + maxLen[n-1] , this is same as maxLen[n] = (n(n+3))/2*

Based on the above statement we can use the formula directly to find the max value without any recursion, look at the following diagram

Another example : N= 9
min value

max value

[pravesh25]

Can Someone explain for case where n=2 and m=4 ?
I mean how it came -1.

[r_madhvendra]

For n=2, the min and max possible length of the rope required would be the same i.e. 5.
2 possible perm- [1,2], [2,1]. Going by the logic length of the rope required= 1+2+1+1 (can be easily seen through ques logic).
Hence rope of size=4 doesn’t work in any possible cases. Therefore -1.

[yogeshk108]

#include<bits/stdc++.h>
int nokia(int l,int r)
{
if( r-l < 2) return 0;
int mid = l+(r-l)/2;
return (r-l) + nokia( l ,mid) + nokia(mid , r);
}

int main()
{
int t , n , l;
cin>>t;
while(t–)
{
cin>>n>>l;
int Max = (n*(n+1))/2 + n;
int Min = nokia(0 , n+1);
if( l <= Max && l >= Min) cout<<0<<endl;
else if(l < Min) cout<<-1<<endl;
else cout<<( l-Max )<<endl;
}
return 0;
}

We only need recursive function calculate minimum value and maximum can be calculated using sum of n numbers + n.

[dikshant25]

I also applied the same approach and same Error

[ruved]

#include <bits/stdc++.h>
using namespace std;

int recur(int nl,int nr)
{

    if(nr-nl<=1) return 0;
 int mid=(nr-nl)/2;
    int c=nr-nl;
    //cout<<c<<" ";
    c+=recur(nl,mid)+recur(nl+mid,nr);
    
//cout<<c<<" ";
return c;

}

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n,w;
cin>>n>>w;
int min=recur(0,n+1);
int max=(n*(n+3))/2;

     if(min<=w&&max>=w)
     cout<<"0";
     else if(w>max)
     cout<<w-max;
     else
     cout<<"-1";
     
      cout<<endl;
 }
return 0;

}

buddy i dont know i am facing wrong answer! could you please see that.

[nkp2312]

Because for n=2, we need at least wire of length 5 . and given wire length is 4, so it is not possible.