ACSU Programming Competition

1 March 1997

Results and Solutions

Problems

The problems were available as a Microsoft Word document. However, I have been informed that the document was infected with the Word macro virus. I will repost the problems once the virus has been removed. If you'd like to see some sample problems, go to the 1996 ACM International contest problelms. Keep in mind that our problems will be similar, but much easier.

Results

The top three contestants were:
  1. Erik Dangremond, 3 correct
  2. Vladimir Livshits, 2 correct
  3. Rachit Siamwalla, 2 correct

Solutions

Problem 1 -- Urban Elevations

There were no correct submissions to this problem, so I will not post the solution. One submission did come close. Unfortunately, it listed the visible buildings in numerical order, not west-to-east order.

Problem 2 -- Stamps

There was only one correct submission to this problem. Here is my solution. 
/* Stamps
   The problem statement is a bit vague. We're supposed to compute the
maximal coverage for each stamp denomination scheme, and output the coverage
and the scheme with highest maximal coverage. The problem is ambiguous in
the case when two schemes have the same coverage. The way this solution is
written, whichever scheme has the least number of stamps is output. If both
schemes have the same number of stamps, then output whichever was input
first. */

#define S 10       /* max # of denominations per scheme */
#define N 10       /* max number of schemes */
#define MAX 100    /* max denomination */

int denom[N][S];   /* denom[i][k] is denomination of stamp k from scheme i */
int num[N];        /* num[i] is number of denominations in scheme i */
int cover[N];      /* cover[i] is maximum cover of scheme i */

void process(int i, int s)
/* assigns to cover[i] the maximum cover of stamp scheme i */
{
int size;          /* maximum possible cover possible with stamps */
int j;             /* index through coverable amounts */
int k;             /* index through stamp denominations */
int array[S*MAX];  /* array[j] is # of stamps required to cover j cents */

size = denom[i][num[i]-1] * s + 1;   /* maximum possible cover */
for (j = 0; j < size; j++)           /* initialize to all uncovered denoms */
   array[j] = 0;
for (k = 0; k < num[i]; k++)         /* can cover denoms that are stamps */
   array[denom[i][k]] = 1;
for (j = 1; j < size; j++)
   {
   if (array[j] == 0)
      break;
   for (k = 0; k < num[i]; k++)
      if (j+denom[i][k] < size)
         if (array[j] < s)
            if ((array[j+denom[i][k]] == 0) ||
                (array[j+denom[i][k]] > array[j]+1))
               array[j+denom[i][k]] = array[j] + 1;
   }
/* j is index of first amount we can't cover */
cover[i] = j-1;
}

void main(void)
{
int s;    /* maximum number of stamps on an envelope */
int n;    /* number of schemes */
int i;    /* scheme index */
int j;
int m;    /* index of scheme with max cover */

do {
   scanf("%d", &s);
   if (s == 0) break;
   scanf("%d", &n);
   for (i = 0; i < n; i++)
      {
      scanf("%d", &(num[i]));
      for (j = 0; j < num[i]; j++)
         scanf("%d", &(denom[i][j]));
      process(i, s);
      }
   m = 0;
   for (i = 1; i < n; i++)
      if ((cover[i] > cover[m]) ||
          ((cover[i] == cover[m]) && (num[i] < num[m])))
         m = i;
   printf("max coverage = %3d : ", cover[m]);
   for (j = 0; j < num[m]; j++)
      printf("%3d", denom[m][j]);
   printf("\n");
   } while (1);
}
The test input was: 
5
2
4 1 4 12 21
4 1 5 12 28
10
2
5 1 7 16 31 88
5 1 15 52 67 99
6
2
3 1 5 8
4 1 5 7 8
1
3
3 1 2 3
3 1 2 4
2 1 2
2
3
3 1 2 3
3 1 2 5
2 1 3
2
2
2 1 50
1 1
3
3
5 1 4 8 98 99
4 1 3 9 27
4 1 4 8 98
3
2
4 1 3 9 27
4 1 4 7 98
0
The correct output was: 
max coverage =  71 :   1  4 12 21
max coverage = 409 :   1  7 16 31 88
max coverage =  48 :   1  5  7  8
max coverage =   3 :   1  2  3
max coverage =   7 :   1  2  5
max coverage =   2 :   1
max coverage =   7 :   1  3  9 27
max coverage =   9 :   1  4  7 98

Problem 3 -- The Jonestown Treasury Problem

This problem reduces to the following: Given n (the number of people in the circle), and k (the number of people the punch is passed), determine l (the last person left alive) assuming that the punch starts at person 1. The order in which the people die enforces a permutation on the integers 1 to n. This permutation is called the Josephus permutation.

I am looking for a closed-form solution to this problem. If you know of one, please let me know.

My solution is: 

/* Jonestown Treasury Problem */

#define N 100      /* max number of people */

int last(int n, int k)
/* returns the last person to die, with n people, passing k times, assuming
that the punch starts on person 1 (person 0, starting index at 0)
NOTE: returns the index of the person STARTING AT 0 !!! */
{
int person[N];     /* 1 means person is alive, 0 means dead */
int i;             /* person who has punch */
int count;         /* number of times punch passed to alive person */
int q;

for (i = 0; i < n; i++)
   person[i] = 1;    /* everyone starts alive */
i = 0;               /* assume punch starts at person 0 */
person[i] = 0;       /* person with punch dies */
for (q = 1; q < n; q++)
   {
   count = 0;
   while (count < k)   /* pass punch k times */
      {
      i = (i + 1) % n; /* pass punch */
      if (person[i])
         count ++;     /* increment if alive person in circle */
      }
   person[i] = 0;      /* person with punch dies */
   }                   /* person i was last to die */
return i;
}

void main(void)
{
int n, k, t, m;    /* defined by problem */
int l;             /* last person to die if start at 1 */

do {
   scanf("%d %d %d", &n, &k, &t);
   if (n == 0) break;
   l = last(n, k);
   m = (t-1 - l + n) % n + 1; /* rotate solution so person t is last to die */
   /* need the -1 and +1 because of indexing at 0 */
   printf("With %d people, passing %d times, keeping %d alive, start punch at person %d.\n",
      n, k, t, m);
   } while(1);
}
The test input was: 
1 1 1
2 1 1
5 1 2
13 9 6
25 25 13
11 99 11
17 22 17
12 7 1
98 2 76
65 43 30
0 0 0
The correct output was: 
With 1 people, passing 1 times, keeping 1 alive, start punch at person 1.
With 2 people, passing 1 times, keeping 1 alive, start punch at person 2.
With 5 people, passing 1 times, keeping 2 alive, start punch at person 3.
With 13 people, passing 9 times, keeping 6 alive, start punch at person 4.
With 25 people, passing 25 times, keeping 13 alive, start punch at person 5.
With 11 people, passing 99 times, keeping 11 alive, start punch at person 6.
With 17 people, passing 22 times, keeping 17 alive, start punch at person 7.
With 12 people, passing 7 times, keeping 1 alive, start punch at person 8.
With 98 people, passing 2 times, keeping 76 alive, start punch at person 9.
With 65 people, passing 43 times, keeping 30 alive, start punch at person 10.

Problem 4 -- Good But Not Perfect

This solution is a slightly modified version of the one by Wilson Huang. 
/* Good But Not Perfect */

void factor(int n, int a[], int *num)
/* returns the factors of a number */
{
int i;

for (i = 2; i < n; i++)
   if (n % i == 0)
      {
      a[0] = i;
      factor(n/i, a+1, num);
      *num = *num + 1;
      return;
      }

/* n is prime */
a[0] = n;
*num = 1;      
}

int sum_digits(int n)
/* sums the digits of a number */
{
int sum = 0;

while (n > 0)
   {
   sum += n % 10;
   n /= 10;
   }
return sum;
}

int good(int n)
/* returns 1 iff n is a good number */
{
int num;          /* number of factors of n */
int array[1000];  /* holds factors of n */
int i;
int sum_fact;     /* sum of digits of prime factors of n */

factor(n, array, &num);
sum_fact = 0;
for (i = 0; i < num; i++)
   sum_fact += sum_digits(array[i]);
return sum_fact == sum_digits(n);
}

void main(void)
{
int n;

do {
   scanf("%d", &n);
   if (n == 0) break;
   if (good(n))
      printf("%d is a good number\n", n);
      else
      printf("%d is not a good number\n", n);
   } while (1);
}
The test input was: 
22
4001
4049
4111
4191
4209
4253
4369
4373
4423
4457
4507
4513
4621
4637
4702
4733
4832
4855
4919
4999
6036
44
100
102
333
864
918
1001
2222
3984
4096
5436
9999
0
The correct output was: 
22 is a good number
4001 is a good number
4049 is a good number
4111 is a good number
4191 is a good number
4209 is a good number
4253 is a good number
4369 is a good number
4373 is a good number
4423 is a good number
4457 is a good number
4507 is a good number
4513 is a good number
4621 is a good number
4637 is a good number
4702 is a good number
4733 is a good number
4832 is a good number
4855 is a good number
4919 is a good number
4999 is a good number
6036 is a good number
44 is not a good number
100 is not a good number
102 is not a good number
333 is not a good number
864 is not a good number
918 is not a good number
1001 is not a good number
2222 is not a good number
3984 is not a good number
4096 is not a good number
5436 is not a good number
9999 is not a good number

Problem 5 -- Secret Agent Man

My solution is: 
/* Secret Agent Man */

void read_int(char *string, int *x, int *i)
{
sscanf(string+(*i), "%d", x);
(*i) += abs(*x) / 10 + 2 + ((*x) < 0 ? 1 : 0);
}

int give(char *string, int rec, int *i)
/* Based on the observation that it is not necessary to perform any kind
of breadth-first search. The head of the organization can reach all of the
spies, so you just have to find one spy that can reach the recipient spy. */
{
int agent;
int a2;

for (agent = 0; 1; agent ++)
   {
   while (1)
      {
      read_int(string, &a2, i);
      if (a2 < 0) break;
      if (a2 == rec) return agent;
      }
   if (strlen(string+(*i)) < 2) break;
   }
return -1;
}

void main(void)
{
char line[80];
int i;
int rec;       /* recipient of message */
int n;         /* number of messages to process */
int who;       /* who to give message to */
int m;

gets(line);
sscanf(line, "%d", &n);

for (m = 1; m <= n; m ++)
   {
   gets(line);
   i = 0;
   read_int(line, &rec, &i);
   who = give(line, rec, &i);
   if (who == -1)
      printf("Message %d cannot be delivered. Agent #%d is unreachable.\n",
         m, rec);
      else
      printf("Message %d, destined for agent #%d, should be given to agent #%d.\n",
         m, rec, who);
   }
}
The test input was: 
4
3 4 1 -1 2 -1 -4 0 1 -1 3 -1
2 3 1 -2 0 -1 3 0 -1 1 3 0 -6
0 1 -1 2 -1 3 -1 4 -1 5 -1 0 -1
0 -1 -1 -1 -1 -1 -1 -1 -1 -1
The correct output was: 
Message 1, destined for agent #3, should be given to agent #4.
Message 2 cannot be delivered. Agent #2 is unreachable.
Message 3, destined for agent #0, should be given to agent #5.
Message 4 cannot be delivered. Agent #0 is unreachable.
Last updated 7 September 1997.