Dec 2021 Diagnostic Test
I’m not sorry.
Scoreboard
FizzBuzz
Counting with extra steps
Stats
I’ve excluded the trainers I could find, but I couldn’t be bothered to check that everyone on the scoreboard was a Dec Course participant, so the stats might be off by a tiny bit :)
# of full scores: 96�Average score: 80.6
Abridged Statement
Print the numbers from 1 to N, but instead print ‘Fizz’ when it is divisible by A, ‘Buzz’ when it is divisible by B and ‘FizzBuzz’ when it is divisible by both
Subtask 1 (35 points): N=100, A=3, B=5
Since the constraints for this subtask are fixed and small, you can just manually (or computationally) work out the output and print it.
I believe that some of you got this subtask because you didn’t know how to read input in C++, so you just wrote a program that worked for this case.
Another way to only get this subtask: if you try to print FizzBuzz when the number is divisible by A times B, you will only get this subtask. Consider: if A and B are not coprime, then numbers not divisible by A times B may still be divisible by both. For example, for A=2 and B=4, 12 is divisible by both 2 and 4 even though it’s not divisible by 8. 3 and 5 are coprime, so this problem doesn’t arise.
Subtask 2 (65 points): No more constraints
#include <bits/stdc++.h>�using namespace std;�int main() {� int N, A, B;� cin >> N >> A >> B;� for (int i = 1; i <= N; ++i) {� string str = "";� if (i % A == 0) str += "Fizz";� if (i % B == 0) str += "Buzz";� if (str == "") str = to_string(i);� cout << str << '\n';� }� return 0;�}
December Training Workload
!based on a true story
Stats
# of full scores: 16�Average score: 20.7
Tester comments: “I think my opinion on the difficulty of this problem may be biased because the key insight was explained in the IMO manga.”
I may have slightly underestimated the difficulty of this question, I thought it would have been much easier than Q3 and Q4
(Image courtesy of tester)�Source: https://mangakakalot.com/chapter/hn926066/chapter_5
Abridged Statement
Find the number of distinct non-decreasing sequences of N non-negative integers that sum to K.
Subtask 1 (31 points): N,K≤7
There are only 49 possible combinations of N and K, and the answers aren’t huge. It’s entirely possible to manually work out all of the answers. I know because some of you did precisely that, made a mistake, and then asked me whether something was wrong with the test cases.
Alternatively, if you coded any dynamic programming solution but did not apply memoization (so it was just naive recursion), you would have gotten this subtask.
Subtask 2 (42 points): N,K≤400
Let us consider the function f(n,k,last). f(n,k,last) gives us the number of non-decreasing sequences with n elements that sum to k, such that all elements are at least as big as last.
f(0,0,last)=1�f(0,k,last)=0�f(n,k,>k)=0�f(n,k,last)=f(n-1,k-last,last)+f(n,k,last+1)
We note that our answer is simply f(N,K,0).
Subtask 2 (42 points): N,K≤400
We note that to compute f(N,K,0), we only need to work out values of f(n,k,last) for n up to N, k and last up to K.
Each value can be worked out in O(1). The three base cases in the previous slide can be trivially handled, while the one recursive case just requires adding two values from smaller values of n and k and larger values of last.
So if we process from (0,0,K) to (N,K,0), we can work out f(N,K,0) in O(NK2) time. This is enough to pass this subtask.
Subtask 3 (27 points): N,K≤5000
We need to find a way to avoid storing the last parameter. Let us just consider g(n,k), the number of non-decreasing sequences of n non-negative integers that sum to k.
The first number in the sequence is either 0 or it is not.
If it is not 0, every number in the sequence must be greater than 0. So we subtract 1 from all of them and they are still non-negative and non-decreasing, so there are g(n,k-n) such possible sequences.
If the first number is 0, we can remove the first number from the sequence. The rest of the sequence is non-negative and non-decreasing, so there must be g(n-1,k) such sequences.
Subtask 3 (27 points): N,K≤5000
In other words, we have a new recursive function g(n,k) as follows:
g(n,<0)=0�g(0,0)=1�g(0,k)=0�g(n,k)=g(n,k-n)+g(n-1,k)
Each value of the function can be worked out in O(1), and there are O(NK) possible inputs to the function, so the algorithm runs in O(NK) and passes.
There is a slightly less optimal version of this algorithm that turns out to run in �O(K2 logN), where the logN comes from summation of reciprocals.
workload_ex
It is possible to solve this problem in O(N logN).
However, this method involves use of knowledge beyond IOI syllabus. It will not be taught in Dec Course and I cannot recommend that you attempt workload_ex unless you are already confident with everything within IOI syllabus (in which case please come and join us as trainer).
Problematic Journey
Are you questioning the questions in this contest?
Stats
# of full scores: 20�Average score: 25.1
Tester comments: “Q3 is classic huh”
I thought this problem was the hardest one to implement in the entire contest. Graph algorithm codes are like that sometimes. The idea is quite classic though so I’m not surprised more of you solved it.
Abridged Statement
Find the smallest possible X such that you can go from node 1 to node N in a connected undirected weighted graph by passing over at most K edges while only using edges with weight at most X.
Subtask 1 (39 points): W=1 for all edges
Since all edges have weight 1, the only question is whether the shortest path from 1 to N passes through at most K edges.
This is a classic single source shortest path problem. With the problem constraints, Dijkstra’s algorithm will pass, but it is simpler and more sensible to use the Breadth First Search method for shortest path on unweighted graphs.
If the shortest path is at most K edges, print 1. Otherwise, print -1.
Dijkstra time complexity: O(E logE)�BFS time complexity: O(N+E)=O(E)
Subtask 2 (26 points): N,E≤2000
We observe that the answer must be the weight of one of the edges (if it isn’t, we can lower it slightly without blocking any edge we need).
We reconstruct a new graph for each possible answer using only the edges that are small enough and check whether there is a way to get from 1 to N in at most K edges. This is exactly the same as Subtask 1.
We choose the smallest possible answer that works, or -1 if there is no such answer.
Time complexity: O(E(N+E))=O(E2)
Subtask 3 (35 points): N,E≤200000
We observe that if there exists a path from 1 to N in at most K edges such that all the edges are at most weight X, the same path also satisfies the criterion for X+1.
This is monotonicity, allowing us to apply binary search for the answer.
(Binary search: we check whether the middle value between 0 and 109 works. If it does, we replace 0 with the middle value, otherwise we replace 109 with the middle value. We repeat until both upper and lower bound are the same. That gives us our answer.)
Time complexity: O(E logE)
Zoo Queue
The solution? A zoo stack
Stats
# of full scores: 18�Average score: 22.3
Tester comments:�[00:22] setter: i have no idea what you're talking about�[00:22] tester: neither do i dw
I thought this problem was going to be really hard. And it was. Except that a lot of the experienced contestants scammed it.
Abridged Statement
Determine if a permutation of [1...N] contains a subsequence of length 3 such that the middle element is smallest and the left element is largest
Subtask 1 (13 points): N≤400
Just iterate over all possible triplets of numbers in the permutation and check whether they satisfy the requirement.
This can be done in O(N3).
Short aside: there is no reason for you not to get these 13 points. Please.
Subtask 2 (30 points): N≤5000
Consider all possible middle elements b.
Note that if b is the middle element in some triplet (a,b,c) that satisfies the condition, then (a0,b,c) where a0 is the largest element to the left of b must satisfy the condition. So we iterate over all elements to the left of b to find a0.
Now we can iterate over all elements to the right of b to see if any c exists such that b<c<a0. Each of these iterations takes O(N) time, so iterating once for each element takes a total of O(N2) time, which is sufficient to pass this subtask.
Subtask 3 (30 points): N≤200000
We see that we can optimise the finding of a0 by computing the prefix maximum array in O(N) time. This gives us a0 for every b.
Now we can easily solve the problem if only we could check for c more quickly. We observe that if we let c0 be the smallest element to the right of b so that b<c0, then if b<c<a0 for some c to the right of b then we must have b<c0<a0. So if we can find c0 quickly, the problem is solved.
We need to quickly find the smallest element larger than some value in an array. Sounds familiar?
Subtask 3 (30 points): N≤200000
We can use a binary search tree! (C++ STL set, since we don’t have duplicates)
We iterate from right to left, keeping a set of all the elements we’ve encountered so far. For each new element b, we simply use set.upper_bound to find the corresponding c0 value in the set.
Now we just need to check whether any b has a0>c0 and we are done.
This can be done in O(N logN) and will pass this subtask.
Subtask 4 (27 points): N≤2000000
This subtask is intended to be solved with a linear-time solution.
There are a wide array of solutions to this subtask, using various tools such as stacks, queues, union-find disjoint sets, et cetera. Most ideas either make use of the concept of storing decreasing “runs” of numbers, or optimise the set method of finding c0.
There are also some O(N logN) scams. By far the most common was using Fenwick tree, but some used priority queues and one person used binary search. As these were fast O(N logN) solutions, they could not be differentiated and were allowed to pass. All of them are variations of the set method of finding c0.
Intended Solution
No one managed to come up with the intended solution. (Which is fair, it is kind of a bit out of the blue.)
Consider a stack. We push the integers from 1 to N into the stack in order. However, we are also allowed to pop the top element of the stack at any time and print it. At the end, all numbers should have been pushed into the stack before being popped and printed. Determine whether it is possible to create a certain sequence by timing the pops correctly.
I claim that “it is possible to create the sequence” is equivalent to “there exists no triplets satisfying the condition in this question”.
Intended Solution
If the sequence does contain such a triplet (a,b,c), then b must be pushed before c, which must be pushed before a. Only then do we pop a, with b and c still in the stack. This means that c must have been on top of b in the stack, which means when we popped b, c must have been popped first. So it is impossible to create such a sequence.
And if the sequence does not contain such a triplet, then it is simple. We iterate through the elements of the sequence. If an element has not been pushed yet, we push it (and all smaller elements) into the stack, and then pop it. Otherwise, we claim that it must be the current top element and can be popped.
Intended Solution
Let’s say we have some number b that has been pushed but is not on the top of the stack. Let’s say the current number at the top of the stack is c. However, we note that using our algorithm, the largest number pushed must be popped immediately. Let’s call the largest number pushed “a”. Now, since c has not been popped, it must appear behind b in the sequence. However, this means that we have the triplet (a,b,c) such that b<c<a in the sequence.
So, there is no such b that has been pushed but is not on the top of the stack when time comes to pop it out. So it is always possible to run our algorithm and create the sequence if there exists no such triplet.
Intended Solution
DNA (IOI)
This problem was here as a joke
Stats
# of full scores: 7�Average score: 11.4
Tester comment: “i'm not going to code out dna on phone”
I thought this problem was actually a good bit easier than Q4, but the pressure of it being an IOI problem would scare all of you. Seems like it worked.
Short Editorial
If we have “AT” in A and “TA” in B, we can fix 2 mistakes with one swap.
If we don’t have any more such pairs, we can fix 3 mistakes in two swaps by turning “ATC” into “TAC” and then into “CAT”.
So we always want to fix all the pairs first, and then fix the triplets.
We can count them using prefix sum, which also allows us to determine whether it is possible (check number of “A”, “T” and “C”).
Think about subtasks yourself.