.

Maybe yes

very very bad comment. Stupid

How is it humanly possible to solve B in 9min 😨

I used log-exp trick, though get WA on test 21

we want to compute first 250 coefficents of ((1+x/1)*(1+x/2)*...*(1+x/(n-1))/n with good precision

we will compute log and then exp

when we will compute log we must compute sum of inverse kth degrees from 1 to n-1

if k=1 it is bruteforce for n<=1e5, otherwise it is log((n-1))+lambda+1/(2*1.0*(n-1))+(1/(12*(n-1)*(n-1)))+o(1/n^2) from https://en.wikipedia.org/wiki/Harmonic_number (i don't know, in Russian version of wikipedia it is +1/(12n^2) in English it is -1/(12n^2)...).

if k>=2 it is 1+1/2^2+...+1/c^2+1/(c+0.5)-1/(n-0.5)+O(1/c^3) (c is 100000)

if k>=3 bruteforce

then exp, luckily it passes

Reformulate the problem, now each guy has number $$$n$$$ and each second does $$$n \to \text{rand}\pmod{n}$$$, whoever reaches $$$0$$$ first wins.

Our solution: almost surely the winner is determined in $$$K$$$ seconds, say, $$$K=200$$$. Let's calculate $$$f(n, k)$$$ being the probability that we reach $$$0$$$ in exactly $$$k$$$ seconds.

Denote by $$$e_k(x_1, \ldots, x_m)$$$ the sum of all $$$k$$$-products of numbers $$$(x_1, \ldots, x_m)$$$. Then $$$f(n, k) = e_{k-1}(1/1, \ldots, 1/(n-1))/n$$$ (exercise for the reader). We can calculate this if we know all respective $$$p_k(1/1, \ldots, 1/(n-1))$$$, where $$$p_k(x_1, \ldots, x_n) = \sum x_i^k$$$.

I cannot say how to do it numerically correctly as I didn't get AC.

You can calculate sums of such type using https://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula

It can be solved using greedy.

Claim 1: It is optimal to use the computer as soon as we can.

Claim 2: It is not optimal to just let a contestant sit idly. Our priority would be to minimize this as much as possible after ensuring the first claim.

Let's say, some contestant just finished solving some task using the computer at $$$X$$$ time unit. Now find the minimum $$$i$$$, such that some contestant can finish solving a problem at $$$(X+i)$$$ time unit using the computer. If you can't find any, no more problems can be solved.

Also, define $$$F_j$$$ = the time unit when $$$j$$$ th contestant gets free

There could be more than one contestant, who can finish solving a problem at $$$(X+i)$$$ time unit. Among them, we pick someone such that his idleness period is minimized. More formally, among them, $$$j$$$ th contestant,

$$$~~~~~~~~~~G_j=X+i-F_j-\text{time required to solve the problem}$$$

Pick the contestant with minimum $$$G_j$$$.

If again, more than one contestant has the same $$$G_j$$$ pick the one who has the minimum $$$F_j$$$.

.

It should be there soon :icpc website Furthermore you should be able to know it from the stream of the closing ceremony

Here it is: https://swerc.eu/2022/theme/scoreboard/public/

If there's a vertex u with degree <n-1, then we can divide edges into (u, v) and (v, w) 2 kinds (v, w!=u). Otherwise the graph is complete graph, we need to devides into 3 kinds: (1, 2), (u, 2) (u!=1) and (u, v) (otherwise).

Thanks bcollet and YocyCraft for the help

java.util.Scanner is extremely slow when dealing massive input. Maybe you can try to use java.io.BufferedReader instead.

In my experience, in most problems requiring some care with floating point precision it is very hard/impossible to prove that the official solution is accurate enough.

Here is a list of not-so-deep things that can mitigate the risk of having a wrong official solution.

1. Implement different solutions performing the operations differently. If they agree (to the desired precision), then it is likely that they are both accurate enough.
2. If replacing doubles with long doubles does not change the result (to the desired precision), then it is likely that the solution is accurate enough.
3. If you ask for precision $$$\epsilon$$$, make sure that your solutions have precision $$$\epsilon/10$$$ or better.
4. If you ask for precision $$$\epsilon$$$, consider enforcing only precision $$$1.1\epsilon$$$.

This is just my take on the matter, if other problem setters have different ideas, I am curious to read them.

Maybe I am not understanding, x = maxsum is the solution.

In your submission, you wrote:

int maxseg = pref.back();
for(int x : {x1, x2, maxseg}) {
  // check each one
}

Here maxseg is actually storing the total number of Ws in the string, right? Or am I missing something in your template? From your comment I assumed that by maxseg you meant the maximum number of Ws in a segment of length n, in which case maxseg always works (as in the editorial).

Yes, we will do it soon!

Here is my summary of the proof:

Vertices from $$$G_k$$$ can be written as $$$(u, b)$$$, where $$$u$$$ is a vertex from $$$G$$$ and $$$b$$$ is a length-$$$k$$$ bitstring.

The edges in $$$G_k$$$ between copies of a vertex $$$v$$$ from $$$G$$$ form an hypercube graph.

Let $$${u, v}$$$ be an edge from $$$G$$$. Consider a vertex $$$(u, b)$$$ from $$$G_k$$$, where $$$b$$$ is a length-$$$k$$$ bitstring.

• if $$$u$$$ and $$$v$$$ have same color, $$$(u, b)$$$ is connected to $$$(v, b)$$$ (proof intuition: we always connect the same copies)

• if $$$u$$$ and $$$v$$$ have different colors, $$$(u, b)$$$ is connected to $$$(v, \overline{b})$$$, where $$$\overline{b}$$$ is the bitwise negation of $$$b$$$ (proof intuition: we always connect to the different copy)

Call a path in $$$G$$$ even (odd) if the number of multicolored edges it uses is even (odd), i.e. the number of times it walks to a vertex of a different color from the previous one

The length of the shortest path between $$$(u, b_u)$$$ and $$$(v, b_v)$$$ is given by the shortest of the following:

• The length of the shortest even path between $$$u$$$ and $$$v$$$ plus $$$\Delta(b_u, b_v)$$$, where $$$\Delta(\cdot, \cdot)$$$ is Hamming distance (proof intuition: go from $$$u$$$ to $$$v$$$ following an odd path and then take the shortest path in the hypercube graph, which is the Hamming distance)

• The length of the shortest odd path between $$$u$$$ and $$$v$$$ plus $$$\Delta(b_u, \overline{b_v})$$$

If the diameter is between $$$(u, b_u)$$$ and $$$(v, b_v)$$$ then there is another diameter between $$$(u, {\tt 00 \ldots 0})$$$ and $$$(v, b_v')$$$, for some $$$b_v'$$$ (proof intuition: the graph is symmetric, so "translate" this path to start in $$$(u, {\tt 00 \ldots 0})$$$).

The distance between $$$(u, {\tt 00 \ldots 0})$$$ and $$$(v, b)$$$ for some $$$b$$$, is either the "shortest even path between $$$u$$$ and $$$v$$$" plus $$$|b|$$$, or "shortest odd path between $$$u$$$ and $$$v$$$" plus $$$k - |b|$$$ (proof intuition: either take an even path between $$$v$$$ and $$$u$$$ and then go from $$$b$$$ to zeros in the hypercube, or take an odd path between $$$v$$$ and $$$u$$$ and then go from $$$\overline{b}$$$ to zeros in the hypercube).

The algorithm can now be described by: for all pairs of vertices in $$$G$$$, $$$u$$$ and $$$v$$$, compute maximum over $$$0 \leq x \leq k$$$ of minimum between "shortest even path between $$$u$$$ and $$$v$$$" plus $$$x$$$, and "shortest odd path between $$$u$$$ and $$$v$$$" plus $$$k - x$$$. You can compute these even/odd paths with a BFS, so this is $$$O(nm + n^2k)$$$.

can you help me understand the proof?

I read the tutorial but didn't understand why Ll or Rr will be >= n

like in this example for n = 4

WRRRWRR

x = 1

if we took the interval [1,4] and check for r=5 Rr(the shortest interval ending with r) will be equal to 1 which is smaller than n