8VC Venture Cup 2017 Elimination Round

8VC Venture Cup 2017 Elimination Round screen cast by eddy1021


Solved A,B in about 8 mins.

C is a nice problem. For a forest, it will tell you for each vertex that which vertex in the same tree distanced farthest from it if two or more are tied, the minimum indexed one will be returned.
We can directly maintain each connected component. Just union each vertex with its farthest one. But the constraint is somehow weird (N<=10000), I hesitated on it for a while.

D is another interesting problem. But with a stupid mistake, I lose about 700 points after hacked by someone(Anyway, still better than failed system test (: ).
Given n, k with gcd(n,k)=1, you are going to draw some line on a n-gon. Vertices of  n-gon are labeled clockwise from 1 to n. Start from 1, you draw a line from 1 to 1+k, then 1+k to 1+2k, and so on. If the index is bigger than n, you should subtract n out. Actually, it's just cyclic on the n-gon.
Then, after drawing each line. you should compute how many region are in the n-gon.
If i-th line will across x line drawn before, it will give x+1 more region. Thus, we just need count how many drawn line will be acrossed by this line. This can be done with BIT or segment tree.

E is a case-studying problem. Given n, k, you should construct a graph with n vertices s.t. the minimum diameter of it and its complement graph is k.
With some example, we can find that if n <= 3 or k = 1, there's no solution. After I tried lots of examples, I found that it's difficult to construct a graph s.t. it diameter and its complement graph's diameter are both large than or equal to 4.
Then, I google about "diameter graph complement". I found a theorem says if the diameter of a graph is larger than 3, the diameter of its complement graph will be less than 3. Now, we know that if k > 3, there's also no solution. And, if k==2, we just need to construct a graph with diameter > 3, its complement graph will give 2. This can be done easily with a path. Thus, we just need to construct a graph and its complement graph both have diameter of 3. This is still not too hard. Specially, n=4 is a special case.
I'm very curious about whether this theorem is well-known. And, how many contestants doesn't know it before contest and directly prove it during contest.

F is a classical problem with extended idea. The description is too long to describe :p. The main problem is that given some number, whether sum of some subset of them are equal to k. Specially, summation of all the number is at most 1000000.
It's a extended version of multiple knapsack problem. We can redistribute those number and get a equivalent set s.t. the set contain each number no more than twice and the answer to each size is exactly the same as original set.
Then, we can have a O(N \sqrt{N}) solution since there are at most O(sqrt{N}) distinct number under the condition that summation of all the numbers are at most 1000000. With some optimization(maybe no need), it can pass system test easily.

G is a classical problem. Given n, k, you should find there are how many way to choose m groups from 1 to n, where a group can be only one number or two consecutive numbers. And, you should answer the question for each m from 1 to k. Specially, the answer should be module with 998244353.
After looking the module number, it directly tell that this problem should be solved with NTT(A variation of FFT). Then, we just need to find the way to convolution. This is still not hard but I can't handle it during the contest.
Actually, it can be done with binary exponential.

Rank 24 on final standing. Regain IGM and highest rating so far after this contest. Hope to keep going on!