7
\$\begingroup\$

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. Maybe 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:

Problem

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 a falsey value 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

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 (Pseudo-Code):

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
\$\endgroup\$
8
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – grc
    Oct 7, 2012 at 6:17
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ Oct 7, 2012 at 18:48
  • \$\begingroup\$ @PeterTaylor DP? abbreviations.com/DP \$\endgroup\$
    – DavidC
    Oct 7, 2012 at 23:46
  • \$\begingroup\$ @DavidCarraher, dynamic programming \$\endgroup\$ Oct 8, 2012 at 6:37
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Oct 10, 2012 at 0:02

2 Answers 2

2
\$\begingroup\$

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?

\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$
    – fersarr
    Oct 28, 2012 at 20:49
  • 1
    \$\begingroup\$ wow, you have less than 20 lines! thats awesome, may be you can test it in that spoj link \$\endgroup\$
    – fersarr
    Oct 28, 2012 at 21:03
  • \$\begingroup\$ Well it times out as a SPOJ submission. It takes a few seconds when I try it at N=500. \$\endgroup\$ Oct 29, 2012 at 19:03
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ 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 \$\endgroup\$
    – fersarr
    Oct 28, 2012 at 20:57

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