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?).
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.
please prove that all values between min and maximum are possible in this problem
1 Like
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.
Better to write ‘lg(n+1)’ (‘log’ base 2).
I don’t understand why this is in “Simple” category. It is so discouraging for people who started coding.
4 Likes
Thanks for sharing this approach
#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;
}
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.
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
9 Likes
Can Someone explain for case where n=2 and m=4 ?
I mean how it came -1.
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.
#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.
I also applied the same approach and same Error
#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.
Because for n=2, we need at least wire of length 5 . and given wire length is 4, so it is not possible.