NOKIA - Editorial

Alternate Proof ==>

Simplest proof to prove that all [min(n),max(n)] are possible is :

case 1 : if n==1
max(1) = min(1) = 2;

case 2 : if n==2
max(2) = min(2) = 5;

case 3 : if n==3
max(3) = 9;
min(3) = 8;

So for n>3 if we go for solution then after dividing the problem we will surely reach some level where we have to solve for n’=3 and thing will be able to create the difference of 1 (if all other branches are remained constant). Hence we can get all the numbers in [min(n),max(n)].

4 Likes

Admin, can you please explain this:

If min[a+1]+min[n-a-2] ≤
max[a]+max[n-a-1] for all a=n/2,
n/2+1, …, n-2, then we can show [
min[n], max[n] ] are all possible.

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.

O(1) solution solution:

max len=(n+1)(n+2)/2

min len=ceil(log(n+1)*(n+1))

all values between max and min are possible.

2 Likes

can someone explain in brief , how to come up with this formula,
" minLen[n] = (n+1) + minLen[n/2] + minLen[n-1-n/2] " ?

3 Likes

I made my solution according to the editorial , someone please have look on code and suggest the mistakes?
I matched few test cases with the solution all good , but its always WA while submitting.

Here’s my


[1] 

Thankyou
  [1]: https://ideone.com/cCKp2G
1 Like

i got the perfect explanation of the logic used by setter, but i am not allowed to post image here. so if anyone is curious to know, can mail me @ sumeshkpandit@gmail.com

how can we say that any value between max an d min is possible?
anyone with a concrete proof for it?

It explains a naive approach previously.

“For a given N, we just need to fix the first position”

Here you have O(N) for fixing the position

“and that partitions the problem in to two independent smaller subproblems and we can merge the answers to these smaller subproblems.”

This takes O(N^4) because for each of the number of the first subproblem(O(N^2)), you can choose any number of the of the second subproblem(O(N^2)).

So for a given N, in O(N^5) you can find the number of used_lengths.

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.
1 Like

@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.

1 Like

@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.
1 Like

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.

1 Like
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;
}