Even i completed it :). It was from one of the coding challenges...
public class Hill {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Integer[] l = new Integer[] {15,5, 4, 3, 2, 8};
hill(l);
}
public static void hill(Integer[] l) {
int max = 0;
for(int i=0;i<l.length;i++) {
if(max<l[i]) {
max = l[i];
}
}
int min =0 ;
while(true) {
int av = (max+min)/2;
if(min==max) {
if(isHill(l, av)) {
System.out.println(min);
}
else {
System.out.println("broke");
}
break;
}
if(isHill(l, av)) {
max = av;
}
else {
min= av+1;
}
}
}
public static Boolean isHill(Integer[] l, int i) {
int prev = -1;
for(int j=0;j<l.length;j++) {
int max = Math.max(prev+1, l[j]-i);
if(Math.abs(max-l[j])>i) {
return false;
}
prev = max;
}
return true;
}
}
On Tue, Mar 25, 2014 at 10:14 AM, Dan <[email protected]> wrote:
>
>
> 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 a topic in the
> Google Groups "Algorithm Geeks" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/algogeeks/ClXwlon0eXo/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> [email protected].
--
-bhargav krishna
--
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].
