Waiting
View problem here
As the problem statement suggests, we need a data structure where people who come early can go into the room early: a queue, storing the departure time of all the students currently in the room. When a student enters, we first pop off all the students from the queue who would have already left. Then there are 3 cases. If the queue is now empty, then there must be an interval of time when the room is empty, more formally, we should add (the time when the student enters - the time when the previous student leaves - 1) to our answer. If there are less than L students in the room, then we can simply add the student’s departure time into the queue. Finally, if the queue is at its max capacity, we retrieve the front element of the queue, which should be the earliest departure time. Then we know that the new student should enter right after that student, so we simply push (earliest departure time + 1 + M) into the queue. After processing all the students, we should obtain our final answer.
C++ Code: https://ideone.com/a5UAju
Bookshelf
View problem here
If we ignore the color restrictions, this becomes a classic 0/1 knapsack problem. The only difference is, instead of taking the max of previous states, we simply take the sum. However, this does not always work as the problem requires you to pick books in a sorted manner. To deal with this, we can simply sort the books beforehand, then the order of the books will be implied as we process each item in non-increasing width. Finally, for the color restriction, we can simply extend our dynamic programming array from dp[x] = number of ways to obtain a total of width x, to dp[x][y = red or blue] = number of ways to obtain a total of width x, with the topmost book being color y.
However, there is one more special case that we need to consider, although it is guaranteed that no two books of the same color will have the same width, we need to consider the case when there are red and blue books of the same width. Consider the scenario where you have a red and blue book of width 5, and the bookshelf has a width of 10. If we process either book before the other, we will get an answer of 1, which is clearly wrong. Therefore, for this scenario, we will need to, in a sense, process these two books in parallel, and consider them as one single double-color book. Combining all the previous thoughts, we finally obtain our algorithm: Sort all the books by their width. Process book j in the following recurrence relationship: for(i = s to width[j]) dp[s] += dp[s - width[j]]. Furthermore, if we have two books of the same width, we also do this: dp[s] += dp[s - 2 * width[j]]. With modding, we should obtain the correct answer. The total complexity of this is just O((r + b)log(r + b)) for sorting and O((r + b)s) for the knapsack component.
C++ Code: https://ideone.com/mCVCuV
Multiply
View problem here
The problem is very similar to the version that just asks for the product of all a[i] on the range [l, r]. The only change is that we need to make an array for each parity (and from this point on we will be describing the solution to the product of all a[i] on [l, r]).
To answer the queries efficiently, we need to precompute the prefix products, skipping over the zeros. For each query the answer would be (mult[r] / mult[l - 1]) mod 1e9 + 7, which is (mult[r] * inv(mult[l - 1])) mod 1e9 + 7, where the inv() stands for the modular multiplicative inverse. That is unless there are zeros on the interval, in which case the answer is 0. So we need to check if there are zeros on the interval [l, r], which can be done with prefix sums or binary search on the list of the positions of the zeros.
C++ code: https://ideone.com/t7ReJL
Energy
View problem here
We can model the problem as a graph: the buildings are the vertices and the roads are the edges. The problem is similar to finding the shortest path from 1 to every other vertex, for which we can use Dijkstra’s algorithm. However, due to the fuel restrictions, we need to modify our algorithm and use a dynamic programming approach, in which our state is [current node][amount of fuel we have] and use Dijkstra for transitions (notice that because we are using Dijkstra, we never go back to the state we already visited).
C++ code: https://ideone.com/AYS570
Number Factory
View problem here
The key insight of this problem is to consider each node as a first order polynomial. If a node is (+,n), it’s f(x) = x + n, and if a node is (-,n), and it’s f(x) = x - n, and for (*,n), its f(x) = nx. Then, a contiguous row of machines can be represented as a composition of functions f_L(f_L + 1(f_L + 2(....f_R(x))). If f_i(x) = ax + b, and f_j(x) = (cx + d), then f_j(f_i(x)) = c(ax + b) + d = (ac)x + (bc + d), which is also a first order polynomial. Now that we have a way to “combine” machines, we can simply build a segment tree, with each segment being the function that when given x, will output ax + b. The total complexity of this problem is just O(MlogN).
C++ code: https://ideone.com/m29e38
Clique
View problem here
The first observation is that the cliques we care about form a DAG. To obtain this DAG, we can simply do a DFS from clique #N. The second observation is that the number of ways to become the captains of the cliques is independent of each other, therefore, we can simply solve for each node, and then the answer should just be the product of all of them. Consequently, this problem simply reduces to, given some currencies that are multiples of each other, what are the number of ways to get a certain sum if the order of which you pay doesn’t matter. Using the unordered nature of this problem, we can further simplify this problem to counting the number of ways to traverse a total distance of D with jumps of different strides that are multiples of each other. Furthermore, D is a multiple of all the strides, and the strides of each jump must be strictly non-increasing.
Let the longest possible stride be L, then we can apply a greedy algorithm to always jump L distance, and after each jump, we mark each of the landings points as a “pivotal point.” Then, because of the fact that the strides are all multiples of each other, we can assert that, no matter how you jump, you will always land on these pivotal points. This inspires a dynamic programming solution: dp[D][A][B] = the number of ways to jump a total distance of D, where the longest/first jump is of stride A, and the shortest/last jump’s stride is greater or equal to B. Since we only care about the jumps’ strides, and they are all multiples of each other, instead of keeping the actual numerical value of the strides A,B and the distance D, we can simply keep track of the (D/A/B)th shortest stride/distance.
Then we can do the transitions in the following manner:
dp[A + B][x][z] = sum for(y = x to z) dp[A][x][y] * dp[B][y][z]
Note that this is essentially a matrix multiplication. Where dp[A + B] = dp[A] * dp[B]. Combining this with our pivotal point observation, we can calculate this recurrence in a much faster fashion:
dp[X] = dp[X - 1] * dp[X - 1] ….. dp[X - 1] = (dp[X - 1])^(stride[X] / stride[X / 1]). Subsequently, the number of ways for node x is just the sum of (i = 1 to x) dp[x][i][1]. Our answer should just the product of all these sums. Calculating for each node simply requires a matrices self exponentiation, which is O(N^3logN), hence the total complexity of processing all the N nodes is just O(N^4logN).
C++ Code: https://ideone.com/KtRakA
An alternative and faster way O(N^3) to solve each node by blair blezers @GabeWu):
The Faulhaber numbers give you the coefficients on the polynomial expression (sum from i = 1 to x of x^k). This lets you compute the sum of the first x k'th powers quickly. Precompute faulhaber for k = 1, 2, ..., 20.
Now, you can show that you reduce the problem to the problem of doing dp[i][j] = (sum from t=1 to j * v[i] of dp[i-1][t]), where v[i] represents the quotient of successive currency values. Also, dp[0][anything] = 1. This is what it looks like if v[i] = [2, 2]:
dp[0][] = 1, 1, 1, 1, 1, 1, 1...
dp[1][] = 2, 4, 6, 8, 16...
dp[2][] = 6, 18, 44, ...
Notice that dp[0][x] is just 1; dp[1][x] is just 2x; dp[2][x] is just sum of 2i from i=1 to 2i, which is just 4x^2 + 2x; etc.
Notice that each dp[i][x] is just a polynomial in terms of x of order i.
Use Faulhaber to compute each dp state, by transforming the dp[i-1][] polynomial into the dp[i][] polynomial. Then you're done!
Guts Round
Since there are so many ways to do these problems, I will simply list the answers for each problem. If you have any questions, feel free to ask us.
1. zgvixpzutjq bybqimyfkka vmyssrbxi
2. B C W
For the rest, note that the actual answers might vary as we actually run your answers through the data, but these are just the parameters we used to generate the data.
4. (7.19762, 93.61239) (-23.61235, 86124.07124) (176.15124, -68192.01628)
5. (-0.74123, 92523.16372) (0.39624, -19824.89502) (2.61235, -8612512.51249)
6. (20,50,30,40,10,50,40,30,30) (50,20,30,20,30,40,10,30,70,30,70,30,70) (50,30,20,10,20,40,30,15,35,30,20,10,20,30,40,50,50,60,70,1,39)
Easter Egg: Download the Rickroll meme JPEG, and change .jpg to .zip. Open the zip file, and inside is a file called KEY.txt, containing the key: "--$KEYUiLA03o1y5Z0212d$--"
Finally, we will keep our Standard Round grader open, so if you want to upsolve our contest, feel free to do so. Note that you must be logged into an account that attempted the Standard Round to access the graders for security reasons. If you don't have such an account, feel free to DM CodeTiger on discord/email us, and we can set up an account for you.
Hope you liked our contest and learned something new xD.