110A - Nearly Lucky Number

We can read in the integer as a string, and count the total number of '4' and '7'. As the length of string is at most 18, it is sufficient to check whether the total number is 4 or 7.

110B - Lucky String

One can find that the optimal sequence should have pattern 'abcdabcdabcd...', and thus we can just output the first n letters.

110C - Lucky Sum of Digits

Suppose that the minimum integer has x 4s and y 7s. Then, we have 4x + 7y = n. To construct the minimum integer, we must have x + y as small as possible. If there are multiple such pairs, we should further find the one with the maximum x, which must be unique. After obtaining the optimal (x, y), the minimum integer have a form of 444...777..77.

110D - Lucky Probability

At first, we find out all the lucky integers and sort them in an increasing order. These lucky numbers in fact have divided the interval [1, 1E + 9] into several sub-intervals, whose borders are just these lucky numbers. Suppose that we have m intervals [a₀, a₁], [a₁, a₂], ..., [a_m - 1, a_m], where a₀ = 1, a₁ = 4, a₂ = 7, a₃ = 44, ...a_m = 1E + 9. For any interval [x, y] that contains exactly k lucky numbers, we must have and . Therefore, it suffices to count the number of pairs (x, y) that satisfy the above condition. Equivalently, we can enumerate all the feasible intervals, i.e., [a_i, a_i + 1] and [a_i + k, a_{i + k + 1}], and find out the number of common integers that also appear in [p_l, p_r] and [v_l, v_r].

Moreover, one should take care of one tricky case, i.e., k = 1. As one can see, when k = 1, [a_i, a_i + 1] and [a_i + k, a_{i + k + 1}] have a common integer a_i + 1, which implies that a_i + 1 has been counted twice if it belongs to both [p_l, p_r] and [v_l, v_r]. Therefore, one should decrease the counting result by one if this case occurs.

110E - Lucky Tree

As this is a tree, deleting any edges will divide it into several independent smaller trees. We can first delete all the edges that have a weight of lucky number and then adopt “union and find” to construct the smaller connected components.

We use a_i to denote the number of nodes belonging to the i-th component. Now, instead of counting the required answer, we count the number of triples that do not satisfy the requirements. Note that if we pick all the three nodes from the i-th component, they definitely are against the requirements. This case gives , where all a_i ≥ 3. Next, if we pick two nodes from the i-th component while one node from another different component, this gives , where a_i ≥ 2. Finally, the desired result is n(n - 1)(n - 2) - n₁ - n₂.

109D - Lucky Sorting

If the given sequence is not initially non-decreasing, we need at least one lucky number.

We denote the original sequence and the sorted sequence as a and b, respectively. For each element in a, it appears in b at a unique position. There are exactly n such pairs, and thus we can adopt two arrays to record their relationship. We use atob[i] to denote that the i-th element in a is at position atob[i] in b, while using btoa[i] to denote that the i-th element in b is at position btoa[i] in a. Then, we enumerate each element in array b, and try to move the “required” element to the current position.

If i = btoa[i], it is not necessary to move any element. On the contrary, we should move the btoa[i]-th element to the i-th position. If either one of a[i] or a[btoa[i]] is a lucky number, it takes one “move” to exchange their positions. Otherwise, we can first exchange a[i] with a lucky number at position j, and then move a[btoa[i]] to the i-th position, which costs two “moves”.

From the above operations, one can check that it is always feasible to sort the original array in a non-decreasing order within 2n “moves as long as there is at least one lucky number. Note that whenever we exchange two elements, both atob and btoa should be updated at the same time.