2018 CMUT BeihangU Contest, Editorial

Revision en3, by skywalkert, 2019-06-17 14:56:28

This editorial corresponds to 2018 Chinese Multi-University Training, BeihangU Contest (stage 5), which was held on Aug 6th, 2018. Moreover, this problem set was also used as Jingzhe Tang Contest 1 in Petrozavodsk Winter Camp on Jan 30th, 2019.

This post will try to elaborate on notes, solutions and maybe some data generating. Before that finishes, you can refer to an old published material.


102114A - Always Online

This problem requires to calculate $$$s$$$-$$$t$$$ min cut between any two vertices on a weighted cactus graph. Try to find some feature of this graph.

solution
note

102114B - Beautiful Now

This problem is yet another problem related to swapping. Can you solve it simply and elegantly?

solution 1
solution 2
note

Wait, wait, wait... Does it seem like a notorious coincidence with this problem? What? This problem has an incredible data range... Does it really solvable??? Oh, I can't believe that!!! >_<


102114C - Call It What You Want

This problem asks you to factorize polynomial $$$(x^n - 1)$$$ over the field of the integers. Besides, the statement contains some mathematical formula you may need to apply. Maybe you just need some observation to solve.

solution
note

102114D - Daylight

This problem can be explained as given an unweighted tree, you need to determine the union of two sets and report its size, where each set is a set of vertices whose distances to a given vertice are no more than a fixed value, and the values for two sets are the same. However, queries are encrypted so you need to handle them one by one (online).

Emmm... A typical data structure problem, right?

Certainly I've found it on CodeChef. What? Why TLE???

solution

102114E - Everything Has Changed

A geometry problem to ensure you have checked in this contest. Read the statement for more details.

solution
note

102114F - Fireflies

Consider all the lattice points in a hypercube $$$\lbrace (x_1, x_2, \ldots, x_n) | 1 \leq x_i \leq p_i \rbrace$$$. Find a maximal subset such that there are no two points $$$(x_1, x_2, \ldots, x_n)$$$, $$$(y_1, y_2, \ldots, y_n)$$$ meeting the condition $$$x_i \leq y_i$$$ for all $$$i$$$. Report its size modulo $$$(10^9 + 7)$$$.

solution

Here is an old problem with small data range.

Tags #editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English skywalkert 2019-06-18 16:00:18 5709 add editorial for L; it is finally finished lol
en7 English skywalkert 2019-06-18 14:00:45 3893 fix typos; add missing details
en6 English skywalkert 2019-06-17 21:44:53 8785 add editorial for J and K; add data range and other details
en5 English skywalkert 2019-06-17 17:38:57 681 add missing part for I
en4 English skywalkert 2019-06-17 17:26:10 5147 add editorial for G to I
en3 English skywalkert 2019-06-17 14:56:28 4828 add editorial for D to F; fill more details in previous sections
en2 English skywalkert 2019-06-17 12:43:20 5037 add editorial for A to C
en1 English skywalkert 2019-06-17 11:10:10 468 Initial revision (published)