Hello Codeforces!!
We're honored to invite you to TheForces Round #14 (Cool-Forces) which will take place on May/23/2023 18:05 (Moscow time).
What is a TheForces Round? (If you don't know, you must read it)
You will have $$$135$$$ minutes to solve $$$7$$$ problems.
Please don't forget the time. Registration is open now.
Problems were prepared and authored by : amenotiomoi, Amir_Parsa, MrSavageVS, BallBreaker, repegfrost.
Also huge thanks to our army of testers : tyr0Whiz, wuhudsm, Little_Sheep_Yawn, O--O, k1r1t0, blxst, Madboly, Virendra115, E404_Not_Found, ExpensiveAC, Abhishek_Srivastava, danish_droid, Muaath_5, Zen-Oh, Binary_Thinker.
Also we want to thank you for participating in our rounds.
Discord Server (800+ people, join for a cookie )
As a problemsetter give me negative contribution.
You're Welcome
As a hater or yours — take it
As a problemsetter, this round has a plethora of interesting problems. Everyone would love it!
As a tester, this is the best contest I have seen so far in the Forces Rounds! It is worth spending time over in this type of contest. PS: Enjoyed testing this round a lot ;)
As a tester and co-founder of theforces, give me some contribution please
is it rated?
Did you read this : What is TheForces Round? (If you don't know, you must read it)?
First time tested a coding round. Thank you. Problems are awesome. Enjoy Problem-solving.
As a tester, I want to say that this contest will make you happy if you want to solve many topics, this will give you that, and it will make your mind explode
True
TheForces again Orz!
As a tester, these guys are more creative than Da Vinci.
Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).
As a tester, I recommend you to definitely give a try.
The contest has amazing problems.
As a tester, i can say the descriptions of problems in this round are pretty neat and easy to read. And I like each problem a lot. Don't forget to read some of the interesting titles and hope you'll have fun!
I came too late haha, hope i'll get some contributions.
Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).
So the round's difficulty is like div.3 rounds or div.2 rounds?
I think it could be more like div2
E is beautiful
do you have a good solution which isnt just bitmask dp? if not, i would have to disagree with you
I solved it using SOS dp in $$$O(n \cdot 2^m \cdot m)$$$ and 31 ms runtime, I'm not sure if this is what you're talking about.
even this version does still not very interesting to me (just one more standard trick), i just bruteforced transitions in 3^m * n
I get what you mean and yes, that the idea is quite standard. I just haven't seen many problems that use the idea and I was slightly surprised when I realized that it worked, guess I should just solve more problems then
the most famous example i know of : https://cses.fi/problemset/task/2181
problem feedback :
A : fine for A
B : standard problem so dont like, who are you fooling with a[i] — i — x instead of a[i] — x
C : it wud be ok problem, but its quite obviously the edu F ripoff (wtf is the point of a 10^18 size array)
D : fine problem
E : standard dp problem
F : its fine, but i believe this idea is over used, have seen it before
G : no comments
How to do F? I can only think of O(n^3) which gets timeout.
maintain a prefix sum of dp states and use segment tree to find the range sum.
just bruteforce i, j and add the number of subsequences where s[i], s[j] would need to be equal if they are not already equal
O(n^3) solution is good enough to pass F.
If a[i] != a[j], then all f(x) that contains both i and j as corresponding characters should increase by 1. And there are $$$(\sum_{x=0}^{min(i-1,n-j)}C(i - 1, x) * C(n - j, x)) * 2^{j - i - 1}$$$ such subsequences. Since $$$min(i-1,n-j) \le n / 2$$$, pre-calculate every $$$\sum_{x=0}^{min(i-1,n-j)}C(i - 1, x) * C(n - j, x)$$$ for each distinct $$$(i-1, n-j)$$$ pair takes $$$O(n^3 / 8)$$$ time complexity. My solutions works within 300ms.
This solution came to my mind and I already coded it during the contest and I spent the remaining time trying to optimize it, after reading your reply I just submitted my code and it passed and didn't get TLE. Thank god it's not a rated codeforces round otherwise I wouldn't have forgiven myself
Tutorial for F/G
Let's consider every pair $$$\displaystyle(i, j)$$$ in the array, and find out $$$\displaystyle f(i, j)$$$ which is how many subsequences will include both $$$\displaystyle i$$$, $$$\displaystyle j$$$ as a mirrored pair.
The answer to the problem should be $$$\displaystyle\sum_{i=1}^{i=n} \sum_{j=i+1}^{j=n} f(i, j)*(arr_i != arr_j)$$$.
If we find a way to calculate $$$\displaystyle f(i, j)$$$ in $$$\displaystyle O(1)$$$, this should be good enough to get solution for easy version in $$$\displaystyle O(n^2)$$$.
Any subsequence that includes both $$$i$$$ and $$$j$$$ should be counted, with only one condition that the number of items in the subsequence to the left of $$$i$$$ should be equal the number of items in the subsequence to the right of $$$j$$$ (to keep $$$i$$$, $$$j$$$ mirrored to each other).
Let's denote the number of available items to the left of $$$i$$$ as $$$L$$$, the number of available items to the right of $$$j$$$ as $$$R$$$. Let's also denote the number of items inbetween $$$i$$$ and $$$j$$$ as $$$M$$$.
It should be clear that $$$n = L + R + M + 2$$$.
Given the above condition only applies to $$$L$$$ and $$$R$$$, the subsequence can include any of the $$$M$$$ items inbetween $$$i$$$ and $$$j$$$, and it would still be valid. This gives us at least $$$W1 = 2^M$$$ options.
There are also options to choose $$$x$$$ items to the left and to the right of $$$i$$$ and $$$j$$$, which gives us $$$\displaystyle W2 = \sum_{X=1}^{X=n} C(L, X)*C(R, X)$$$ more options.
As the case with many other summations involving binomial coefficients, $$$W2$$$ can be reduced to $$$\displaystyle C(L+R, L)$$$.
Thus, $$$\displaystyle f(i, j) = W1 * W2 = 2^M * C(L+R, L)$$$.
where $$$L = i - 1$$$, $$$R = n - j$$$, $$$M = n - L - R - 2$$$.
Which can be calculated fast enough in O(1).
Let's try solving the problem in a reversed way. Let's assume that all pairs $$$(i, j)$$$ are bad initially, and then subtract $$$f(i, j)$$$ for pairs that are not gonna need to change (i.e. $$$arr_i = arr_j$$$).
More specifically the answer should be
$$$\displaystyle (n - 1) * 2^{n - 2} - \sum_{i=1}^{i=n} \sum_{j=i+1}^{j=n} f(i, j)*(arr_i == arr_j)$$$.
calculating $$$f(i, j)$$$ only for pairs where $$$arr_i = arr_j$$$.
The name of the problem gives us some hint that sqrt analysis must be involved.
We can observe that for values that occurr only once in the array, we don't really need to compute anything. (Remember we are now only concerned with pair $$$(i, j)$$$ where $$$arr_i = arr_j$$$).
Similarly, for any index $$$i$$$, where $$$arr_i$$$ occurr a few number of times $$$< sqrt(n)$$$, we need to iterate over a few number of pairs $$$(i, j)$$$ which can be done easily if we keep the occurrences of each value separately.
However, for indices with more repeating values, we need another way.
We are now concerned with values that occurr more than sqrt(n) times in the array. Obviously, there can't be more than sqrt(n) of those values.
Let's have another look at the formula for $$$f(i, j)$$$ that we have compiled above.
$$$\displaystyle f(i, j) = 2^M * C(L+R, L)$$$.
where $$$L = i - 1$$$, $$$R = n - j$$$, $$$M = n - L - R - 2$$$.
Let's write $$$f(i, j)$$$ purely in terms of just i, and j.
$$$\displaystyle f(i, j) = 2^{j - i - 1} * C(n + i - j - 1, i - 1)$$$.
Let's also expand the binomial coefficient
$$$\displaystyle f(i, j) = 2^{j - i - 1} * \frac{factorial(n + i - j - 1)}{factorial(i - 1) * factorial(n - j)}$$$.
Let's organize things a little bit.
$$$\displaystyle f(i, j) = 2^{i - 1} * fact^{-1}(i - 1) * 2^{j} * fact^{-1}(n - j) * fact(n + i - j - 1)$$$.
Now we can notice the terms in the formula are either dependent on $$$i$$$ only, or $$$j$$$ only, or $$$i - j$$$. This is a big hint that we can evaluate the summation of $$$f(i, j)$$$ using multiplying polynomials.
Let's imagine we have two polynomials P1 including terms that depend on i only, and P2 that includes terms that depend on j only.
$$$\displaystyle P1(x) = \sum_{i=1}^{i=n} 2^{i-1} * factorial^{-1}(i-1) * x^{i}$$$
$$$\displaystyle P2(x) = \sum_{j=1}^{j=n} 2^{j} * factorial^{-1}(n - j) * x^{-j}$$$
We can represent the multiplication of them as
$$$\displaystyle P(x) = P1(x) * P2(x)$$$
$$$\displaystyle P(x) = \sum_{i=1}^{i=n} \sum_{j=1}^{j=n} (2^{i-1} * fact^{-1}(i-1) * 2^{j} * fact^{-1}(n - j)) * x^{i-j}$$$
The resulting polynomial $$$P(x)$$$, is kind of the same as summation of $$$f(i, j)$$$ over all possible $$$(i, j)$$$, except that for each term we need to multiply it by $$$fact(n + i - j - 1)$$$ (notice that $$$i - j$$$ is the exponent of $$$x$$$ in the resulting polynomial).
Luckily, we have got number theoretic transform to do the magic for us and multiply polynomials in $$$O(nlog(n))$$$.
We can construct polynomials $$$P1$$$ and $$$P2$$$ for each value $$$V$$$, that occurrs more than $$$sqrt(n)$$$ times in the array.
For example $$$P1(x)$$$ should look like
$$$\displaystyle P1(x) = \sum_{i=1}^{i=n} 2^{i-1} * factorial^{-1}(i-1) * (arr_i == V) * x^{i}$$$.
Doing the polynomial multiplication should get us summation of $$$f(i, j)$$$ for all $$$(i, j)$$$ where $$$arr_i = arr_j = V$$$.
This adds up to $$$O(nsqrt(n)logn)$$$.
Actually if you implement it better, the time complexity is $$$\mathcal{O(n\sqrt{n\log n}})$$$ as the complexity in different parts are different and only one contains $$$\log$$$.
Auto comment: topic has been updated by Amir_Parsa (previous revision, new revision, compare).