Saturday, May 31, 2008

My very first algorithm problem experience

Back in 1997, my Informatics teacher, Yulia Lvovna Vorontsova, has suggested that I participate in Moscow regional (Moscow consists of 10 regions: Central, Northern, Northwestern, Western, ..., Northeastern, and (guess?) Zelenograd) olympiad in informatics.

The olympiad had three problems to offer, but the only one I remember now is: given an integer N not exceeding 10000, output 2 to the power of N.

I've never solved algorithm problems before that olympiad, so everything was new and difficult to me. Luckily, I knew how to read or write files in Pascal. I've solved problems in Pascal then, but I'll use Java for explanations here.

I've thought about keeping an array of digits. This array was fixed-size, and the first element contained the most significant digit (which was always zero, of course, as the size was chosen with a bit of margin). I can reconstruct my code as (this is definitely a very inaccurate reconstruction, but I don't remember much from 11 years ago):
 1: String power(int n) {
2: int[] digits = new int[5000];
3: digits[4999] = 1;
4: for (int i = 0; i < n; ++i) {
5: int p = 0;
6: for (int j = 4999; j >= 0; --j) {
7: int r = p + 2 * digits[j];
8: p = 0;
9: while (r > 10) {
10: p += 1;
11: r -= 10;
12: }
13: digits[j] = r;
14: }
15: }
16: String s = "";
17: for (int i = 0; i < 5000; ++i)
18: if (s.length() > 0 || digits[i] > 0)
19: s += digits[i];
20: return s;
21: }
This code suffers from several common problems (like repeating 5000 and 4999 all over the place), but I'm still amazed how could I get it working in 6th grade.

The rules for that contest were standard IOI-style, that means we've had to write solutions for several problems during the contest, and after the end of contest they were checked on several testcases each, and getting correct answer on each testcase was scored by some amount of points. Of course, the checking was done manually: one of the judges sat next to you and ran your program in command line (it was DOS everywhere at that time) of Norton Commander.

And you know what? The above program passed all testcases but one. The testcases were (not exactly, but the idea should be understandable): 1, 2, 5, 10, 10000. And apparently the answer for 10000 was incorrect. Can you spot the bug in the above code?

Strange, but I remember comparing the correct and wrong answers for that testcase now. The correct answer started with 1995, and my program output something that started with 1994. How could there be such tiny error? Because r > 10 should be r >= 10. Digits of '10' are not good :)

That was my very first problem, and my very first bug. Everything did work out well in the end, as I advanced to Moscow-wide olympiad anyway, and then to Russian olympiad, and then...

8 comments:

  1. Hi, are you going to keep this blog updated?

    ReplyDelete
  2. Inspiring and informative to the thousands of fans that you have! keep writing! :)

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. I guess the whole point was to introduce 6th graders to the idea of integer overflow?

    The kids these days have it so easy...

    in python:

    >>> def power(int):
    ... two2the = 1
    ... for i in range(int):
    ... two2the = two2the * 2
    ... return two2the
    ...
    >>> power(1)
    2
    >>> power(2)
    4
    >>> power(5)
    32
    >>> power(10)
    1024
    >>> power(10000)
    19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376L

    ReplyDelete
  5. Nice story ...u got more stories like this one? :)
    and your code works fine for values upto 16609 :D
    Good Luck & Have Fun from Havis

    ReplyDelete
  6. There is a bug in your code :)
    Not while (r > 10) but while (r >= 10)

    ReplyDelete
  7. Beatdbest 31 HimanshuMay 10, 2013 at 1:34 PM

    seeems very interesting..:)

    by the way can u please help me to decide from where  i should practice questions? i am confused as there are lot of sites to get started. i have all the theortical knowledge of algorithms.

    ReplyDelete