I just stumbled upon this one (I know, a little late). At least this way... it's too late to be helpful if it was a Homework assignent. :-)
This is one of those problems that, at first, appears difficult, but , upon closer inspection, turns out to have a very straight forward (elegant?) solution. Take any two adjacent values from the list... call them a & b In the worst case scenario, the value of a is higher than the value of b... a > b Therefore, we need an X value that solves the inequality.... a - X < b + X Rearrange this equation just slightly to another equivalent equation... a - b < 2X This indicates that a slightly different (but, still equivalent) problem can be solved to arrive at a correct solution. Only allow values from 0 to 2X, [0,2X] to be added to the original values in the array (ie. no subtractions). This simplifies things greatly and allows for a clear algorithm solution that can be easily performed in a single pass through the array. Essentially, you find a value of 2X that works... then divide that in half, and convert the resulting float type value to a whole integer value to get the final X value that solves the 'original' problem statement. The fortran code below has been tested and appears to work just fine. The real algorithm of note is the function routine: *FUNCTION TransformArray( v ).* Note that the important code is only 7 simple lines long and should be easy to recode in most any language. It runs extremely fast, even for array sizes of 10000. There's also 'fluff' code here, written to test multiple test sets to check the value of X arrived and to time everything. at is the desired answer. Does anyone know of any Practical applications for this algorithm?? I'm guessing it's just an interesting problem. Dan :-) Module Transform Contains * Function TransformArray( v ) Result(x) !--------------------------------------------------- ! Find a minium X value to transform the array, v(:) ! Transformed array values can be negative. It is a trivial task to ! alter this to guarantee no negative values in the transformed array. !---------------------------------------------------* Integer, intent(in) :: v(:) Integer :: x Integer :: i, b x = 0 b = v(1) Do i = 2, Size(v) b = Max( b+1, v(i) ) x = Max( x , b-v(i) ) End Do x = Ceiling( x/2.0 ) ! smallest integer greater/equal to the value. * End Function TransformArray* Subroutine Validate_X( v, x ) !--------------------------------------------------------------------- ! Given a value of x, see if the array can be successfully transformed ! This is merely code to see if the X value arrived at is correct. !--------------------------------------------------------------------- Integer, intent(in) :: v(:) Integer, intent(in) :: x Integer, allocatable :: vt(:), xt(:) Integer :: i, n n = Size(v) Allocate( vt(n), xt(n) ) vt(1) = v(1) - x xt(1) = -x Do i = 2, n vt(i) = Max( vt(i-1)+1, v(i)-x ) xt(i) = vt(i)-v(i) End Do write(*,'(a,29999i6)') ' v = ', v write(*,'(a,29999i6)') ' xt = ', xt write(*,'(a,29999i6)') ' vt = ', vt If( Any( abs(xt) > x ) ) Then write(*,'(a)' ) ' A higher x value was required during the transformation.' write(*,'(a,i0,a)') ' X = ', x, ' does not work.' End If If( Any( vt(1:n-1) >= vt(2:n) ) ) & write(*,'(a)') ' ERROR: Transformed array is not in "Strictly Ascending" order!' End Subroutine Validate_X End Module Transform Program Main !---------------------------------- Use Transform Implicit None Integer, parameter :: nmax=10000 Integer :: n, x Integer, allocatable :: v(:) Real, allocatable :: r(:) Integer :: it1, it2 Allocate( v(nmax), r(nmax) ) call timer(it1) write(*,*) write(*,*) 'Test Case #1: array size = 5, Easy to check' n = 5 v(1:n) = (/5,4,3,2,8/) Call Solve_for_X() write(*,*) '------------------------------------------' write(*,*) write(*,*) 'Test Case #2 array size = 8, Easy to check' n = 8 v(1:n) = (/8,12,7,15,10,20,12,16/) Call Solve_for_X() write(*,*) '------------------------------------' write(*,*) write(*,*) 'Test Case #3: array size = 10000 w/ random array values up to 999' n = 10000 Call Random_Seed() Call Random_Number( r(1:n) ) v(1:n) = 1 + Int(999*r(1:n)) Call Solve_for_X() write(*,*) '------------------------------------' call timer(it2) write(*,*) 'Total time = ', Real(it2-it1)/100.0 Contains Subroutine Solve_for_X() !------------------------ x = TransformArray( v(1:n) ) write(*,'(a,i0)') ' X minimum = ', x Call Validate_X( v(1:n), x ) ! Check to see if a smaller X value would have worked write(*,*) write(*,'(a,i0,a)') ' Check to see if x = ', x-1, ' will work:' Call Validate_X( v(1:n), x-1 ) End Subroutine Solve_for_X End Program Main *Test Case #1: array size = 5, Easy to check* X minimum = 3 v = 5 4 3 2 8 xt = -3 -1 1 3 -2 vt = 2 3 4 5 6 Check to see if x = 2 will work: v = 5 4 3 2 8 xt = -2 0 2 4 -1 vt = 3 4 5 6 7 A higher x value was required during the transformation. X = 2 does not work. ------------------------------------------ *Test Case #2 array size = 8, Easy to check* X minimum = 5 v = 8 12 7 15 10 20 12 16 xt = -5 -5 1 -5 1 -5 4 1 vt = 3 7 8 10 11 15 16 17 Check to see if x = 4 will work: v = 8 12 7 15 10 20 12 16 xt = -4 -4 2 -4 2 -4 5 2 vt = 4 8 9 11 12 16 17 18 A higher x value was required during the transformation. X = 4 does not work. ------------------------------------ *Test Case #3: array size = 10000 w/ random array values up to 999* X minimum = 5466 v = 422 430 670 62 37 561 287 : : : 565 664 389 273 xt = -5466 -5466 -5466 -4857 -4831 -5354 -5079 : : : 4923 4825 5101 5218 vt = -5044 -5036 -4796 -4795 -4794 -4793 -4792 : : : 5488 5489 5490 5491 Check to see if x = 5465 will work: v = 422 430 670 62 37 561 287 : : : 565 664 389 273 xt = -5465 -5465 -5465 -4856 -4830 -5353 -5078 : : : 4924 4826 5102 5219 vt = -5043 -5035 -4795 -4794 -4793 -4792 -4791 : : : 5489 5490 5491 5492 A higher x value was required during the transformation. X = 5465 does not work. ------------------------------------ Total time = 9.99999978E-03 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.