@bhargav : could you please explain your algorithmn On 3/25/14, bhargav krishna yb <[email protected]> wrote: > 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]. >
-- 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].
