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

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.

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.

Computerizing Philippine Elections

A true computerization of Philippine elections will utilize computer and communications technology in all stages of the electoral process: during registration of voters, the actual casting of ballots, the subsequent canvassing of votes, and the final tabulation and reporting of election results. It can not be just the use of stand-alone automated counting machines, namely PCs with optical mark readers (OMRs) to count votes made on paper ballots, because then, the transmission of precinct results to municipal, provincial, and national tabulation centers becomes a major problem. Stand alone PCs is the technology of the 1980s, and would have been appropriate election technology at that time. Now, we live in the connected world of the twenty-first century, in which people make financial transactions over secure web connections. If secure web is good enough to be trusted for making financial transactions, then it is good enough to be trusted to properly count our votes during elections.

The Election Modernization Act (RA 8436) declares as policy of the State: "to ensure free, orderly, honest, peaceful and credible elections, and assure the secrecy and sanctity of the ballot in order that the results of elections, plebiscites, referenda, and other electoral exercises shall be fast, accurate and reflective of the genuine will of the people". To carry out this policy, "the Commission on Elections (Comelec) ... is authorized to use an automated election system ... for the process of voting, counting of votes and canvassing/consolidation of results of the national and local elections ...". RA 8436 goes further and commands Comelec to " ... acquire automated counting machines, computer equipment, devices and materials and adopt new forms and printing materials ...". I do not understand why a law with such noble purpose needs to specify the use of automated counting machines, an inappropriate technology in these Internet times. The Comelec should respect the policy, the spirit of the law, but implement a mechanism that is more appropriate today.

Internet Infrastructure: Election Hardware

All over the country, one finds computer rental shops that rent out computer time to walk-in customers for use in Internet access, gaming, chat, word processing, etc. Almost all of the better schools have Internet-connected computer laboratories. The ExpressNet and BancNet automatic teller machines are all over the country, and are all connected in a huge nationwide network. In the homes of many families, one finds computers that can connect to the Internet via dial-up telephone lines or via faster always-on DSL connections. Many coffee shops and similar establishments have wifi hotspots that provide Internet access to customers who bring laptops or wifi-enabled mobile phones and PDAs. Many of us carry in our persons mobile phones that can browse the Internet via GPRS or 3G. The connected infrastructure is already in place, except that ExpressNet and BancNet may have to install a temporary Internet gateway during election periods. So there exists locally an essentially connected network of PCs, laptops, PDAs, and mobile phones, that can be used during elections. All that is needed are Comelec server farms connected to the Internet, and software commissioned by Comelec to serve the secure registration web pages and the secure election web pages.

Comelec can rent computer time from all these computer rental shops, schools, banks, and wifi hotspots. It can pay at PHP25.00 per hour per PC, or at PHP2.00 per voter, or some other reasonable price.

The Comelec does not even have to buy the server farm that will be used only during elections, and will be unused for the three years between elections. Instead, the Presidential Commission on Information and Communications Technology (CICT) can acquire the server farm for the government to be used regularly by all government agencies, and during the election season to carry the additional load of registration and election.

Internet Infrastructure: Election Software

On the PCs, laptops, PDAs, and mobile phones, all we need is a web browser program, like Internet Explorer for WindowsOS, and Firefox for WindowsOS and LinuxOS. Internet-capable PDAs and mobile phones already have browser programs built into them. If the Comelec wants to standardize on the OS and browser program, for uniformity of user interface, it could adopt Knoppix or Ubuntu, which are both free boot-from-CD LinuxOS. Every school, computer rental shop, Internet cafe, etc can be given a few UbuntuCDs with which to boot all their PCs, already pre-configured for the special needs of Comelec registration/election.

On each Comelec server in the server farm, we need a database of registered voters, which can be implemented using PostgreSQL or MySQL, both of which have free versions. Also, the CICT or Comelec programmers must write the secure registration and election web pages. They can use PHP on Apache/SSL, both of which are free. If the CICT or Comelec can not afford the cost of programmers, then we can use student programmers from UP, Ateneo, DLSU, Mapua, UST, etc. The government can save a lot of money this way, and the students can submit their programs as their BS degree theses.

With this kind of infrastructure already in place, or easily made available, the government can affordably implement the mandate of RA8436.

Voter Registration over Secure Web

Comelec will designate which among the many computer rental shops, schools, Internet cafes, etc will be used as official registration and election centers. Comelec will determine which computers in these registration centers can be used for registration and election. Let us call these Comelec-approved PCs the ComelecPCs. Voters who will register or vote will not go to their original precincts in the public schools, but instead, go to these Comelec-designated registration and election centers.

The registration program will be running on the Comelec server farm, and will be accessed using the ComelecPCs, under the supervision of Comelec-designated registrars. In the first year of implementation, Comelec does not have to issue voters' IDs, since it does not seem to have the budget for it. Registration will therefore consist of entering the voter's data on the webform, assignment of a voter's ID number, and selection by the voter of his secret password, which only the voter knows. When registration is complete, the voter is given a slip of paper with his name and voter's ID number. The voter may choose to write his secret password on this slip, if he chooses, so that he does not forget his password. To vote, all that the voter needs is his ID number and his secret password.

At any time after registration, the voter may access the Comelec server farm, using the Comelec URL, to change his secret password.

After the first year of implementation, the Comelec may choose to issue SmartCard voters' IDs, which contain computer-readable data about the voter, such as voter's name, voter's ID number, and other useful data. Then the ComelecPCs need to be equipped with SmartCard readers, and that will mean additional expenses.

Voting over Secure Web

On election day, the Comelec server farm will accept votes during the usual voting hours, and stop accepting votes at the end of the voting period. A voter can go to his assigned ComelecPC, and vote using that computer, or he can stay at home and vote using his home PC, or vote using his wifi-enabled laptop at a wifi-hotspot Cafe, or vote anywhere using his mobile phone. This way, no goon can stop a voter from casting his vote. The government must ensure that the Comelec-designated election centers with the ComelecPCs is properly secured from goon-threat.

The official election centers will have Comelec-designated election staff, to help voters who may not be computer-literate.

To vote on election day, a voter must login to the Comelec election URL, by supplying his voter's ID number and his password. Further, he must authenticate himself as a human voter, and not a computer program casting a vote, by typing in text that he is asked to read from a graphic. If the voter forgets his voter's ID number, he can give his name and address, and the webpage will give him his voter's ID number. Then he can login with his voter's ID number and password. If he forgets his password, then the voter can not vote at home. He must then go to his designated election center, and show proof of his identity to the Comelec registrar in the center. The voter's ID number, and two picture IDs (any two of passport, driver's license, SSS ID, GSIS ID, BIR ID), should be sufficient proof of identity. These proofs of identity are scanned, and uploaded to the Comelec website, as part of the voter's login process.

On successful login, the webserver program determines the voter's town, district, and province, and gives him a webpage showing all candidates, their pictures, and a one-liner on their program of government. The voter just clicks his choices, and when he is satisfied he clicks on the SUBMIT button, and his vote is cast.

At the end of the voting period, the webserver program computes town, district, province, and national summaries, and displays the result in a webpage for the world to see.

Conclusion

With such an election system in place, election results are known immediately after the polls close.

There will be problems, like voter's selling the voter's ID numbers and passwords to the highest bidders, or goons controlling an election center, and forcibly extracting voters' ID numbers and passwords from everyone, and voting in their place. No election system will ever be perfect.

The method proposed here, though imperfect, is affordable and workable, and is much better than the current system of manual elections, where even ghosts can vote.

Paul marries Mia

My son Paul married his girlfriend Mia on Saturday, September 9, 2006, at Christ the King Parish Church on Greenmeadows Avenue in Libis, Quezon City. It was a Catholic wedding. During the reception at the Greenmeadows Clubhouse -- one of the principal sponsors, Dr. Angel Chua, the bride's father, Mr Ed Madrid, and I -- we were asked to give advice, some words of wisdom to the newly wed couple.

I was told to keep my piece to two to three minutes only. So here are some "words of wisdom" to the newly wed.

Pareng Ed Madrid said that he didn't really lose a daughter, but instead gained a son, so now he has three sons. I didn't really lose a son, but gained a daughter, so now I have three daughters.

To Paul and Mia:

Call on God to give you the grace to live together as husband and wife, from today, for the rest of your lives. We heard Fr. Bob Pepito say, "That is why a man must leave his father and mother, and cling to his wife, and the two shall become as one". You are two distinct and unique people, and to be as one for the rest of your lives requires tremendous effort and miraculous intervention from God. Make prayer a daily family practice, to call on God to keep you one.

To Paul:

Paul, love Mia. She did not marry you for your money, because you have none. She did not marry you for your good looks, because you have barely half your father's good looks. She must have married you for love. So love her. Love her in your thoughts, words, actions, and omissions. In what you do or not do, in what you say or not say, in what you think, you must be guided by you love for her. Do not cheat, or take another woman or man to bed, but her.

A Father's Blessing:

A Jesuit priest once told me that a father's blessing, like that of Abraham to Isaac, is like God's blessing. So I now give you my blessing: May God bless you Paul and Mia, and may he give you happiness and peace, and if He wills, may he give you children and riches beyond count. And may God bless us all.

What "AmboSpeak" is about

AmboSpeak will be a commentary about the Filipino, as I see the Filipino from my narrow point of view. It will be a once-in-a-while commentary, since I am not too good at writing, but I will write whenever the Spirit moves me, and I have something really important to talk about, or whenever I have very strong opinions about an issue -- whether academic, religious, political, etc.

This is just an ice-breaker. You will hear more from me.