Wednesday, October 04, 2006

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:
Nbipartite number

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[].


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(); }

Tuesday, October 03, 2006

Computerizing Philippine Elections: The Comelec Computers

The Comelec has spent a lot of money on those PCs with OMR (Optical mark readers). PCs are delicate machines and get obsolete very quickly. If you keep them in storage, like Comelec is doing now, and the storage facilities are not the proper kind for sensitive electronic equipment, then they may break down in storage, or if they don't, they may become obsolete if stored for too long. Just compare the 300MHz Intel Celerons of a few years back to today's 2.8GHz Intel Core Duos. You do not want to use the 300MHz Celerons today because, either they are just too slow for your needs today, or they have already broken down. That is why in my original article, I suggested that Comelec should not buy PCs for use at the voting precincts, because Comelec will end up with obsolete or broken-down PCs in just two to three years. That is why I suggested that Comelec rent PCs from schools, Internet cafes, banks, etc. What Comelec should buy are the PC servers for the Comelec server farms. Comelec should also buy bandwidth to connect their servers to the Internet.

We are a country consisting of more than seven thousand islands, separated by seas. If you use the Comelec PC/OMRs to produce precinct summaries on diskettes, which is what Comelec wanted to do, you still had that serious problem of moving those diskettes via land and sea, to the election tabulation Centers. God sent the Internet to these seven thousand islands as an instrument of unity -- to unite our people in one communication link, so that our voices and votes can be heard instantly, just seconds after we cast our votes. What buses and sea-going vessels failed to do, the Internet will -- that is, connect our people together, so that our voices can be heard as one, instantly!

What do you do with those Comelec PC/OMRs? They are already here, laying idle in the Comelec warehouses, probably slowly breaking down in storage, their cmos batteries discharging, the DIMM ram connectors oxidizing, etc. Do we just let billions of pesos of our tax money go to waste? I suggest that we use these machines. We equip them with network cards, and on election day, we place them in the Internet cafes, at school computer labs, in banks and in offices that have Internet connection. And we use them for paper-ballot voting, for those people who are afraid of touching computers. The only difference is, as soon as the voter finishes accomplishing his paper ballot, he can stick it into the OMR, which reads his votes, sends his vote via the Internet to the Comelec server farm, so that his vote is instantly counted, just like the vote of everyone else.

So now, people can vote using [PC/Internet/browser] in cafes, schools, or at home. People can also vote using the [ComelecPC/OMR/Internet/paper-ballot] in Internet cafes, and schools. People can also vote using [mobile phone/GPRS/Internet] anywhere they are.

Just take your pick.

Sunday, October 01, 2006

Computerizing Philippine Elections, Part 2

The biggest complaints about the method of computerization that I proposed earlier are: (1) There are many far flung areas in the Philippines where there are no roads, no electricity, no computers, and no Internet. (2) Many parents and grandparents are computer illiterate, or they cannot handle the mouse firmly to click on a candidate's name.

The first problem is easy to solve. Let us allow people in those far flung areas where there are no facilities to vote the old way -- teachers commissioned by Comelec go to those far flung areas, carrying ballots, ballot boxes, and other election paraphernalia, on horseback, if necessary. People will vote the same old-fashioned way -- on paper ballots. Their votes get counted the same old slow way. Their votes will be counted, but will be included in the national count many months after the elections are over, because manual counting and manual transporting of election results take time. The rest of the country -- those that live in the big towns and cities, where there are computers and Internet -- can vote in the new manner that I proposed. Their votes are counted and the results of voting are announced a few seconds after voting hours close on election day. The will the people, the great majority of whom live in the big towns and cities, is immediately known. People who live in those far-flung areas are too few for their votes to change the results already made known by the Internet count. Isn't knowing the will of the people the reason for elections, in the first place?

The second problem of computer illiteracy can be eased somewhat by proper choice of user interface. The election web page can allow the user to vote using the mouse, or the keyboard, or the touch screen if it is available. Voters who do not know how to use a mouse can use the keyboard instead; candidates will be assigned letters on the qwerty keyboard and all that the voter needs to do is press the key corresponding to his candidate. For multi-page elections, when there are many candidates, some keys can be assigned to do the function of "previous page" and "next page". Whether the voter uses the mouse or keyboard or touch screen to vote, the voter still needs to authenticate himself to the election program, and he does this by logging in (typing) with his voter's ID number and password. If the voter can not even do this, then he has to use the old fashioned way of voting with a paper ballot.

The mobile phone can also be used to vote. Since the phone has only ten numbers, then only eight candidates can be shown per web page, since two keys need to be reserved for "page up" and "page down". Yet the phone can be used for voting by those who are phone savvy, and we Filipinos are well-known for being phone-savvy.

These two problems can not be solved immediately. It will take many years before all barrios had electricity, computers, and Internet. It will take many years, maybe forever, before every Filipino can learn to use computers or mobile phones. This does not mean that we should not try to use this wonderful technology, which is already here in our midst, to effect clean, orderly, honest, and fast, elections.