If the problem is to solve $$$a_1 x_1 + a_2 x_2 + ... = b$$$ then you just iterate over parity of $$$x_1, x_2, ...$$$ and then reduce the problem to one where each $$$a_i$$$ is doubled.

waiting for the programs to finish

So now that you've solved every problem(and can access every problem's discussion page), can you tell us if the "one-minute rule" is real?

That Prime Contest task discussion

Do you know how to find ref. [5] (罗煜翔。(2020)。浅谈 Nimber 和多项式算法。IOI2020 中国国家集训队论⽂集。) ? I wanna see how to do semi-relaxed multiplication in $$$ \frac{n\log ^2 n}{\log \log n} $$$(if that's what it says). And what nimbers have to do with it xd.

Do you have this report as a PDF?

https://codeforces.me/blog/entry/101672

https://codeforces.me/blog/entry/51880?#comment-358982

I also couldn't get it for a long time. The problem I had was that you can do inclusion-exclusion over sets where you do put the $$$ \lt $$$ signs into and then the solution is pretty much the same except at the end you need to sum over all possible "merges" of a sequence(like for [2,3,1] you sum over [2,3,1], [5,1], [2,4], [6]) which looks unsolvable.

Had to read the beginning carefully again to understand it.

I still can't download A's full input(status code 500). If it's just me, could anyone help me out and upload it somewhere? Every other problem's fine.

Also no K=1 tests in D1 -- kinda evil.

This is so bizarre. What's the smallest $$$\varepsilon$$$ such that an $$$O(n^\varepsilon)$$$ algorithm deserves a CVE? More or less than 1.5?

Notice that u with minimal number of elements in S(u) is a leaf.

Do you know how to prove this? It does make sense intuitively.

The real question is why would you keep your email public?

I don't understand how primitive types works in Kotlin. They say

On the JVM platform, numbers are stored as primitive types: int, double, and so on.

Well, first of all, I don't understand what that means. Let's assume it means something like "Int, Double etc. are equivalent to primitive java types". But then why do we need IntArray and the like?(and yes, I know the answer is that IntArray is int[] and Array<Int> is Integer[]).

Now let's look at val MOD = (1e9 + 7).toInt(). How is this going to work? Which object is toInt() going to be invoked on? Or is it going to be optimized during compilation?

If it's the former then all of this is kinda useless for CP. If it's the latter, it's very cool of course but kind of... opaque? Is this the case for every method of Int(Double)?

All in all, many questions, almost no answers(or I can't be bothered to try and find them).

No analysis for BOXES? I'll post my linear solution in the meantime.

After thinking and wolframing for a bit, the task boils down to computing $$$_2F_1(-k,k-n;1;\frac43) = F(-k, k - n)$$$ for all $$$k$$$ from $$$1$$$ to $$$n$$$. After googling and reading about this for a bit, we find out about so called "contiguous relations" for hypergeometric functions that let us find in $$$O(1)$$$ the value of $$$F$$$ at one of the "neighbors"(in the 2D-space of $$$(a,b)$$$ pairs) of $$$(a,b)$$$ given $$$F(a,b)$$$ and the value of $$$F$$$ at another of its neighbors. So we naively compute $$$F(-1,1-n)$$$ and $$$F(-2,1-n)$$$ and then kind of "walk down" this staircase. You only need formulae 15.2.14 and 15.2.19 from here.

I mean, sure, the basic notions of various algebraic structures and properties is certainly helpful in that context but my perception of the OP question was that they were interested in some actual group theory concepts or results(like Burnside's lemma) applicable in CP.

And since I've already started writing this comment, two examples come to my mind:
1. Problems like "two strings are called equivalent if we can make them the same by performing some operations like insert '121' anywhere or delete '21' substring, do something about it". You say that these rules are actually presentation of a group and that simplifies the problem. Example
2. Schreier–Sims algorithm, which was discussed (in Russian) here.

wut

A very minor nitpick: the algorithm from "Subset Sum Speedup 2" section actually finds the largest sum not exceeding $$$C$$$, doesn't just check if a set with sum $$$C$$$ exists.

And here is a more substantial nitpick: towards the end of "(max,+) convolution" when you start describing how to build a totally monotone matrix to feed it to SMAWK, the linked paper simply says "...Consider the matrix $$$A$$$ with $$$A_{ij} = a_j +b_{i−j}$$$, where we suppose that elements of the sequences with out-of-bounds indices have value $$$- \infty$$$." (they need row maxima, hence the negative infinity).
But this is wrong! The matrix constructed this way will not be totally monotone, which you can easily see by looking at a 2x2 submatrix with three $$$\infty$$$ in it. The infinities added "above" the matrix must be strictly increasing and those added "below" must be decreasing(in each row). Also, the "lower" and "upper" infinities must always compare the same way, doesn't matter how exactly.

How do you become a tester as an unrated user?

The idea of using two different functions that are only equal at prime arguments is brilliant!

Also there is a simpler description of step 2 that shows how to solve this problem for any number instead of just 4.
What we need is to find $$$\sum f(p a_i)$$$ given $$$p$$$ and $$$\sum f(a_i)$$$. In our case, $$$f(n)[x] = n^k x^n$$$ -- a polynomial in $$$x$$$.
But then $$$f(p a)[x] = (p a)^k x^{p a} = p^k (a^k (x^p)^a) = p^k f(a)[x^p]$$$ which is linear at can be applied to the whole sum.

Apparently this algorithm is attributed to Gauss. You can make it guaranteed $$$O(\log n)$$$ by noticing that $$$p = nq + r = n(q+1) - (n-r)$$$ and $$$\min(r, n - r) \le \frac n2$$$.

But no one usually analyses your simpler one-liner version.

Thanks, this is pretty neat. It's also pretty interesting how your fetch method both pulls information from parent and pushes it down to children.

You can also do this with the usual down-propagation: just store two "push" variables in each node — one for propagating down the splay tree and another for propagating to your "light" children. cancel then only makes sense for splay tree roots so maintaining it in rotate is much simpler: just copy parent's value to the child. On the flip side you need to handle the actual "light" children propagation during expose but you're already doing some extra work there because of subtree sum queries.

Who is this Min25 guy anyway? They're like a modern Prometheus, bringing the most arcane NT-algorithms into our measly CP realm. Yet I've never heard anything about them except their nickname.

This code is pretty weird tbh.

1. You use map instead of set.
2. I don't get why we need sets in the first place, during "query merging" you can just check if the query endpoints were in the different components before and will be in the same component after(yes, that means the other "clone" of this query becomes a dead weight). Doing it this way also removes a log from the complexity.

https://codeforces.me/blog/entry/74847

First of all, orz orz orz.

But I don't think the solution you linked uses mcfx optimization. AFAICT, mcfx optimization counts the number of times a node has been pushed into the queue, and if it's in $$$[2; \sqrt V ]$$$ then it push_front's otherwise it push_back's. It speeds up your solution from 1637 ms to 343 ms!

That's a 2016 problem xD

How does this work if you edit your post/comment?

There're several on Project Euler.

I just meant the numbers can get $$$n$$$ times larger.

To add to all that's been said, this is (almost) as difficult as max-plus convolution since you can do a[i] += i * INF; b[i] += i * INF.

A https://acm.timus.ru/problem.aspx?space=1&num=1481

Exactly the same problem, even the input/output format.

You need somehow to only count each arrangement only once. This isn't straightforward to do in the "cycle" case because multiplying the polynomials only accounts for the sequence of chains lengths. So in addition to that we also say that each sequence starts where the "chain" containing "$$$b_0 \le b_1$$$ starts.

And if the first "chain" has length $$$k$$$ then there're $$$k$$$ position(i.e. "$$$\le$$$" inequalities that we always keep) where it can be started, because the $$$b_0 \le b_1$$$ inequality can be at the any of $$$k$$$ positions in that chain and that position uniquely corresponds to a starting position.

Example: say $$$n=10$$$ and the chains lengths are $$$( 3, 2 )$$$. This corresponds to 3 arrangements:
$$$b_0 \le b_1 \lt b_2 \le b_3 \lt b_4 \le b_5 \wedge b_6 \le b_7 \lt b_8 \le b_9$$$

$$$b_8 \le b_9 \lt b_0 \le b_1 \lt b_2 \le b_3 \wedge b_4 \le b_5 \lt b_6 \le b_7$$$

$$$b_6 \le b_7 \lt b_8 \le b_9 \lt b_0 \le b_1 \wedge b_2 \le b_3 \lt b_4 \le b_5$$$

1) If n is even.
$$$a_0 + a_1 \lt m \Leftrightarrow a_0 \le m - 1 - a_1$$$.
So if we consider the sequence $$$ b_i = ( a_0, m - 1 - a_1, a_2, \dots, m - 1 - a_{n-1} ) $$$ then every number must belong to $$$[0; m)$$$ and we must have $$$b_0 \le b_1 \ge b_2 \le \dots \le b_{n-1} \ge b_0$$$
(if you use $$$m - a_i$$$ then some numbers are in $$$[0..m)$$$ while others are in $$$[1..m]$$$ which was a bit inconvenient to me).

Now, we apply inclusion-exclusion principle for all "$$$\ge$$$". Let's break the cycle(ignore the $$$b_{n-1} \ge b_0$$$ condition) first to make it easier.
What this means is we always keep all the $$$\le$$$ signs, and replace some of the $$$\ge$$$ signs with $$$ \lt $$$ while ignoring the rest of $$$\ge$$$, count the numbers of sequences satisfying all the inequalities we got, multiply it by $$$(-1)^{\textrm{[# of \gt 's we ignored]}}$$$ and then sum it over all $$$2^n$$$(or $$$2^{n-1}$$$ since we ignore the last inequality right now) possibilities of inverting/ignoring the signs.

For example we might get something like $$$b_0 \le b_1 \wedge b_2 \le b_3 \lt b_4 \le b_5$$$ -- several independent chains of $$$\le$$$ and $$$ \lt $$$ alternating. How many solutions are there to $$$b_0 \le b_1 \lt b_2 \le b_3 \lt \dots \lt b_{2k-2} \le b_{2k-1}$$$? It's pretty simple to find out it's $$$f_k={{m+k}\choose {2k}}$$$.

If we consider a polynomial $$$P(x)=-f_1 x - f_2 x^2 - f_3 x^3 - \dots$$$ and calculate $$$1 + P + P^2 + P^3 + \ldots = \frac{1}{1-P}$$$, then its $$$x^n$$$ coefficent gives us exactly the number we needed(multiplied by $$$(-1)^n$$$).

How to deal with the cycle? First of all, we can't use all $$$n$$$ "$$$ \gt $$$" signs since it would mean $$$b_0 \gt b_0$$$. Before, we always had the first "chain" that started with $$$b_0 \le b_1$$$. Now let's say the first "chain" is the one that contains the $$$b_0 \le b_1$$$ condition. It's easy to see that if this first "chain" has length $$$k$$$(e.g. $$$k$$$ "$$$\le$$$" signs), then there are $$$k$$$ positions where it could've started and other than that it's exactly the same as in the "no-cycle" case.
So you just need to consider $$$Q(x) = -f_1 x - 2 f_2 x^2 - 3 f_3 x^3 - \dots$$$ and the answer is $$$Q + Q P + Q P^2 + \dots = \frac{Q}{1-P}$$$.

2) If n is odd.

Let's say a number $$$x$$$ is big if $$$x \ge \lceil \frac{m}{2} \rceil$$$ and small otherwise. As I've said above, since two large numbers can't be next to each other, you can split your cycle into segments which look like "small-large-small-large-small". So we only need to a) find out how many possible segments there are for each possible segment length and b) how to use that information to solve the problem.

b) is very similar to the solution of part 1), except you don't need to use the PIE.

To solve a), first subtract $$$\lceil \frac{m}{2} \rceil$$$ from every large number. If $$$m$$$ is even, you just got the "no-cycle" case of part 1), however the length of your sequence is now odd instead of even.
If $$$m$$$ is odd, you have to notice that a small number $$$\lfloor \frac{m}{2} \rfloor$$$ can't be next to a large number, so you can set $$$m := m-1$$$, EXCEPT that $$$\lfloor \frac{m}{2} \rfloor$$$ still can be used in a segment of length 1.

Finally, how to deal with the fact that the sequence length is now odd? Similarly to solving the "circle" problem of part 1), we must consider the first chain separately. There are $$${m + k - 1} \choose {2k-1}$$$ solutions to $$$b_0 \gt b_1 \ge b_2 \gt \dots \gt b_{2 k - 3} \ge b_{2 k - 2}$$$ so you just define a polynomial $$$R$$$ that has these coefficients and the answer is $$$\frac{R}{1-P}$$$(here we'll need all of its terms, not just a single one).

orz

To make it a bit clearer for anyone else: the part about odd $$$n$$$ means that we can split our circle into segments of form $$$xy \dots yx$$$.

The (non-rigorous) conclusion I came to answer my question(why does/could it work for every function) was: essentially all the functions we usually use in these kind of problems can be given by their Taylor series. So stuff like exp, ln, square root, etc. is just a linear combination of the polynomial powers, hence if we can do multiplication we can do anything. Not very convincing, I know, but it was good enough for me.

This expression is expanded into a = a ^ (b = b ^ (a = a ^ b)); then the left-hand operand is evaluated first which results in the first a after = not getting "updated" after the innermost ^= as you are probably expecting.

Right, I was missing the idea of replacing zeroes with non-zeroes.

In "E. So Many Possibilities...", how to find "dp(l, S)" in $$$O(2^n n m)$$$ ?

This is a really nice way to look at it and makes the complexity analysis much more intuitive IMO.

What is "soooooooooo cool" about it? The fact the Time Limit is set to 1500 ms and not 1000 ms?

This is so fucking cool, wow.

Do you know any other problems(on some online judge) that can be solved using this stuff? Especially if they require finding exp or square root of "set power series"?

UPD: After reading your solution and Lu Kaifeng's report it seems that the ranked Möbius transform is much more powerful than "Fourier meets Möbius" suggests: looks like you can apply any function to the set power series by applying it to a "ranked" vector for each mask independently. At the very least it works for subset convolution and logarithm so it would be very surprising if this doesn't hold in general.

But what is this witchcraft??? Why does it work?

Isn't it just (almost)850F - Rainbow Balls?

(1, 0) == (-1, 0) according to your comparator. But I'm actually interested if there's an elegant way to do this as well.

G(almost) https://www.russiancodecup.ru/en/tasks/round/20/B/

Upd: also https://codeforces.me/gym/100239/problem/B

The actual submission https://contest.felk.cvut.cz/19cerc/submits/2014.

I think the formula is described in the paragraph starting with "Each site has its own...".

64553387
ArrayList sucks, boxing/unboxing also sucks, so sometimes you have to use something like /blog/entry/14328 or just primitive int arrays. Yeah, I know it's a bit ridiculous.

I thought the last sentence only applied to the example tests. Not sure if that was your intention :) But thanks for the answer anyway.

But nothing was said about about how vertices in interactor's responses are chosen(well, except for the samples).

So what was the jury interactor's strategy for C?(I hope it's not a secret)

Have you implemented this? I tried doing exactly that(I think) but only got zeroes for the max test.

Editorial solution for div1 hard works in 2.844s and the time limit is 3 seconds, that's not cool.

C http://acm.timus.ru/problem.aspx?space=1&num=1972

What is this book?

It did happen to me once but not on CF(I think it was on Yandex.Contest)

peltorator, take notes

Are they ever expected?

Why did you switch to cpp for the last problem btw?

Is it really necessary to have 130+ tests for A?

Sick advertisement :D

I don't see algorithm about Hamiltonian cycle on wikipedia.

I found rng58's analysis, even muted, pretty easy to understand: https://youtu.be/WFg2yJGZ2Cw?t=47m41s

More like this weekend.

When can we expect solutions to GHJ?

In E do you even build suffix trees for every s_i and t_i(or just one big suffix tree)? And if you do, how to get position in small tree from position in big tree?

Well, (u, u) and (v, v) use values from D and the other two use values from F so I don't think they cancel each other out or something.

When we use zero E tags the answer is sum over all matchings of given tree(because we can still use v->u and u->v edges). I don't understand the last part but it probably gets more complicated too.

Why is given graph a tree then?

The usual way to find the number of equivalence classes under a group of actions — Burnside's lemma.

Try here, Java works much better on CF.

And what about point distribution?

Or just group them by (x+y)%8.

If you can't give us rating, at least give us practice rooms ;_;

But how do you handle sum from l to r(and C-type customers)?

I really like today's problems, is TC back?

It can be done in as described here: http://codeforces.me/blog/entry/12513, last problem.

Also, map can be replaced with binary search

Could you elaborate on that? I don't really understand what it means.

Lol, I got AC for problem E with O(2^n / 2) bruteforce(with some pruning of course)

http://codeforces.me/contest/618/problem/F

Were you the writer?

I think in problem F it's clearer to let t(r) = E(number of steps taken if we reach S at the end, otherwise 0), then everything that follows makes perfect sense. If we make it conditional on reaching S first, then probabilties of moving to r-1 and r+1 aren't equal and overall it's a bit messier(but still doable).

Because div2A(which is like a+b) has 110+ tests and was solved by ~3500 people.

Is there a combinatorial interpretation of formulas for problem E?(I mean formulas in the first part of editorial)

But there is a linear solution to this problem.

C was much harder than D and E IMO.

(1 + 2)ⁿ

This round had not 1 or 2, but 4(FOUR) testers. And none of them implemented bruteforce solution for A? I've always thought this is exactly testers' purpose.

160+ tests in problem A X_X

wisely

LOL

You were also the writer for the last 2 contests(w/o this SRM) I participated in :O

For "Avoiding Adjacent", what is the complexity of dynamic programming solution? And was it supposed to get AC?

How is "unused code rule" enforced? Had to scroll through 3-4 screens of templates today before reading one solution(and there were some comments inside too). pinging cgy4ever

Cool!

How to solve "Ample Syrup" in linear time?

http://www.cs.technion.ac.il/~itai/publications/Algorithms/Hamilton-paths.pdf

It makes sense that summing many doubles is less precise than multiplying long by double. Why does it only matter in java is less clear to me.

In practice, one dfs is enough for n, m = 10⁵.

Given a connected undirected graph, find number of pairs of edges such that graph becomes disconnected when these two edges are deleted.

First, consider table dp[i][j] — minimum cost to transform first i symbols of pattern into first j symbols of text. We have dp[0][j] = 0(because substring can start at any position) and usual transitions.

Now for each difference j - i(say j - i = d) and each value s(0 ≤ s ≤ k) let's find the maximum i such that dp[i][i + d] = s, call it f[s][d]. If one of these maximums is equal to |P|, then we found a required substring.

f[0][d] is just equal to lcp of P and T[d..] To calculate f[i][d] it's enough to consider f[i - 1][d + { - 1, 0, 1}], skip one symbol in P, T or them both, move forward by corresponding lcp and choose maximum of three values.