Auto comment: topic has been updated by gabrielwu (previous revision, new revision, compare).

calen_golin orz

very bad contest problems are very hard. Leetcode contests was better

Update: Aaron asked Bessie out, and FJ gave his blessing!

Here is my alternate solution for Textile Display (problem 9).

Consider for each color $$$m$$$, it's contribution to the result. Suppose that it has a final occurrence at index $$$i$$$ (1-based). Then it contributes $$$i$$$ to the sum. This can happen in $$${i-1 \choose C_m-1}C_m!(N-C_m)!$$$ ways. So a formula which gives the final answer is

Which simplifies to

Now we use the following formula to evaluate the last part of the above expression: (see here)

Applying the formula, we get a really nice simplification:

So we can solve this in $$$O(N+M)$$$ without precomputing any factorials, inverse factorials, etc.

Alternate solution to 102824I - Textile Display:

We consider this as an expected value problem, where we want to find the expected number of villagers that see a given color, if the textiles are permuted randomly. Let's say there are $$$N$$$ total textiles, and $$$C$$$ of this special color.

In this case, we'll rephrase randomly permuting the textiles like this: consider a circular bracelet of $$$N+1$$$ textiles, $$$C+1$$$ of which are the special color. This divides the bracelet into $$$C+1$$$ segments that look like ...YYYYX where X is special and Y is non-special. Select an X to put at the end, and cut the bracelet to form a line ending with that X.

The expected number of villagers to see the special color is $$$(N+1) - \mathbb{E}[\text{length of the last segment}]$$$. Since all the segments are symmetric, this is $$$\displaystyle (N+1) - \frac{N+1}{C+1}$$$.

Therefore, summing over all colors (treating each one as special once), and multiplying by $$$N!$$$ to get the total instead of the EV, we have $$$\displaystyle N! \sum (N+1) \left(1 - \frac{1}{C_i+1}\right)$$$.

Code (98410227):

modnum ans = 0;
for (auto c : counts)
    ans += 1 - 1 / (c + 1);
ans *= modnum::factorial(n + 1);

Sorry for stupid questions but I cannot see the problem in gym! Its not visible.

There is actually a $$$O(n \log n)$$$ solution for Locked in the Past (problem 5).

(I think this is same definition as editorial)

We define $$$dp[i][j]$$$ as the cost after processing first $$$i$$$ positions of the lock and turning the current section by $$$j$$$. Note that $$$j=A_i \pmod k$$$, also note that here I increment $$$k$$$ so that numbers are on $$$[0,k)$$$.

Now, the transition for this is as follows, suppose $$$j \geq 0$$$, $$$dp[i+1][j]$$$ is the minimum over $$$dp[i][k], k \geq j$$$ and $$$dp[i][k]+j-\max(k,0),k<j$$$. The case for $$$j \leq 0$$$ is similar.

It may not seem so obvious but our $$$dp$$$ function is actually slope trick-able.

We focus on $$$j \geq 0$$$ first.

For some $$$dp[i+1][j]=\min(dp[i][k_1], dp[i][k_2]+j-k_2)$$$, where $$$k_1$$$ is the smallest integer bigger than $$$j$$$ and $$$k_2$$$ is the largest integer smaller than $$$j$$$ due to the fact that $$$j=A_{i+1} \pmod k$$$ and $$$k_2=A_i \pmod k$$$, $$$j-k_2$$$ is a constant.

Somehow, this function is concave upwards. We shall store the difference between $$$dp$$$ value and see how this value changes.

Suppose $$$dp=\{0,1,3,6,9\}$$$ and the value of the change is 2. Our new $$$dp'=\{0,1,3,5,8,11\}$$$.

Lets look at the difference arrays $$$diff=\{1,2,3,3\}$$$ and $$$diff'=\{1,2,2,3,3\}$$$. It turns out we just added the value of the change inside. Now we can use priority queue to store this slope function.

The case for $$$j<0$$$ is similar.

We can easily update our $$$dp$$$ function with $$$2$$$ slope functions, one for $$$j<0$$$ and another for $$$j \geq 0$$$ with special care taken for values near 0 to maintain that $$$j<0$$$ and $$$j \geq 0$$$ for each slope function respectively. Thus, we have solved the problem in $$$O(n \log n).$$$

source code

It was an amazing problemset. Thanks.

skittles1412 orz

Kinda random, just wondering, what’s Maxwell Zhang’s codeforces handle?

Thanks for Instructive Problems! galen_colin Will you make video Editorials for this? That'd be really Great!!

Please make other's Code public in the Gym. This helps a lot! Also the code for 6th(Night of the Candles) isn't opening.

In the editorial of "textile displays" it is mentioned that we can precompute inverses of factorials in linear time. How to do it (I know how in nlogn)?

For "Locked in the Past", what's a test case where you'd have to rotate a wheel more than K? It seems like that'd never be optimal?

Thank you for the contest, I really enjoyed the problemset!

Can anyone explain the Python solution for Tanya's Revenge given in the editorial? gabrielwu 12tqian