Problem D: 2006 Programming Contest World Finals

In the 2006 World Finals of the ACM International Collegiate Programming Contest (ICPC) which was held in San Antonio, Texas, in April, the following was given as Problem D.

"Given a positive integer N, where N < 100000, find the smallest bipartite number that is greater than and a multiple of N. A bipartite number is any positive integer that contains exactly 2 distinct decimal digits s and t such that s is not 0 and all occurrences of s precede all occurrences of t. For example 44444411 is bipartite (s is 4 and t is 1), So are 41, 10000000, and 5555556. However, neither 4444114 nor 44444 are bipartite".

For example, for the numbers N in the first column the smallest bipartite number that is greater than and a multiple of N is given in the second column:

N	bipartite number
125	500
17502	77778888
2005	222555

The code to determine if a given number X is bipartite, is fairly easy to write. Here X is a multiple of N. One code to do it, int isbipartite(X), is given below, where a return value of 1 is true, and 0 is false.

The obvious solution to the problem is, given N, let X take the values 2N, 3N, 4N, ... , and the first of these values that is bipartite is the solution. The only problem with this solution is, for many values of N, the method takes too much time, and your program exceeds the execution time limit set by the judges.

Last night, I tried to compute a table, that for N=1 to 99999, determines which smallest multiple of N, namely which of 2N, 3N, 4N, ... , is a bipartite number. The way I did this is to compute 2*1, 2*2, 2*3, 2*4, ... , 2*99999, and if any one of these is already bipartite, I did not include it any more in the next step of the table construction. In the next step, I computed 3*1, 3*2, 3*3, 3*4, ... , 3*99999, and if any of these is already bipartite, then I did not include it anymore in the next step. And so on. I ran the program overnight, and this morning when I woke up, my table construction program has only found bipartite numbers for 700 of the 99999 numbers.

Then over breakfast, I discovered a better and quicker brute force solution. The method involves three steps. (1) Generate all the bipartite numbers that will fit in a integer of type long long (up to 18-20 decimal digits). This step took a few seconds with the program genbipartite() given below. (2) Sort the output of step 1, into a file bipartite.list. This step also took a few seconds. Steps (1) and (2) can actually be done using the Unix command

genbipartite | sort > bipartite.list

(3) For each number X in bipartite.list, from smallest to largest, determine which of the numbers N from 1 to less than X is an exact divisor of X, and if so, and if N does not have a bipartite number assigned to it yet, assign X as the bipartite number for N. This step was done with the function construct_table(). This last step took less than four minutes. Now you have a table that gives for each positive integer N from 1 to 99999 the number X that is greater than N, a multiple of N, and bipartite. The final solution will just involve table look up. All three steps can be combined using the Unix command

genbipartite | sort | construct_table > solution.c

Of course you still need to complete the program solution.c to do the look up in the table biparttab[].

Appendix

Here are the C program snippets that I mentioned above. They might be a little too much for the casual reader, so I have put them all together at the end of this post.

int isbipartite(long long X)
{
  int c, d, e, j, k;
  char numText[22];
  sprintf(numText, "%lld", X);
  for(c=numText[0], j=1; (d=numText[j]) != '\0'; ++j) {
    if(c != d) break;
  }
  if(d == '\0') return 0;
  for(k=j; (e=numText[k]) != '\0'; ++k) {
    if(d != e) break;
  }
  if(e == '\0') return 1;
  return 0;
}

/* genbipartite.c */

void genbipartite(void)
{
  int j, k;
  long long jj, kk, m, n, x;
  for(j=2; j<=18; ++j) {
    for(k=1; k < j; ++k) {
      for(m=0, jj=k+1; jj <= j; ++jj)
        m = m*10 + 1;
      for(n=0, kk=1; kk <= k; ++kk) {
        m = m*10;
        n = n*10 + 1;
      }
      for(jj=1; jj <= 9; ++jj) {
        for(kk=0; kk <= 9; ++kk) {
          if(jj == kk) continue;
          x = jj*m + kk*n;
          fprintf(stdout, "%018lld\n", x);
        }
      }
    }
  }
}

int main() { genbipartite(); }

/* construct_table.c */

struct tbl {
  int done;
  long long multiple; 
};

struct tbl entry[100000];

void construct_table(doid)
{
  int j;
  long long x;
  for(j=1; j < 100000; ++j) {
    entry[j].done = 0;
    entry[j].multiple = 0;
  }
  while(fscanf(stdin, "%lld\n", &x) == 1) {
    for(j=1; j < 100000; ++j) {
      if(j >= x) break;
      if(x % j == 0) {
        if(entry[j].done) continue;
        entry[j].multiple = x;
        entry[j].done = 1;
      }
    }
  }
  fprintf(stdout, "long long biparttab[99999] = {\n"); 
  for(j=1; j < 100000; ++j) {
    fprintf(stdout, "%lld,\n", entry[j].multiple);
  }
  fprintf(stdout, "};\n");
}

int main() { construct_table(); }