104683A - Banis and Cards by Banis
Let $$$k=\lfloor\frac{n}{m}\rfloor$$$. The answer is $$$(1+\cdots+k)\cdot m=\frac{k(k+1)}{2}\cdot m$$$.
104683B - Left or Right Shift by wuhudsm
Consider modifying each character from left to right.
To change character $$$s_i$$$ to $$$'a'$$$, it is not difficult to see that the minimum number of operations needed is $$$min(s_i-'a','z'+1-s_i)$$$.
If the remaining number of operations $$$r$$$ is less than $$$min(s_i-'a','z'+1-s_i)$$$, then shift the current character to the left $$$r$$$ times.
You need to be careful: if all characters become $$$'a'$$$ and the remaining number of operations is odd, you need to change $$$s_n$$$ to $$$'b'$$$.
104683C - Yet Another ÷2 or +1 Problem by wuhudsm
Consider the following problem:
For a string $$$t$$$ of length $$$m$$$, if $$$t$$$ is palindrome and $$$t+t_m$$$ is also palindrome, what kind of string is $t$？
We can find that $$$t_1=t_2=\cdots=t_m$$$ must hold.
Then the solution is clear. We can do bruteforce until we obtain a string where all characters are equal. Afterwards, you only need to add the same character at the end every time.
There will be only $$$O(\log n)$$$ iterations because after every time we add character to the end we will divide size of string by $$$2$$$.
104683D - Sum and Difference by Banis
What's the minimum sum we can get? The answer is $$$2l+2$$$.
Consider starting from the minimum sum and only increasing the sum by $$$1$$$ at a time.
Construction: $$$l+2, l, l+3, l+1, l+4 \dots$$$
104683E - L-shaped Dominoes by chromate00
Let $$$dp_{i,fa,fb}$$$ be answer if we consider only first $$$i$$$ columns, where $$$fa$$$ and $$$fb$$$ respectively represent whether $$$a_i$$$ and $$$b_i$$$ are covered by dominoes or not. Transitions are obvious.
104683F1 - Maximum Flow in DIV3?(Easy Version) and 104683F2 - Maximum Flow in DIV3?(Hard Version) by astilate
let's say that $$$l=r=n$$$.
It's obvious that if $$$a$$$ is not a divisor of $$$n$$$, then vertex $$$a$$$ cannot contribute to $$$flow(n)$$$.
Think about the divisors less than $$$\sqrt{n}$$$ or more than $$$\sqrt{n}$$$.
How about the divisors which is just equal to $$$\sqrt{n}$$$?
How can we calculate $$$\Sigma_{i=l} ^r flow(i)$$$ faster? How about count the multiples instead of divisors?
Let's classify the case.
(1) for edge from $$$1$$$ to $$$n$$$, we can flow $$$n$$$.
(2) for divisor $$$d$$$ less than $$$\sqrt{n}$$$, there're edge from 1 to $$$d$$$ with capacity $$$d$$$ and edge from $$$d$$$ to $$$n$$$ with capacity $$$n/d$$$. In this route, since $$$n/d > d$$$, we can fully flow $$$d$$$.
(3) for divisor $$$d$$$ more than $$$\sqrt{n}$$$, there're edge from 1 to $$$d$$$ with capacity $$$d$$$ and edge from $$$d$$$ to $$$n$$$ with capacity $$$N/d$$$. In this route, since $$$d > n/d$$$, we can fully flow $$$n/d$$$.
(4) if $$$n$$$ is square number, for divisor $$$d$$$ equal to $$$\sqrt{n}$$$, we can flow $$$d$$$ by the edge from 1 to $$$d$$$ and from $$$d$$$ to $$$N$$$.
We can show that above flowing strategy is optimal. It's obvious that $$$a$$$ is not a divisor of $$$n$$$, then edge from vertex $$$a$$$ cannot contribute to $$$flow(n)$$$. For divisor $$$d$$$ less than $$$\sqrt{n}$$$, it flows all of the inward flows to $$$N$$$, so in this case there's no argumenting path. For divisor $$$d$$$ more than $$$\sqrt{n}$$$, all vertex $$$d$$$ is saturated, so there's no argumenting path.
In conclusion, $$$flow(n)$$$ is $$$n + (\text{sum of divisors less than }\sqrt{n}) * 2 + (\sqrt{n} \text{ if it's integer, otherwise } 0)$$$
Time complexity : $$$O(\sqrt{n})$$$
Let's start from the truth $$$flow(n) = n + \text{(sum of divisors less than sqrt(n))} * 2 + \text{(1 if sqrt(n) is an integer, otherwise 0)}$$$
We can calculate the sum of $$$(l~r)$$$ in $$$O(1)$$$. So, we just consider the $$$\text{(sum of divisors less than sqrt(n))} * 2 + \text{(sqrt(n) if it's an integer, otherwise 0)}$$$ part.
For all $$$i$$$ less than or equal to $$$\sqrt{r}$$$
- if $$$l \le i^2 \le r$$$, then there's $$$\text{(1 if sqrt(n) is an integer, otherwise 0)}$$$ factor where $$$n=i^2$$$, and there're $$$\lfloor (r-i * i)/i \rfloor$$$ numbers which contain $$$d$$$ as a divisor less than $$$n$$$.
- if $$$i^2 < l $$$, then there's no $$$\text{(1 if sqrt(n) is an integer, otherwise 0)}$$$ factor, and there's $$$\lfloor (r-i * i)/i\rfloor - \lfloor(l-1-i * i)/i \rfloor$$$ numbers which contain $$$d$$$ as a divisor less than $$$n$$$.
So, we can calculate $$$\Sigma_{i=l} ^r flow(i)$$$ faster by counting multiples instead of divisors.
Time complexity: $$$O(\sqrt{r})$$$
104683G - Useless Trick by amenotiomoi
First notice that we only need to make first $$$m$$$ characters contain $$$k$$$ ones, and $$$s_i=s_{i-m}$$$ for all $$$i$$$ such that $$$m+1\leq i\leq n$$$.
Now let's say you fixed your answer string and you want to find the minimum number of operations to get it. Obviously the answer is the number of segments of consecutive ones after xoring the answer string with $$$s$$$.
Number of segments of consecutive ones can be calculated using amount of pairs of distinct adjacent numbers, so our answer is $$$\frac{\sum{x_i\oplus x_{i-1}}}{2}$$$ where $$$x$$$ is xor string. (you need to add zeros on left and right of string).
You can calculate it using dp.
Editorial for $$$F1$$$ and $$$F2$$$ when? waiting since last night :(
Here is my solution for F . note that max-flow = min — cut. so our goal is to find a partition of V into A and B , such that 1 is in A , n is in B. rest other vertices will be in one A or B. Size of cut = sum of weight of all edges from A to B. any vertex v > sqrt(n) won't be placed in B. a vertex v <= sqrt(n) will be placed in B iff. it is a divisor of n , else it will be in A. now you can compute the answer for a given n in sqrt(n).
For $$$F1$$$, it is easier to see that flow for any given number $$$N$$$ is $$$N + \sum_{d \mid N}^{}min(d, \tfrac{N}{d})$$$. We can brute force for all the divisors of $$$N$$$ to compute this with resultant time complexity as $$$O(\sqrt{N})$$$.
For $$$F2$$$, we can find the contribution of each $$$d$$$ on numbers in range $$$[L, R]$$$ First we have the contribution of each number itself that is $$$L + L + 1 + ... + R = \tfrac{R(R + 1)}{2} - \tfrac{L(L - 1)}{2}$$$
since $$$R \leqslant 1e14$$$, it is sufficient to iterate till $$$1e7$$$ and get contribution of each number in range $$$[L, R]$$$.
A number $$$d$$$ contributes to flow of $$$N$$$ as:
$$$2d$$$ if $$$d \mid N$$$ and $$${d_{}}^{2} < N$$$
$$$d$$$ if $$${d_{}}^{2} = N$$$
Therefore, for any $$$d$$$ we can find the count of such numbers and calculate the total contribution of $$$d$$$ in range $$$[L, R]$$$ in $$$O(1)$$$
Final answer will be $$$\tfrac{R(R + 1)}{2} - \tfrac{L(L - 1)}{2} + \sum_{2}^{1e7}contribution(d)$$$
Sorry for late editorial. I've made it and updated now!
Can someone take a look why this DP on L-shaped Dominoes fails test 3
https://glot.io/snippets/gpo6vt80f8