We discussed solutions to some of the problems from the NAQ last weekend. Full solution slides and other data are available on the NAQ 2018 webpage. Anyone interested in competing in the ACPC (there are cash prizes!!!) should register here prior to October 25th.
With Zach Goldthorpe leading discussion (thank you!), we did another practice contest. One of the problems, Counting Stars, was coded up as a group. You can find the code for that here. Zac Friggstad's solutions for all of the problems are here.
We did a quick intro to the club for new members followed by a practice contest. Problems discussed were Stuck In A Time Loop, Trik, Oktalni, Splat, Nine Knights, Arranging Hat, One-Way Roads. Download solutions here.
Solutions from intro session. Thanks to Daniel Mitchell for sharing!
Bipartite graphs. Slides:
Slightly less standard topics in these notes: edge colouring and partially ordered sets.
An important missing topic is tries, look it up to learn about them!
We discussed basic tricks in combinatorics and arithmetic. Slides:
Combinatorics and Arithmetic
The topic was number theory. Slides:
More suggested problems were added after the meeting.
We discussed geometry. Slides:
Additional code is on these posted slides that was not presented in the meeting.
Jason Yuan presented notes on algorithms in weighted graphs (Thanks Jason!). Slides: Weighted Graphs Slides
We discussed unweighted graphs. Slides: Unweighted Graphs Slides
We discussed dynamic programming. The notes and the Kattis problems discussed are here:
Dynamic Programming Slides
We had our first intro coding session! It was very well attended :)
The list of problems is here. But to submit, you have to find the problem on Kattis by searching for its ID, as the "contest" itself is over.
Solutions (in both C++ and Python3) can be found here.
We discussed the recent UBC practice contest in the problem solving session.
In the coding session, we did a mini-contest on Open Kattis. The list of problems is here, but the contest is officially "over" so if you want to submit you will have to search the problem IDs individually (e.g. pot, svm, everywhere, pizza2) and then submit through the normal problem description page. The .zip of the problem solutions (in both C++ and Python3) can be found here.
The problems discussed are from a recent UBC practice. You can still submit to the links below. Email me if you want a login.
Straightforward, but you should use 64-bit integers (i.e. long long) if you use C++ as the multiplication result does not fit in a 32-bit integer in general.
We coded a function that would give the distance between two charcters. Given this, all you have to do is compute the distance between two strings and sort them in order of this distance.
Noah had a nice solution here for just the distance calculation. See if you can use it to solve the rest of the problem!
Compute the smallest positive integer X such that K divides C*X-1. Can do easily with a modular inverse calculation. I just added it to the code archive this weekend (why wasn't it there already?). You can find it here.
Be careful to correctly handle the case when K = 1. Remember that every kid needs a positive amount of candy and there must still be exactly one candy leftover.
The answer was to simply output the maximum number from the input sequence. This was our first example problem. We solved it in Python3.
Build an array "front[a]" that, for a branch a, gives the number of the branch just below 'a'. If 'a' is the root of a tree, then front[a] = -1. Then we just have the cat jump down the tree by iterating the instruction "cat = front[cat]" until cat = -1. We implemented the solution in C++, look at it to see how to check when we have read the last value on a line.
While there is a consecutive pair of characters 'CC', count how many 'P' characters lie to the left then remove this 'CC'. Similarly for consecutive 'PP'; count how many 'C' characters lie to the right then remove this 'PP'. Once this is done, the sequence alternates between 'P' and 'C'. Ignore any leading 'C' or trailing 'P', so the sequence looks like 'PCPCP ... CPC'.
There is a formula for this based just on its length, one can derive it by, say, swapping the first three characters so it starts 'CPPCPCPCPCP ...'. Apply the above rule when there are consecutive 'PP' to reduce the length of the alternating sequence. Output the total count. Of course, one needs to prove this works, but this is the idea.
One could carefully implement this to run in linear time (e.g. don't actually delete consecutive letters, just do the right book keeping).
Welcome to the club!
We discussed B and C in quite a bit of detail.
For each "cross section" t, consider the grid with ' ' (a space) at cells with height <= t and 'x' at spaces at cells with height > t. A "pool" is a connected region of spaces that is not connected to the outside ocean. For each space, the value w[i][j] to be computed is the smallest t such that t cell (i,j) is a ' ' but is not in a pool (i.e. is connected to the outside). There are at most 1000 cross sections to try, which should be fast enough.
We can make this much faster by sorting the cells by initial height h[i][j]. Maintain a grid of ' ' for pool, 'o' for connected to ocean, and 'x' mountain. When processing cell (i,j) we change 'x' to ' '. If any neighbour of (i,j) is 'o', then set entry (i,j) to 'o' and floodfill any adjacent pool of ' ' with 'o'. The cross section when a cell first gets marked 'o' is the w[i][j] of that cell. Every cell gets floodfilled once, so apart from the initial sort it takes linear time in the size of the grid.
Let f(r) be the polynomial. We can assume, by truncating the input sequence (a.k.a. dividing by r+1), that the constant term is nonzero. So f(-1) > 0. We also have f(1) < 0.
So just use the bisection method to find the root: set lo = -1, hi = +1. Evaluate f(mid) where mid = (lo+hi)*0.5. If f(mid) < 0 update hi = mid, else update lo = mid. Iterate until lo < hi + 1e-10 and print the answer.