For more information on the ACM International Collegiate Programming Contest (ICPC), click here.
Recent blog entries
________

20160914 Practice: Solutions for GNYR 2012
Greater New York Regionals is usually considered to have easier problems compared to other regions. This set in particular is math heavy but the math used is fairly elementary and code is quite short! If you are new to ACM, here is the chance to practice many of the standard techniques.Problem F was quite nice and thanks to David and Paul for solutions.Problem AProblem SummaryOutput sum_{i=1..n} i, 2i1, 2iSolutionYou can precompute the answer by brute force or use formula:sum i = n(n+1)/2sum 2i1 = n^2sum 2i = n(n+1)ComplexityTime complexity: O(1)Problem BProblem SummaryCompute the number of sequences of ...
Posted 16 Sep 2016, 11:01 by jason chiu

Practice 20160910: Solutions for GCPC 2012
This week's contest is mostly "read problem carefully and implement". Problem D was quite unusual, problems CFGK were very standard algorithms, and relatively little insight required for problems ABEHJI.Thanks to Andy and Angus for alternate (easier) solutions.Problem AProblem StatementSimulate battleships game and determine who wins.SolutionThe problem statement is very confusing and long, so read it carefully. In particular, key points are:1. Despite the "you don't know who shot what" part, the first player did make the first shot2. The player continues to make shots until he misses or he sinks all enemy ship3. If player 1 sinks all of player 2's ship, then player 2 gets one last ...
Posted 15 Sep 2016, 21:32 by jason chiu

Practice 20160903: Solutions for Universidade de São Paulo Team Tryouts 2016
The
contest wasn't too bad although there were some harder problems! I
encourage everyone to think and read the solutions and solve a problem
they didn't/couldn't solve!If you only solve
problems you could solve, it's hard to improve. The key to improvement
is to solve problems you couldn't solve before.As usual, my code is here: https://www.dropbox.com/sh/prf8vqxp6uwcb26/AAAdlS8q09UlA8l5tbwdm0VAa?dl=0Solutions by Paul and I are as described belowProblem A  Renzo and the Lost ArtifactProblem SummaryYou have two rectangles of equal proportions, one is smaller and placed inside another. You want to find a point in the bigger rectangle such that if you map the ...
Posted 5 Sep 2016, 22:56 by jason chiu

Practice 20160827: Solutions for Universidade de São Paulo ICMC 2016
A fairly straightforward contest. I encourage everyone to implement the more interesting problems.My code: https://www.dropbox.com/sh/q83a43tcx265emj/AACIMFPQPGKlt15_2SZzqIGla?dl=0My solutions are as shown below:Problem A  Giant Snail MazeProblem SummaryYou want to find the shortest path from the center to the outermost circle in a graph of N concentric circles with Q >= N radial line segments connecting them.SolutionSimply construct the graph and run Dijkstras. Constructing the graph may take some implementation effort. First you iterate through all the "openings" and add 2 vertices for each opening: one on the (circular) rail track inside (or the exact center if it's an opening on the innermost wall) and one on ...
Posted 5 Sep 2016, 16:24 by jason chiu

Practice 20160820: Solutions for Samara VII (2014)
I solved all problems except problem I, with some help from Paul and Andrew.My code: https://www.dropbox.com/sh/s86b6xf58i9vb6w/AABtLkkIo9eP9UmGqgUJIimRa?dl=0My solutions are below:Problem A  Golden DragonsProblem SummaryYou want to find if graph B is a subgraph of the complement of A, up to an isomorphism. There are weird constraints like n >= 3ab where a is max degree of A and b is max degree of B.SolutionHere's a greedy algorithm that doesn't work by itself:For each vertex in A (in some arbitrary order), randomly pick any unassigned vertex from B that doesn't cause any conflicts (i.e. its edges in B to assigned vertices in B ...
Posted 5 Sep 2016, 16:06 by jason chiu

