2018 CMUT BeihangU Contest, Editorial

Правка en4, от skywalkert, 2019-06-17 17:26:10

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)$$$. How fast can you achieve to solve it?

solution

Here is an old problem with smaller data range.


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.

There are some restrictions, such as $$$l, r, v$$$ are randomly selected, and $$$m \approx n \log n$$$.

solution 1
solution 2
solution 3

102114H - Hills And Valleys

Given an array 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.

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

solution
Теги #editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский skywalkert 2019-06-18 16:00:18 5709 add editorial for L; it is finally finished lol
en7 Английский skywalkert 2019-06-18 14:00:45 3893 fix typos; add missing details
en6 Английский skywalkert 2019-06-17 21:44:53 8785 add editorial for J and K; add data range and other details
en5 Английский skywalkert 2019-06-17 17:38:57 681 add missing part for I
en4 Английский skywalkert 2019-06-17 17:26:10 5147 add editorial for G to I
en3 Английский skywalkert 2019-06-17 14:56:28 4828 add editorial for D to F; fill more details in previous sections
en2 Английский skywalkert 2019-06-17 12:43:20 5037 add editorial for A to C
en1 Английский skywalkert 2019-06-17 11:10:10 468 Initial revision (published)