Exciting ICPC World Finals 2015 in Marrakech

Also this year did we participate in the 39^th ACM Intercollegiate Programming Contest World Finals, held in Marrakech, Morocco; the ‘we’ being: the “I Can’t Pronounce Catachtonic” team composed of Yaseen Hamdulay, Robert Spencer, and Sean Wentzel, and me as coach, from the University of Cape Town. We’re the only team from Sub-Saharan Africa, and one of 10 teams in the Africa & Middle East Region, of a total of 128 teams that participated, who were selected from 38160 contestants from 2534 universities of 101 countries on 6 continents that competed in the qualifying regionals.

One year more of studying, practice, and training wiser, our last training session indicated we might be a contender for A&ME regional winner. (For overall winner, we’d need to have and do what the medalist teams do, such as starting training in your early teens and winning IMO and IOI, weekly training sessions, monthly local contests, week-long training camps by previous medal winners, designated labs, competitive programming courses, scholarships and whatnot that other coaches talked about regarding preparations. At this point in time, we don’t have nearly enough such resources.)

The ‘first to solve a problem’ did so in a mere 5 minutes, from opening the envelope with the problems to having submitted the right code! This was Problem A: Amalgamated Artichokes, and the honour went to Peking University, setting a new record. The UCT team did so in 14 minutes, due to being sidetracked with another first. Then it was like: is this the only ‘easy’ problem, and the rest as grueling as last year’s problem set, and will it come down to ‘the team who solves the second problem will win A&ME’? Soon thereafter, the UCT team solved a second problem—but then so did two other A&ME teams, upping the ante that perhaps the 3^rd solved problem would be the decider. UCT was still leading—at some point even on 27^th position in the overall scoreboard. I got too nervous, and went for lunch, hoping they would have solved a 3^rd one upon returning to the scoreboard. And lo an behold, they had, still leading for A&ME, though overall moving down to the 50s-70s in the dynamic scoreboard. To make matters more exciting for spectators, there were 5 PCs with shared screens and video, so one can see one’s team live on webcam, and see what they are coding, every single keystroke. Nifty, imho; nail-biting for some coaches of medal-contenders.

Right before the scoreboard was frozen regarding solved problems (for the last hour of the 5-hour nonstop contest), the American University of Cairo had solved 4 problems, surpassing UCT, but at the cost of a lot of penalty time due to a few wrong submissions, so if the UCT team would solve another problem, and Cairo not, then we’d win A&ME region on time difference. I could see UCT submitted a solution, hoping it was right. Then, sitting in the spectator area, and the Cairo team sitting near that, the scoreboard updated that they had submitted a solution for their 5^th problem… and then came the involuntary reaction of its team members, being a mini-cheer. And UCT did not surpass that in the last 30 minutes. Overall, this placed Cairo on 75^th place in the final standing, winning the prize for the A&ME region, and UCT just below that, as second in the A&ME region on a very respectable 83, therewith also receiving congrats from other participants, coaches, and interested spectators.

The “I Can’t Pronounce Catachtonic” team from UCT

So, relatively, they did well, having solved an impressive 4 problems, being A, D, I, and J, and all correct on first submission. This placed UCT ahead of other well-known, and arguably better resourced, universities, such as Uni Illinois at Urbana-Champaign, Virginia Tech, IIIT, Uni Western Australia, Cornell, Moscow Aviation, Calgary, and Rice. That said, at the other end of the spectrum, St. Petersburg ITMO broke the record of having solved all contest problems—a first of all the 39 editions of the ICPC world finals—and first to solve problem G. Moscow State Uni came second (11 problems solved out of 13, with first to solve B and H), Uni of Tokyo came third (also 11 problems solved, with first to solve J and K), and the fourth gold medal went to Tsinghua University (10 problems solved, and first to solve C).

If you don’t feel like solving the problems yourself, but still want to know the answer to, among others, cheese slicing, shooting asteroids, tile cutting, and the qanat irrigation system, then have a look at former UCT coach Bruce Merry’s analysis of the problems and directions of the solutions.

All in all, it was a good World Finals. An the food was good, the weather good, the other events too (including a fun camel ride), meeting up with coaches and some contestants met last year, the CLI symposium brought some useful information as well, and Steven and Felix Halim generously gave me a hardcopy of their Competitive Programming 3 book. Sean won the ICPC Quest, so a 1^st prize was brought back to Cape Town.

The planning for participating with a strong UCT team next year has commenced; the 2016 finals will be in Thailand.

Advertisement

First tractable encoding of ORM conceptual data models

For (relatively) many years I’ve been focusing on as-expressive-as-possible languages to represent information and knowledge, including the computationally impractical full first order logic, because one would/should want to be as precise as possible and required to represent the subject domain in an ontology and universe of discourse for the application in a conceptual data model. After all, one can always throw out the computationally unpleasant constructs later during the implementation stage, if the ontology or conceptual data model is intended for use at runtime, such as OBDA [1], test data generate for verification [2], and in the query compilation stage in RDBMSs [3]. The resulting slimmed theories/models may be different for different applications, but then at least the set of slimmed theories/models share their common understanding.

So, now I ventured in that area, not because there’s some logic x and conceptual modeling language y has to be forced into it, but it actually appears that many fancy construct/features are not used in publicly available conceptual data models anyway (see data set and xls with some analysis). The timing of the outcome of the analysis of the data set coincided with David Toman’s visit to UCT as part of his sabbatical and Pablo Fillottrani’s visit, who enjoyed the last exchange of our bi-lateral project on the unification of conceptual data modelling languages (project page). To sum up the issue we were looking at: the need for run-time usage of conceptual data models requires a tractable logic-based reconstruction of the conceptual models (i.e., in at most PTIME), which appeared to hardly exist or miss constructs important for conceptual models (regardless whether that was ORM, EER or UML Class Diagrams), or both.

The solution ended up to be a logic-based reconstruction for most of ORM2 using the Description Logic, which also happens to be the first tractable encoding of (most of) ORM/ORM2. With this logic, several features important for conceptual models (i.e., occur relatively often) do have their proper encoding in the logic, notably n-aries, complex identification constraints, and n-ary role subsumption. The, admittedly quite tedious, mapping

Low resolution and small version of our DL15 poster summarising the contributions.

captures over 96% of the constructs used in practice in the set of 33 ORM diagrams we analysed (see data set). Further, the results are easily transferable to EER and UML Class diagrams, with an even greater coverage. The results (and comparison with related works) are presented in our recently accepted paper at the 28th International Workshop on Description Logics (DL’15) that will take place form 7 to 11 June in Athens, Greece.

The list of accepted papers of DL’15 is available, listing 21 papers with long presentations, 16 papers with short presentation, and 26 papers with poster presentations. David will present our results in the poster session, as it’s probably of more relevance in the conceptual modelling community (and I’ll be marking exams then), and some other accepted papers cover more new ground, such as casting schema.org as a description logic, temporal query answering in EL, exact learning of ontologies, and more. The proceedings is will be online on CEUR-WS in the upcoming days as volume 1350. I’ve added a mini version of our poster on the right. I tried tikzposter, as they look really cool, but it doesn’t support figures (other than those made in latex), so I resorted to ppt (that doesn’t support math), wondering why these issues haven’t been solved by now.

Anyway, more about this topic is in the pipeline that I soon hope to be able to give updates on.

 

References

[1] Calvanese, D., Keet, C.M., Nutt, W., Rodriguez-Muro, M., Stefanoni, G. Web-based Graphical Querying of Databases through an Ontology: the WONDER System. ACM Symposium on Applied Computing (ACM SAC’10), March 22-26 2010, Sierre, Switzerland. pp 1389-1396.

[2] Toman, D., Weddell, G.E.: Fundamentals of Physical Design and Query Compilation. Synthesis Lectures on Data Management, Morgan & Claypool  Publishers (2011)

[3] Smaragdakis, Y., Csallner, C., Subramanian, R.: Scalable satisfiability checking and test data generation from modeling diagrams. Automation in Software Engineering 16, 73–99 (2009)

[4] Fillottrani, P.R., Keet, C.M., Toman, D. Polynomial encoding of ORM conceptual models in . 28th International Workshop on Description Logics (DL’15). CEUR-WS vol xx., 7-10 June 2015, Athens, Greece.