Intel Code Chanllenge Elimination Round

Title link and Code link

Question A failed even though I knew it was a pitfall. Question D took me the last five minutes to come up with an idea, but I was confused again and had no time to finish. . .

*A Broken Clock

The meaning of the question is to give the 12-timing mode and the 24-timing mode of the watch. In the 12-timing mode, the clock is in the range of 1~~12, and the minutes are in the range of 0~~59. In 24-hour timing mode, the clock is in the range of 0~~23, and the minutes are in the range of 0~~59. Ask for the smallest number to change so that the given time meets the requirements.

Note that in the case of 20:00 in the 12-timer mode, it does not become 01:00 but 10:00. . . .

B Verse Pattern

Calculate whether the number of vowel characters in each string array is equal to the given number. . .

C Destroying Array

Given an array, delete one number at a time and ask for the maximum sum of the remaining consecutive numbers after each deletion.

The other way around is to add numbers. Each time you add, use union-find to combine the left and right numbers and maintain the maximum value.

*D Generating Sets

The meaning of the question is that there are different numbers of $n$. You can choose any number $x$. There are two operations. 1. Put it back after $x*2$. 2.Put it back after $x*2+1$. After several such transformations, it becomes the given array. The requirement is to find the first n numbers so that the largest number among these n numbers is the smallest.

In fact, it is a binary tree. Each time, the largest number is selected and divided by 2 to see if it can occupy this position. If not, then search upwards until no upward path can be found.

Others just get by with set, but I have to create a priority queue + map. . . mdzz.

*E Research Rover

There is a grid of $n*m$. Initially, when standing at the point of $(1,1)$, there is an amount of oil of $S$. Now there are some points that will reduce the amount of oil by half. Ask about the expectation of the remaining oil in the grid of (n, m). After simplification, the fraction is expressed as $\frac {P}{Q}$, giving the result of $P*Q^{-1}$, where $Q^{-1}$ represents the inverse element of $Q$ module $10^9+7$.

First of all, the score of the result does not need to be considered for simplification, because assuming that $P$ and $Q$ both have a common divisor $d$, then
$$
P_{d}*d*Q_{d}^{-1}*d^{-1}=P*Q^{-1}
$$
So $Q$ is the number of plans from $(1,1)$ to $(n,m)$, and $P$ is the total amount of oil achieved in all situations.

Another thing to note about this question is that the maximum value of $S$ is $10^6$, which means that if more than 20 consumption points have passed, it will always be 1. So only the situation with less than or equal to 20 consumption points needs to be considered.

In this case, the idea is similar to [51nod’s big grid] (http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1486) (this is also on codeforces…). dp[i][v] represents the number of plans from the $v$ point to the end point through $i$ consumption points. Thinking from back to front is equal to
$$
dp[i][v] = C(n+m-x_v-y_v,n-x_v) - \sum_{j=v+1}^{k}C(x_j+y_j-x_v-y_v,x_j-x_v)*dp[i][j] - \sum_{j=0}^{i-1} dp[j][v]
$$
To explain the above formula, $C(n+m-x_v-y_v,n-x_v) $ is the total number of plans from this point to the end point, minus the previous point that passed through $i$ points, multiplied by the number of plans it has to here. This is consistent with the idea of taking a grid. This part is equal to the number of times it passes from $0$ to $i$ times to the end point. Subtracting the previous one is the number of plans that this point passes through $i$ points. Finally, it is the number of solutions at point (1,1) multiplied by the amount of oil.

Finally, considering the case where the number of passes is greater than 20, $C(n+m-2,n-1)$ subtracts the number of previously calculated solutions to get the remaining situation, multiplies it by 1, and adds it to the result.

The last question is often stuck. When calculating inverse elements, it is best to use recursion:
$$
inv[i]=(Mod-\frac {Mod}{i})*inv[Mod %i]%Mod
$$

F Cyclic Cipher

The meaning of the question is that $n$ sequences are given, and each sequence has $k_i(1 \leq k_i \leq 40 )$ numbers. Each sequence continuously cycles one bit to the right. Take the first number of each sequence and form a sequence from top to bottom. Calculate the longest continuous sequence of each number. Perform $10^{100}$ times in total. Among these, what is the longest continuous sequence of each number.

It will be found that if $x$ meet together in a continuous sequence, assuming it is at the $S$ second, the position in the $i$ sequence is $p_i$, and the length of the $i$ sequence is $k_i$, then the following conditions will be met
$$
S\equiv p_i (mod\ k_i)
$$

$$
S\equiv p_j (mod\ k_j)
$$

It is found that this is the content of Chinese Remainder Theorem. Referring to this Comment, it can be deduced:
$$
p_i+k_i*x=p_j+k_j*y
$$

$$
\Rightarrow p_i-p_j\ = k_j*y-k_i*x
$$

$$
\Rightarrow p_i-p_j\equiv 0 (mod\ GCD(k_i,k_j))
$$

Because any two in the continuous sequence must satisfy such a relationship, just enumerate the right endpoint and update the left endpoint.