Sir, please help me with my logic for this problem.
After spending some time on this question, I came with a math expression, which I believe is correct. The main part of my method depends on the fact that for ‘n’ positions, there will be a minimum and a maximum length of cable needed to make the desired connections - this is the obvious part. Upon doing some calculations on pen-paper, I came up with the following:
if n==1: min=max=2 else if n==2: min=max=3 else: min=4*(n-1) max=(n*(n+3))/2
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:
- m lies between hi and lo (both inclusive)
based on that logic, the psuedocode is:
input n if n==1: lo=hi=2 else if n==2: lo=hi=5 else: lo=4*(n-1) max=(n*(n+3))/2 input m if m<lo: print -1 else if m>hi: print (m-hi) else: print 0
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.
Please help me find the flaw in the logic.
This is my submitted code ::: http://www.codechef.com/viewsolution/4142797