Domino Effect Problem

Question

Last week we had a programming contest in my university and I am very curious about one of the problems , one which only one team (but from another city) was able to solve. May be its not that hard, but I cant find any solutions that will take less than a second of execution time. The problem is the following:

You have N domino tiles separated by different amounts (integer values that are given to you) and you know the height H of these tiles (all have the same height). They are all placed standing up so that if you push one it falls in the direction of the next one. This way, if tile i is close enough (H or less) to tile i+1, the first one will push the second one when it is pushed down, producing the domino effect. Suppose that not all the distances that separate the tiles are smaller than H, what's the minimum amount of moves you need to make in order to have all the distances be at most H? You can't move the first nor the last tile. Print -1 if it is not possible.

Note: You are only allowed to move integer amounts and only to spots on the line defined by tile i-1 and tile i+1. This means you cant grab one and place it wherever you want.

here are the input sizes: (3 ≤ N ≤ 1000) (1 ≤ H ≤ 50) and the distances (1 ≤ Di ≤ 100 for i = 1, 2, ..., N-1). Someone uploaded it to SPOJ recently http://www.spoj.pl/problems/TAP2012E/

Input:

N H

d1 d2 d3 d4 ... d(n-1)

Output:

Minimum amount of moves.

Sample

Input1

8 3

2 4 4 1 4 3 2

Output1

3

Sample2

Input2

10 2

1 2 2 2 2 2 2 2 3

Output2

8

Sample3

Input3

5 2

2 2 2 2

Output3

0

Sample4

Input4

5 3

1 6 2 4

Output4

-1 (NOT POSSIBLE)

I have only found a good solution for two cases:

D=sum_of_all_distances
MaxPossible=(N-1)*H

if D==MaxPossible and there is no di such that di>H
    Answer=0

else if D>MaxPossible
    Answer=-1

Answer 1

I tried in Perl which tries immediate tile distance adjustment and then cascading movements to get required distance

Execution syntax perl programName N H d1 d2 ... dn-1
Test cases sample: perl domino_slider.pl 8 3 2 4 4 1 4 3 2 output :3

use subs /dominochecker distancechecker subcheckright subcheckleft RigidMode/;

## Receive Input Tile Height D1 D2 ... Dn-1
$Tiles=$ARGV[0];
$Height=$ARGV[1];
$loop_count=0;
for $i (2...$#ARGV){
   $distance[$loop_count]=$ARGV[$i];
   $loop_count++;
}

$loop_count=$move=0;

sub dominochecker {
   $lc=0;$retflag=0;
   while ($lc<$Tiles-1) {
     if ($distance[$lc]>$Height) { 
         $retflag=1;
     }
     $lc++;
   }
   return $retflag;
}

sub subcheckleft {
   $lc=0;$retflag=0;$c=$_[0];
   while ($lc<$c) {
     if ($distance[$lc]>$Height) { 
         $retflag=1;
     }
     $lc++;
   }
   return $retflag;
}

sub subcheckright {
   $retflag=0;$c=$_[0];
   while ($c<$Tiles-1) {
     if ($distance[$c]>$Height) { 
         $retflag=1;
     }
     $c++;
   }
   return $retflag;
}

$loop_count=$move=0;

if (dominochecker==0) { ## if already in Domino Effect
print "\n $move \n";
exit;
}

sub RigidMode{
$loopend=$_[0];
$loop_count_local=0;
while ($loop_count_local<$loopend) {
  if ($distance[$loop_count_local]<=$Height) { 
    $loop_count_local++;
  } else {
    if ($distance[$loop_count_local-1]<$Height && $loop_count_local+1 !=1 && defined($distance[$loop_count_local-1]) ) {      
       $move++;
       $available=$Height-$distance[$loop_count_local-1];
       $required=$distance[$loop_count_local]-$Height;
       if($available<=$required) {
       $distance[$loop_count_local-1]=$distance[$loop_count_local-1]+$available;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$available;
       }else{
       $distance[$loop_count_local-1]=$distance[$loop_count_local-1]+$required;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$required;
       }
       $loop_count_local=0; 
    }elsif($distance[$loop_count_local+1]<$Height && $loop_count_local+2 !=$Tiles && defined($distance[$loop_count_local+1]) ){  
       $available=$Height-$distance[$loop_count_local+1];
       $required=$distance[$loop_count_local]-$Height;
       if($available<=$required) {
       $distance[$loop_count_local+1]=$distance[$loop_count_local+1]+$available;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$available;
       }else{
       $distance[$loop_count_local+1]=$distance[$loop_count_local+1]+$required;
       $distance[$loop_count_local]=$distance[$loop_count_local]-$required;
       }      
       $move++;
       $loop_count_local=0;
    }
    else{
    $loop_count_local++;
    }
  }
}
}

RigidMode($Tiles-1);

if (dominochecker==0) {
    print "\n $move \n";
    exit;
}else{
    $loop_count=$move=0;
    for $i (2...$#ARGV){
        $distance[$loop_count]=$ARGV[$i];
        $loop_count++;
    }
    $loop_count=$move=0;
    while ($loop_count<$Tiles-1) {
    if ($distance[$loop_count]<$Height) {      
       $available=$Height-$distance[$loop_count];
       if (subcheckleft($loop_count)>0){
         $move++ if $distance[$loop_count-1]-$available>0;
         $distance[$loop_count]=$Height if $distance[$loop_count-1]-$available>0 ;
         $distance[$loop_count-1]=$distance[$loop_count-1]-$available if $distance[$loop_count-1]-$available>0;
         RigidMode($loop_count+1);
         $loop_count=0 if $distance[$loop_count-1]-$available>0;
         $loop_count++ if $distance[$loop_count-1]-$available<=0;
       }elsif(subcheckright($loop_count)>0) {
         $move++ if $distance[$loop_count+1]-$available>0;
         $distance[$loop_count]=$Height if $distance[$loop_count+1]-$available>0;
         $distance[$loop_count+1]=$distance[$loop_count+1]-$available if $distance[$loop_count+1]-$available>0;      
         RigidMode($loop_count+1);
         $loop_count=0 if $distance[$loop_count+1]-$available>0;
         $loop_count++ if $distance[$loop_count+1]-$available<=0;
       }else{
         $loop_count++;
       }
    }else{
         $loop_count++;
    }
    }
}

if (dominochecker==0) {
    print "\n $move \n";
    exit;
}
else{
    print "\n -1 \n";
    exit;
}

Answer 2

Python

N, H = map(int, raw_input().split())
D = map(int, raw_input().split())

# map from (number of dominoes, distance to last domino) to                                                                                                        
# the number of moves needed to adjust the first number of dominoes                                                                                                
# exactly that far.                                                                                                                                                
M = {}
M[1,0] = 0

for i in xrange(2, N+1):      # i = number of dominos to try                                                                                                       
  for d in xrange(H*(i-1)+1):
    M[i,d] = 1e9
  for d in xrange(H*(i-1)+1): # position of last domino                                                                                                            
    for e in xrange(1, H+1):  # distance from last domino to previous one                                                                                          
      if d-e > H*(i-2): continue
      if d-e < 0: continue
      if sum(D[:i-1]) == d:
        # don't move last domino, arrange rest                                                                                                                     
        M[i,d] = min(M[i,d], M[i-1,d-e])
      else:
        # arrange rest, move last domino to right location                                                                                                         
        M[i,d] = min(M[i,d], 1 + M[i-1,d-e])

print M.get((N,sum(D)), -1)

Standard dynamic programming. Runs pretty much instantaneously on the example inputs. How big a problem do we have to solve in under a second?