As a tester, I think the problems are decent!

Guess there is big variance for these task. I also think of polynomial immediately after reading the statement and solve it in a reasonable time, but D took me a whole day to solve and I failed to solve C.

Alternative solution of D:

Let $$$k$$$ be the largest integer with $$$\frac{k \cdot (k + 1)}{2} \le x + y$$$. Consider two bag with capacity $$$x, y$$$ respectively. For $$$w = k, k - 1, \ldots, 1$$$ in this order, put the item with weight $$$w$$$ into the bag with larger capacity remain. Let $$$x', y'$$$ denote the final capacity remain for two bags. We claim this process minimize $$$\max(x', y')$$$.

Proof.

W.L.O.G. assume $$$x \ge y$$$, call the bag with $$$x$$$ initial capacity the first bag, and the other be the second bag.

case 1 ($$$x \ge y + \frac{k\cdot (k + 1)}{2}$$$): trivial

case 2: items would be add into the first bag until its capacity is no more than the second bag, let $$$m$$$ be the item added to make this happen. then at this point, the difference of capacity between two bag would be no more than $$$m$$$, and in the subsequent item addition, the difference would be no more than the item added last, thus $$$|x' - y'| \le 1$$$ holds at the end, which achieve the lower bound of $$$\max(x', y')$$$.

G is nice, thanks!

This kind of binarization idea is also useful in lot of counting problem and mostly used together with "Tail-Sum Formula"

$$$E[X] = \sum\limits_{k \gt 0} \Pr[X \ge k]$$$

For r.v. that always evaluate to non-negative integers. ($$$\Pr[X \ge k]$$$ essentially tells you only need to separate elements into "$$$ \lt k$$$" and "$$$\ge k$$$", which is the reason why it fit well with binarization)

For example, this problem.

number of transition in F can be further reduced to around $$$10^7$$$ by observing either $$$p$$$ or $$$q$$$ is prime in optimal choices, since if

holds, then

So any pairing of two composite number can be decomposed into two "smaller" pairing without worsening the cost.

There is another way of showing the claim of E2 (also solve the whole problem):

For any positive integer sequence $$$A$$$ of length $$$N$$$ without duplicate, $$$A$$$ would be a permutation of $$$[1, 2, \ldots, N]$$$ if and only if $$$\sum\limits_{i = 1}^N A_i = \frac{N(N+1)}{2}$$$.

So the problem is reduced to finding the number of ways to permute strings so the sum is $$$\frac{N(N+1)}{2}$$$. Since this is the lower bound of the sum over any positive integer sequence without duplicate, we can relax the condition into minimize the sum and check if it is $$$\frac{N(N+1)}{2}$$$.

The only way to minimize it is to sort strings by frequency of $$$1$$$ bits. Which deduce the final solution in the editorial and also prove why we can permute strings with same number of $$$1$$$ bits arbitrarily.

Actually codeforces did use AI to proofread problems automatically, though it seems not all of the mistakes would be found by AI :(

good, how about you?

If you check the box of "Show editorial in other language", there is an editorial ( テーマ一覧（ネタバレ注意）) with hint that the technique are used for each problems

Well, it seems the TL is extremely tight and even my implementation of $$$O(N(\frac{4}{3})^L)$$$ solution pass in 3.4 second...

$$$O(N2^{L/2})$$$ solution probably need lot of optimization in order to pass.

Does it means we can hack a fixed seeded solution or even randomized seed? I can't understand the math part ><

Auto comment: topic has been updated by Misuki (previous revision, new revision, compare).

To be honest, a large portion of modern CF problems requires no algorithm (especially first half of Div.2). And it might be healthier to think CF round as discrete puzzle contest rather than DS&algo contest.

If you really just want to solve algorithmic tasks, try ICPC or atcoder beginner contest. Though you would still meet such "mathy problems" but with less frequency.

Provide an almost brain-dead solution to F:

fix the node $$$v$$$ on binary search tree as the node where we found value $$$k$$$. assume there are $$$L$$$ elements less than $$$k$$$ and $$$R$$$ elements greater than $$$k$$$, then the number of such $$$a$$$ is $$$\binom{k - 2 + L}{L}\binom{m - k - 1 + R}{R}$$$.

sum over $$$k$$$ gives $$$\sum\limits_{k = 2}^{m - 1}\binom{k - 2 + L}{L}\binom{m - k - 1 + R}{R} = \binom{m - 3 + L + R + 1}{L + R + 1}$$$. (by the identity $$$\sum\limits_{x \in \mathbb{Z}}\binom{a + x}{a}\binom{b + c - x}{b} = \binom{a + b + c + 1}{a + b + 1}$$$). Note that $$$k = 1$$$ and $$$k = m$$$ can be handled in $$$O(1)$$$.

So for each vertex $$$v$$$, just enumerate $$$L+R$$$ then we can calculate everything in $$$O(n\log n)$$$ since sum of subtree size in binary search tree is $$$O(n\log n)$$$.

A related problem

I enjoy solving E, F very much, thanks for the round!

Just use LLONG_MAX, it's in the c++ standard and expressive!

reference

What's the reason to set $$$N = 5'000'000$$$ for pF? The TL/ML seems very tight under such constraint :/

Thanks for introducing the application of CDQ in various task, I learned a lot from this blog!

And about the CDQ + SOS part, actually it's possible to solve it in just $$$O(n2^n)$$$, the idea is to maintain the $$$z(dp)$$$ "dynamically" while calculating $$$dp$$$. ($$$z(dp)$$$ stands for the array produced by doing SOS on array $$$dp$$$, i.e. $$$z(dp)_i = \sum\limits_{j \subseteq i}dp_j$$$).

In other word, we want to solve the following problem:

Given an $$$0$$$-indexed array $$$dp$$$ of length $$$2^n$$$, initially filled with $$$0$$$ except $$$dp_0$$$.

For $$$i = 1, 2, \ldots, 2^n - 1$$$ in this order, do the following operation:

1. query $$$\sum\limits_{j \subset i}dp_j$$$

2. add $$$f(\sum\limits_{j \subset i}dp_j)$$$ to $$$dp_i$$$

To solve it, we maintain $$$z(dp)$$$ dynamically during the recursion call of CDQ. Since $$$dp_0$$$ is the only non-zero element of the initial array, $$$z(dp)$$$ should filled with $$$dp_0$$$ initially.

And when we have a fixed "LCP" of length $$$L$$$ and ready to call $$$\text{LCP+0+...}$$$, we do an inverse SOS on subarray $$$z(dp)[\text{LCP+0...0}, \text{LCP+1...1}]$$$ to invert the effect of $$$(N-1-L)$$$-th bit, i.e. do $$$z(dp)_{(i | 2^{N - L - 1})} \mathrel{{-}{=}} z(dp)_i$$$ for all $$$i$$$ match with $$$\text{LCP+0+...}$$$

Then recurse into $$$\text{LCP+0+...}$$$, add some elements to $$$dp$$$, and when the call to $$$\text{LCP+0+...}$$$ is done, we do an SOS on the same subarray to add the effect of $$$(N-1-L)$$$-th bit back.

Then whenever we reach a leaf node $$$l$$$ of the recursion, $$$z(dp)_l = \sum\limits_{i \subset l}dp_i$$$ would hold so we can answer the above query in $$$O(1)$$$.

And the total complexity would be the sum of size of all subtree of the recursion tree, which is $$$O(n2^n)$$$.

This is my implementation of this technique on a similar problem

D1. Asesino (Easy Version)

D2. Asesino (Hard Version)

there is a misspelling in the statement under the table:

The response of the cell ... when i has role a and j has "row" b. ("row" -> "role")

(Sorry for necroposting)

I was wondering whether it's possible to apply this algorithm to compute HLD that can additionally support subtree query, which not just require computing time stamp of each node but also require the largest subtree should be visited before others, and turns out it's possible!

To do it, we can compute subtree size and the size of max child subtree in the first run, then do counting sort on vertices by subtree size, and finally traverse the tree again in decreasing order of subtree size to compute time stamp and head of the chain.

And the result is blazingly fast!! Though I'm a bit surprised that DFS is kind of the bottleneck of the whole code rather than other $$$O(n\lg n)$$$ fenwick tree/segtree part.

Here is my submissions:

Vertex Add Subtree Sum (79ms, 29.46Mib)

Vertex Set Path Composite (316ms, 15.88Mib)

Vertex Add Path Sum (212ms, 31.92Mib)

Jump On Tree (139ms, 21.85Mib)

Lowest Common Ancestor (155ms, 25.73Mib) (My <$$$O(\frac{n\lg n}{w})/O(1)$$$> LCA took 90ms on this one)

AGC073-A Chords and Checkered

Especially the solution given by Um_nik, which is so beautiful

Let $$$a = [a_1, a_2, \ldots, a_n]$$$ be non-decreasing array of integers, then $$$\min_{i \neq j}(a_i \oplus a_j) = \min_{1 \leq i \lt n}(a_i \oplus a_{i + 1})$$$

Just want to mention there is an another easy way to understand SOS. That is, to think it as high dimension prefix sum.

For example, when the dimension is $$$2$$$, we can do something like

int a[n][m];
for(int i = 0; i < n; i++)
  for(int j = 1; j < m; j++)
    a[i][j] += a[i][j - 1];
for(int i = 1; i < n; i++)
  for(int j = 0; j < m; j++)
    a[i][j] += a[i - 1][j];

And it's not hard to see how to extend this to higher dimension: Just do prefix sum for each dimension. In the case of SOS, we are dealing with $$$n$$$ dimension array where each dimension have two possible index $$$\{0, 1\}$$$. So we would have something like

int a[2][2][2];

for(int i1 = 1; i1 < 2; i1++)
  for(int i2 = 0; i2 < 2; i2++)
    for(int i3 = 0; i3 < 2; i3++)
      a[i1][i2][i3] += a[i1 - 1][i2][i3];

for(int i1 = 0; i1 < 2; i1++)
  for(int i2 = 1; i2 < 2; i2++)
    for(int i3 = 0; i3 < 2; i3++)
      a[i1][i2][i3] += a[i1][i2 - 1][i3];

for(int i1 = 0; i1 < 2; i1++)
  for(int i2 = 0; i2 < 2; i2++)
    for(int i3 = 1; i3 < 2; i3++)
      a[i1][i2][i3] += a[i1][i2][i3 - 1];

Then store the array as $$$a[2^N]$$$ instead of $$$a[2][2][2][2][2]...$$$ and use some bitwise operation, you would get the code exactly the same as the first SOS code in your article.

The link of above comment have rough discussion for each problem

D is cool, thanks!

Congratulations!

Then there may be ~100 people in the world who may solve at least one problem...

My solution:

Consider solving for a fixed $$$x$$$ first.

We can build a trie of $$$A$$$ then traverse it to find the $$$A_j$$$ that minimize $$$x \oplus A_j$$$. Which can be found it the following manner:

Start from the root, and assume the current bit we are consider is $$$i$$$-th bit.

• if there is a child correspond to the $$$i$$$-th bit of $$$x$$$, go to that child
• otherwise, go to the only child, which will incur $$$2^i$$$ cost because $$$i$$$-th bit of $$$x \oplus A_j$$$ must be $$$1$$$.

Then to deal with all $$$x \in [0, M)$$$, notice that all $$$x$$$'s go to a child would still be consecutive under $$$\pmod {2^i}$$$, so to maintain all $$$x$$$'s go to a child, we store (first term of the consecutive $$$x$$$'s, the number of $$$x$$$'s) then everything can be dealt easily. (ex. $$$(2, 7)$$$ under $$$\pmod {2^2}$$$ represent $$$[2, 3, 0, 1, 2, 3, 0]$$$)

More specifically, we start from root with $$$(0, M)$$$ and traverse the trie with a BFS. Assume we have $$$(s, len)$$$ currently.

• if there is two children, split all integers in $$$(s, len)$$$ into two group by their $$$i$$$-th bit, then send two group to their respective children.
• otherwise send all integers to the only children, if the only child represent $$$1$$$, this would incur a cost of $$$2^i \cdot (\text{the number of integers in (s, len) with i-th bit being 0})$$$, and vise versa.

As a tester, I think the whole problemset is awesome! orz to author for making so much interesting problems!

I passed it with 1900ms after the contest, but I use 2x states compared to tutorial ($$$(L, R]$$$ for all $$$1 \leq l, r \leq NK$$$, but tutorial only use $$$1 \leq l \leq r \leq NK$$$), and if we just consider subarrays with $$$l \leq r$$$ like editorial did, we can calculate DP in decreasing order of $$$l$$$, then increasing order of $$$r$$$, which would have much better constant than other ways.

So it's probably my fault in my case.

I just wrote a test that keep merging two treap with size 10^18, and turns out it use around $$$\frac{4 \times 10^7}{Q} \approx 2\ln(\text{10^18})$$$ per merge operation. Though I'm not sure how to analysis it properly.

Btw, I didn't think that much and just create as many node as possible under ML when submitting it then pray it works lol

ARC076F — Exhausted

Agree, problems of this round upto D are not as hard as other rounds for me. Especially CD are just straightforward application of techniques.

You can go up for $$$x$$$ step then go down to other subtree by $$$k - x$$$ step.

Could the complexity be worse than $$$O(E\log V)$$$ when containing negative edges? For $$$r \lt L$$$, I build the edge with cost $$$-x_u$$$ connect from $$$u$$$ to the node in segment tree, and edge with cost $$$x_v$$$ connect from node in segment tree to $$$v$$$, and It pass in 1500ms.

My Submission

Problem solving require creativity/curiosity to the problem, it's not like doing chore where you can force yourself to finish it. If you are not interested in a problem, I can hardly believe you can come up with sth new but just apply everything you've already know, which I won't call it "progress".

Consider using "total number of socks have same color as the one on your hand" (include the one on your hand), then you would switch to another sock you draw only when that one have more number in total, so "total number of ..." would be non-decreasing in the whole process, and you can find the probability to transit from $$$u$$$ to $$$v$$$ for every $$$u \le v$$$, then let $$$E[u]$$$ be the expected number of times we need to draw to have a pair when start with a sock have $$$u$$$ in total. Then we have $$$E[u] = 1 + \sum\limits_{v \gt u} Pr[u \rightarrow v] E[v] + Pr[u \rightarrow u]E[u]$$$ so $$$E[u] = \frac{1 + \sum\limits_{v \gt u}Pr[u \rightarrow v] E[v]}{1 - Pr[u \rightarrow u]}$$$, then just dp in decreasing order of $$$u$$$.

I miss the day when there are lot of blog talking about brilliant ideas/techniques and problem solving, nowadays they are replaced by tons of blog talking about cheater :(

The problem you said don't need Möbius function, it can be solved by just noticing $$$x$$$ is perfect square is equivalent to each prime factor appear enen number of times in $$$x$$$'s prime factorization, so you only care the parity of each primes occurrence, thus you can replace every $$$x$$$ by the product of $$$x$$$'s distinct prime factor(let's call it $$$x'$$$), then $$$xy$$$ is perfect square iff $$$x'=y'$$$, which is trivially enough to solve directly.

Regard to the use of Möbius, as the blog said, it's essentially PIE on prefix/suffix sum of multidimension array with divisibility relation, so you would use it whenever you have a prefix/suffix sum array and want to obtain the original array.

I read the sublinear summation part of the slide and understand everything in around 20 minutes, the slide is very concise and I learn something new today, thanks you!

Though I have a little question, if I understand correctly, it can be applied to any function $$$f$$$ s.t. there exist $$$g, h$$$ satisfy $$$f * g = h$$$ and prefix sum of $$$g, h$$$ are easy to compute. And I think it can be applied to $$$\mu$$$ and $$$\phi$$$ because of $$$\mu * 1 = [n = 1]$$$ and $$$\phi * 1 = id$$$. And I wonder if there are more function can be compute in such manner except $$$\mu, \phi$$$?

Auto comment: topic has been updated by Misuki (previous revision, new revision, compare).

About the solution of next prime, it's not correct to use average prime gap to estimate complexity since the test cases are not necessarily generated randomly, and the upper bound of prime gap should be used. And I doubt Miller-Rabin test can be run in just one log factor. the implementation from KACTL seems to have 2~3 log factors depending on whether you think size of $$$A$$$ as constant.

Wow, didn't expect this problemset would update, it's time to solve them!!

For problem F, I think the complexity of official solution should be $$$O(nk^2 + nk \log n)$$$ since calculating range nor takes $$$O(k)$$$ time.

btw, using push down on sparse table instead of segtree can reduce time complexity of processing range max updates from $$$O(nk\log n)$$$ to $$$O(nk + n\log n)$$$

I like today's problem F, thanks for the great problem :)

I think there is no need to use __int128? everything works well under double.

(Not sure why codeforces can't render it, now I put a link to the picture instead) picture

For $$$n = 8, k = 1$$$, the MCF graph would look like the above picture. Consider adding edges going out from source incrementally from rightmost and try to augment using it. The augmenting path would either going down -> going down to sink or going down -> going right (maybe $$$0$$$ step) -> going up to cancel some used edge.

The first case would happen only when $$$n = 7, 5, 3, 1$$$ and the second case would happen when $$$n = 2, 4, 6$$$.

For second case, only canceling the edge with maximum weight won't cause negative cycle in the residue graph thus giving the optimal solution of current flow graph.

Then you could find that, to simulate such augmenting process, we just need to use a priority queue to maintain weight of used edged going out from source.

I think it's more natural (and maybe more general) to reduce it to a min cost flow problem then try to simulate it using the property of the flow graph without actually running the MCMF algorithm, which would be too slow.

A few problems that can be solved in this way:

https://www.acmicpc.net/problem/17169

https://www.acmicpc.net/problem/14001

https://atcoder.jp/contests/abc363/tasks/abc363_g

Try AtCoder, especially ARC/AGC contains tons of ad-hoc problems focus on thinking and puzzle solving skill

By Luca's theorem we know $$$\binom{n}{k} \equiv 1 \pmod{2} \Leftrightarrow k$$$ contains subset of bits of $$$n$$$ in binary notation.

Also we have $$$\binom{n}{cnt_0, cnt_1, \ldots, cnt_{m-1}} = \binom{cnt_0}{cnt_0} \cdot \binom{cnt_0 + cnt_1}{cnt_1} \cdot \binom{cnt_0 + cnt_1 + cnt_2}{cnt_2} \cdot \binom{cnt_0 + cnt_1 + cnt_2 + cnt_3}{cnt_3}\dots \cdot \binom{n}{cnt_{m - 1}}$$$, to make lhs an odd number, terms on rhs should all be odd numbers. Consider the last term $$$\binom{n}{cnt_{m-1}}$$$, $$$cnt_{m-1}$$$ should contains subset of bits of $$$n$$$, then consider the previous term before it $$$\binom{n-cnt_{m-1}}{cnt_{m-2}}$$$, $$$cnt_{m-2}$$$ should contains subset of bits of $$$n-cnt_{m-1}$$$ which is exactly bits in $$$n$$$ but not in $$$cnt_{m-1}$$$, then consider previous terms and so on.

This process is essentially deleting bits from $$$n$$$ and distribute them to $$$cnt$$$, then it become quite intuitive that the above claim is true.

In this problem, yes. But there may be problems that would make a difference. And I hope this won't happen when we facing them.

Thanks for the contest! I like pC very much.

But about problem E, I think it's quite bad to define path to allow going through same vertex multiple times, since it contradict the conventional definition of path, and it's better to call it a "walk" instead of "path".

You can just see the first line + first summation of second line above, that's how we get it.

Consider the normal edit distance DP with time complexity $$$O(|S||T|)$$$, i.e.

If you analysis it carefully, it's unnecessary to consider all states with edit distance $> K$, thus for each $$$i$$$, we only need to consider $$$dp[i][j]$$$ where $$$i - K \leq j \leq i + K$$$, which reduce the complexity into $$$O(|S|K)$$$.

Let $$$S$$$ be the set of all possible graph, $$$W(G)$$$ be cost of MST of $$$G$$$, $$$T_{\leq x}(G)$$$ be the minimum spanning forest form by edges in $$$G$$$ with weight $$$\leq x$$$, $$$w_e$$$ be the weight of an edge. Then we have

Then the problem reduced to sth similar to this problem, and can be solved by dp.

If you find two prime $$$p, q$$$, it's definitely good, and the distance between two prime is around $$$O(lg^2 C)$$$ so if you enumerate like that, it would stopped very quickly.

btw, it's known as prime gap

Hmm, seems it's indeed weird, not sure why change of that flag would cause such difference

Let $$$x$$$ be the smallest real number s.t. there are at least two building intersect with the line, then the range of real number to be able to see all building is $$$(x, \infty)$$$. When $$$x \ge 0$$$, output $$$x$$$ is consider correct just because it have arbitrarily small relative error to the correct answer rather than it's visible on $$$x$$$, and when $$$x \lt 0$$$, $$$0$$$ is visible and the problem ask you to output $$$-1$$$ in such case.

The first one is correct behavior according to the definition in the problem

From a point P with coordinate x and height h, building i is considered visible if there exists a point Q on building i such that the line segment PQ does not intersect with any other building.

For the second one, I guess it would work as long as $$$L = 0, R = 2^k$$$ for big enough $$$k$$$? Not sure how to estimate the error but it feel reasonable to have less error when $$$R$$$ is power of $$$2$$$ since computer store everything in binary. I also trapped on this one, guess it's a lesson to learn :P

ARC171E — Rookhopper's Tour

The setting feels very chaotic to me initially, but after thinking it though, it turns out there exist an elegant way to analysis the problem model very simply to make it solvable. It's just... astonishing!

Actually big-O is just a notation to describe the grow rate of functions, and that's it. There is no restriction say big-O should only describe function of complexity in worst case and it's nothing weird to use it to describe function of complexity in average case, and you can plug any function you want into it.

wiki

each val correspond to different cut points, so it's always possible

To derive the rest of solution, just add the binary string back and you would see the contribution when cutting $$$(i - 1, i)$$$ just change from $$$n - i$$$ to (the number of Bob's fish in $$$[i, n]$$$) — (the number of Alice's fish in $$$[i, n]$$$) and you want to make sum of this stuff no less than $$$k$$$, so you just keep picking the cut point with largest weight until sum of them is no less than $$$k$$$.

If you ignore the binary string and consider some fix choice of group partition and plot it on the 2D plane where x-axis are fishes and y-axis be there respective value, you would get a bar graph like

ex. cut between (2, 3), (4, 5), (7, 8):
       **
    *****
  *******
--------->
123456789

then instead of summing over value for each x, let's consider summing them for each y, then you would see if you made a cut between $$$i, i + 1$$$, then it will increase answer by $$$n - i$$$, then it would become much easier to derive the solution in the editorial.

problem E is interesting, thanks you!

As a tester, I'm requested to bump this blog

I think most of the contestant solve it using slope trick though (alternative solution in editorial)

Incorrect implementations of the Floyd--Warshall algorithm give correct solutions after three repeats

Keep to algorithmic problems, switch to idea-based problems after gaining skill

That's exactly what AtCoder is doing, ABC contain a bunch of standard problem for beginner to learn, while ARC/AGC contain a bunch of idea-oriented problems for non-beginner to improve thinking. So I think doing AtCoder would be a good choice?

some related comment from rng_58, previous admin of AtC

For the number of prefix gcd, it's worth mention that, if we think the values of array as factorized form and map the frequency table of prime factors to a vector(ex. $$$50 = 2^1 \cdot 3^0 \cdot 5^2$$$ so we use vector $$$[1, 0, 2, 0, 0, 0, \ldots]$$$ to represent it), then taking gcd of two number is essentially taking element-wise min of their respective vector, and the sum of element in a vector is $$$O(\lg n)$$$ so we can decrease it $$$O(\lg n)$$$ times.

You can also think it as an extended result of prefix bitwise and have $$$O(\lg n)$$$ different value.

41 point, I earn at least 10~ points by just using vim + families with console lol (ex. vim allow split screen inherently, vim motion, not laggy editor.../diff command in unix/using output redirection to not copy paste testcase everytime etc...)

One another thing, 2400 perf on ABC is never equivalent to CF 2526 perf even on modern div.2, since cf problem are far more ad-hoc than ABC, I think it's equivalent only if you test it on ARC/AGC.

Maybe try to filer out div.2 problem? these are prone to be overrated compared to div1(+2) problems

You would be rated even if you just register and didn't submit anything, so it's better to register right before the contest next time :)

Thanks for the great blog! I think it's worth mention that writing a few example on paper and making conjecture/observation based on them is also extremely useful and used a lot when solving ad-hoc problems.

When Div.1/2 are hold separately, purple would belongs to div.1

top left is oshinoko

As a tester, I wish all contestant having fun in this contest.

problem B was really interesting, thanks you!

Thanks you, I've fix it. the second one is $$$L' \ge L + R$$$ because the nature of the operation (i.e. whenever you add $$$1$$$ to a node, you would also add $$$1$$$ to its ancestors)

because each operation is indistinguishable, so you should use star and bar to calculate it (i.e. the number of ways to put $$$a$$$ indistinguishable balls into $$$b$$$ distinguishable slots). $$$b^a$$$ is used to calculate the number of ways to put $$$a$$$ distinguishable balls into $$$b$$$ distinguishable slots. And it's important to think the objects are distinguishable or indistinguishable in counting problems.

Sorry about that, I didn't notice such bruteforce solution during preparation, I would take more care about such thing next time :(

Sorry, it should be fixed now.

I mean the lower bound of the answer for any fixed $$$a$$$, not necessarily with all elements equal

Turns out a tester's solution TLE on the hacked test, now it should be fixed.

Actually I would recommend you to write a bruteforce and see where goes wrong with your solution. Since in contest, you can't see the hidden testcase, and it's useful to have such ability as a contestant.

Sorry, I've add binary search solution on it (Solution2)

It have less standard idea and rely on pure puzzle solving ability more in my opinion, but if you have a good perspectice about the problem it might be easier. For example, I think the problem as some kind of spanning tree problem and try to keep finding edge connect different component. (Solution2 in editorial)

Sorry, I was thinking hint for my solution when writing it but the solution part is from coordinator. I've add Soluion2 which correspond to the hint section.

glad you like it :)

Thanks for the round! the conclusion of A is concise and the prove is not hard, I like it.

(though I can't solve anything after that qq)

It's intended, see This post

I think there isn't much problem rely on invariant or variable substitution in my experience (at least ~ orange, not sure about red~ but probably not much still). And I feel most of the problems from ARC and old AGC can be solved by just proper reasoning and basic combinatoric skill rather than you said "weird math trick".

Thanks for the round! This is my first time to participate in TOKI contest and the problems is really interesting for me!

Actually G also appear in past TopCoder round https://community.topcoder.com/stat?c=problem_statement&pm=17083

I also think having non-easy start would works to avoid speedforce while keep the duration 2 hour for higher rated people. And that is what separated Div.1/Div.2 aim for. But due to sponsorship, they had to make it Div.1+2 and to avoid speedforce they need to make duration of contest longer. In such case, maybe we can figure out a way to do sponsorship without merging the problemset?

the segtree used here to maintain query (min, frequency of min) and range add is the same as the one used to solve area of union of rectangle, which is a quite standard problem?

Thanks for the round, the problems are awesome!