Written by Himangshu Saikia on 12 March 2008
Well this one was long due, being an ACM first timer, I just had to write this post. If someone reading this is intending to get useful how-to’s for the ICPC, you’ve come to the wrong place 😉 But you can always check out the problems here. The final standings for the Kanpur site contest are listed here.
Morning of the first day we were two men, Harpreet and myself, sans Malik. Nothing much except a good keynote speech from an IBM fellow, during which I was mostly sleepy. Owing to Antaragni, the campus looked greener, with live drama and street dancing couples hogging the road to the lecture halls, IITK offered a more-than-picturesque scene. The dinner was amazing, with great people everywhere, and the Finnish band ‘poets of the fall’ were gearing up for the rock show, and yeah, Malik was there at last. We were entertained by the huge crowds which had gathered for the cult-fest, especially the ones at the dance events, they were amazing enough to leave a feeling of sadness, considering how many years it’ll take for IITG to come to this level.. *sigh*
The next day was different. The contest was going to be tough, as expected. And our team doesn’t gel pretty well. Maybe this was the first time we were doing group programming. At the breakfast table Malik was greeted by one of his friends from IITB, whom he had met in France, and soon enough the other introductions followed. It was nice and at the same time intimidating, to be competing with these guys. Malik’s buddy was the JEE AIR 10 of our time, and if that wasn’t enough, the AIR 1 was also in his team 🙂 Cool isn’t it? And pretty much expected… C’mon, even if you got an AIR of 100, doesn’t mean you get IITB CS right?! These people were demigods, and they’ve been to the world finals at Tokyo last year, winning the Coimbatore contest. Man, this one’s gonna be good. 😀
Finally we were there, inside the CC, seated next to a single terminal and lotsa blank sheets. There were seven problems in all, and we had five hours to solve them. Here’s a short description of each.
Alpha-triangle: Objective was to find a triangular combination from a given set of words such that |AB| = |BC| = |CA| and that A.head = C.head, A.tail = B.head, and B.tail = C.tail. Words can be concatenated but cannot be broken down.
Baby: Variations of the n-queens problem, where from an n-rook position, an n-queen position was to be derived, using minimum number of moves.
Card: The magician’s card trick problem, where from a given combination of four cards belonging to four different suits, a missing fifth card should be determined.
Deposit: A variation of the compound interest problem.
Expression: Given a set of characters, an operation table on those characters and a number of strings, the LR and RL equivalence of the strings are to be determined.
Fable: A cat and mouse game in which the least number of steps to change from an initial configuration to a final one is desired.
Garrison: A typical dfs problem to determine the co-ordinates of unreachable vertices in a graph.
Eventually we couldn’t solve problems A and B. And landed up 16th place. NITT guys (read: Prasanna) completed all of them in less than three hours. IITM, IIITH, Univ Moratuwa guys from Sri Lanka and the girls from Taiwan Univ solved all seven in order of increasing time(ranking). It was depressing enough for me and Malik to keep roaming around and not even attend the prize distribution ceremony. Harpreet had left later that evening, and the two of us dared to queue up for the Atif Aslam show amidst thousands of hard-core fanatics. Alas, we had no passes and all there was for us was to watch football in the Hall IX canteen before going to sleep. All in all a good experience, reality check so to say. The only consolation? Tie-ing with the team we met at the breakfast table 🙂 Atleast we were not last year’s regional champs to be pulling our hair apart!