skywalkert's blog

By skywalkert, history, 5 years ago, In English

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.

solution
note

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
note

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.

solution
note

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???

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

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

How fast can you achieve to solve it?

solution

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

solution

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

solution
note

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

solution
note

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

solution
note

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

solution
note

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

  • Vote: I like it
  • +79
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Due to the limitation of this Chinese online judging system, each problem can have only one secret test, and even the sample test will not be checked.

The funny thing is that a team from PtzCamp unexpectedly solved problem J in time complexity $$$\mathcal{O}(n \Sigma)$$$. Even though there exists a large test to slow it most, one test is not enough to make it TLE due to the relaxed time limit.