You are hereProgramming Problems / 2008 Programming Solutions

2008 Programming Solutions


By gconway - Posted on 17 April 2012

Magic Cups

#include <stdio.h>

int n,x,y;

int main()

{

scanf("%d",&n);

scanf("%d %d",&x,&y);

 

while (x != -1) {

if (x == n) { n = y; }

else if (y == n) { n = x; }

scanf("%d %d",&x,&y);

}

printf("%d\n",n);

     return 0;

}

 

Number Mix

The solution is:

N! / (C[0]! x C[1]! x C[2]! x C[3]! x C[4]! x ..... x C[8]! x C[9]!)

Where N is the number of digits in the input number and C[i] is the number of times the digit "i" appears in the input number. Note: when we put an exclamation mark after a number, we mean "factorial".

"N factorial" = N! = N x (N-1) x (N-2) x ..... x 4 x 3 x 2 x 1

E.g. 4! = 4x3x2x1 = 24

______________________________________________________________________

Discussion

How many different ways do we have of mixing up the digits of: 1234567890?

Well to create a new number, we start by picking the first digit, and we have 10 choices.

Then for the second digit, we have 9 choices left. Then for the third digit, we have 8 choices left.

.....and then for the 10th digit, there will be only one number left (1 choice).

So the total number of ways of mixing them up is 10 x 9 x 8 x 7 x 6 .... x 2 x 1 = 10! = 3628800

We write this as "Ten Factorial" or "10!"

So if we have 'n' digits then we have 'n!' ways to mix them up.

 

In case of numbers with repeating digits, there is a problem. Take 323.

If we make the two "3" digits different, there are 3! = 6 combinations.

1 = 2[3]{3} = 233

2 = 2{3}[3] = 233

3 = {3}2[3] = 323

4 = [3]2{3} = 323

5 = {3}[3]2 = 332

6 = [3]{3}2 = 332

We have lots of duplicates and have to figure out how to avoiding counting these.

Let's take the number 45555.

For any mixture of these digits, the four 5's can be rearranged and it wont change the value of the number.

There are 4! ways to rearrange four 5's. This leads to the equation above.

 

Here is the code:

 

#include <stdio.h>

int c[10]; // count of each digit type

int i, n, x;

int main()

{

scanf("%d", &n);

   for (i=0 ; i<10 ; i++) c[i] = 0; // Init Count

   i=1;

x=1;

while(n > 0)

{

c[n % 10]++;

n = n / 10;

// compute k! (k factorial)

// where k is the number of digits in the input number

x=x*i;

i=i+1;

}

 

   for(i=0;i<10;i++)

while (c[i] > 0) // this is a fancy way of dividing by c[i]!

x = x / c[i]--;

 

   printf("%d\n",x);

return 0;

}

 

Object Detection

In this task, you have to examine ALL possible rectangles, and for each rectangle: count the number of foreground pixels in it.

To do a full search, you need 4 nested FOR loops (X position of top left corner of rectangle, Y position of top left corner, X position of bottom right corner, Y position of bottom right corne) and then a further 2 nested for loops within them (to add up all the foreground pixels), giving a total of 6 nested for loops ... O(N^6).

Using integral images, it is possible to compute the sum of pixels in a rectangular area in constant time, so this can be reduced to O(N^4).

For more information on integral images, See The Paper

// Solution by Stephen Dolan

#include <stdio.h>

 

int im[60][60];//im[row][col]
char buf[60];
int main(){
  int i,j,ix,jx,w,h;

// read input

scanf("%d %d ",&w,&h);

  for (i=0;i<h;i++){
    gets(buf);
    for (j=0;j<w;j++){
      im[i][j] = (int)(buf[j] - '0');
    }
  }

//integrate im

  for (i=0;i<=h;i++){
    int s = 0;
    for (j=0;j<=w;j++){
      int t = im[i][j];
      im[i][j] = s;
      s += t;
    }
  }
  for (j=0;j<=w;j++){
    int s = 0;
    for (i=0;i<=h;i++){
      int t = im[i][j];
      im[i][j] = s;
      s+=t;
    }
  }

//search

  int bestf = 0, besta = 1, besti=0, bestj=0, bestix=0, bestjx=0;
  for (i=0;i<h;i++){
    for (ix=i+1;ix<=h;ix++){
      for (j=0;j<w;j++){
        for (jx=j+1;jx<=w;jx++){
          int f = im[ix][jx] - im[i][jx] - im[ix][j] + im[i][j];
          f = f * f;
          int a = (ix-i) * (jx-j);
          if (f * besta > a * bestf){
            besta=a,bestf=f,besti=i,bestj=j,bestix=ix,bestjx=jx;
          }
        }
      }
    }
  }

printf("%d %d %d %d\n", bestj+1, besti+1, bestjx-bestj, bestix-besti);

  return 0;
}

 

Non-Fixed Permutations

//
// Code to compute F(n)
// The number of non-fixed permutations of size 'n'
//

#include <stdio.h>

#define MODVAL 1073676287

int main(void) {

        int grid[2][2];
        int n, i, j;
        scanf("%d", &n);

grid[0][0] = 0; // F(1) = 0

        grid[0][1] = 1;
        for (i=2 ; i<=n ; i++) {
                grid[1][0] = 0;
                //To avoid multiplication overflow,we use repeated addition
                for (j=0 ; j<(i-1) ; j++)
                        grid[1][0] = (grid[1][0] + grid[0][1]) % MODVAL;

grid[1][1] = (grid[1][0] + grid[0][0]) % MODVAL;

                grid[0][0] = grid[1][0]; // This value is F(i)
                grid[0][1] = grid[1][1];
        }

printf("%d\n", grid[0][0]);

        return 0;
}