Contest Duration: - (local time) (100 minutes) Back to Home

## G - Teleporting Takahashi Editorial by spheniscine

The problem can be reframed as counting the number of strings of $$N$$ tokens X+, X-, Y+, Y-, Z+, Z-, such that $$\text{count}_s(\texttt{X+}) - \text{count}_s(\texttt{X-}) = X$$, and likewise for $$Y$$ and $$Z$$.

First, let’s assign $$X \leftarrow |X|$$, $$Y \leftarrow |Y|$$, $$Z \leftarrow |Z|$$, as this doesn’t affect the answer. (It’s equivalent to swapping X+ for X-, etc.)

And we consider the case that $$X + Y + Z > N$$ or $$(N-(X + Y + Z)) \text{ mod } 2 = 1$$, where the answer is $$0$$.

First let’s consider a reduction of this problem to two dimensions (i.e. omitting the Z+ and Z- tokens) for a string of length $$X + Y + 2k$$. The answer would be

$\binom{X + Y + 2k}{k}\sum_{i=0}^k\binom{X + Y + k}{X + k - i}\binom{k}{i} = \binom{X + Y + 2k}{k}\binom{X + Y + 2k}{X + k}$

The left hand expression can be interpreted as first picking $$k$$ tokens to be negative, then picking $$X+k-i$$ positives to be X+ and $$i$$ negatives to be Y- (thus leaving $$k - i$$ instances of X-). We can then apply Vandermonde’s identity: $$\displaystyle\sum_{i=0}^c\binom{a}{c-i}\binom{b}{i} =\binom{a+b}{c}$$, this can be interpreted as drawing $$i$$ balls from a bucket with $$b$$ balls and drawing $$c-i$$ balls from a bucket of $$a$$ balls, which is bijectively equivalent to drawing $$c$$ balls from the combined bucket of $$a+b$$ balls.

We’re now able to calculate the two dimensional case in $$O(1)$$, ignoring precalculation of factorials and inverses. It is thus relatively easy to solve the three dimensional case in $$O(N)$$, by fixing the number of Z+ and Z- in our string and summing the cases.

$d := \frac{N - (X + Y + Z)}{2}$

$ans := \sum_{k = 0}^{d}\binom{N}{Z+2(d-k)}\binom{Z+2(d-k)}{d-k}\binom{X + Y + 2k}{k}\binom{X + Y + 2k}{X + k}$

posted:
last update: