VT International Collegiate Programming Contest Team Advances to National Championship
January 22, 2020
Virginia Tech Department of Computer Sciences recently served as a one of eight host sites for the International Collegiate Programming Contest (ICPC) Regional Competition for the Midatlantic Region, drawing more than 26 teams from the region.
Due to the excellent time and lack of errors for the first six problems, the Virginia Tech team, consisting of Yibo Huang, Alex Lind, and Benjamin Reidys, took 5th place by a comfortable margin and qualified for the 2020 North American Championship in Atlanta next February. Huang is a USACO finalist and former Virginia Tech High School Programming Contest contestant.
The best 55 teams from all across North America will participate with the midatlantic region having six slots.
The judges this year stuck again to only eight problems (other regions typically pose 10-13 questions nowadays). They had a strong start, solving six out of the eight problems in under two hours, taking the lead in the region on the scoreboard. Due to some misfortune, they failed at the 7th problem and couldn't recover to do the 8th.
Here's the problem our team couldn't solve: given a tree with 1 million nodes where each of the nodes has a number as its label, find the longest increasing subsequence for each of the sequences formed by the node labels on all paths from the root to all other nodes (there are appr. 1 million such paths). If there's more than one longest increasing subsequence of equal length, count how many there are. Report both the length of the longest increasing subsequence and how many subsequences there are of this length, modulo 11092019. Your program must run in 4s or less.
Team preparation paid off as well: one problem required solving the "bomb problem" aka minimum enclosing circle, as a subproblem. Overall, Virginia Tech's teams solved hundreds of problems at multiple weekend practices leading into the contest and during the summer months. Overall, only 89 out of 158 solved three problems or more.
Here is the complete list of the Virginia Tech teams and placements:
5th place - Yibo Huang, Alex Lind, Benjamin Reidys
13th place - Siddharth Akalwadi, Calvin Godfrey, Jeffrey Peng
19th place - Joseph Dyer, Vamsi Manne, Henry Wang
41st place - Weihao Gao, Colin Peppler, Yen Truong
43rd place - Sai Ajayakumar, Mohammad Haider, Vinh Pham
46th place - Jared Blumen, Gabriela Velazquez-Pergola, Liling Yuan
61st place - Mark Braganza, Matt Davison, Bill Norris
69th place - Andrew Ahnn, Brook Tamir, Ashvin Venkatesan
75th place - Arash Behpour, Danny Chhour, Kyle Long