We will hold M-SOLUTIONS Programming Contest.
- Contest URL: https://atcoder.jp/contests/m-solutions2019
- Start Time: https://www.timeanddate.com/worldclock/fixedtime.html?iso=20190601T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- writer: yokozuna57
- Rated range: ~ 2799
The point values will be announced later.
We are looking forward to your participation!
How to solve problem E https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_e.
i find a blog on stack exchange https://math.stackexchange.com/questions/165266/how-to-find-the-product-of-n-terms-of-an-arithmetic-progression-where-common-dif
will it work ?
I used this formula answ = x * d^(n — 1) * f( d / x , n — 1 ), where f(x,y) = fact(x + y) / fact(x — 1).
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.
ok ! but what about x/d , it can be in fraction. what u did for it ?
$$$\frac{x}{d}=x * d^{-1} = x * d ^ {mod - 2}$$$
radoslav11 Why upto 2*mod building for segment tree.
x/d + n — 1 can be more than mod.
Answer is zero when $$$ \dfrac{x}{d} + n - 1 \geq MOD $$$.
Why . Does it because there will be a number which will be a multiple of mod? How
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$$$
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:
Observe 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
andright_wins
. In the $$$b$$$'th position ofright_wins
, in the $$$I$$$'th bit, store if person $$$I$$$ can win interval $$$[I+1, b]$$$. Similarly in the $$$a$$$'th position ofleft_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
andright_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 ofright_wins[b]
, and the $$$b$$$'th bit ofleft_wins[a]
. To update these, setwins[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
andright_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.I think pC is a common problem in probability textbooks, so it may be easy for some people.
How you solved.
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 B
Finally consider the C value by multiply $$$\frac{100}{100-c}$$$ to the expectation
How you come up with 100/(100-c)
I have seen a great comment explaining this idea before.
mango_lassi wow, amazing solution.
Does the "M" stand for "Math"?
haha Mathcoder ?
How to solve C?
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?
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}$$$.
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.
How to solve D?
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.
Thanks aarcee.
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).
You are sorting by the degree of each vertex instead of sorting it by the size of subtree.
Thanks.
F was very similar to the D1 1000 from the last TopCoder round.
Yes, it's very similar. I haven't checked this TC task, sorry...
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))?