2018 CMUT BeihangU Contest, Editorial

Revision en8, by skywalkert, 2019-06-18 16:00:18

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 is now finished, in which I try to elaborate on notes, solutions and maybe some data generating. Alternatively, you can refer to an old published material, though I think the old English version did not explain something clearly.

102114A - Always Online

This problem requires to calculate $$$s$$$-$$$t$$$ min cut between any two vertices on a weighted cactus graph having $$$n$$$ vertices, denoted by $$$\mathrm{flow}(s, t)$$$. You need to report $$$\sum_{s < t}{(s \oplus t \oplus \mathrm{flow}(s, t))}$$$.

$$$n \leq 10^5$$$, $$$\sum{n} \leq 10^6$$$, weights are $$$\leq 10^9$$$.

Try to find some features of this graph.


102114B - Beautiful Now

Given an integer $$$n$$$, you are asked to swap digits of $$$n$$$ in exactly $$$k$$$ turns. In each turn, you can swap two digits, which can be the same digit, but after this turn, $$$n$$$ must not have any leading zero. Calculate the maximal and the minimal values you can get in the end.

$$$100$$$ tests, $$$n, k \leq 10^9$$$.

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

solution 1
solution 2

Wait, wait, wait... Does it seem like a notorious coincidence with this problem? What? This problem has an incredible data range... ($$$n < 10^{1000}$$$) 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 integer polynomials. Besides, the statement contains some mathematical formulas you may need to apply.

$$$n \leq 10^5$$$, $$$\sum{n} \leq 5 \times 10^6$$$.

Maybe you just need some observation to solve.


102114D - Daylight

Given an unweighted tree having $$$n$$$ vertices, you need to determine the union of two sets and report its size for $$$m$$$ queries, 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).

$$$10$$$ large tests, $$$n, m \leq 10^5$$$.

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

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


102114E - Everything Has Changed

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


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)$$$.

$$$n \leq 32$$$, $$$p_i \leq 10^9$$$.

How fast can you achieve to solve it?


Here is an old problem with smaller data range. If anyone can tell me who the author is, I will add the credit soon.

102114G - Glad You Came

There are $$$m$$$ operations over an array $$$a_1, a_2, \ldots, a_n$$$, each operation of which is to update $$$a_i$$$ $$$(l \leq i \leq r)$$$ by $$$\max(a_i, v)$$$. You need to determine the array after all the operations.

$$$n \leq 10^5$$$, $$$\sum{n} \leq 10^6$$$, $$$m \leq 5 \times 10^6$$$, $$$\sum{m} \leq 5 \times 10^7$$$. Besides, $$$l, r, v$$$ are randomly selected.

solution 1
solution 2
solution 3

102114H - Hills And Valleys

Given an array of length $$$n$$$, consisting of $$$0, 1, \ldots, 9$$$, your task is to reverse exactly one interval and then make the longest non-decreasing subsequence of the whole array as long as possible. The reversed interval is also required to report.

$$$n \leq 10^5$$$, $$$\sum{n} \leq 2 \times 10^5$$$.


102114I - Innocence

Count the number of solutions for the equation $$$x_1 \oplus x_2 \oplus \cdots \oplus x_N = K$$$, where $$$x_i$$$ can be any integer in $$$[L, R]$$$. There are $$$Q$$$ queries with the same $$$N, L, R$$$ but different $$$K$$$.

$$$100$$$ large tests, $$$N \leq 10^9$$$, $$$0 \leq L, R, K < 2^{30}$$$, $$$Q \leq 100$$$.


102114J - Just So You Know

A non-empty substring $$$B$$$ is selected from a given string $$$A$$$ of length $$$n$$$ with equal probability among all the possible substrings. You are given the string $$$A$$$ and asked to determine which the substring $$$B$$$ is. More precisely, you need to guess out what it looks like, instead of where it is in the string.

You can claim conjectures and then the jury will prove that it is true or false. You need to find a strategy to minimize the expected number of claiming and report the expected number as an irreducible fraction.

$$$n \leq 10^6$$$, $$$\sum{n} \leq 10^7$$$, character set size $$$\Sigma \leq 100$$$.


102114K - Kaleidoscope

Count the number of non-isomorphic colored rhombic hexecontahedrons such that each face of each polyhedron are colored by one of $$$n$$$ given colors and the $$$i$$$-th color occurs on at least $$$c_i$$$ faces of each polyhedron. Report the number modulo $$$p$$$.

Two states are isomorphic if and only if one can transform into another by 3D space rotation.

In geometry, a rhombic hexecontahedron is nonconvex with $$$60$$$ golden rhombic faces with icosahedral symmetry.

$$$100$$$ large tests, $$$n \leq 60$$$, $$$1 \leq p < 2^{30}$$$.


102114L - Lost In The Echo

Calculate the $$$n$$$-th term of the sequence A140606 in modulo $$$(10^9 + 7)$$$.

This term means the number of inequivalent expressions having $$$n$$$ distinct variables where each variable occurs exactly once, and only binary operators $$$+$$$, $$$-$$$, $$$*$$$, $$$/$$$ (and with parentheses) are permitted, which means unary minus or plus is forbidden. Two expressions are equivalent if and only if they can be simplified as the same rational expression.

$$$n = 1, 2, \ldots, 6 \times 10^4$$$.


Which problem do you prefer or hate most? Feel free to share your thoughts in comments! ^_^

Tags #editorial


  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)