M-SOLUTIONS Programming Contest Announcement

6 years 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.

→ Reply

spirited_away_

6 years ago, # ^ |

ok ! but what about x/d , it can be in fraction. what u did for it ?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+11

$$$\frac{x}{d}=x * d^{-1} = x * d ^ {mod - 2}$$$

→ Reply

6 years ago, # ^ |

← Rev. 2 →

radoslav11 Why upto 2*mod building for segment tree.

→ Reply

6 years ago, # ^ |

-7

x/d + n — 1 can be more than mod.

→ Reply

Rahul

6 years ago, # ^ |

+13

Answer is zero when $$$ \dfrac{x}{d} + n - 1 \geq MOD $$$.

→ Reply

6 years ago, # ^ |

Why . Does it because there will be a number which will be a multiple of mod? How

→ Reply

Rahul

6 years ago, # ^ |

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$$$

→ Reply

mango_lassi

6 years 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 F

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 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.

→ Reply

6 years ago, # ^ |

I think pC is a common problem in probability textbooks, so it may be easy for some people.

→ Reply

6 years ago, # ^ |

How you solved.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

How you come up with 100/(100-c)

→ Reply

6 years ago, # ^ |

I have seen a great comment explaining this idea before.

→ Reply

do_good_

6 years ago, # ^ |

← Rev. 2 →

+23

mango_lassi wow, amazing solution.

mango lassi solution

const int N = 2000;
bitset<N> left_wins[N];
bitset<N> right_wins[N];
bitset<N> 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<N> 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<N> res = left_wins[0] & right_wins[n-1];
	cout << res.count() << '\n';
}

→ Reply

6 years ago, # |

+42

Does the "M" stand for "Math"?

→ Reply

spirited_away_

6 years ago, # ^ |

haha Mathcoder ?

→ Reply

_LeMur_

6 years ago, # |

+21

How to solve C?

→ Reply

spookywooky

6 years 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?

→ Reply

mshcherba

6 years 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}$$$.

→ Reply