125 Ad spot 125 Ad spot

ACMSolver or Art of Programming? 24 X 7 Updates

From 2002 ACMSolver is campaigning for free programming knowledge!

4 June 2011 Comments Off

Steven Halim’s book: Slides Download

Sample codes for the data structures and algorithms mentioned in the book:
NEW (but not yet stable): C++ and Java codes.zip (latest update 24 January 2011)

PDF slides for coaches/instructors/lecturers/students who wants to do self-study:

Material (public version)
sample_chapter_1.pdf ; skillset.xls ; and paper on CS32333
week02_ds_libraries.pdf ; and Fenwick Tree paper
(Union Find and Segment Tree are skipped)
week03_paradigms.pdf; A* search, and IDA* search
week04_dp_1.pdf; DP 0-1 Knapsack; and DP TSP
week05_graph_1.pdf (MST is skipped)
week06_graph_2.pdf (Euler graph is skipped)
week08_dp_2.pdf (some interesting examples are skipped)
week09_graph_3.pdf (max flow/bipartite graph variants are skipped)
week10_maths.pdf (there are so many topics…, many are skipped)
week11_string.pdf (DP on string has been discussed earlier)
week12_geometry.pdf (plane sweep; intersection problems skipped)
1 June 2011 Comments Off

QuestToSolve.Com | A nice attempt to improve problem solving skills

A nice attempt to improve problem solving skills: http://www.questtosolve.com/

“(…)In the spirit of Steven Halim’s World of Seven: Methods to Solve website, that posted the solutions to hundreds of problems for the University of Valladolid (UVa) Online Judge website, we have decided to not only tackle UVa problems in preparation of ACM ICPC competition, but also to post the answers that we find for each problem in the hope that our repository of solutions will be as great an informational resource to programmers everywhere as Steven’s was.

Who are we? Two students majoring in Computing Science from Simon Fraser University in British Columbia, Canada.(…)”

1 June 2011 Comments Off

ACM-ICPC World Final 2011 Problems – by Petr Mitrichev

I couldn’t stop myself from sharing a nice post from Petr Mitrichev’s blog:

“(…) I’ve taken some time to reflect on the World Finals problems – hopefully that will be interesting for you to read. If you were not following the World Finals closely, you should probably skip this post :)

The problems are at http://cm.baylor.edu/digital/icpc2011.pdf, the unofficial solutions from Per at http://www.csc.kth.se/~austrin/icpc/finals2011solutions.pdf.

I’ve really liked the problemset, so please don’t take my words below as criticism – I’ve just tried to look at the problems from different angles and classify them in different ways, and maybe suggest some improvements for the future.

Problem A – To Add or to Multiply – ad-hoc (number theory?) (by ad-hoc I mean “need creative thinking to solve but no necessary prior algorithm/mathematics knowledge or experience solving similar problems”), most difficulty in corner cases and finding the lexicographically smallest answer.
Problem B – Affine Mess – exhaustive search (do what’s described in the problem statement) + solving a system of 2 linear equations, most difficulty in corner cases.
Problem C – Ancient Messages – ad-hoc, out-of-format problem, as there’s no precise definition of valid input.
Problem D – Chips Challenge – maximum flow (reduction to flow is the most difficult part).
Problem E – Coffee Central – exhaustive search (do what’s described in the problem statement) + the набившая оскомину idea about using inclusion-exclusion for rectangle sums. Most difficulty in finding the lexicographically smallest answer.
Problem F – Machine Works – DP plus incremental convex hull within one quadrant. The key to producing NlogN solution is the somewhat well-known idea about incremental convex hull to find the maximum of a set of linear functions. Most difficulty is inventing this speedup (if not known in advance) and implementing incremental convex hull.
Problem G – Magic Sticks – ad-hoc, geometry. The solution has two main parts – inventing and then proving (or believing) the key mathematical fact about throwing away the longest edge, and solving a sub-problem where you have to maximize the area of the polygon with the given sides. The sub-problem is again quite well-known and was a significant advantage to the teams who saw it before. However, I believe the most difficult part was the longest edge fact. There was also a catch about one edge taking more than Pi angle which many teams forgot to account for.
Problem H – Mining Your Own Business – graph theory, ad-hoc. The most mathematically beautiful problem of the contest in my opinion. The main difficulty is constructing the “if and only if” condition for the set of escape shafts.
Problem I – Mummy Madness – interval trees (or priority queues), ad-hoc. The main difficulty is realizing (a.k.a proving or believing) the problem can be reduced to checking if a square is completely covered by a set of squares. The NlogN solution to that sub-problem is very well-known and should be very easy for top teams.
Problem J – Pyramids – quite straightforward DP (backtracking should also work). I don’t see any significant difficulty at all here, but if I were to choose the main difficulty, it would be building the lexicographically largest answer in the DP solution.
Problem K – Trash Removal – a well-known problem. Solvable in NlogN using rotating calipers, but since the constraints were so low, that solution is an overkill. The only difficulty with such small constraints was to realize that the line should be parallel to the line connecting some pair of vertices. The main difficulty is the geometric formulas, but those are very easy as well.

Problem H was really standing out from the problemset, in my view, because it required graph theory thinking but at the same time involved no heavyweight algorithms or implementation difficulties. I would love to see more problems like this, but they are very hard to come up with. Problem C is unusual (so one might argue it gets close to the boundary of teams might reasonably expect) but still good. Problems E, F, I, J, K are “professional” problems – the most difficult part of each lies in a “standard set of tools” that most competitive programmers hone from contest to contest. This is not a negative thing – those ideas form the standard set of tools exactly because they’re most useful “building blocks” of various algorithms. Problem K may be too well-known though. Problem G is borderline as it combines a beautiful ad-hoc part with quite difficult algorithm that might be well-known to some teams but not others. Problem D is borderline (but still very good in my opinion) because the “reduce to maximum flow” trickery can also be viewed as a part of “standard set of tools”, and thus the problem is quite “professional” too. Problems A, E, J require relatively little thought, and have main difficulty in figuring out the corner cases and careful implementation, which is not exciting, and I’d say 3 such problems is too much (but maybe I’m too subjective after several teams I’ve supported got buried in those issues).

To spice up the long text, here’s my picture with the World Champions:

Please share your thoughts :) …”

31 May 2011 Comments Off

Ranklist (Scoreborad) ACM ICPC WF 2011

ACM International Collegiate Programming Contest (abbreviated as ACM-ICPC or just ICPC) is an annual multi-tiered computer programming competition among the universities of the world.Congratulations to Zhejiang University – the 2011 ACM-ICPC World Champions!

Congratulations to Zhejiang University – the 2011 ACM-ICPC World Champions!

Photo by Ravi Melaram

Photo by Jason Daly

Rank Team Solved Time
1 Zhejiang University 8 1228
2 University of Michigan at Ann Arbor 8 1462
3 Tsinghua University 7 800
4 St. Petersburg State University 7 893
5 Nizhny Novgorod State University 7 938
6 Saratov State University 7 966
7 Friedrich-Alexander-University Erlangen-Nuremberg 7 1088
8 Donetsk National University 7 1155
9 Jagiellonian University in Krakow 7 1176
10 Moscow State University 7 1187
11 Ural State University 7 1345
12 University of Waterloo 7 1555
13 Taurida V.I. Vernadsky National University 6 614
14 National Taiwan University 6 804
15 University of Warsaw 6 872
16 St. Petersburg State University of IT, Mechanics and Optics 6 931
17 Nanyang Technological University 6 958
18 Universidad de Buenos Aires – FCEN 6 965
19 Korea Advanced Institute of Science and Technology 6 965
20 Peking University 6 1012
21 Sharif University of Technology 6 1066
22 Carnegie Mellon University 6 1110
23 Shanghai Jiao Tong University 6 1113
24 Lviv National University 6 1150
25 The Chinese University of Hong Kong 6 1243
26 Zhongshan (Sun Yat-sen) University 6 1367
27 University of Electronic Science and Technology of China 5 648
28 Taras Shevchenko Kiev National University 5 754
29 Massachusetts Institute of Technology 5 803
30 Belarusian State University 5 811
31 Universidade Federal de Pernambuco 5 817
32 University of Tokyo 5 822
33 South Ural State University 5 839
34 Kazakh-British Technical University 5 874
35 Perm State University 5 927
36 Kyoto University 5 935
37 Novosibirsk State University 5 1010
38 Fudan University 5 1225
39 Harbin Institute of Technology 5 1312
40 Tianjin University 5 1353
41 University of Helsinki 5 1447
42 Universidade Federal do Paraná 4 386
43 Moscow Institute of Physics & Technology 4 452
44 Wuhan University 4 550
45 Universidade de São Paulo – Escola Politécnica 4 590
46 Princeton University 4 673
47 Universidade de São Paulo – Instituto de Matemática e Estatística 4 675
48 International Institute of Information Technology – Hyderabad 4 710
49 East China Normal University 4 732
50 Universidad Nacional de Córdoba – FaMAF 4 759
51 University of Alberta 4 763
52 Seoul National University 4 772
53 Swiss Federal Institute of Technology Zurich – VIS 4 808
54 Beijing Jiaotong University 4 813
55 Indian Institute of Technology – Delhi 4 862
56 University of Wroclaw 4 896
57 University of Stellenbosch 4 981
58 Pontificia Universidad Católica del Perú 4 1025
59 Hangzhou Dianzi University 3 263
60 Fuzhou University 3 272
61 California State University – Chico 3 288
62 German University in Cairo 3 389
63 University of New South Wales 3 395
64 Ain Shams University 3 426
65 Bangladesh University of Engineering and Technology 3 431
66 Leiden University 3 447
67 Huazhong University of Science & Technology 3 447
68 Instituto Tecnológico de Aeronautica 3 491
69 University of Miami 3 536
70 Shandong University 3 538
71 Universidade Federal de Minas Gerais 3 560
72 Harvey Mudd College 3 601
73 Simon Fraser University 3 682
74 Ho Chi Minh City University of Science 2 137
75 University of Oklahoma 2 142
76 Hong Kong University of Science and Technology 2 152
77 Universidad de Guanajuato – CIMAT 2 159
78 Zhejiang Normal University 2 193
79 University of Chicago 2 225
80 Duke University 2 243
81 Alexandria University – Faculty of Engineering 2 248
82 American University of Sharjah 2 299
83 Harbin Engineering University 2 332
84 University of Wisconsin – Madison 2 359
85 Orel State Technical University 2 374
86 Universidad del Valle 2 375
87 Universidad Católica Boliviana – La Paz 2 377
88 University of Minnesota – Twin Cities 2 408
89 Universidad de las Ciencias Informáticas 2 426
90 University of California – San Diego 2 542
91 University of Maryland 2 596
92 Illinois State University 2 607
93 Universidad de La Habana 2 703
94 Universidad Nacional de Colombia – Bogotá 2 718
95 University of Virginia 2 883
96 University of Canterbury 1 38
97 South Dakota School of Mines and Technology 1 146
98 EAFIT University 1 175
99 Cairo University – Faculty of Computers and Information 1 193
100 University of Illinois at Urbana-Champaign 1 242
101 Amirkabir University of Technology 0 0
101 DJ Sanghvi College of Engineering 0 0
101 Indian Institute of Technology – Kanpur 0 0
101 King Abdullah University of Science and Technology 0 0
101 Sichuan University 0 0

Well.done all teams specially-B.U.E.T. Annihilator, Dr. Mohammad Kaykobad, Tasnim Imran Sunny, Muntasir Mashuq, Anindya Das for solving three (3) problems.
Source: http://scrool.se/icpc/wf2011/

30 May 2011 Comments Off

The 2011 World Finals Ranklist – ACM International Collegiate Programming Contest

The 2011  World Finals Ranklist – ACM International Collegiate Programming Contest. See live cast:



photo by Bettina Johnson

John Bonomo, ICPC World Finals chief judge, has been part of the judging team since the 2002 Honolulu competition. “Our main purpose is to handle any slight problems with the test data, look at problems that contestant teams continually get wrong, and for clarification,” he said. Bonomo explained how the judging process has become increasingly automated with the advancement of technology. “We used to look through code and run testing,” he said. “Now the satisfaction comes from crafting challenging sets of problems.”

According to ICPC director of judges Jo Perry, there is one judge per problem in the World Finals. The chief judge and director of judges are used as extra hands during the finals and are also responsible for putting the problem sets together for the competition. Perry became involved with the judging side of the competition after being asked by a colleague at North Carolina State University to submit problems to a then infant ICPC competition.

Some of the judging staff became involved with judging simply for their love of the ICPC. Originally born in Sweden and now living in Canada, Per Austrin became involved with the competition as a contestant for his Swedish university. He joined the judging team when he could no longer compete due to age and has been a regular World Finals judge since 2008. “I enjoy the contest,” he said. “The construction of problems is almost like the other side of solving them.”

Former Google programmer Derek Kisman got his start with the World Finals as a contestant for The University of Waterloo during the Prague competition. He said, “I love the ICPC and being behind the scenes now as a judge.” Kisman enjoys coming up with problems that spawn interesting discussions and plans to continue judging for the ICPC as long as possible.

While many on the judging team have always known the international programming competition under the familiar ICPC name, Stan Wileman remembers the forerunner to the official contest we know today. While attending the University of Houston as a graduate student, Wileman and his early team of programmers learned of a contest at Texas A&M. “We overslept the day of the completion and arrived at the tail-end,” Wileman said. “We were late but still managed to win the damn thing and split the $100 grand prize!”

Today, Wileman has earned two hats with the ICPC as a World Finals judge and the regional director of North Central North American region. Bettina Johnson, ICPC Digital

Live Ranklist


29 May 2011 Comments Off

Some Cheatsheet/download


Some ACM Sample Problems