gabrielwu's blog

By gabrielwu, history, 4 years ago, In English

Thank you to everyone who participated in the mBIT Fall 2020 competition today! All of the information on this blog post is also available in our archive, which also includes the full leaderboard.

Problems and Editorials

Test your solutions on our Codeforces Gyms: Standard, Advanced

Results

We are pleased to announce the winners!

Advanced Division

Winning Teams:

  1. Zagreb Oblutci (HS team) — Dorijan Lendvaj (XV. gimnazija Zagreb), Krešimir Nežmah (XV. gimnazija Zagreb), Patrick Pavić (XV. gimnazija Zagreb)

  2. qncqwy6w69 (HS team) — Suneet Mahajan (Douglas Community School), Kostia Savchuk (коростишівське нвк "школа-ліцей"), Ashley Khoo (NUS High School), Fedor Romashov (The Advanced Educational Scientific Center MSU)

  3. Peer Pressure Aaron to go on a Date with BessieViraj Maddur, Aditya Parulekar, Steven Cheng, Aaron Lamoreaux

  4. cantsolvediv2a (HS team) — Hankai Zhang (Detroit Country Day School), Anthony Wang (Ladue Horton Watkins HS)

  5. jharada fan clubHuaiyu Wu, Yuting Zhou, Antonio Molina Lovett, Maryam Bahrani

  6. Coastal Demolishers (HS team) — Richard Qi (Princeton HS), Anand John (Brandywine HS), Nathan Chen (Garnet Valley HS), Shiva Oswal (Seven Springs Academy)

Standard Division

Winning Team: <input class="input" placeholder="Insert Creative Name Here">Ryan Bai (Carmel Valley MS)

Second Place MS Team: Watermelon JuiceDaniel Wu (Tilden MS), David Sy (Tilden MS), Paul Trusov (Tilden MS)

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

calen_golin orz

»
4 years ago, # |
  Vote: I like it -53 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    We're glad you enjoyed our contest! We spent a lot of time this past year writing problems and organizing the event. It makes us feel great when we see people like you who show up and try our problems, even when they're hard. We hope to see you at the next mBIT!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    setters are not to blame for your low level

»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

$$$ \sum\limits_{1\leq m\leq M}\sum\limits_{C_m\leq i\leq N}i\cdot{i-1 \choose C_m-1}C_m!(N-C_m)! $$$

Which simplifies to

$$$ \sum\limits_{1\leq m\leq M}C_m(N-C_m)!\sum\limits_{C_m\leq i\leq N}\frac{i!}{(i-C_m)!} $$$

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

$$$ \sum\limits_{1\leq i \leq n}\frac{(i+k-1)!}{(i-1)!} = \frac{(n+k)!}{(n-1)!(k+1)} $$$

Applying the formula, we get a really nice simplification:

$$$ \sum\limits_{1\leq m\leq M}C_m(N-C_m)!\frac{(N+1)!}{(N-C_m)!(C_m+1)} = (N+1)!\sum\limits_{1\leq m\leq M}\frac{C_m}{C_m+1} $$$

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

»
4 years ago, # |
Rev. 5   Vote: I like it +24 Vote: I do not like it

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);
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Woah, these solutions are both really slick! Goes to show that combo problems almost always have multiple solutions.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can find the problems in the pdf in the Contest Materials at the bottom right.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for pointing this out.

»
4 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

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.

Fna3gV.md.png

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    We had another $$$O(n\ log\ n)$$$ solution during the contest.

    First, add $$$1$$$ to $$$k$$$ to make things nicer.

    Make a difference array from the input array. So for $$$mod\ 11$$$, the array $$$1,6,3,2,7$$$ turns into $$$1,5,8,10,5$$$. Now an operation in the original array corresponds to adding $$$1$$$ to some position in the new array and subtracting $$$1$$$ from some other position, or just adding/subtracting $$$1$$$ from a single position. The goal is still to have every element equal to $$$0\ mod\ k$$$.

    Now you should choose some elements which will tend to $$$0$$$, and others which will tend to $$$k$$$. Let $$$x$$$ be the number of "subtract $$$1$$$" operations needed to make everyone in the first pile $$$0$$$, and $$$y$$$ for everyone in the second pile to be $$$k$$$ using "add $$$1$$$" operations. Then you can solve it in $$$max(x,y)$$$ operations.

    It's not too hard to prove that there exists some number $$$i$$$ such that it is optimal to choose the smallest $$$i$$$ numbers which will tend to $$$0$$$ and the rest of them which will tend to $$$k$$$.

    So just sort the numbers and try every $$$i$$$.

    code

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

It was an amazing problemset. Thanks.

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

skittles1412 orz

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Sorry, Codeforces doesn't seem to allow people to view other people's codes unless you're in coach mode for public gyms. So if you're in coach mode, you can see other people's code, but otherwise, the only way to make this happen is to make the gym private and send out invite links (please correct me if I'm wrong). And yep, thanks for catching our error with the code for Night of the Candles. We have fixed it, so it should be working now.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    That's a very good question! In our initial solution we assumed that to be true, and it wasn't until much later that we realized we needed to account for rotations of more than K. Consider this case:

    N = 17, K = 2
    2 1 0 2 1 0 2 1 0 1 2 0 1 2 0 1 2
    

    The optimal answer is 9. This involves rotating the full interval [1,17] up by 1, then the interval [2, 16] up by 1, then the interval [3, 15] up by 1, and so on. The 0 in the middle ends up being rotated 9 times.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Wow that’s very hard to come up with, thanks ! Also, I’m a bit confused on what the optimization with suffix maximums is doing in the code, I had an idea to do something with a lazy segment tree but I’m not sure how to simplify it more

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 3   Vote: I like it +13 Vote: I do not like it

        gabrielwu 12tqian can either of you help me out with this?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          There are two types of transitions to go to $$$dp[i][0][j]$$$. The first type is $$$dp[i][0][j] = dp[i-1][1][k] + u[i][j]$$$. We can speed up this transition to $$$\mathcal O(1)$$$ by storing the max of $$$dp[i-1][1][k]$$$ across all $$$k$$$ after we advance $$$i$$$ each time.

          The other type of transition is if $$$dp[i][0][j] = dp[i-1][0][k] + \max(0, u[i][j] - u[i][k])$$$. There are two possibilities. One, $$$j = k$$$, which we can process in $$$\mathcal O(1)$$$. Two, $$$j < k$$$, in which case $$$u[i][j] < u[i][k]$$$, and the maximum is just $$$0$$$. So we must need to consider $$$dp[i-1][0][k]$$$ for $$$k > j$$$, which can be done using suffix minimums as we iterate down $$$j$$$. Three, $$$j > k$$$. Then we have to consider the minimums of $$$dp[i][0][k] - u[i][k]$$$ (you can take out the $$$u[i][j]$$$ and add it back in at the end) across all $$$k < j$$$. This can easily be done using a prefix/running minimum as we iterate up $$$j$$$.

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    Hi,

    I may have used a different naming convention in the Python code, but the main idea is the similar as the editorial. This was my convention (a "red" node is one that has a battle fort):

    Given node u, let up[u][k] represent the maximum number of battle-ready paths there can be which have at least one node in the subtree of u such that

    • The edge between u and u's parent is directed up.

    • There are exactly k red nodes reachable from u that are ancestors of u.

    Similarly, down[u][k] represents the maximum number of battle-ready paths there can be which have at least one node in the subtree of u such that

    • The edge between u and u's parent is directed down.

    • There are exactly k nodes in total that are ancestors of u and can reach u.

    Then the transitions are as follows (let v iterate over all children of u):

    • If u is red, up[u][k] = k+(sum of max(up[v][k+1], down[v][1]) )

    • If u is white, up[u][k] = k+(sum of max(up[v][k][up], down[v][1]) )

    • If u is red, down[u][k] = k+(sum of max(up[v][1], down[v][k+1]) )

    • If u is white, down[u][k] = (sum over of max(up[v][0], down[v][k+1]) )

    I'll leave it to you to prove this recurrence.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Nice! It is somewhat similar, but I think this way thinks about end points differently. It also avoids the knapsack transition, and it is more clearly $$$O(n^2)$$$.