### YouKn0wWho's blog

By YouKn0wWho, 2 years ago,

Thanks for participating in my contest . I hope you liked the problems. I would love to hear your feedback in the comments.

If you find anything wrong in the editorial which is more likely to happen because I have written a rather long editorial to make you understand the solutions better, then comment below.

Also, don't forget to upvote to pay for the editorial. See you in my next contest!

Code
Code
Code
Code
Code
Code (1D1D DP)
Code (D&C DP)
Code
Code
• +517

| Write comment?
 » 2 years ago, # |   +302 1B was shit
•  » » 2 years ago, # ^ |   +62 Problems like div2 D(div1 B) which only requires some stupid mathematical observations makes me lose all hope from Codeforces.
•  » » » 2 years ago, # ^ |   +26 The process that worked for me to solve it was: Do a brute force for $x < y$ case, see all the possible answers for a few hand-made tests. Look at one of an ends of the answers sequence (upper end works). Observe that the number is close to $y$. Think of the solution in the form $n = y - \varepsilon$ where $\varepsilon$ is very small. Then $y \bmod n = y \bmod (y - \varepsilon) = \varepsilon$. And $n \bmod x = (y - \varepsilon) \bmod x = y \bmod x - \varepsilon$. The two are equal, so $2 \cdot \varepsilon = y \bmod x$. So, yeah, some amount of observation was required, but it mostly followed from looking at the brute-forced list of all possible answers.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +4 I solved it by very straightforward solution. 133667090 suppose, n = ax + r, and y = bn + r then y = abx + (b + 1)r if y < x, then ab = 0, just return x + y else, try to divide ab as two integers and check if the answer is valid I don't know why it works. Hope someone can proof it or hack it.
•  » » » » » 2 years ago, # ^ |   +16 It's correct but you need to carefully check whether the factorization leads to a valid answer. a=floor(y/x), b=1, r=(y-ax)/2 is a solution (since x, y are both even, r will be integer).
•  » » » » » » 2 years ago, # ^ |   +8 That' it! I divided from 1, so always got the answer you mentioned. Thanks.
•  » » » » » 2 years ago, # ^ |   +8 In the 3rd statement returning (x+y) was just an observation or you calculated. Can you elaborate plz
•  » » » » » » 2 years ago, # ^ |   +9 A view of it: The expression $n \bmod x = y \bmod n$ is complex. And $n$ can be up to $2 \cdot 10^{18}$ according to the statement. But if $n$ was large enough, the formula will transform into just $n \bmod x = y$, which is simple. So let us think about large enough $n$. When $x > y$, the expression $n \bmod x = y$ means we can use $n = x \cdot k + y$ for any large enough integer $k$. Turns out $k = 1$ is fine.
•  » » » » » » » 2 years ago, # ^ |   +8 Ohh got it. Thanks a lot Gassa.
•  » » » » 2 years ago, # ^ |   0 Hey Gassa, can you please explain why ymod (y-e) = e ?
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Try to imagine it with concrete numbers: Let $y = 1\,000\,000$ and $\varepsilon = 5$. Then $1\,000\,000 \bmod 999\,995$ is simply $1\,000\,000 - 999\,995 = 5$.Generally, the equation $y \bmod (y - \varepsilon) = y - (y - \varepsilon)$ holds for $0 \le \varepsilon \le y / 2$.
•  » » » » 20 months ago, # ^ |   +8 Hello! I was unable to come up with this kind of solution. What do you suggest to do if I want to solve problems like this in a real contest. Should I take this problem seriously regarding the approach you took like I could understand the things you wrote and they were pretty much justified in them so no doubt in that.
•  » » » » 7 months ago, # ^ |   0 How this statement:(y−ε)modx=ymodx−ε is true? It is only possible if ε is less than x. But how are we sure that ε is always smaller than x;
•  » » 2 years ago, # ^ | ← Rev. 3 →   +78 My div1B experience: struggle >1 hour writing equations to find n with rigurous maths. in the last 15 minutes: look at random particular cases of x and y and try to guess the formula. I actually got AC with a half-guessed formula 1 minute before the round ended... Perfectly balanced guessforces problem
 » 2 years ago, # | ← Rev. 3 →   +67 #mathsforces #adhocforces
•  » » 2 years ago, # ^ |   +3 you are alt of spacetime , aren't you ?
•  » » » 2 years ago, # ^ |   0 stalker
 » 2 years ago, # | ← Rev. 3 →   +8 Great Contest! Was able to solve 3 and 4th went off in nick of time.Completely Mathforces And thanks for the fast editorial.
 » 2 years ago, # |   -10 My DIV2B didn't get AC though it's the same as you described
•  » » 2 years ago, # ^ |   +5 a[i]<=a[i-1] would probably get you ac
 » 2 years ago, # | ← Rev. 4 →   -26 Editorial be like: Meme
 » 2 years ago, # | ← Rev. 2 →   +11 For 1603A - Di-visible Confusion we can also go from the end of an array and try to remove each item, and after each removal repeat the process. If you passed the whole array and didn't find an element to remove, the answer is NO. It can be shown that in the worst case you will pass each element no more than 21-22 times (you proved it in the editorial), so this solution is also possible.The only sad thing about this solution is that you need to calculate an actual index of your element, and in order to do that you may need Fenwick tree.Solution: 133626329
•  » » 2 years ago, # ^ |   +27 I think we do not need a Fenwick tree in this solution: simply shift each element after the removed one. (The complexity is good since each element is shifted at most 21 times.)Code: 133622802
•  » » » 2 years ago, # ^ |   +18 Or just use linked lists
•  » » 23 months ago, # ^ | ← Rev. 2 →   +3 P-A Ignore
 » 2 years ago, # | ← Rev. 3 →   +8 In the editorial for problem C it is written that "must be divisible by at least one integer from 2 to i+1", I guess it should have been "not divisible by". thanks. btw, great contest.UPD: It is updated now.
 » 2 years ago, # |   +70 did anton also write the Thanks to Anton for writing editorial for this problem.
 » 2 years ago, # | ← Rev. 2 →   +17 These cringy math symbols are going to give me nightmare tonight
 » 2 years ago, # |   +14 Whoa, i've got a simple solution for div.1 C, though i don't know how to prove its correctness (so maybe it's wrong).We use brute force set r from n to 1, and move l to the left, when minimal hasn't changed we skip it.And it passed (right now)!!!133667648
•  » » 2 years ago, # ^ |   0 I think this solution is actually provable, cause every iteration you increase the value of one of the elements of cut array. And since there are O(sqrt(i)) possible values of cut[i] the total number of iterations is O(n*sqrt(n)).
 » 2 years ago, # |   0 Was this submission hackable? It's technically wrong because there might be overflow but I think all integers coming from this overflow have 9 digits or more, so none could divide the numbers, which is unfortunate.
 » 2 years ago, # |   +35 I solved Div1F with a different formula: the answer is $\sum_{l=0}^{k-1}({\binom{n}{n-l}}_{2} \cdot \prod_{i=1}^{l}(2^k - 2^i))$where ${\binom{n}{k}}_{2} = \frac{(1-2^n) \cdot \dots \cdot (1-2^{n-k+1})}{(1 - 2) \cdot \dots \cdot (1 - 2^k)}$is a gaussian binomial coefficient (https://en.wikipedia.org/wiki/Gaussian_binomial_coefficient).
 » 2 years ago, # | ← Rev. 3 →   +8 I have an $O(n\log^3 n)$ solution for D1D which sadly I wasn't able to debug during contest because of wasting time on A: Just use segtrees to optimize calculating $f(n,K)$. Precalculate $g(n,k)$ which is the number of $l$s such that $gcd(n,l)=k$, and mainting a segtree with range add and range minimum. When we encounter $n$, we insert $f(n-1,k-1)$ into segtree, and go over all $n$'s divisors $d$ and add $[1,d]$ by $g(n,d)$.
•  » » 2 years ago, # ^ |   -26 My solution is similar to you.And it is the only problem I do during the contest.I submit with another account (
 » 2 years ago, # |   +17 Enough Math for today. errrrrr
 » 2 years ago, # |   +23 Alternative solution for Div1A/Div2C: notice, that it is always beneficial to erase last element if possible — it won't ever affect any other number in the array and it have to be removed at some point. Why not now? If you can't remove the last element, then it's beneficial to erase second-to-last element, if possible. The proof is by similar argument to the previous one. ... In other words -- find the first element in reversed array that we are capable of removing. Execute this simple rule in a loop until array is empty (output YES) or no more elements can be removed (output NO). Convince yourself that each element will be checked only a handful of times -- it's pretty hard to select a number that will be divisible by many of the indices $i + 1$, $i$, $i - 1$, ... . As the original editorial proved, it's at most 21 times. Implement code using $\texttt{std::list}$ and $\texttt{std::find_if}$ (notice that find_if breaks when it finds first occurence) -- 133627167. Total complexity: $\mathcal{O}(21n)$
 » 2 years ago, # |   +3 It just felt like a math contest or something, I wish I had seen more algorithm-oriented problems.
 » 2 years ago, # | ← Rev. 4 →   +1 There is another solution to problem C as well: Start from the end, if the last number is not divisible by (i+1) then erase it as it will not affect other elements. Now, find all the indexes which satisfy the given divisibility condition and store them in a priority queue. It is always good to delete elements (if possible) from the right. Also, calculate the count of consecutive values which will divide the number and we don't need to check this for more than 12-13 times. Now delete the first element of the priority queue and update the values of all the indexes greater than the current deleted element and you are sure that you will not need to traverse each element more than 12-13 times, so it's fine. End when the priority queue becomes empty (as this tells that all the divisible elements are removed) and check if all the elements are deleted or not. My code : https://codeforces.com/contest/1604/submission/133638614
 » 2 years ago, # |   -68 math
 » 2 years ago, # |   -70 math
 » 2 years ago, # |   -74 every
 » 2 years ago, # |   -62 where
•  » » 2 years ago, # ^ |   0 Sir why you write 500000 comments in 0.9 seconds like a psychobot???
 » 2 years ago, # |   +123 Here is how the donation amount looks like: Div2A - 0.005 * 9529 = 47.645 USD Div2B - 0.006 * 6274 = 37.644 USD Div2C/Div1A - 0.008 * (4012+967) = 39.832 USD Div2D/Div1B - 0.01 * (2273+911) = 31.84 USD Div2E/Div1C - 0.04 * (27+396) = 16.92 USD Div2F/Div1D - 0.2 * (1+24) = 5 USD Div1E - 2 * 8 = 16 USD Div1F - 2 * 3 = 6 USD Total - 200.881 USD FYI I will get 400 USD for this contest. So the donation amount is indeed half of this as I have estimated before the contest, although didn't think that it would be this accurate. I will update you again when I get the money from Codeforces, more likely after a few months as I haven't received my previous contest's payment yet which happened 3 months ago!Also, thanks for being a part of this. You have just helped someone who is in need (I mean after I distribute the money).
•  » » 2 years ago, # ^ |   0 Where will the money be donated?
•  » » » 2 years ago, # ^ |   +24 I will update you when I get my payment. I will mostly distribute them to some poor people from the street. If you have some suggestions let me know.
•  » » » » 2 years ago, # ^ |   +3 just a suggestion try to donate to someone asking for help in ketto or something like that(means who r suffering from medical crises)
•  » » » » 2 years ago, # ^ |   +8 It's fine. I feel like it is the best way to do it, having no third parties involved will make sure that the money will be given to those who really need it.
•  » » » » 2 years ago, # ^ |   0 TeamSeas
•  » » 2 years ago, # ^ |   +27 It's actually cool that the guess was so close!
 » 2 years ago, # |   +56 Unpopular OpinionA contest full of maths is really boring.
•  » » 2 years ago, # ^ |   +38 And Honey when you solve it within a minute.
 » 2 years ago, # |   +8 Can you provide a proof for D&C Div 1 D time complexity? I belive you should rely on the properties of this specific dp, because otherwise you can make a test where at the bottom level you would have something like $opt_i = i - \frac{n}{2}$, which would lead to $O(n \sqrt n)$ time complexity for one layer.
 » 2 years ago, # |   +11 The Editorial is quite long, it would be nice if you had used spoiler type as u did for code.
 » 2 years ago, # | ← Rev. 4 →   +5 PS: I GOT FST! For Div.2 C what I did was for every $i$, finding the nearest $j$ such that $j + 1$ is not divisible by $a[i]$ and pushing the index $i$ to $mp[i - j]$. Here, $mp$ is a map of vectors. $mp[d]$ eventually stored the indices that become erasable after $d$ elements from their left gets erased. Obviously we need to start by erasing some element in $mp[0]$. Here, starting with the rightest element $x$ is the optimal because minimum number of elements gets negatively affected from this operation. So we erase $x$ from $mp[0]$. After erasing $x$ we have to check whether there are new erasable elements to the right of $x$ and such elements can only be in $mp[1]$. Thus we check whether the rightest element of $mp[1]$ (let's call it $y$) is bigger than $x$. If not, we have to keep erasing from $mp[0]$. If yes, it is a good idea to first erase $y$ along with the indices that get erasable after erasing $y$ (It is a recursive process). Only after that we can continue with erasing from $mp[0]$. Eventually all the vectors should become empty in $mp$. If they are empty then the answer is "YES", otherwise the answer is "NO".Here is some in-contest ugly code but it failed the system test :( 133669599What the code does is there is a function solve(k, iterator) and k means the rightest element we have deleted before calling this function and the iterator basically finds the most recent non-empty vector waiting for their elements to get erased. Can anybody help me what is wrong with my solution?
 » 2 years ago, # |   +17 Why Itst_boyfriend's submissions are being shown out of contest?
•  » » 2 years ago, # ^ |   0 i think his code matched with others unfortunately and he was removed from the contest
 » 2 years ago, # |   0 In Div2 D, in case of (x
•  » » 2 years ago, # ^ |   0 x=4,y=14. It will fail on lot of cases like this.
 » 2 years ago, # |   +1 Seems like the solution of maths question paper.
 » 2 years ago, # |   +40 Here is a simpler solution to div1C:Assume that we want to calculate the extreme value of $a_1, a_2, \dots, a_i$. Let $t[j]=$ how many numbers $a_j$ is divided into, $v[j]=$ the smallest number $a_j$ is divided into. We know $t[j]=\lceil\frac{a_j}{v[j+1]}\rceil$, $v[j]=\lfloor\frac{a_j}{t[j]}\rfloor$. It can be observed that the extreme value of $a_j, a_{j+1}, \dots, a_i$ is $\sum_{k=j}^i (t[j]-1)$.For $i$ from $1$ to $n$, calculate $t[j]$ and $v[j]$ for all $j \leq i$. When we add a new element $a_i$ at the back, we can update $t[j]$ and $v[j]$ from $i-1$ to $1$ by brute force, but we stop the procedure when $t[j]$ is not changed. It seems to be an $O(n^2)$ solution, but for a certain $j$, $t[j]$ can be up to only $O(\sqrt C)$ different values, so we only update a value at most $O(\sqrt C)$ times, the solution is in $O(n \sqrt C)$ time.Code: 133689083
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 My solution (133668323) is similar to this. The worst test case for this I found locally is 100000 99999 99998 ... 3 2 1, where the inner loop body is executed ~35 million times. It is a bit more than $100\,000 \cdot \sqrt{100\,000}$, but still far from that amount doubled, which is the theoretical upper bound. I wonder if there is a more clever test to push the count further.
•  » » 2 years ago, # ^ |   0 It may be a dumb question but I don't see why it's ok to stop when $t[j]$ is not changed.
•  » » » 2 years ago, # ^ |   +11 The values $t[j]$ and $v[j]$ together fully define what happens to the left of them.For example, when you separate $10$ into three parts, you know the best way to do it is $10 = 3 + 3 + 4$. Going to the left of this position, all you need to know is that all the parts have to be $\le 3$. So, if you have already calculated what is the optimal solution on the left for parts $\le 3$, there is no need to do it again.It's like memoization but without recursive calls.
•  » » » » 2 years ago, # ^ |   0 Sorry I didn't notice the part to the left is still added to the answer when we stop. I wrongly thought we weren't adding it again. I got it now, thank you.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 That's a nice solution, imo nicer than the editorial.
•  » » 2 years ago, # ^ |   0 I think an important point you didn't mention is that the value of t[j] is non-decreasing for increasing i
 » 2 years ago, # |   0 I have an alternate solution for Div 2C that I personally find easier. I found a simple solution where I simply store an array of numbers to represent how many positions each value of a must be shifted to no longer be divisible by i+1, then I walk through the array and ensure that each value is less than the amount of numbers preceding it in the array. This works because it can be proved that as long as the sequence can be reduced, there is always an optimal move that does not negatively affect any of the other positions, so you do not need to worry about shifting a number from a non-divisible status to a divisible status. Apologies for any confusion as I am not too familiar on how to format comments and I am not too skilled at describing algorithms. My code is here: https://codeforces.com/contest/1603/submission/133704780Very cool contest! I personally quite enjoyed the observation/logic side... I don't think the maths were too difficult either, although I couldn't figure out 2D for x
 » 2 years ago, # |   0 Any intuition behind div2 D in the second part where y >= x
 » 2 years ago, # | ← Rev. 2 →   +55 YouKn0wWhoDiv1 F — The explanation has many off-by-one errors. In particular, the answer for $X\neq 0$ should actually be $\sum_{i=0}^{k-1}(-1)^i(2^{k-1-i})^n\prod_{j=0}^{i-1}(2^{k-j-1}-1)\cdot 2^{k-i-1}.$ if (X) { mi ans = 0; F0R(i,K) { mi cur = pow(mi(2),N*(K-i-1)); F0R(j,i) cur *= po2[K-j-1]-1; cur *= po2[K-i-1]; ans += (i&1?-1:1)*cur; } return ans; } Shouldn't $n$ be $k$ here? Let's replace $n-t$ by $n$, ...
•  » » 2 years ago, # ^ | ← Rev. 4 →   +37 It's also worth noting that counting the number of length-$N$ sequences such that the resulting subspace has dimension $k$ for each $k\in [0,K]$ is given by $\#(k)=\prod_{i=0}^{k-1}(2^K-2^i)\cdot \left([t^{N-k}]\prod_{i=0}^{k}\frac{1}{1-q^it}\right)$This can be computed with the q-binomial theorem (with $q=2$). After computing these, the answer will be $\sum_{k=0}^{K}\frac{2^K-2^k}{2^K-1}\cdot \#(k).$Code: 133694728I was not aware that evaluating $\left([t^{N-k}]\prod_{i=0}^{k}\frac{1}{1-q^it}\right)$was doable but it seems that rainboy managed to find this link during the contest, congrats!
•  » » » 2 years ago, # ^ |   +26 The formula can be obtained by disturbing the GF. Let $F(t)=\prod_{i=0}^k \frac1{1-q^it}$, then we have $(1-t)F(t) = (1-q^{k+1}t)F(qt)$, hence a recurrence.
•  » » » » 2 years ago, # ^ | ← Rev. 4 →   +16 Not totally sure which formula you are referring to. Could you elaborate on how $(1-t)F(t)=(1-q^{k+1}t)F(qt)$ allows us to determine the coefficients of $F(t)$?EDIT: Ok, if we define $c_i=[t^i]\prod_{i=0}^{n-1}\frac{1}{1-q^it},$then $c_i-c_{i-1}=q^ic_i-q^{n+i-1}c_{i-1}\implies c_i=\frac{q^{n-1+i}-1}{q^i-1}\cdot c_{i-1},$from which the result follows. Thanks!
•  » » » » » 2 years ago, # ^ |   +27 Consider the $[t^n]$ of two sides of the equation, then it gives a recurrence of $[t^n]F$.
 » 2 years ago, # | ← Rev. 3 →   0 1D : Isn't $c(x,2x-1)=x$?All pair like $(i,i)\ (x\leq i \leq 2x-1)$ satisfy $gcd(i,j)>=l$.Upd : And the editorial's difination of $c(i,j)$ is diffent from statement's.
 » 2 years ago, # | ← Rev. 2 →   -28 Really Mathforces.
 » 2 years ago, # |   0
 » 2 years ago, # |   +3 Perhaps the editorial for Div1 D,E are the clearest ones I've ever seen.The problems are truly nice.
 » 2 years ago, # |   +8 There is a mistake in the Proof of the observation 3 in problem E. Perhaps the author mistook i as j:(
•  » » 2 years ago, # ^ |   +5 You are right. I will update asap.
 » 2 years ago, # |   +8 woo, the author's just got so crazy at sqrt that it appears at the overall complexities of three adjacent problems!
 » 2 years ago, # |   +11 The Editorial of Div1E is really detailed and easy-understanding.Thank you!
 » 2 years ago, # | ← Rev. 2 →   0 Why my submission is giving wrong answer not runtime error? submission 133743503 , I have checked "assert(ans%x == y%ans && ans <= 2000000000000000000LL && ans >= 1);". Am I missing something ?
•  » » 2 years ago, # ^ |   +11 You have modified the value of x before your assert function.
 » 2 years ago, # | ← Rev. 2 →   0 For 1603C - EXTREME EXTENSION - Extreme Extension, the space can be reduced to O(sqrt(M)) where M = 100,000, the maximum possible input value. This is using the observation that if we have a quotient x/k, then min(k, x/k) ≤ sqrt(x), so instead of a single vector of length M, we can use two vectors of length sqrt(M) (one of the values of k, one for the values of x/k).The solution still takes O(N sqrt(M)) time.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +10 I'm a bit confused about all the downvotes. What did I do wrong?(Note: edited the above post to show how the problem can be implemented as an on-line algorithm, i.e., without allocating an N-element array upfront.)
 » 2 years ago, # |   +1 Excellent Contest. I think observations are important for CP rather than implementing the same algorithms continuously in more or less the same way to solve the questions. All Of CP is actually Mathematics only so I personally liked all the problems.
 » 2 years ago, # |   0 I have a doubt in regards to the editorial for Div1 C. Shouldn't $b_{1}=a_{i+1}\mod a_{i}$? If we set $b_1$ to what is mentioned in the editorial, won't the updated value for $a_1$ be wrong for the array $[10, 3]$? As far as I understand, the updated value for $a_1$ should be $1$ here, but according to the editorial it seems to be $2$.Can someone please clarify?
•  » » 2 years ago, # ^ |   0 It should be $2$, because $2$ is greater and it is possible to achieve this using $3$(the minimum) operations: $[10, 3] \rightarrow [2, 2, 3, 3, 3]$. In your case, it is $[1, 3, 3, 3, 3]$ using $3$ operations. But if we can achieve $2$ why bother with $1$ which is lower?
•  » » » 2 years ago, # ^ |   0 Oh I see now. Thanks!
 » 2 years ago, # |   0 There is a much cleaner solve for div2C/div1a (my solve is 133995726). Basically you find the highest non-divisor of a_i under i + 1 and check if that is less than 2. If any of these are less than 2 then the answer is NO, otherwise it is YES.The reason this works is because the only time we cannot remove a number is when there are not enough numbers before it to get it to a value where it is not divisible. Otherwise it is enough to just remove the rightmost number that can be currently removed, which will always exist.
 » 2 years ago, # |   0 div1A(2C)can be greedily deleted from the back, and then simulated with the stack?I passed the question like this, but I don't know whether greed is correct
•  » » 2 years ago, # ^ |   +8 It is indeed correct.
 » 2 years ago, # | ← Rev. 2 →   +8 Problem 1C, why $\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\sum\limits_{j=i+1}^{\lfloor \frac rk\rfloor}=\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\phi(i)$?I think it should be $\sum\limits_{k=l}^r\sum\limits_{i=1}^{\lfloor \frac rk\rfloor}\sum\limits_{j=i+1}^{\lfloor \frac rk\rfloor}=\sum\limits_{k=l}^r\sum\limits_{i=2}^{\lfloor \frac rk\rfloor}\phi(i)$.
•  » » 2 years ago, # ^ |   0 I agree.
 » 2 years ago, # |   +75 I've discovered a much simpler sulotion with $n^3\sqrt n$ time complexity for problem E.It's currently the fastest solution on codeforces:Link
 » 2 years ago, # |   +56 I have a question with the time complexity of Div1.E.In the observation 7,the solution improved the time complexity from $\mathcal O(n^5\log n)$ to $\mathcal O(n^3\sqrt{n}\log n)$ by only enumerating $a_i$ from $n-2\sqrt{n}$ to $n$. But we still have $\mathcal O(n^2\sqrt{n})$ states，and the complexity of transfering is $\sum_{k=1}^{n-a_1+1}\dfrac{a_1}{k}$ ，which is still $\mathcal O(n\log n)$ . So I think the time complexity is $\mathcal O(n^4\log n)$ ，and I don't know why my understanding is wrong. Can someone help me sort this out?
•  » » 2 years ago, # ^ |   +6 I'm sorry that I found the mistake in my understanding. In fact,the complexity of transfering which is $\mathcal O(n\log n)$ is actually the sum of transfering $dp(i,j,1),dp(i,j,2),\dots,dp(i,j,k)$ ，so the whole time complexity is $\mathcal O(n^2)\times \mathcal O(n\log n)\times \mathcal O(\sqrt{n})=\mathcal O(n^3\sqrt{n}\log n)$. Sorry for wasting your time.
 » 2 years ago, # |   0 1D and 1E was so great! I really like it.
 » 2 years ago, # |   0 Problem F is an amazing problem. I have two solutions not listed in the editorial or in the comments.I will prove the following claim: let $f(n,l)$ be the number of $n$-tuples of vectors in $\mathbb{Z}_2^k$ such that the spanning set of these vectors has size $2^l$. Then $f(n,l)=\prod\limits_{i=0}^{l-1} \frac{(2^k-2^i)(2^n-2^i)}{2^l-2^i}$First proof, by recursion and bashing. First observe that $f(n,l)=2^l f(n-1,l)+(2^k-2^{l-1}) f(n-1,l-1)$This is true by considering whether the last case increases the spanning set or not.Now we induct on n and $l$.Base Case: $n=l$. Clear.Inductive Step: It suffices to show that $\prod\limits_{i=0}^{l-1} \frac{(2^k-2^i)(2^n-2^i)}{2^l-2^i}-2^l\prod\limits_{i=0}^{l-1} \frac{(2^k-2^i)(2^{n-1}-2^i)}{2^l-2^i}$ $=(2^k-2^{l-1})\prod\limits_{i=0}^{l-2} \frac{(2^k-2^i)(2^{n-1}-2^i)}{2^{l-1}-2^i}$We first cancel out the $\prod\limits_{i=0}^{l-1} (2^k-2^l)$on both sides. This is equivalent to showing $\prod\limits_{i=0}^{l-1} \frac{(2^n-2^i)}{2^l-2^i}-2^l\prod\limits_{i=0}^{l-1} \frac{(2^{n-1}-2^i)}{2^l-2^i}=\prod\limits_{i=0}^{l-2} \frac{(2^{n-1}-2^i)}{2^{l-1}-2^i}$Now we expand the left hand side to get $\frac{1}{\prod\limits_{i=0}^{l-1} (2^l-2^i)} (\prod\limits_{i=0}^{l-1} (2^n-2^i) - \prod\limits_{i=0}^{l-1} (2^n-2^{i+1}))$ $=\frac{\prod\limits_{i=1}^{l-1} (2^n-2^i)}{\prod\limits_{i=0}^{l-1} (2^l-2^i)} (2^n-1-2^n+2^l)$ $=\frac{\prod\limits_{i=1}^{l-1} (2^n-2^i)}{\prod\limits_{i=1}^{l-1} (2^l-2^i)}$Dividing both sides by $2^{l-1}$yields the desired result.The motivation for the first proof is that the numbers have a nice form.Second proof, via polynomial. We first count the number of $2^{l}$-element spans (S such that there exist $x_1,\cdots,x_l$ such that $S$ contains all and only elements of the form $v_1x_1 \bigoplus \cdots \bigoplus v_lx_l$ for $v_i\in {0,1} \forall 1\le i\le l$ in $\mathbb{Z}_2^k$.On one hand, there are $\prod\limits_{i=0}^{l-1} (2^k-2^i)$ ways to pick $l$ linearly independent elements. On the other hand, there are $\prod\limits_{i=0}^{l-1} (2^l-2^i)$ ways to select the same span.Now, fix a span. We use inclusion-exclusion to find the number of ways to pick $n$ vectors such that their span has size $2^l$. It is not hard to show that this is a polynomial of degree at most $l$ in $2^n$ (i.e. the answer for $n$ is $P(2^n)$ for some $\deg P\le l$). Furthermore, for $n=0, 1, \cdots, l-1$, the answer is 0, which implies $P(x)=c\prod\limits_{i=0}^{l-1} (x-2^i)$. For $n=l$ the answer is $\prod\limits_{i=0}^{l-1} (2^l-2^i)$, implying $c=1$, as needed.Now the answer is simply $\frac{1}{2^k-1}\sum\limits_{l=0}^{\min\{k,n\}} f(n,l)(2^l-1)$because the probability that an element is in a randomly selected span of $2^l$ elements is $\frac{2^l-1}{2^k-1}$I tried to format this, but sometimes the dollar signs don't render (they render on the overleaf compiler) and I have to use double dollar signs.
 » 23 months ago, # |   0 I think the editorial has a typo in 1C.The contribution term near the end currently says $i \cdot dp(i + 1, x) \cdot \left(\lceil \frac{a_i}{a_{i+1}} \rceil - 1 \right)$. I believe the $a_{i+1}$ should be $x$.
 » 22 months ago, # |   0 Here's my algorithm for Moderate Modular Mode. If x = y, then just print x If x < y, then print (x + y) /2 If x > y, then print x + yI'm having trouble finding edge cases for this algorithm. Here's my code if needed143933295
 » 22 months ago, # |   0 For Div2E, I was stuck at the following part --> how do you find the smallest k for which $\lceil \frac{a_i}{k} \rceil \leq a_{i+1}$. Turns out this is just $\lceil \frac{a_i}{a_{i+1}} \rceil$. Somehow not that intuitive to me, so I was binary searching and thus getting TLE. Is there some easy ways to work with such kind of inequalities.
 » 17 months ago, # |   -10 Hello,     In Problem 1603B - Moderate Modular Mode for the second case (when x ≤ y), can't we simply take the average ? Because if n the average of x and y, it will be the same distance from x to n and from n to y ... Is there any Counter Example ??
•  » » 17 months ago, # ^ |   0 This only works if n % x == n — x and y % n == y — n, which is not always true. Consider x = 4 and y = 30, for example. If we use your strategy, n = (4 + 30) / 2 = 17. But 17 % 4 = 1 not 13.
 » 10 months ago, # |   0 Div1 E Complexity seems to be actually $O(n^3\sqrt n)$ with a constant of $\frac{\pi^2}{18}$. By eliminating all unnecessary transits, the result will look something like this: \begin{aligned} &\sum\limits_{mn,i,j,k,i_0} [j+ik\le mn] [i_0i\le j]\\ =&\sum\limits_{mn,j,k} \frac{mn-j}{k} \frac{j}{k}\\ =&\sum\limits_{mn,j} (mn-j)j \sum\limits_{k} \frac{1}{k^2}\\ \end{aligned}The former $\sum(mn-j)j$ sums up to $O(n^3\sqrt n)$ because $mn\in [n-2\sqrt{n},n]$ with a constant of about $1/3$, and the latter $\sum \frac{1}{k^2}$ sums up to less than $\zeta_2=\frac{\pi^2}{6}$. The total constant is therefore $\frac{\pi^2}{18}$.I tested it with the following code, in which Cnt=469601774 when n=400 and Cnt=1054688268 when n=500, which matches the result quite well (the actual constant is a little smaller because of other optimizations) Code#include #define For(i,a,b) for(int i=a;i<=b;i++) #define Rev(i,a,b) for(int i=a;i>=b;i--) #define Fin(file) freopen(file,"r",stdin) #define Fout(file) freopen(file,"w",stdout) #define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false)) using namespace std; typedef unsigned long long ull; typedef __uint128_t L; struct FastMod { ull b, m; FastMod(ull _b) : b(_b), m(ull((L(1) << 64) / b)) {} inline ull reduce(ull a) { ull q = (ull)((L(m) * a) >> 64); ull r = a - q * b; // can be proven that 0 <= r < 2*b return r >= b ? r - b : r; } }; FastMod F(2); const int N=505; typedef long long ll; int n,mod,ans,f[N][N][N],C[N][N],Cnt; signed main(){ cin>>n>>mod; F=FastMod(mod); For(i,0,n) { C[i][0]=1; For(j,1,i) C[i][j]=F.reduce(C[i-1][j]+C[i-1][j-1]); } ans=2; int B=sqrt(n)+2; For(mn,n-2*B,n) if(n+1-mn<=mn){ Rev(i,n-1,1){ if(n-i<=mn){ f[i][0][0]=C[n][i]; if(i*(n+1-mn)<=mn&&f[i][0][0]) ans=F.reduce(ans+f[i][0][0]); } For(j,0,mn){ for(int k=max(1,n-i+(j!=0)-mn);mn+k<=n&&j+i*k<=mn;k++) { for(int i0=i+1;i0<=n&&(i0-i)*k<=j;i0++){ Cnt++; f[i][j][k]=F.reduce(f[i][j][k]+1ll*f[i0][j-(i0-i)*k][k-1]*C[i0][i]); } if(j+i*(n+1-mn)<=mn&&f[i][j][k]) ans=F.reduce(ans+f[i][j][k]); Cnt++; f[i][j][k]=F.reduce(f[i][j][k]+f[i][j][k-1]); } } } For(i,1,n-1){ For(j,0,mn){ for(int k=1;mn+k<=n&&j+i*k<=mn;k++) f[i][j][k]=0; } } } cout<
 » 4 months ago, # |   0 i just want to ask , why the solution to div1 A should be like that , i understand the editorial but still didnt get it.