TopCoder SRM 489 Div 1 Medium (Dice Rotation)

Another bad SRM for me :( I couldn't even submit any problem although I was just 1 click away from solving the medium problem with 30 seconds to go when the network router decided to go offline. My only achievement in this SRM was one successful challenge.

I'm going to explain how I approached the dice rotation problem. In this problem you have to move a standard dice placed at (0,0) cell of an infinite Cartesian plane to (goalx, goaly) by rotating it to right or up. The top of the dice have to show '1' when it starts its journey at (0,0) and also when it ends its journey at (goalx,goaly) and it cannot be on top in any intermediate cell. goalx and goaly can be as high as 10^9.

Firstly I observed that all the given sample inputs have output 2 and samples seemed pretty random too. So, there might not be too many ways it can reach the destination cell. It is clear if you move the dice to any direction 4 times consecutively '1' will appear on the top surface again. To move the dice a long distance in any direction, you have place the '1' face out of rotating axis. For example, when going up (moving in y-direction), you have to place the '1' face in right or left. When moving right again, you have to first move it to bottom (by going right) and then to front (by going up) and then you can continuously move to right until you reach one cell below your destination.

So, I decided to write a solution for smaller cases to check if there's any pattern in it. It can be done using dynamic programming. We have to find number of ways we can reach a cell (x,y) with face z on top. After writing that brute force solution, its easy to find that the solution is always 2 unless one of the goalx or goaly is 4. In that case, it would be 3 plus the other number. One special case is (4,4) for which input should be 12. And also, if one of goalx or goaly is 1, the answer will be 0 unless the other is 4.

After match analysis:

We can always reach the destination in 2 standard paths which are shown below -

The speciality with 4 is because of the fact that if we rotate dice in one direction 4 times, it will reach the original state. For example, lets say goalx = 4 and goaly = 6. Starting with (0,0) we can take any of the following path -

There are 7 ways to reach (4,6). Plus there will be 2 standard paths. So, the proper formulation of the solution would be

npaths = 2 + (goalx==4)?(goaly+1):0 + (goaly==4)?(goalx+1):0

Source code below -

/*
Problem Name : Dice Rotation
Problem Number : Topcoder SRM 489 Div 1 Medium
Link : http://www.topcoder.com/stat?c=problem_statement&pm=11212
Problem Type : Math, Dynamic Programming
Difficulty : 6.5 / 10
Interest : 8.5 / 10
Complexity : O(1)
Date : December 1, 2010
*/
#include<string>
#include<vector>
#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

#define rep(i,n) for(i=0;i<(n);i++)

int dp[50][50][6];
int final[50][50];

struct DiceRotation{
 int rotate(int cur, int dir) {
  if(dir == 0) { //right
   if(cur == 0) return 4;
   if(cur == 4) return 5;
   if(cur == 5) return 1;
   if(cur == 1) return 0;
   return cur;
  }
  if(dir == 1) { //up
   if(cur == 0) return 2;
   if(cur == 2) return 5;
   if(cur == 5) return 3;
   if(cur == 3) return 0;
   return cur;
  }
 }


 void init() {
  int i,j,k,x,y;
  int r1,r2;
  for(x=1;x<=40;x++) for(y=1;y<=40;y++) {
   memset(dp,0,sizeof(dp));
   dp[0][0][0] = 1;
   rep(i,x+1) rep(j,y+1) rep(k,6) if(dp[i][j][k] > 0){
    r1 = rotate(k,0);
    r2 = rotate(k,1);
    if(r1 == 0) {
     if(i+1 == x && j == y) dp[i+1][j][r1] += dp[i][j][k];
    }
    else dp[i+1][j][r1] += dp[i][j][k];
    if(r2 == 0) {
     if(i == x && j+1 == y) dp[i][j+1][r2] += dp[i][j][k];
    }
    else dp[i][j+1][r2] += dp[i][j][k];
   }
   final[x][y] = dp[x][y][0];
   printf("%d %d => %d\n",x,y,dp[x][y][0]);
  }
 }
 int theCount(int goalx, int goaly) {
  //init();
  if(goaly < goalx) swap(goalx,goaly);
  if(goalx == 1) {
   if(goaly == 4) return 2;
   return 0;
  }
  if(goalx == 4 && goaly == 4) return 12;
  if(goalx == 4 || goaly == 4) return goalx+goaly-1;
  return 2;
 } 
};