PROBLEM LINKS:DIFFICULTYSimple PREREQUISITESarrays, divideandconquer, recursion PROBLEMGiven an array A[0..N+1], consider the indices [1..N] as spots for the soldiers and index 0 as the left tower and the index N+1 as the right tower. Initially set A[0] = 1, A[N+1] = 1 and rest all have 0s. Given a permutation P[1..N] of the indices {1, 2,...,N}, we fill them with 1s in that order and find the length of used wire as follows.
You can see that the used_length depends on the permutation P and given an integer M, we need to find the minimum length of unused wire. It is same as asking for the maximum possible used_length ≤ M for some permutation P. If M is not sufficient for any permutation P, output 1. QUICK EXPLANATIONIf you have solved the problem or almost got it yourself, this explanation is for you. If you have not solved it and eager to know how to build the idea from scratch, skip this part and go to the Detailed explanation section below. There is a simple bruteforce solution and other clever solution. They are explained below.
For minimum, its always better to try partitioning the problem into two equal subproblems. For maximum, we just need to place in the order {1,2,3...N} Now, can you prove that all the values between [ minLen[n], maxLen[n] ] are possible ? An idea is given in tester's approach. DETAILED EXPLANATIONIf you haven't solved this problem yet, take some time now and try different cases on paper. eg. Consider N = 4 and try to find all possible sum_of_lengths for different permutations of {1,2,3,4}. You can also take a look at the explanation of sample cases under the problem statement for better understanding. First lets see an almost bruteforce solution. Consider the array A for N = 9. SETTER'S SOLUTIONCan be found here APPROACHThe problem setter used the approach given in the detailed explanation above. TESTER'S SOLUTIONCan be found here APPROACHThe problem setter and the tester have independently observed that each of the values between [min, max] can be achieved for some permutation P. This method takes only O(N) time. Here is a rough idea of the proof using induction, in tester's words. max[0] = min[0] = 0 Here we assume that for k = 1,2,...,n1, [ min[k], max[k] ] are all possible, If you can come with a more intuitive and simple proof, please edit this post and add a section 'Alternate Proof'.
This question is marked "community wiki".
asked 18 Jun '12, 00:22

Simpler way to prove/conclude this ?
answered 18 Jun '12, 01:29

"For minimum, its always better to try partitioning the problem into two equal subproblems. minLen[n] = (n+1) + minLen[n/2] + minLen[n1n/2] For maximum, we just need to place in the order {1,2,3...N} maxLen[n] = (n+1) + maxLen[n1] , this is same as maxLen[n] = (n*(n+3))/2" I didn't understand how one can prove this. Is it a rule of thumb? Also, can you fix the '?' in the "min[a+1]+min[na2] ? max[a]+max[na1]". It appears in a lot of problems statements in practice as well. answered 18 Jun '12, 11:27
Note the following is not a proof: Yet it can give some intuition, f(n) = n+1 + f(nx) + 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 = n1, 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.
(18 Jun '12, 17:43)
@mkagenius  the equation in the first line of your explanation should be f(n)=(n+1)+f(x)+f(nx1). 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.
(18 Jun '12, 19:47)
1
@shubh09, yes, you are right. it should be, f(n)=(n+1)+f(x)+f(nx1). 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.
(18 Jun '12, 19:56)
1
Let me put it this way  if the length of the wire to connect the ith soldier (meaning i1 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.
(18 Jun '12, 20:13)
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?).
(18 Jun '12, 20:26)
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.
(18 Jun '12, 21:48)
showing 5 of 6
show all

Here this function calculates the minimum value for a given N. mid=N/2 if n is even and mid=N/2+1 if n is odd .....Please tell me if anything is wrong in this function.
answered 18 Jun '12, 01:18

Sir, please help me with my logic for this problem.
I did calculations manually uptill n=6 and things turned out correct thus far. Now, given a value of 'm', it will fall in either of the 3 cases:
based on that logic, the psuedocode is:
Unfortunately, this gave a WRONG ANSWER. So I compared the output of my code with that of an accepted code and couldn't find any differences. answered 25 Jun '14, 23:37

can anybody tell me what should be "?" in this quote :
answered 24 Jun '12, 23:49

can anybody make me understand this question by giving one simpler example? answered 10 Mar '17, 18:31

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)].
link
This answer is marked "community wiki".
answered 15 Aug '17, 14:53

O(1) solution solution: answered 19 Dec '17, 00:03

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