### rng_58's blog

By rng_58, history, 16 months ago,

We will hold M-SOLUTIONS Programming Contest.

The point values will be announced later.

We are looking forward to your participation!

• +75

 » 16 months ago, # |   0 How to solve problem E https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_e.will it work ?
•  » » 16 months ago, # ^ |   0 I used this formula answ = x * d^(n — 1) * f( d / x , n — 1 ), where f(x,y) = fact(x + y) / fact(x — 1).
•  » » » 16 months ago, # ^ |   0 can u explain me how u calculated ?
•  » » 16 months ago, # ^ |   +26 First handle the $D=0$ corner case. Now we know that if $N \geq mod$, answer is $0$.Let's look at $x * (x + d) * (x + 2d) * ... * (x + (n - 1) * d)$. We will get $d$ out of every bracket and get $d^n * \frac{x}{d} * (\frac{x}{d} + 1) * (\frac{x}{d} + 2) * ... * (\frac{x}{d} + n - 1)$. This is basically a product of consecutive numbers when having them moded.To find this product fast, we can build a segment tree for products on {1, 2, 3, 4, ..., 2 * mod}. Another way is to do suffix and prefix products.
•  » » » 16 months ago, # ^ |   0 ok ! but what about x/d , it can be in fraction. what u did for it ?
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   +11 $\frac{x}{d}=x * d^{-1} = x * d ^ {mod - 2}$
•  » » » » » 16 months ago, # ^ |   0 ok , inverse + fermat's theorem .. i get it. thanks ! :)
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 radoslav11 Why upto 2*mod building for segment tree.
•  » » » » » » 16 months ago, # ^ |   -7 x/d + n — 1 can be more than mod.
•  » » » » » » » 16 months ago, # ^ |   +13 Answer is zero when $\dfrac{x}{d} + n - 1 \geq MOD$.
•  » » » » » » » » 16 months ago, # ^ |   0 Why . Does it because there will be a number which will be a multiple of mod? How
•  » » » » » » » » » 16 months ago, # ^ |   0 Let $k = \dfrac{x}{d} \pmod{MOD}$. Note that $k \lt MOD$. The answer reduces to$d^n \cdot \left( k \cdot (k + 1) \cdots (k + n - 1) \right) \pmod{MOD}$. Now if $k + n - 1 \ge MOD$, it is clear that one product term is equal to $MOD$
 » 16 months ago, # | ← Rev. 2 →   +18 What's with the difficulty distribution? A,B,D are trivial, F was pretty hard, and C,E are impossible :/I liked F a lot though. My solution is $O(n^{3} / 64)$ with bitsets: Solution to FObserve that person $I$ can win interval $[a, b]$ only if he can win someone who can win interval $[a, I-1]$ and someone who can win interval $[I+1, b]$.Create two arrays of bitsets, left_wins and right_wins. In the $b$'th position of right_wins, in the $I$'th bit, store if person $I$ can win interval $[I+1, b]$. Similarly in the $a$'th position of left_wins, in the $I$'th bit, store if person $I$ can win interval $[a, I-1]$. If $b < I$ or $I < a$, then the bit is zero.Now person $I$ can win interval $[a, b]$ only if the $I$'th bit of left_wins[a] & right_wins[b] is set.To calculate left_wins and right_wins, Make two loops, one looping $b$ from $0$ to $n-1$, and the inner looping $a$ from $b$ to $0$. For the interval $[a, b]$, $a < b$, update the $a$'th bit of right_wins[b], and the $b$'th bit of left_wins[a]. To update these, set right_wins[b][a] = ((wins[a] & left_wins[a+1] & right_wins[b]).count() > 0 ? 1 : 0); left_wins[a][b] = ((wins[b] & left_wins[a] & right_wins[b-1]).count() > 0 ? 1 : 0); wins[I] is a bitset just storing the persons person $I$ wins against, so the first just checks if there exists someone who can win interval $[a+1, b]$ who $a$ can win, and the second does the same for inteval $[a, b-1]$ and $b$. Note that every bit of every position of left_wins and right_wins gets calculated once (except where $I < a$ or $b < I$), and every time we calculate it, we do some operations on a bitset with size $n$. Therefore we do $O(n^{3} / 64)$ work.The answer will be (left_wins[0] & right_wins[n-1]).count(), since bits set to one in that are the persons who can win the entire contest.
•  » » 16 months ago, # ^ |   +8 I think pC is a common problem in probability textbooks, so it may be easy for some people.
•  » » » 16 months ago, # ^ |   0 How you solved.
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 consider the case when $c = 0$then you can calculate the expectation of A wins the game in i steps for $i$ = $n$ to $2*n - 1$$E(i) = i * C(2*n-1,i) * p_a^n * p_b^i$and do the same thing with BFinally consider the C value by multiply $\frac{100}{100-c}$ to the expectation
•  » » » » » 16 months ago, # ^ |   0 How you come up with 100/(100-c)
•  » » » » » » 16 months ago, # ^ |   0 I have seen a great comment explaining this idea before.
•  » » » » » 2 months ago, # ^ |   0 Can you explain the formula ?
•  » » 16 months ago, # ^ | ← Rev. 2 →   +23 mango_lassi wow, amazing solution. mango lassi solutionconst int N = 2000; bitset left_wins[N]; bitset right_wins[N]; bitset wins[N]; int main() { int n; cin >> n; for (int i = 1; i < n; ++i) { string str; cin >> str; for (int j = 0; j < i; ++j) { if (str[j] == '1') wins[i][j] = 1; else wins[j][i] = 1; } } for (int b = 0; b < n; ++b) { right_wins[b][b] = 1; left_wins[b][b] = 1; for (int a = b-1; a >= 0; --a) { bitset mask; mask = wins[b] & left_wins[a] & right_wins[b-1]; if (mask.count() > 0) left_wins[a][b] = 1; mask = wins[a] & left_wins[a+1] & right_wins[b]; if (mask.count() > 0) right_wins[b][a] = 1; } } bitset res = left_wins[0] & right_wins[n-1]; cout << res.count() << '\n'; } 
 » 16 months ago, # |   +42 Does the "M" stand for "Math"?
•  » » 16 months ago, # ^ |   +5 haha Mathcoder ?
 » 16 months ago, # |   +21 How to solve C?
•  » » 16 months ago, # ^ |   -10 And, what is "the expected number of games". Number of games with a possibilitie of min 0.5 of reaching n? And, how can "the expected number of games" be a fraction?
•  » » 16 months ago, # ^ |   +15 We can reduce the problem to one with $C = 0$. Just normalize $A$ and $B$, so that $A + B = 1$, and multiply the answer by $\frac{1}{1 - C}$.
•  » » 16 months ago, # ^ |   +19 I will denote by $a$, $b$ and $c$ the probabilities and not the percentages. First find the expected number of turns to have a non-draw outcome. It is equal to $\frac{1}{1-c}$ and I will denote it as $d$.Now let's fix the number of wins of the first player, assuming the second will win. Let this number be $x$. Then we choose which of the games will be wins for the first player. This means we will have to add to the answer: $d * (n + x) * \binom{n + x - 1}{x} * (\frac{a}{a + b})^x * (\frac{b}{a + b})^n$. We do the same if the first player wins.
•  » » » 16 months ago, # ^ |   0 Thanks.
 » 16 months ago, # |   +1 How to solve D?
•  » » 16 months ago, # ^ |   0 Consider a straight tree like 1-2-3-4-5. We can notice that we have to assign ci values in increasing/decreasing order to attain the maximum value. The same thing applies to any tree. Considering 1 as the root and every path from 1 to a leaf node should be in decreasing order to attain the maximum value where our maximum value is the sum of all c[i]'s except the largest value. This is equivalent to every node in subtree should be less than or equal to the root node of the subtree. Sort all the subtrees by their sizes and assign them the values in increasing order of c[i]'s.
•  » » » 16 months ago, # ^ |   0 Thanks aarcee.
•  » » » 16 months ago, # ^ |   0 I used dfs starting from the index having maximum size of subtree. And kept assigning them c[i]'s in decreasing order. i.e. the root gets a higher value of c[i] than any of its children. But I got WA. This is my submission . What is the problem with my code(logic).
•  » » » » 16 months ago, # ^ |   0 You are sorting by the degree of each vertex instead of sorting it by the size of subtree.
•  » » » » » 16 months ago, # ^ |   0 Thanks.
 » 16 months ago, # |   +20 F was very similar to the D1 1000 from the last TopCoder round.
•  » » 16 months ago, # ^ |   0 Yes, it's very similar. I haven't checked this TC task, sorry...
•  » » » 16 months ago, # ^ |   0 no issue even though similar, many dont solve this problem earlier.
 » 16 months ago, # |   0 Am I correct that in C's editorial 1 is added as because Y(m) = c*(1 + Y(m)) + (1-c)*(1 + Y(m-1))?