My $$$O(n\sqrt n)$$$ solution for problem D that works in just 78 ms!

My approach for problem C, Binary search the waiting time before starting to move. https://codeforces.com/contest/1716/submission/166993379

Solution to 1716F - Bags with Balls using the multinomial theorem.

Let $$$ B $$$ iterate through all the ways $$$ (b_1,\dots, b_n) $$$ to take the balls out of the bags and define $$$ g(x):= x\text{ mod } 2 $$$, and $$$F(B):=\text{# of odd balls}$$$. The answer we want to compute is

Now suppose $$$c$$$ of the $$$n$$$ indices are positive, there are $$$\binom{n}{c} $$$ ways to choose them. Also notice that we can just erase the indices equal to $$$ 0 $$$ from the multinomial coefficient (the answer remains the same). So rewriting the sum

we can compute the last part since the indices of the bags from which we pick odd balls are fixed

We arrive at finall formula we can compute in $$$O(k)$$$ (not taking in account the precomputations) after noticing that

Where $$$ S(i,j) $$$ is the stirling numbers of the second kind.

In problem C, at least for me, letting a_ij+1 be the time limit instead of aij is somehow frustrating, and the lack of explanation for samples make it even worse.

video Editorial for Chinese:

Bilibili

Question on problem D. There is an approach that calculates the same as in the editorial, but in a slightly different way, and gets WA. The solution is the following: let's calculate $$$dp_i,_j$$$ — the number of ways to achieve $$$i$$$ using $$$j$$$ steps. $$$dp_0,_0 = 1$$$. Transition is presented in full form and can be calculated faster.

$$$dp_i,_j$$$ = $$$\sum_{w=1, q=k+j-1}^{i - wq >= 0} dp_{i - wq},_{j - 1}$$$

What is the difference between calculated $$$dp_i,_j$$$ from the solution described above and calculated $$$dp_s,_i$$$ from the editorial?

Would any kind-hearted person mind explaining to me why "the sum of F^k over all possible combinations is equal to the sum of G(t) over all possible tuples t"? I am not able to figure out why they are equal, what is the intuition behind and how could we prove it (the rest is straightforward tho, just can't comprehend the rephrased problem)

Can anyone who used prefix sums for calculating $$$dp[i][j]$$$ for D share their code? I'm having trouble implementing it.

In problem $$$A$$$, can anybody explain solution using modulo. I don't want to deal with rounding. It's confusing for me. If $$$n$$$ $$$mod$$$ $$$3 = 0$$$ then answer is $$$\frac{n}{3}$$$, else if $$$n$$$ $$$mod$$$ $$$2 = 0$$$ then answer is $$$\frac{n}{2}$$$. But what in other cases ?

With how unusually long the editorial for C is, I'm surprised that the problem-setters still felt it was appropriate to keep it as a Div2C.

For D, the editorial should probably mention how we need to keep track of the first non-zero value in each row (variable $$$mn$$$ in the solution) and only start filling it up from there, since it seems like starting from the beginning resulted in many TLEs.

Does anyone have a testcase that breaks my submission for C? 167164510

F can be solved more easily by using Stirling Number and Descending Power.

There is a much easier way to solve F.

A classic conversion is that:

Using the above formula:

Consider the combinatorial meaning of the red part. It chooses some boxes to take out balls with odd numbers, then it chooses $$$i$$$ of them, and calculate the number of ways. Let's reverse the steps, we can find out that the answer to the red part is equal to the number of ways to perform the following steps:

1. Choose $$$i$$$ balls.
2. Let the chosen balls be odd numbers. No constraints on the rest of the balls.

Thus, the answer can be simplified as follows:

which can be solved in $$$\mathcal{O}(k^2)$$$.

How to solve problem C if you can visit the cell more than once??

Problem C can also be solved in super ugly way using binary lifting and segment tree.

Video Solution for Problem C.

Can somebody help with this submision, It takes O(m) time and I get time limit. https://codeforces.com/contest/1716/submission/167315560

F can also solved this way: The answer can be represented as:

If we let $$$p$$$ $$$=$$$ $$$ \frac {\lceil {m/2} \rceil}{(m - \lceil{m/2}\rceil)}$$$ then our objective is to compute the following sum:

Let:

Then it's clear that the answer is $$$dp(k) (m - \lceil{m/2}\rceil) ^ {n}$$$. Now it follows that:

where $$$s(i,j)$$$ is stirling number of the first kind. If we let $$$g_{i} = f_{i}(p) p^{i}$$$, then:

where $$$S(i,j)$$$ is stirling number of the second kind.

How to solve Question D during contest because I'm not able to think about such transitions between sum[] and dp[] array?

Can anyone explain how to approach these kind of dp questions?

For problems like C, I found it's incredibly time-consuming for me to get every +1/-1/0 right, like the indices starting from 0/1, the number of steps required starting from the first cell/before the first cell. Does anybody have suggestions for dealing with this?

Is D's time limit too strict? Just adjusting some int/long long representations and whether printing the newline operator can change TLE to AC.

Hello, BledDest, for the problem B-Permutation Chain ( t (1≤t≤99) n (2≤n≤100)), I submitted this code, but I'am getting TLE surprisingly.

static void solve() { int n = sc.nextInt(); System.out.println(n); int[] arr = new int[n];

for(int i=0; i<n; i++){
        arr[i] = i+1;
        System.out.print(arr[i]+" ");
   }

   System.out.println();
   int temp=0;

   for(int i=1; i<n; i++){

            temp = arr[i-1];
            arr[i-1] = arr[i];
            arr[i] = temp;
            for(int j=0; j<n; j++){
                System.out.print(arr[j]+" ");
            }
            System.out.println();

   }
}