125 Ad spot 125 Ad spot

ACMSolver or Art of Programming? 24 X 7 Updates

From 2002 ACMSolver is campaigning for free programming knowledge!

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:

http://scrool.se/icpc/wf2011/

http://www.icpclive.com/?page=live333#

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

http://scrool.se/icpc/wf2011/

29 May 2011 Comments Off

Some Cheatsheet/download

http://code.google.com/p/acmudec/downloads/list

Some ACM Sample Problems

Tags:
21 May 2011 Comments Off

UAlbarta CS Code Repository

2D_Geometry/ 30-Apr-2010 15:08 -
3D_Geometry/ 23-Feb-2004 15:23 -
Archive/ 06-Feb-2009 20:53 -
Arithmetic/ 26-Oct-2005 10:44 -
C++/ 26-Oct-2005 11:15 -
Combinatorics/ 23-Feb-2004 15:23 -
Data_Struct/ 23-Feb-2004 15:23 -
Dynamic/ 23-Feb-2004 15:23 -
Generators/ 23-Feb-2004 15:23 -
Graph_Theory/ 13-Jan-2006 13:39 -
Java/ 23-Feb-2004 15:23 -
Makefile 10-Nov-2003 17:14 69
Misc/ 26-Oct-2005 10:34 -
Num_theory/ 26-Aug-2008 11:13 -
OLD/ 23-Feb-2004 15:23 -
Old/ 14-Mar-2003 20:26 -
Parsing/ 23-Feb-2004 15:23 -
Search/ 23-Feb-2004 15:23 -
index.txt 13-Nov-2003 13:36 7.6K
masterlist.txt 26-Aug-2008 11:15 12K
misc/ 25-Nov-2005 14:51 -
oldfiles.txt 19-Mar-2003 17:32 3.9K
tables.txt 21-Jan-2003 16:43 3.9K
todo.txt 13-Jan-2006 13:41 304
updatelist.txt 13-Jan-2006 13:40 6.4K

Source: http://webdocs.cs.ualberta.ca/~contest/code/

21 May 2011 Comments Off

ACM UVa Problems Category

New Comer

★ 100 The 3n + 1 problem
★ 10189 Minesweeper
★ 10137 The Trip
★ 706 LCD Display
★ 10267 Graphical Editor
★★ 10033 Interpreter
★ 10196 Check The Check
★ 10142 Australian Voting

Data Structure

★ 10038 Jolly Jumpers
★★ 10315 Poker Hands
★★ 10050 Hartals
★★   843 Crypt Kicker
★ 10205 Stack ‘em Up
★★ 10044 Erdos Numbers
★ 10258 Contest Scoreboard
★★★ 10149 Yahtzee

String

★ 10082 WERTYU
★★ 10010 Where’s Waldorf?
★ 10252 Common Permutation
★★ 850 Crypt Kicker II
★ 10188 Automated Judge Script
★★ 10132 File Fragmentation
★★★ 10150 Doublets
★★ 848 Fmt

Sorting

★ 10041 Vito’s Family
★★   120 Stacks of Flapjacks
★★★ 10037 Bridge
★ 10191 Longest Nap
★★ 10026 Shoemaker’s Problem
★★ 10138 CDVII
★★ 10152 ShellSort
★ 10194 Football (aka Soccer)

Arithmetic and Algerba

★ 10035 Primary Arithmetic
★ 10018 Reverse and Add
★   701 The Archeologists’ Dilemma
★★ 10127 Ones
★★★   847 A Multiplication Game
★ 10105 Polynomial Coefficients
★ 10077 The Stern-Brocot Number System
★★★★ 10202 Pairsumonious Numbers

Combinations

★ 10183 How Many Fibs?
★★ 10213 How Many Pieces of Land ?
★★ 10198 Counting
★★ 10157 Expressions
★★ 10247 Complete Tree Labeling
★★ 10254 The Priest Mathematician
★★ 10049 Self-describing Sequence
★★   846 Steps

Number Theory

★ 10110 Light, More Light
★★ 10006 Carmichael Numbers
★ 10104 Euclid Problem
★★ 10139 Factovisors
★★ 10168 Summation of Four Primes
★ 10042 Smith Numbers
★ 10090 Marbles
★★ 10089 Repackaging

Backtracking

★★ 861 Little Bishops
★★★ 10181 15-Puzzle Problem
★★ 10128 Queue
★★ 10160 Servicing Stations
★★ 10032 Tug of War
★★ 10001 Garden of Eden
★★★ 704 Colour Hash
★★★ 10270 Bigger Square Please…

Graph Traversal

★ 10004 Bicoloring
★★ 10067 Playing with Wheels
★★★ 10099 The Tourist Guide
★★   705 Slash Maze
★★★ 10029 Edit Step Ladders
★★★ 10051 Tower of Cubes
★★★ 10187 From Dusk Till Dawn
★★★ 10276 Hanoi Tower Troubles Again!

Graph Algorithm

★★ 10034 Freckles
★★★ 10054 The Necklace
★★ 10278 Fire Station
★★★ 10039 Railroads
★★★ 10158 War
★★★ 10199 Tourist Guide
★★★★ 10249 The Grand Dinner
★★★ 10092 The Problem with the Problem Setter

Dynamic Programming

★★ 10131 Is Bigger Smarter?
★★★ 10069 Distinct Subsequences
★★★ 10154 Weights and Measures
★★★   116 Unidirectional TSP
★★ 10003 Cutting Sticks
★★★ 10261 Ferry Loading
★★★ 10271 Chopsticks
★★★ 10201 Adventures in Moving – Part IV

Grid

★ 10161 Ant on a Chessboard
★★★ 10047 The Monocycle
★★ 10159 Star
★★ 10182 Bee Maja
★★★   707 Robbery
★★ 10177 (2/3/4)-D Sqr/Rects/Cubes/Boxes?
★★ 10233 Dermuba Triangle
★★★ 10075 Airlines

Geometry

★ 10310 Dog and Gopher
★★ 10180 Rope Crisis in Ropeland!
★★ 10195 The Knights Of The Round Table
★★★ 10136 Chocolate Chip Cookies
★★ 10167 Birthday Cake
★★ 10215 The Largest/Smallest Box …
★★★ 10209 Is This Integration ?
★★★ 10012 How Big Is It?

Computational Geometry

★★ 10135 Herding Frosh
★★ 10245 The Closest Pair Problem
★★★ 10043 Chainsaw Massacre
★★★ 10084 Hotter Colder
★★★ 10065 Useless Tile Packers
★★   849 Radar Tracking
★★★ 10088 Trees on My Island
★★★★ 10117 Nice Milk

Source: http://www.cnblogs.com/penseur/archive/2011/03/10/1979491.html