No jiangly will win

Upd: oh he really won! orz

good contest!

I cannot do it either mate

think of O( Q * 26 ) complexity

Really? I felt like E was just "yeah this is your standard ABC dijkstra problem, enjoy implementing for 10-15 mins :)" while F actually required some rough thinking.

How did you do for F ?

Any ideas why this solution to E :: Last Train fails just a single test case?

it's prime factorization i think

count-of-pairs-in-an-array-whose-product-is-a-perfect-square

How ? I implemented segTree with sets in G, but D was just dividing and checking a pair of cases

are you serious?？

We can achieve a square number bigger than 2e5

Why would the squares be bounded by $$$2 \cdot 10^5$$$?.

Consider $$$A = [5 \cdot 10^4, 2 \cdot 10^5]$$$, here $$$A_1 \cdot A_2 = 10^{10}$$$ which is a perfect square greater than $$$2 \cdot 10^5$$$.

Ai = 2e5, Aj = 2e5, the product is equal to (2e5)^2. So squares till 2e5 are not enough.

First compute the probability that dealer gets at least $$$x$$$ points linearly. Then do dynamic programming over $$$dp[x]$$$ = probability that you win if you start with $$$x$$$ points.

https://atcoder.jp/contests/abc342/submissions/50612581

For the dealer we can simulate the probabilities of them having a particular sum at the end since they have a fixed move for a given sum.

dealer_probabilities[0] = 1
for x in [0, l - 1]:
    for y in [1, d]:
        if x + y <= n:
            dealer_probabilities[x + y] += dealer_probabilities[x] / d
    dealer_probabilities[x] = 0

Now for the player, if we stop at a specific score $$$x$$$, we know the probability of winning is $$$\text{player_probability[x]} = 1 - \sum_{i = x}^{n}{\text{dealer_probability[i]}}$$$. However, we can also decide to continue playing, in which case it becomes the average probability among all possible dice rolls, i.e, $$$\frac{\sum_{i = x + 1}^{\text{min(x + d, n)}}{\text{player_probability[i]}}}{d}$$$, so we take the max of these two values. Doing this in decreasing order of $$$x$$$ gives us a way to calculate the probability for all scores.

for x in [n, 0]:
    stop_playing_probability = 1
    for y in [x, n]:
        stop_playing_probability -= dealer_probability[y]
    continue_playing_probability = 0
    for y in [1, d]:
        if x + y <= n:
            continue_playing_probability += player_probabilities[x + y] / d
    player_probabilities[x] = max(stop_playing_probability, continue_playing_probability)

Then player_probability[0] is the value you want. To speed this up from $$$O(n ^ 2)$$$ to $$$O(n)$$$, use difference arrays and prefix sums to get rid of the inner loops in both of the above parts.

Notice that there are at most 26 distinct characters in the string xD (Initially, I was on the verge of doing small in large)

I couldn't even understand statement of $$$B$$$

Tl;dr — Simple range addition, point query segtree except t[v] is a multiset of possible values and you take the max of all of the sets.

Let each node contain a multiset of possible values for the range. Initially this is $$$a_i$$$ for a leaf node and nothing for all other nodes.

When we perform a lazy update for the range $$$[l, r]$$$, we will add this to the set of each of the terminal nodes ($$$l = tl$$$ and $$$r = tr$$$) we reach.

Now every node in the range $$$[l, r]$$$ is covered by at least one of these nodes, so for each query we can just walk over all the nodes which cover the position and take the max of all the values.

Note that cancellations are now just update operations but with "erase 1 occurrence of x" instead of "insert 1 occurrence of x".

Code

Consider this input:

7
atcoder
3
a d
e d
d v

Your code gives dtcovvr as output. However, d is supposed to be replaced by v. Why do we still see d in the output?

You can find square-free part of number (make sure to handle zeros separately). In particular, the square-free parts of both numbers must be equal. Or, you can do something similar to what is done in 1225D - Power Products, where you ignore zeros, and check the rest (there are only $$$\mathcal{O}(\log 10^5)$$$ prime factors for each number).

the main idea is: 1. build the graph from end to begin(not from begin to end) 2. using Dijkstra

the code he used is C++20, a little smooth.