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 :) …”

8 April 2011 Comments Off

Asia Teams Qualified for ACM-ICPC World Finals 2011 Orlando Florida

From Dr. C J Hwang’s Blog:

” (Total 35 teams; 2010 Host universities are selected only if they are very close to qualified lines. But no preference is applied to any team this year. )
(x/y : x = points used for the site; y = slots calculated from ICPC registration and the formula of Asia Rules; Foreign team used 0.3 points; repeated domestic team 0.6; other 1.0.)

(Those teams in light blue color are the 15 universities having multiple qualified teams. University coach(es) must decide only one team to WF if there are multiple qualified teams from the same university. )

1. Asia Amritapuri (3.2/3.0)
Fudan University – HexHeaven (China) (0.6) (Amritapuri’s Rules)
Indian Institute of Technology Delhi – Proof (India) (1.0)
DJ Sanghvi College of Engineering – phoenix (India) (1.0)
International Institute of Information Technology Hyderabad – Blitzkrieg (0.6)

2. Asia Chengdu (4.6/4.2)
Zhongshan (Sun Yat-sen) University – SYSU_Calvados (0.6)
Peking University – PKU_JiangYou (0.6)
Shanghai Jiaotong University – SJTU_Halo (0.6)
Wuhan University – OpenLegend (1.0)
University of Electronic Science and Technology of China – UESTC_Melody (0.6)
Fudan University – Sierpinski (0.6)
Tsinghua University – Dragonfly (0.6)

3. Asia Daejeon (1.9/1.3)
Korea Advanced Institute of Science and Technology – RoyalRoader (0.6)
National Taiwan University – nekonekosoft (0.3)
Seoul National University – reverse_iterator (1.0)

4. Asia Dhaka (1.0/0.9)
Bangladesh University of Engineering and Technology – B.U.E.T Annihilator (1.0)

5. Asia Fuzhou (5.4/5.0)
Shanghai Jiaotong University – phosphor (0.6)
Tsinghua University – mschinator (0.6)
Zhejiang University – ArcOfDream (0.6)
Shandong University – Code_geass (1.0)
Harbin Institute of Technology – DPS (1.0)
Zhongshan (Sun Yat-sen) University – SYSU_Vermouth (0.6)
East China Normal University – ecnu_puzzle (1.0)

6. Asia Hangzhou (4.8/4.5)
Shanghai Jiaotong University – Luminar (0.6)
Tsinghua University – DivineRapier (0.6)
Zhejiang University – NFA (0.6)
Sichuan University – APTX4869 (1.0)
Huazhong University of Science &Technology – Erbao (1.0)
Zhejiang Normal University – PpG_LongPo (1.0)

7. Asia Hanoi (1.5/1.3)
Nanyang Technological University – NTU Pigeons (0.3)
Hong Kong University of Science and Technology – HKUST_Optimus Prime (0.3)
National Taiwan University – Tali (0.3)
Ho Chi Minh City University of Science – HCMUS-Equanimity (0.6)

8. Asia Harbin (4.4/3.9)
Peking University – PKU_JY (0.6)
Tsinghua University – DivineRapier (0.6)
Tianjin University – TJU-Zero (1.0)
Zhongshan (Sun Yat-sen) University – SYSU_Vermouth (0.6)
Beijing Jiaotong University – BJTU-ACMagic (1.0)
University of Electronic Science and Technology of China – UESTC_Walz (0.6)

9. Asia Jakarta (0.9/0.9)
National Taiwan University – +1ironwood branch (0.3)
Chinese University of Hong Kong – ManiAC (0.3)
Nanyang Technological University – NTU GladiaToRs (0.3)

10. Asia Kanpur (1.6/1.3)
International Institute of Information Technology Hyderabad – ANY Dream
(India) (0.6)
Indian Institute of Technology Kanpur- Deep Thought (1.0)

11. Asia Kaohsiung (0.9/0.6)
National Taiwan University – 319ea9529889333f93af9dcf1d6e4c2 (0.6)
University of Tokyo – USAGI Code (0.3)

12. Asia Kuala Lumpur (1.2/0.7)
Chinese University of Hong Kong – ManiAC (0.3)
Nanyang Technological University – NTU Pigeons (0.3)
Hong Kong University of Science and Technology – HKUST_Optimus Prime (0.3)
Ho Chi Minh City University of Science – Vietnam Equanimity (0.3)

13. Asia Tehran (2.0/1.5)
Amirkabir University of Technology – Last War of PMP (1.0)
Sharif University of Technology – 3gespenek (1.0)

14. Asia Tianjin (4.8/4.2)
Tsinghua University – Dubhe (0.6)
Zhejiang Univertsity – NFA (0.6)
Shanghai Jiaotong University – ViGoR (0.6)
Fuzhou University – OpenGL (1.0)
Harbin Engineering University – Blue Sky (1.0)
Hangzhou Dianzi University – HDU-Knuth (1.0)

15. Asia Tokyo (2.2/1.7)
University of Tokyo – USAGI Code (0.6)
Korea Advanced Institute of Science and Technology – RoyalRoader (0.3)
Kyoto University – d3sxp (1.0)
National Taiwan University – Lisa at Gaspard (0.3)

16. Appendix : Resolution of ACM-ICPC Contest Council China:
Chinese teams will use WF slots from China sites if a Chinese team obtained
rank 1 or 2 from contests in other administrative sub-regions. (0.0/0.0)
These teams are also qualified:
Fudan University – ACE (Dhaka)
Zhejiang University – ArcOfDream (Hanoi)
Shanghai Jiaotong University – Halo (Jarkata)
Shanghai Jiaotong University – Luminer (Tokyo)

17. Appendix : Resolution of ACM-ICPC Contest Council China:
To encourage teams from outside of Mainland China to participate China
contest sites, ACM-ICPC Contest Council China will offer China site slots
to those teams from other sub-regions if those teams are placed inside
the qualified lines.

*** How many takers this year? Zero.
(Resolutions are linked from Asia Rules.)

18. Team participating in a contest site outside of their administrative sub-region
and without an advanced agreement with their home site, there will be no WF slot for the team. However, those teams will receive awards, prizes and certificates just like other teams in any Asia regionals. (Refer to Asia rules.)”

About Dr. C J Hwang:

ACM-ICPC Asia Director; Professor of Computer Science Texas State University; Author of Two Chinese Literature Books.

3 April 2011 Comments Off

ACM-ICPC 2011: From Egypt to Orlando!

ACM-ICPC 2011: From Egypt to Orlando!

I was wondering how the ACM-ICPC will be held in Egypt in the current scenario. Anyway, not to worry, The 2011 ACM-ICPC World Finals sponsored by IBM has been rescheduled in Peabody Orlando Hotel, Orlando, Florida
May 27-31, 2011.

According to Bill Poucher:

“Originally, we planned to have the World Finals in Egypt in 2014 or 2015. We have switched back to that plan due to recent events. While we could have had the World Finals in Sharm El Sheikh last week, transportation through Cairo has been difficult. Now with Consular Travel Advisories, it is not an option.

We hope… to reschedule so that you could all experience Egyptian hospitality at its finest. In the meantime, let’s wish our friends a safe path to a better future….”

The tentative schedule is as follows ( at http://www.peabodyorlando.com/):

  • May 27 – Welcome
  • May 28 – Tech Trek, Excursion to Sea World
  • May 29 – Opening / Rehearsal,
  • May 30 – World Finals, Awards Dinner, Harry Potter Island Celebration
  • May 31 – Teams Depart
  • May 31 – RCD Symposium
  • June 1 – RCDs depart

Best wishes to all qualified WF, ACMer’s- from ACMSolver.org (Ahmed Shamsul Arefin)

1 January 2011 1 Comment

FIT MMU ACM-ICPC training website

FIT MMU ACM-ICPC training website

FIT MMU maintains a nice programming training website. It has following resources:

Introduction & Tutorial on Graph Algorithms
Graph Traversal (DFS, BFS)

UVA problems you can try:

Resources:

- Graph Samples
- Skiena’s BFS/DFS Samples
- Graph by Ooi Wei Tsang (NUS)

Tutorial on Binary Search Tree & Tree Traversals
(with some reference to Recursions)

UVA problems you can try:

Resources:

Tutorial on Iterators and STL Associative Containers

UVA problems you can try:

Resources:

Tutorial samples

Using Data Structures for Problem-Solving:

Some good web resources on STL

Useful Links

  1. UVA Online Judge Site
  2. ACM-ICPC Live Archive
  3. Official ACM_ICPC website
  4. UVA Toolkit by Mark Greve
  5. Steven Halim’s “Methods to Solve”
  6. ACMSolver by Ahmed Shamsul Arefin
  7. Algorithmist
  8. ACM Beginner
  9. Dr. CJ Hwang (ACM-ICPC Asia Director)’s Blog

Downloads

Original website: http://fit.mmu.edu.my/icpc/

1 January 2011 Comments Off

Asia Teams Qualified for ACM-ICPC World Finals 2011

This post is taken from: http://icpcasia.blogspot.com/

1. Asia Amritapuri (3.2/3.0)
Fudan University – HexHeaven (China) (0.6) (Amritapuri’s Rules)
Indian Institute of Technology Delhi – Proof (India) (1.0)
DJ Sanghvi College of Engineering – phoenix (India) (1.0)
International Institute of Information Technology Hyderabad – Blitzkrieg (0.6)

2. Asia Chengdu (4.6/4.2)
Zhongshan (Sun Yat-sen) University – SYSU_Calvados (0.6)
Peking University – PKU_JiangYou (0.6)
Shanghai Jiaotong University – SJTU_Halo (0.6)
Wuhan University – OpenLegend (1.0)
University of Electronic Science and Technology of China – UESTC_Melody (0.6)
Fudan University – Sierpinski (0.6)
Tsinghua University – Dragonfly (0.6)

3. Asia Daejeon (1.9/1.3)
Korea Advanced Institute of Science and Technology – RoyalRoader (0.6)
National Taiwan University – nekonekosoft (0.3)
Seoul National University – reverse_iterator (1.0)

4. Asia Dhaka (1.0/0.9)
Bangladesh University of Engineering and Technology – B.U.E.T Annihilator (1.0)

5. Asia Fuzhou (5.4/5.0)
Shanghai Jiaotong University – phosphor (0.6)
Tsinghua University – mschinator (0.6)
Zhejiang University – ArcOfDream (0.6)
Shangdong University – Code_geass (1.0)
Harbin Institute of Technology – DPS (1.0)
Zhongshan (Sun Yat-sen) University – SYSU_Vermouth (0.6)
East China Normal University – ecnu_puzzle (1.0)

6. Asia Hangzhou (4.8/4.5)
Shanghai Jiaotong University – Luminar (0.6)
Tsinghua University – DivineRapier (0.6)
Zhejiang University – NFA (0.6)
Sichuan University – APTX4869 (1.0)
Huazhong University of Science &Technology – Erbao (1.0)
Zhejiang Normal University – PpG_LongPo (1.0)

7. Asia Hanoi (1.5/1.3)
Nanyang Technological University – NTU Pigeons (0.3)
Hong Kong University of Science and Technology – HKUST_Optimus Prime (0.3)
National Taiwan University – Tali (0.3)
Ho Chi Minh City University of Science – HCMUS-Equanimity (0.6)

8. Asia Harbin (4.4/3.9)
Peking University – PKU_JY (0.6)
Tsinghua University – DivineRapier (0.6)
Tianjin University – TJU-Zero (1.0)
Zhongshan (Sun Yat-sen) University – SYSU_Vermouth (0.6)
Beijing Jiaotong University – BJTU-ACMagic (1.0)
University of Electronic Science and Technology of China – UESTC_Walz (0.6)

9. Asia Jakarta (0.9/0.9)
National Taiwan University – +1ironwood branch (0.3)
Chinese University of Hong Kong – ManiAC (0.3)
Nanyang Technological University – NTU GladiaToRs (0.3)

10. Asia Kanpur (1.6/1.3)
International Institute of Information Technology Hyderabad – ANY Dream
(India) (0.6)
Indian Institute of Technology Kanpur- Deep Thought (1.0)

11. Asia Kaohsiung (0.9/0.6)
National Taiwan University – 319ea9529889333f93af9dcf1d6e4c2 (0.6)
University of Tokyo – USAGI Code (0.3)

12. Asia Kuala Lumpur (1.2/0.7)
Chinese University of Hong Kong – ManiAC (0.3)
Nanyang Technological University – NTU Pigeons (0.3)
Hong Kong University of Science and Technology – HKUST_Optimus Prime (0.3)
Ho Chi Minh City University of Science – Vietnam Equanimity (0.3)

13. Asia Tehran (2.0/1.5)
Amirkabir University of Technology – Last War of PMP (1.0)
Sharif University of Technology – 3gespenek (1.0)

14. Asia Tianjin (4.8/4.2)
Tsinghua University – Dubhe (0.6)
Zhejiang Univertsity – NFA (0.6)
Shanghai Jiaotong University – ViGoR (0.6)
Fuzhou University – OpenGL (1.0)
Harbin Engineering University – Blue Sky (1.0)
Hangzhou Dianzi University – HDU-Knuth (1.0)

15. Asia Tokyo (2.2/1.7)
University of Tokyo – USAGI Code (0.6)
Korea Advanced Institute of Science and Technology – RoyalRoader (0.3)
Kyoto University – d3sxp (1.0)
National Taiwan University – Lisa at Gaspard (0.3)

16. Appendix : Resolution of ACM-ICPC Contest Council China:
Chinese teams will use WF slots from China sites if a Chinese team obtained
rank 1 or 2 from contests in other administrative sub-regions. (0.0/0.0)
These teams are also qualified:
Fudan University – ACE (Dhaka)
Zhejiang University – ArcOfDream (Hanoi)
Shanghai Jiaotong University – Halo (Jarkata)
Shanghai Jiaotong University – Luminer (Tokyo)

17. Appendix : Resolution of ACM-ICPC Contest Council China:
To encourage teams from outside of Mainland China to participate China contest sites, ACM-ICPC Contest Council China will offer China site slots to those teams from other sub-regions if those teams are placed inside the qualified lines.

*** How many smart takers this year? Zero.
(Resolutions are linked from Asia Rules.)

18. Team participating in a contest site outside of their administrative sub-region
and without an advanced agreement with their home site, there will be no WF slot for the team. However, those teams will receive awards, prizes and certificates just like other teams in any Asia regionals. (Refer to Asia rules.)

Point Distributions: (Total 35 teams; 2010 Host universities are selected only if they are very close to qualified lines. But no preference is applied to any team this year. )
(x/y : x = points used for the site; y = slots calculated from ICPC registration and the formula of Asia Rules; Foreign team used 0.3 points; repeated domestic team 0.6; other 1.0.)

7 November 2010 Comments Off

Unofficial ranklist of ACM-ICPC Dhaka Site 2010

Unofficial ranklist of ACM-ICPC Dhaka Site 2010

Rank Name Solved Time
1 B.U.E.T. Annihilator 6 748
2 Fudan A.C.E. 6 1042
3 B.U.E.T. Budbud 5 644
4 DU Resonance 5 727
5 DU Primes 4 482
6 DU Impulse 101 4 491
7 B.U.E.T. Ja Issa Tai 4 505
8 SUST_Unpredictable 4 540
9 B.U.E.T. Asymptotes 4 917
10 EU BLIZZARD 4 1020
11 B.U.E.T. Aeternitas 3 273
12 B.U.E.T. Dynamites 3 294
13 BUBT Runtime Error 3 345
14 EWU OBTUSE 3 353
15 SEU_Fallen_Prime 3 357
16 DIU FATAH 3 361
17 SUB Epsilons 3 371
18 SUST_SUBCONSCIOUS 3 405
19 JU-Wind Of Change 3 407
20 CUET ICON 3 429
21 Stamford Burnout 3 509
22 Aust_Invincible 3 513
23 UIU_Surge 3 524
24 SUST SANINS 3 532
25 DU Army Ants 3 555
26 AIUB-TERMINUS BOUND 3 577
27 IUT TripleHelix 3 586
28 AIUB-HORCRUX 2 129
29 SUST_HAGRIDS 2 165
30 UIU_Salient 2 190
31 RU scrap 2 210
32 MIST Fire Flies 2 214
33 RU Scrupulous 2 218
34 NSU Ardent 2 223
35 BRACU BYTE. 2 234
36 IUT Minnows 2 253
37 MBSTU_Bok-Dharmik 2 271
38 RUET_VOLATILE 2 289
39 RUET_RNS 2 324
40 CU PRIMER 2 342
41 EU UNPREDICTABLE 2 373
42 KUET Worship 2 375
43 EWU GOLAPI 1 8
44 EWU Jonak 1 11
45 AUB UNIX 1 13
45 MIST Volcano 1 13
45 ULAB Phenom 1 13
48 JU_PRANTIK 1 14
49 EU_OPTIMISTIC 1 15
49 RUET_%I64d 1 15
51 DCC Agantuk 1 16
51 IIUC.Authentic 1 16
53 I.I.U.C_Craft 1 17
53 UAP Blind Archers 1 17
55 RUET_TRINITY 1 18
55 UAP Black Gold 1 18
57 DIU SERENDIPITY 1 19
57 IU Freedom 71 1 19
59 IIUC Triangle 1 20
60 BGC Jump Start 1 22
60 MBSTU Coder 1 22
62 MBSTU Master Mind 1 23
62 NSTU SILICON CREWS 1 23
62 PU Prime Pentachoron 1 23
65 BGC Purbo Lekhonic 1 24
65 HSTU_INVADER 1 24
65 HSTU_SUPERNONA 1 24
65 SUB Fractal 1 24
65 USTC Diophantine 1 24
70 USTC Covenant 1 25
71 BRACU SPARTAN 1 26
72 IU Natun Shakal 1 27
73 DCC Creative 1 28
74 DUET_Sparkle 1 32
75 IIUCFireFlyes 1 35
76 RUET_Tracker 1 37
77 USTC Duronto 1 38
78 JKKNIU ONEZERO 1 39
78 RUET_WARRIORS 1 39
80 CU CORE 1 41
80 Stamford I/O 1 41
82 RUET_BIOS_TRIANGLE 1 41
82 RUET_SCRUPULOUS 1 41
84 AUST_PARAMOUNT 1 42
84 PSTU-DESERT-CREATOR 1 42
86 RUET_INTERRUPT+ 1 47
86 USTC Pioneer 1 47
88 BRACU RANGERS. 1 48
89 IIUC Run Time Error 1 50
90 Darul_camouflage 1 54
90 DUET_Foresight 1 54
92 RUET_MATRIX 1 59
93 DUET_Hunger 1 76
94 USTC Versatile 1 80
95 UODA RED SPRINT 1 88
96 KUET Fire Bugs 1 117
97 RUET_REFRESH 1 119
98 BGC Vampire 1 168
99 AUB_SUCCESS 1 188
100 ADUST Pirates 1 196
101 BGC Accepted 1 328
102 Darul_epsylon 0 0
102 PSTU-UNIX 0 0
Submitted/1st Yes/Total Yes

Created by CSUS PC^2 8.7 20081028 00

http://www.ecs.csus.edu/pc2/

Last updated Sat Nov 06 15:42:46 BDST 2010

Source: buet_contest_teams@yahoogroups.com