Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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
share|improve this question
1  
Some harder test cases: 10 2 \ 1 1 3 2 2 2 2 2 3 should output 8, and 8 3 \ 4 4 1 1 1 4 4 should output 4. –  grc Oct 7 '12 at 6:17
    
While this is an interesting problem (my initial hunch is that DP is the solution, but I'd have to think about it), the purpose of this site is effectively to run mini-contests. That's why the FAQ says that each question should have an objective winning condition. Can you select a suitable condition which allows you to pick the "best" of the correct answers? –  Peter Taylor Oct 7 '12 at 18:48
    
@PeterTaylor DP? abbreviations.com/DP –  David Carraher Oct 7 '12 at 23:46
    
@DavidCarraher, dynamic programming –  Peter Taylor Oct 8 '12 at 6:37
1  
You could make the problem specification a bit clearer. What exactly is a "move" – you take one tile out of the chain and put it in some other empty place? Or, you just push a single stone closer to one of its neighbours? Can you move by arbitrary distances, or just in steps of one? — BTW, real domino tiles can not be placed that far apart and support a chain reaction, it's actually more like √½ ⋅ H. –  leftaroundabout Oct 10 '12 at 0:02

2 Answers 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?

share|improve this answer
    
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 spoj.pl/problems/TAP2012E –  fersarr Oct 28 '12 at 20:49
1  
wow, you have less than 20 lines! thats awesome, may be you can test it in that spoj link –  fersarr Oct 28 '12 at 21:03
    
Well it times out as a SPOJ submission. It takes a few seconds when I try it at N=500. –  Keith Randall Oct 29 '12 at 19:03

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;
}
share|improve this answer
    
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 spoj.pl/problems/TAP2012E –  fersarr Oct 28 '12 at 20:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.