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 [email protected].
