### YouKn0wWho's blog

By YouKn0wWho, 7 months 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 Tutorial of Codeforces Round #752 (Div. 1) Tutorial of Codeforces Round #752 (Div. 2) Comments (130)
 » 1B was shit
•  » » Problems like div2 D(div1 B) which only requires some stupid mathematical observations makes me lose all hope from Codeforces.
•  » » » 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.
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   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.
•  » » » » » 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).
•  » » » » » » That' it! I divided from 1, so always got the answer you mentioned. Thanks.
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   I solved the equations and got ab = floor(y/x), r(b+1) = y(mod(x)) I made the mistake of taking a=1 and b=floor(y/x). Logic_zys Why is this wrong?PS: Got it I guess. Is it because in this case r = y(mod(x))/(b+1) which isnt always necessarily an integer.
•  » » » » » In the 3rd statement returning (x+y) was just an observation or you calculated. Can you elaborate plz
•  » » » » » » 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.
•  » » » » » » » Ohh got it. Thanks a lot Gassa.
•  » » » » Hey Gassa, can you please explain why ymod (y-e) = e ?
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   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$.
•  » » » » » » Okay got it. Thanks alot Gassa
•  » » » » 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, # ^ | ← Rev. 3 →   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
•  » » I actually enjoyed doing the math, but for problems like this there's usually an unfair advantage as one can easily guess the solution.
•  » » I got it WA because of a silly mathematical mistake. Today's questions were focused on mathematics and observation more. It does not require any kind of logical and implementation.
 » 7 months ago, # | ← Rev. 3 →   #mathsforces #adhocforces
•  » » you are alt of spacetime , aren't you ?
•  » » » stalker
 » 7 months ago, # | ← Rev. 3 →   Great Contest! Was able to solve 3 and 4th went off in nick of time.Completely Mathforces And thanks for the fast editorial.
 » Nice contest and hope to see you again .
 » My DIV2B didn't get AC though it's the same as you described
•  » » a[i]<=a[i-1] would probably get you ac
 » 7 months ago, # | ← Rev. 4 →   Editorial be like: Meme » Div2 A — Simple mathDiv2 B — Simple observationDiv2 C — PainDiv2 D — More Pain СпойлерThe contest was good, managed to solve four problems with so many penalties. Anyways, Thanks for the fast editorial.
 » 7 months ago, # | ← Rev. 2 →   For 1603A - Раз-делимое замешательство 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
•  » » 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
•  » » » Or just use linked lists
•  » » 4 months ago, # ^ | ← Rev. 2 →   P-A Ignore
 » 7 months ago, # | ← Rev. 3 →   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.
 » did anton also write the Thanks to Anton for writing editorial for this problem.
 » 7 months ago, # | ← Rev. 2 →   These cringy math symbols are going to give me nightmare tonight
 » 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
•  » » can you make this more detailed please?
•  » » 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)).
 » 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.
 » 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).
 » 7 months ago, # | ← Rev. 3 →   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)$.
•  » » My solution is similar to you.And it is the only problem I do during the contest.I submit with another account (
 » Enough Math for today. errrrrr
 » 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)$
 » It just felt like a math contest or something, I wish I had seen more algorithm-oriented problems.
 » 7 months ago, # | ← Rev. 4 →   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
•  » » A priority queue is an overkill. A simple thing as you said select greedily from the right and delete it, it will be looking O(n*n) in nature but you will be iterating and cross one element not more than 20-21 times(because we also remove the particular element). So asymptotic complexity will be (20*n). My code: https://codeforces.com/contest/1604/submission/133691492
•  » » » 6 months ago, # ^ | ← Rev. 4 →   I'm still not convinced that the complexity is O(20*n). I think it can be in O(1) time. You just have to check the first 22 numbers. If there is even a single number that is not removable, then you're done, and the output is "NO". Otherwise, all the numbers are removable. Here, you are also done. The only way that the rest of the list is not removable is if all the numbers are greater than 22! which they're not since they're upper bounded by 10^9. I think the editorial offers an O(n + 22^2) only because it takes O(n) to read in the original array.My submission O(1): https://codeforces.com/contest/1604/submission/135795122
 » math
 » math
 » every
 » where
•  » » Sir why you write 500000 comments in 0.9 seconds like a psychobot???
 » 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).
•  » » Where will the money be donated?
•  » » » 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.
•  » » » » just a suggestion try to donate to someone asking for help in ketto or something like that(means who r suffering from medical crises)
•  » » » » 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.
•  » » » » TeamSeas
•  » » It's actually cool that the guess was so close!
 » Unpopular OpinionA contest full of maths is really boring.
•  » » And Honey when you solve it within a minute.
 » 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.
 » The Editorial is quite long, it would be nice if you had used spoiler type as u did for code.
 » 7 months ago, # | ← Rev. 4 →   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$. 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$. 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$. Thus we check whether the rightest element of $mp$ (let's call it $y$) is bigger than $x$. If not, we have to keep erasing from $mp$. 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$. 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?
 » Why Itst_boyfriend's submissions are being shown out of contest?
•  » » i think his code matched with others unfortunately and he was removed from the contest
 » I think DIV2 C is more difficult than DIV2 D. D was based on observation and can be guessed also. I actually enjoyed the contest. Thanks for fast editorial :)
 » In Div2 D, in case of (x
•  » » x=4,y=14. It will fail on lot of cases like this.
•  » » I guess (x+y)/2 will only work when y<2x. Suppose y is of the order 3x for example x=2 and y=6. In that case according to your hypothesis n should be (2+6)/2= 4 But n% x= 4%2= 0 and y%n= 6% 4=2 Hope that helps you to realize what (x+y)/2 will not work every time :)
 » Seems like the solution of maths question paper.
 » 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
•  » » 7 months ago, # ^ | ← Rev. 2 →   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.
•  » » It may be a dumb question but I don't see why it's ok to stop when $t[j]$ is not changed.
•  » » » 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.
•  » » » » 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.
•  » » 7 months ago, # ^ | ← Rev. 2 →   That's a nice solution, imo nicer than the editorial.
•  » » I think an important point you didn't mention is that the value of t[j] is non-decreasing for increasing i
 » 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
 » Any intuition behind div2 D in the second part where y >= x
 » Thank youu, nice contest and nice editorial
 » 7 months ago, # | ← Rev. 2 →   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$, ...
•  » » 7 months ago, # ^ | ← Rev. 4 →   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!
•  » » » 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.
•  » » » » 7 months ago, # ^ | ← Rev. 4 →   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!
•  » » » » » Consider the $[t^n]$ of two sides of the equation, then it gives a recurrence of $[t^n]F$.
 » Can someone please explain this part of problem B editorial: If XOR is 0, then there will be an even number of bi’s such that its last bit is 1. But then the sum will be even. But here the sum n is odd, which produces a contradiction.I didn't understand the part that talks about the last bit.Thanks.
 » 7 months ago, # | ← Rev. 3 →   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.
 » Do you dream to make it mathForce?
 » 7 months ago, # | ← Rev. 2 →   Really Mathforces.
 » Div2 D can be solved by elementary maths. If y>=x then, If n%x = r means n=a*x+r. y%n should also be r, so y=a*x+2r, so that (a*x+2r)%(a*x+r)=r. This way n%x=y%n=r. Now a=y/x and r=(y%x)/2, since y=a*x+2r. If y
 »
 » He loves number 69 very much.
 » The key idea for Div2C: Any number can have at least one element that is not a factor of that element between 2 and 23 under the given constraints that a[I] does not exceed 1e9. It is because LCM(2,... 23)>1e9. So checking the first 23 elements are enough. Therefore, the time complexity is O(23 * 23) in the worst case.
 » I don't know why the number 69 exists in each problems test case. In Div2.D there is 420 also. youKnowWho might love those two numbers. 69 & 420
 » can anyone plz check my code for c and tell tc in which it fails i tried it with factorial uptil 21 dividing it was failing in 9422th token of pretest 2 plz tell i am confuse =d thnx in advance
 » Shit Contest. Only Maths. For dumb people like me how I will able to solve such questions.
 » Perhaps the editorial for Div1 D,E are the clearest ones I've ever seen.The problems are truly nice.
 » 7 months ago, # | ← Rev. 3 →   Can someone please explain the multiplication of i in E/div2 ? ans += 1LL * (split - 1) * y * i; , We need to make (split-1) times on current element a[i]. After which it will be st, now the number of times we need to make it is when i+1 element is x, which is y.Now this counts up for number of times we make the split, why we multiply it by i ? UPD : this will be considered for each of prefix. hence we multiply by i.
 » There is a mistake in the Proof of the observation 3 in problem E. Perhaps the author mistook i as j:(
•  » » You are right. I will update asap.
 » Congratulations for being the top contributor.
 » woo, the author's just got so crazy at sqrt that it appears at the overall complexities of three adjacent problems!
 » The Editorial of Div1E is really detailed and easy-understanding.Thank you!
 » 7 months ago, # | ← Rev. 2 →   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 ?
•  » » You have modified the value of x before your assert function.
 » 7 months ago, # | ← Rev. 2 →   The idea of using the axis to find the solution n is great! (This congruence equation :n modx=ymod n would be more difficult to solve if computed algebraically).
•  » » thank you to the author!
 » 7 months ago, # | ← Rev. 2 →   For 1603C - 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.
•  » » 7 months ago, # ^ | ← Rev. 2 →   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.)
 » 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.
 » 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?
•  » » 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?
•  » » » Oh I see now. Thanks!
 » 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.
 » 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
•  » » It is indeed correct.
 » 7 months ago, # | ← Rev. 2 →   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)$.
•  » » I agree.
 » 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
 » 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?
•  » » 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.
 » @YouKnowWho thanks for writing long — detailed editorial as they are helpful for beginners and strugglers Thanks
 » 1D and 1E was so great! I really like it.
 » can any one tell me why my code fail in test 2 [https://ideone.com/9wIQ4F] problem c div2
 » 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.
 » in problem Moderate Modular Mode the editorial shows the answer is y− (y mod x)/2 but I haven't understood why this answer is always correct and how we reached this solution can anyone explain pls ?.
 » why (X+Y)/2 doesn't work for X
 » 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$.
 » 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
 » 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.