### rui_er's blog

By rui_er, history, 4 months ago,

1972A - Contest Proposal

Hint 1
Tutorial
Solution

1972B - Coin Games

Hint 1
Hint 2
Tutorial
Solution

1967A - Permutation Counting

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967B1 - Reverse Card (Easy Version)

Hint 1
Hint 2
Tutorial
Solution

1967B2 - Reverse Card (Hard Version)

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967C - Fenwick Tree

Hint 1
Hint 2
Tutorial
Solution

1967D - Long Way to be Non-decreasing

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967E1 - Again Counting Arrays (Easy Version)

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1967E2 - Again Counting Arrays (Hard Version)

Thanks A_G for discovering that E2 is possible!

Hint 1
Hint 2
Tutorial
Solution

1967F - Next and Prev

Hint 1
Hint 2
Hint 3
Tutorial
Solution
• +113

 » 4 months ago, # | ← Rev. 2 →   +111 too math, downvoted...
•  » » 4 months ago, # ^ |   +163 I thought the problem was cool
•  » » 4 months ago, # ^ |   +141 not enough persistent segment tree...
•  » » 4 months ago, # ^ | ← Rev. 2 →   +12 it is mid night here and i had to do mAtHs
 » 4 months ago, # |   +28 Auto comment: topic has been updated by rui_er (previous revision, new revision, compare).
 » 4 months ago, # |   +57 I don't think that this round deserves hate. div2A-D2 were all good. I say that as someone stuck on D2 for almost 2 hours. My final submission was rejected because of strict limits. However, the trick $p^2 < n$ can compensate for it. I find it fascinating, and I am glad to have seen it. The model code is much simpler than mine.The downside is that all problems (the ones I attempted) had the same (math) tag. But, it is a common trend nowadays. We cannot do anything about it, so cope.
•  » » 4 months ago, # ^ |   +25 it had some very nice problems, definitely
 » 4 months ago, # | ← Rev. 2 →   +21 Well, here is the main contribution list of the writers. A：idea by rui_er, prepared by rui_er B：idea by rui_er, prepared by rui_er C：idea by yinhy09, developed by TheScrasse, prepared by N_z__, wyrqwq D1 & D2：idea by wyrqwq, developed by N_z__, TheScrasse (UPD : newb_programmer), prepared by N_z__ E：idea by rui_er, prepared by rui_er F：idea by wyrqwq, developed by N_z__, prepared by wyrqwq, N_z__ G1 & G2：idea by wyrqwq, developed by A_G, prepared by wyrqwq, N_z__ H：idea by N_z__, developed by negative1, prepared by N_z__ Please feel free to tell us which is you favourite problem and why, and even the problems you dislike too. Meanwhile, I would also like to thank our hard-working coordinator and testers. They together made it possible for us to hold this round.If there is a chance, we hope to meet again with better problems.
•  » » 4 months ago, # ^ |   +70 D1 is not mine, it was accidentally invented by the tester newb_programmer while he was solving D2.
•  » » 4 months ago, # ^ |   +3 I liked 2F/1D. Too hard for me to solve during round but solution nicely unfolds in several steps
•  » » 4 months ago, # ^ | ← Rev. 2 →   +10 2F/1D is really cool. I would have been annoyed if hint 2 was the intended solution. Btw typo in editorialIf it is possible for ai=w after k steps, w←w+1; Otherwise, i←i+1. If i gets to n+1 first, it's valid. If w gets to m+1 first, it's invalid.Here, w←w+1 and i←i+1 are at incorrect positions.
•  » » 3 months ago, # ^ |   -8 orzorzorz
 » 4 months ago, # | ← Rev. 2 →   -8 can anyone explain, why my code is WA on test 7 (problem B) #include "bits/stdc++.h" #define int long long signed main() { int tt; scanf("%lld", &tt); while (tt--) { int n; scanf("%lld", &n); char c[n]; scanf("%s", &c); std::string s(c); int cntU = std::count(s.begin(), s.end(), 'U'); if (cntU % 2 == 1) printf("YES\n"); else printf("NO\n"); } } 
•  » » 4 months ago, # ^ |   -8 Inadequate char array length.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 Thanks!
•  » » » 4 months ago, # ^ |   0 but why? its size is n
•  » » » » 4 months ago, # ^ |   0 You need a \0 (which is $0$ if you convert it to int) to tell the language that a C-type string ends here. So you'll need extra space.
•  » » » » » 4 months ago, # ^ |   +6 ok thanks! i will never use char[], scanf, printf
•  » » » » » » 4 months ago, # ^ |   +8 That's a bit of an overreaction, isn't it?
•  » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 I only used this for three days
 » 4 months ago, # |   0 Whoa did not expect the solution to B would be so simple
 » 4 months ago, # |   -8 is it possible to solve 2C/1A using Priority Queue? Not in $O(k)$. I din't think of binary search and now my Pupil is on the line :sob:
•  » » 4 months ago, # ^ |   -8 I've tried, but its making solution too much complex bcz of such input: 1 1 1 2 2 2 3 3 3
•  » » 4 months ago, # ^ |   0 Here 258928208
•  » » » 4 months ago, # ^ |   0 can you explain please?
•  » » » » 4 months ago, # ^ |   0 Here curr is storing the minimum value all the elements can reach and rem stores the remaining operations after that minimum value is reached. Every element in priority queue I am comparing with previously reached value and calculating whether it possible to reach next top of priority queue value with remaining k.
 » 4 months ago, # | ← Rev. 2 →   0 Too much time wasted for proving the solution of B
•  » » 4 months ago, # ^ |   0 but how did you prove it? that Alice wins if the number of U's have to be odd.
•  » » » 4 months ago, # ^ |   0 At every turn, the parity of the total number of 'U' cards flips. This is because once we flip a 'U' card, the number of 'U' cards decreases by 1. Now since it has two neighbours , it will be either a). DD -> UU b). UU -> DD c). UD -> DUEither the number of U increases by 2, decreases by 2 or remains same. Since we already discarded a U card, the parity always flips. Also since the maximum number of U can be the current size of the string, we can guarantee the game will end at most after n turns. The winner of the game is the person who gets the string with only 1 U left. So we can conclude that whoever starts with odd number of U's will be the one who will get to the state where there is 1 U left, and hence will win the game.
•  » » » » 4 months ago, # ^ |   +3 Thanks a lot for the explanation!
•  » » » » 3 months ago, # ^ |   0 Hey, I understand that the parity of the number of $U$'s always changes but that does not provide any rigorous proof that if the number of $U$'s is odd then Alice wins. I struggled a bit to provide more rigorous proof for this thing.(Proof by induction does not work since the number of $U$'s can increase).I think the main observation is that the number of $U$'s is bounded by the length of the string $n$. That means that there is a point in time where the number of $U$'s always decreases and can't increase any more.If you consider the number of $U$'s throughout operations it might look like this:  3 -> 4 -> 5 -> 2 -> 3 -> 4 -> ... -> some bound -> start decreasing till 1 I would assume that the proof would work for any number of increase/decrease values as long as the parity always flips, there is an upper bound and the game will always end.
•  » » » » » 3 months ago, # ^ |   0 The game always ends in at most $n$ moves and Alice can always make a move since the number of coins facing up is odd, so nonzero, which means that the game must end on Bob's turn.
•  » » » » 2 months ago, # ^ |   0 Nice explanation. I write too complex code for this problem
•  » » 3 months ago, # ^ |   -8 Yeah,Mathematical problems are difficult to prove.I hate math.
 » 4 months ago, # |   0 weak pt. I just wrote the limit as the correct limit -1.
•  » » 4 months ago, # ^ |   0 then I fst at 1A
•  » » 4 months ago, # ^ |   0 me too. I set the limit of binary search to 1e18 and it overflowed.
 » 4 months ago, # |   +3 Could solve all the way to the problem D2. My math knowledge was useful in both task D1 & D2, however, mathforces.
 » 4 months ago, # |   0 Editorial is Little bit confusing for me.Please can anyone verify that following approach was correct?1)sort array use binary search, to make all all element atleast equal to X This x will have range from min of array to max+k of array..2)then ..make arrangement,1->n in this cycle and calculate the answer...using this x
•  » » 4 months ago, # ^ |   +3 You don't need binary search if you already sorted array. Find $fulls$ = number full permutations (bin search or sort + prefix sum) $r$ = remaining k add $a_i > fulls$ (and purchase $r$ distinct $a_i <= fulls$) at any end of full permutations to form additional permutations of $1..n$. 258906139
•  » » » 4 months ago, # ^ |   0 I used binary search on k, I sorted array just ,
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 how will you arrange for this test case 2 3 2 how will you add the extra 2 ?
 » 4 months ago, # | ← Rev. 2 →   +8 in div2D1 you do not have to count using math, you can naively run a for loop. The time complexity will be still $\mathcal{O}(n+m)$ for each test case. This is because, for each value of $m$ the loop will take $\mathcal{O}(\frac{n}{k^2})$ time, and $\sum_{k=1}^\infty{1/{k^2}}$ converges to $\pi^2/6$.
•  » » 4 months ago, # ^ |   +9 We can also notice that $a$ must be a multiple of $b$ and iterate $b$ from $1,2,..m$ and $a$ from $b,2b,...n$, then it turns into $O(n\log{n})$.
•  » » » 4 months ago, # ^ |   0 Unfortunately couldn't make the same trick work for Div2D2, do you have any idea how?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 My solution for D2 uses same trick 258920365. Though it is O(n log^3(n))
•  » » » » » 4 months ago, # ^ |   0 Cool that it fits in time
•  » » » » » » 4 months ago, # ^ |   0 Well, i am sure that it is less than O( nlog^3 n), but i don't know what it is exactly.
•  » » » » » 3 months ago, # ^ |   0 Can you elaborate on your approach?
•  » » » » » » 3 months ago, # ^ | ← Rev. 3 →   +1 Consider $g = gcd(a, b)$, than $(a + b) | b \cdot g$ is equivalent to $k \cdot (a + b) = b\cdot g$ (for some $k$). Let $a_0 = \frac{a}{g}$, $b_0 = \frac{b}{g}:$ $\newline k \cdot a_0 \cdot g + k \cdot b_0 \cdot g = b_0 \cdot g^2$ Then dividing by $b:$ $\frac{k \cdot a_0}{b_0} + k = g$Notice that $gcd(a_0, b_0) = 1$, but $\frac{k \cdot a_0}{b_0}$ is some integer, thus $b_0|k$. In other words $k = b_0 \cdot c$ (for some $c$).So we get $c \cdot a_0 + c \cdot b_0 = g$, it means that $c|g$. Also $g|b$. Having $c, g, b$ we can get $a, a_0$. So I used that trick to iterate over every triple $(c, g, b)$(Also you need to check that $gcd(a_0, b_0) = 1$)And a bit of optimization: notice that $b < \frac{g^2}{c}$ (otherwise $a$ won't be positive).
•  » » » » » » » 3 months ago, # ^ |   0 Thanks. I wasn't thinking about $k=b0⋅c$. So I didn't solve this problem.
•  » » » 4 months ago, # ^ |   0 can you explain me why a must be a multiple of b?
•  » » » » 4 months ago, # ^ |   0 in div2.D1 b.gcd(a,b) divides (a+b) hence b divides (a+b) , => (a+b) = k.b Then a = (k-1).b , this means b divides a
•  » » » » » 4 months ago, # ^ |   0 this is so easy man, now I got it.
•  » » 2 weeks ago, # ^ |   0 Could you please explain why can we use step $k^2$ for the inner loop?
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Check the editorial for necessary conditions of a valid pair. My solution is just about omitting some math from it.
•  » » » » 2 weeks ago, # ^ |   0 Now I got it, thank you! I thought your solution was not using math at all :)
•  » » 5 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } If someone asked why $\displaystyle \sum_{k=1}^{\infty} \frac{1}{k^2} \text{ converges to } \frac{\pi^2}{6}(C)$We can use integration test to determine whether $f(k)$ converges or diverges .. $\displaystyle \int_0^\infty \frac{dk}{k^2}=1$Thus you can estimate the value of convergence and you'll get the $\displaystyle C\approx 1.64$.
 » 4 months ago, # |   0 My O(n log^3 n) solution has passed the Div1B2, can anyone hack it or give a tighter complexity?258888693
•  » » 4 months ago, # ^ |   +11 your complexity is $O(answer * log(n))$ :) max answer is $11680996$
•  » » » 4 months ago, # ^ |   0 Thanks.Is this explaination correct? "For most cases, gcd(u,i-u)=1, so we can assume the enumeration quantities approximate to the answer."
 » 4 months ago, # |   -10 Nice maths training contest
 » 4 months ago, # | ← Rev. 2 →   0 Can anyone give me the reason why this got signed integer overflow 258927405. I have checked the code it and it is correct for other ranges,but fails here.
•  » » 4 months ago, # ^ |   0 mid=1e17, and k-=mid*n.
•  » » » 4 months ago, # ^ |   0 Thanks i got it ,k can get too much negative to handle more subtraction
•  » » » 4 months ago, # ^ |   0 but how can i fix this?
•  » » » » 4 months ago, # ^ |   0 break when k<0
 » 4 months ago, # | ← Rev. 2 →   +34 As far as I'm concerned, E is a bit classical and similar to CF837F.Thanks anyway to this round that made me GM.
 » 4 months ago, # | ← Rev. 2 →   0 A different solution to div1. A, div2. C using binary search.The answer is completely binary searchable and there isn't anything wrong with it, but it doesn't match my intuition. Let binary search on the number of Full permutations you create, we can handle the remaining part manually with an O(n), in binary search, let's check if we can have $x$ full permutations created, to check it we can just calculate the need for that much permutation for each item and see if have more or less if we had less we just add the mid - a[i] to the want variable, it's just the matter to check if want <= k.Obviously, l is the answer, so you know that you can create n*(l-1) + 1 full permutations, (for x permutations, we need $n+x-1$ elements).Now let's handle the remaining value. we manually loop through all the elements and if any element had anything less than l, we just add that to the want variable, otherwise the number of permutations you can create gets increased by one(reader's exercise: Why? ).the code: 258927507
•  » » 4 months ago, # ^ |   0 Had the exact same idea ... dont know where it went wrong ... help
•  » » » 4 months ago, # ^ |   0 I think the issue with your code is that the initial high value is very high and may lead to overflow (I'm not certain how because I don't use C++ that often). If you change it to 1e13, it works just fine.
•  » » » » 4 months ago, # ^ |   0 It was (mid-a[i]) so it overflowed ... Damn I am stupid
•  » » 4 months ago, # ^ |   0 Please tell me how the number of permutations is increased by one if any element is more than k pls. if k=0 and you have 2 3 2 where will you add the extra two
•  » » » 4 months ago, # ^ |   0 think about how you set up the first permutation if you have some extra from one
•  » » » » 3 months ago, # ^ |   0 can you give a bit more hint about the construction of the answer? I am still not able to fully understand how it will always increase the number permutations by one
•  » » » 3 months ago, # ^ |   0 Oh I just noticed I miss typed in the original commentBy k I meant L sorry
•  » » » 3 months ago, # ^ |   0 2 3 1 2
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 1 2 3 2 1 2 3in between!
 » 4 months ago, # |   -35
 » 4 months ago, # |   +8 OMG D2...I got: a = dp >= (p + q)p b = dq >= (p + q)qSo, I decided to sum up them and get: a + b >= (p + q)^2Nice contest though
 » 4 months ago, # |   +54 Loved the round, thank you! The best moment of the contest for me was when I started coding Persistent Segment Tree in Div.1 D (it wouldn't have worked probably) and realized that there's a cute solution with much less code! Though E1 looks like a pretty standart problem to be honest...
 » 4 months ago, # |   0
 » 4 months ago, # |   0 For 1972C - Permutation Counting, I first misread the problem as to find the maximum possible answer for any $m \le n$, where the subarrays form permutations of $[1,m]$. 258892957I'm not sure if that was the right approach for the misread verison, but after realizing my mistake, simply disabling the outer loop to handle only $m=n$ case made it AC. 258896138Would've been great for me if the problem was actually about the misread one :)
 » 4 months ago, # |   +10 Very good math problems and fast editorial. Thanks!
 » 4 months ago, # |   0 I am a newbie and I intend to reach to pupil quickly.What resources should I follow to reach it and I really feel annoyed with questions like B that was asked today.I tend to spend a lot of time on such problems and many a times contest gets ended and I am unable to come up with solution.Please guide me
•  » » 4 months ago, # ^ |   0 Take a look at the codeforces catalog. There people much smarter than me have posted the exact thing you are looking for.From resources to guides on how to improve and tutorials on specific topics and even stuff on mindset and attitude.https://mirror.codeforces.com/catalog
 » 4 months ago, # | ← Rev. 4 →   +55 I like Div1E, thanks, though I couldn't make it on time...(QAQ) Here is my solution.We can rephrase the problem as a random walk: The states are $-1, 0, \ldots, m-1, m$. Start at $b_0$. States $-1$ and $m$ are absorbing. From states $0, \ldots, m$, decrement with probability $1/m$, increment otherwise. Let $z_i$ be the probability that it does not end up at $i$ after $n$ steps. The answer is $m^n (1 - z_{-1})$. If we had infinite number of steps instead of $n$, the problem would be classical. Let $f_i$ be the probability that, starting from $i$, it is eventually absorbed at $-1$ after infinite number of steps. We have $f_{b_0} = z_{-1} + \sum_{0\le i\le m-1} z_i f_i$. It is known that $f_i = \dfrac{(m-1)^{m-i}-1}{(m-1)^{m+1}-1}$ for $m \ne 2$ and $f_i = \dfrac{m-i}{m+1}$ for $m = 2$. (Caveat: What if $998244353$ divides the denominator? It turns out no such case exists within the constraints, luckily.)To compute $z_i$ for $0 \le i \le m-1$, we can reduce it to certain path counting and use reflection method as in the editorial. It takes $O(n/m)$ time for each $i$, thus $O(n)$ overall. (Caveat: The sum of $m$ is not bounded! We should do this only for $b_0-n \le i \le b_0+n$.)
 » 4 months ago, # | ← Rev. 2 →   +47 Lol, I thought about the model solution to E1, but also thought "Huh? quite weird $O(min(nm, \frac{n^2}{m})$ tradeoff solution with a ton of detailed math? I'm not coding that for 1750 points! There must be some much slicker way to do this!" and that turned out to be exactly the intended solution xD... But I managed to get D instead and I wouldn't be able to do both anyway
•  » » 4 months ago, # ^ |   0 I wish I could become as good as you to even come up with that complexity of the problem.
 » 4 months ago, # |   0 Could anyone explain the output of this test case for the div2C problem?10 91 9 1 2 1 5 7 5 3 3 The answer is 27 but I am only getting 26 as max.[6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10]
•  » » 4 months ago, # ^ |   +1 Here is an optimal solution for that test case Buy 3 cards of the first and third ones Buy one card for the fourth one Buy two cards for the fifth one then you can arrange them as follows and get 27 as the maximum score: 1 2 3 6 7 8 4 5 9 10 1 2 3 6 7 8 4 5 9 10 1 2 3 6 7 8 4 5 9 10 1 2 3 6 7 8 
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Can you please explain why this case has answer 3? I can only simulate the answer is maximum 2, no matter how much I try. Thank you. 16 01 2 1 2 1 1
•  » » » » 3 months ago, # ^ |   0 You can arrange them like this: 2 4 1 3 5 6 2 4 then you get [1, 6], [2, 7], [3, 8] as valid subarrays
•  » » » » » 3 months ago, # ^ |   +1 Thank you so much, brother.
 » 4 months ago, # |   +8 I have made detailed video explanations for C and D1 Question Here are the links for anyone who wishes to watch
•  » » 4 months ago, # ^ |   0 Why didn't you mention in the comment that it's not in English? To gain some unintended view?
•  » » » 4 months ago, # ^ |   +1 Will make english versions as well next time Sorry for the incovininence
•  » » 3 months ago, # ^ |   -8 Why did you write I have made detailed video explanations for C and D1 Question Here are the links for anyone who wishes to watch instead of मैंने सी और डी1 प्रश्न के लिए विस्तृत वीडियो स्पष्टीकरण बनाया है, जो कोई भी देखना चाहता है उसके लिए यहां लिंक हैं?What drove your decision to advertise the videos in english? =)
 » 4 months ago, # |   0 can anyone help me finding what's wrong with this approach in 2/C
•  » » 4 months ago, # ^ |   +1 Inside the binary search, you can break when tmp < 0 (clearly). Turns out, you "must" break otherwise some negative integer overflow will occur and unintentionally make tmp positive even though it should DEFINITELY be negative once tmp < 0 occurred. I got AC on your submission with this change. 258943287
•  » » » 4 months ago, # ^ |   0 yeah i just found the problem with my code
•  » » 4 months ago, # ^ |   0 NVM it was actually signed integer overflow! :(
 » 4 months ago, # |   +13 We can also solve Div1C in $O(n \log^{2} n )$ by maintaining the generating function $g_{i}(x)$ for every position $1 \leq i \leq n$, where $[x^{n}]g_{i}(x)$ denotes the value of $f^{n}(a)[i]$ where $a$ is the array we are trying to find and $f$ is the "fenwick function" from the statement. We maintain it by processing $i$'s in the ascending order of their lowest bit and summing up the generating functions. The result can be extracted as $a[i] = [x^{k}]g_{i}(x)$.
 » 4 months ago, # | ← Rev. 2 →   +46 I enjoyed div1C a lot, thank you! I came up with a solution different than the one mentioned in the editorial (using matrices). SolutionSuppose we are currently at index $i$ and we know its value, we have to calculate its contribution to other values that follow it (there are at most $\log_2(n)$ values). Let's arrange values from smallest index to largest index, assuming they're $a, b, c, d,$($a$ $is$ $val_i), \cdots$, then we will do the following $k$ times: $a = a$ $b = a + b$ $c = a + b + c$ $d = a + b + c + d$and so on. As we see, it's easy to calculate using matrices with $O$( $log(n)^3$ $log(k))$ time.So the total complexity is $O(nlog(n)$ $+$ $log(n)^3 log(k))$ time.And here is my submission : 258943002
•  » » 4 months ago, # ^ |   +5 If i understood correctly, your solution is actually the same as the editorial solution, because if im not mistaken, the part that you calculate with matrices is exactly the same binomial coefficient mentioned in the editorial(if we solve the equations that you mentioned, to get an explicit formula).
•  » » » 4 months ago, # ^ |   +16 Yeah, that's right. But the good thing is that I don't have to solve any equation. Just let matrices do it!
•  » » » » 4 months ago, # ^ |   +5 Yup, I agree.
 » 4 months ago, # |   0 I still need to practice,my math is very poor...
 » 4 months ago, # |   +1 How to find more problems like B which require you to make a very minute observation like it was parity of number of 'U's removed here for every possible type of move, at times it is first and last element....Is there any way of improving in such problems which don't follow of flow of logic and just break as soon as we make an observation ... ?I was able to solve D1 and C both but couldn't come up with B and it happens quite a lot ..
 » 4 months ago, # |   +55 A brutal solution for 1C: Let $T$ be the linear operator that does the "Fenwick tree" transform, one can verify that $(T-I)^{k}=0$ for $k = \log n$. So to solve the equation $T^m v = a$, just compute the coefficient of $x^{-m} \bmod (x-1) = \sum_{i •  » » 4 months ago, # ^ | 0 I'm eager to grasp your solution; could you recommend any prerequisite resources to aid my understanding? Thanks in advance. •  » » » 3 months ago, # ^ | +5 Solution này dùng ma trận của ánh xạ tuyến tính á. Nếu bạn học Đại Số Tuyến Tính ở chương trình ĐH rồi thì sẽ biết cách dùng này. •  » » » » 3 months ago, # ^ | 0 cam on bro •  » » 3 months ago, # ^ | 0 Just a minor typo, the mod should be$(x-1)^k$, not$(x -1)$, right? •  » » » 3 months ago, # ^ | 0 Yes, thanks for pointing that out •  » » 3 months ago, # ^ | ← Rev. 3 → 0 I have yet to understand why the linear operator$T$, which is a$n\times n$matrix, can be applied to a vector in linear time? That is, when we multiply a$n\times n$matrix with$n\times 1$matrix, the time complexity should be$O(n^2)$, right? Or have I left out something important? •  » » » 3 months ago, # ^ | +1 I mean for the specific$T$in this problem, it holds •  » » » » 3 months ago, # ^ | ← Rev. 2 → 0 Thank you very much. This problem is hard, even when you have a good understanding of Linear Algebra and found that$(T-I)^n = 0$due to the Cayley-Hamilton theorem, that will just not enough, let alone proving that$T-I$is nilpotent. You need to find the nilpotent degree of$T-I$, that is the smallest value of k such that$(T-I)^k = 0$and come up with$k \leq \log n$is not that easy at all. Also an inexperienced coder like me can stumbled on my dumb question above :))) •  » » 3 months ago, # ^ | ← Rev. 2 → 0 After reading your solution, I had difficulty in computing coefficient$c_i$so I have changed my approach to the following:Instead of computing$c_i$, I used Taylor Series here:$ \begin{aligned} x^{-m}&= 1 + -\frac{m}{1!}(x-1) + \frac{m(m+1)}{2!}(x-1)^2+\ldots\\&\equiv 1 + -\frac{m}{1!}(x-1) + \ldots +(-1)^{k-1}\frac{m(m+1)\ldots(m+k-2)}{(k-1)!}(x-1)^{k-1} \mod (x-1)^k \end{aligned} $So we have$ T^{-m} = 1 + -\displaystyle\frac{m}{1!}(T-I) + \ldots +(-1)^{k-1}\frac{m(m+1)\ldots(m+k-2)}{(k-1)!}(T-I)^{k-1}. $We can set$k=20$because$\log n \leq 20$. But if$m$is large, then it's likely that we will get integer overflow even when using long long because the last coefficient can be up to$\displaystyle\frac{(10^9)^{20}}{20!}$. So we have to compute these coefficient according to their modulo. That triggers another problem, we have to compute the inverse of$i$modulo$998244353$for all$i=\overline{1,19}$, since$998244353$is a prime number, we can write a program to get all of them easily, that is // inverse[i] is the number x that x*i equiv 1 mod 998244353 vector inverse = {0 ,1, 499122177, 332748118, 748683265, 598946612, 166374059, 855638017, 873463809, 443664157, 299473306, 272248460, 582309206, 460728163, 926941185, 865145106, 935854081, 939524097, 720954255, 105078353}; And I got accepted. Here is my solution259730338  » 4 months ago, # | 0 TOOOOOO much math... But the problem attached seem good imo Ive also stuck at D1/D2 almost 2h, Im not good at algebra... Each problem was so coooool but the set was tooooooo biased... •  » » 4 months ago, # ^ | 0 I managed to do both D1 and D2 from first using brute force on a smaller number and then finding a pattern to optimize it. •  » » » 3 months ago, # ^ | 0 Yes I've tried to do as similar method. Maybe I almost reached to answer but failed to implement it due to limited time :( my skill issue lmao  » 4 months ago, # | 0 what is | in D1 and D2 stand for? •  » » 4 months ago, # ^ | ← Rev. 2 → +1 | means "divides"  a|b reads as "a divides b"   » 4 months ago, # | +25 It seems that there are many alternative solutions to E2. Looking through the submissions, here are some that I don't understand (and they look quite different from the editorial):jiangly maroonrk maspy potato167 Would any of you mind explaining how your solution works? :) •  » » 4 months ago, # ^ | ← Rev. 2 → +28 Let$path_{[0,M)}(b,i)$denote the number of Dyck path from$(0,b)$to$(i,0)$, which lies within the range$0 \leq y < M$. Then, we need to compute$\sum_i f[i] \cdot path_{[0,M)}(b,i)$for some coefficients$f[i]$.By the reflection principle,$path_{[0,M)}(b,i)$can be represented as$\sum_{b'} (\pm 1) \cdot path(b',i)$, where$path(b',i)$has no restriction to the range of$y$.Therefore, we need to compute$\sum_b (0 \text{ or } \pm 1) \cdot \sum_i f_i \cdot path(b,i)$. So, the problem is reduced to computing$\sum_i f_i \cdot path(b,i)$for each$b$. In other words, computing the composition$\sum f_i(x+x^{-1})^i = f(x+x^{-1})$.In this case, we can show that$f_i$forms a geometric sequence (from$b_0$to$N-1$), and$f(x)$takes the form of$(\text{a sparse polynomial of degree N+1}) / 1-rx^2$. Therefore,$x^{N-1}f(x+x^{-1})$is a polynomial of degree$2N+2$divided by a polynomial of degree$4$, and this can be computed in$O(N)$time.By the way, the composition$f(x+x^{-1})$can be computed in$O(N\log N)$time (https://mirror.codeforces.com/blog/entry/126124). I studied it today. •  » » 3 months ago, # ^ | 0 My solution is almost the same as maspy's solution. The only difference is the way to compute$g_b=\sum_{i} f_i \cdot path(b,i)$. I didn't use polynomial things and directly calculated the recurrence relations for$g_b$by considering paths. •  » » » 3 months ago, # ^ | +3 I didn't use polynomial things and directly calculated the recurrence relations for ... Would you mind elaborating? •  » » » » 3 months ago, # ^ | +21 Let$g_b=\sum_{0 \leq x, 0 \leq y, x+y \leq K, x-y=b} w^{x+y} {x+y \choose x}$. Then consider$g_b-w(g_{b+1}+g_{b-1})$. It can be calculated in$O(1)$time.  » 4 months ago, # | -8 Can anyone explain more clearly the solution of problem E div1? I do not really understand.  » 4 months ago, # | +4 Update rank too late !  » 4 months ago, # | +3 The solution of 2D2/1B2 is pretty amazing: I couldn't believe that we can delete q of$(p+q)\mid qd$in such an easy proof!All in all, I think this contest is better than my last contest Educational Codeforces Round 141 (Rated for Div. 2). Thinking deeply should be the biggest feature of codeforces, that's why I prefer this round. Though in mathforces, a high quality contest is needy. •  » » 4 months ago, # ^ | 0 Can you please explain how we get p •  » » » 4 months ago, # ^ | ← Rev. 2 → +1 It is show in editorial that gcd(p+q, q) = 1. Therefore (p+q)%d == 0. (p+q)%d = 0; p+q = (x*d) we get min value of p+q at x = 1. p+q >= d we know, p >= 1 && q >= 1. Therefore, p < d  •  » » » » 4 months ago, # ^ | +3 Thank you! •  » » 3 months ago, # ^ | 0 Can you please explain the deletion part? •  » » » 3 months ago, # ^ | 0 k=gcd(a,b) p=a/k,q=b/k -> gcd(p,q)=1gcd(p+q,q)=gcd((p+q)-q,q)=gcd(p,q)=1so q is useless in this fraction, and you can delete it.  » 4 months ago, # | 0 Enumerate$i$from$1$to$n$. Enumerate$a_i = w$for$w$from$1$to$m$. If it is possible for$a_i = w$after$k$steps,$w \gets w + 1$; Otherwise,$i \gets i + 1$. If$i$gets to$n + 1$first, it's valid. If$w$gets to$m + 1$first, it's invalid. Should it be "If it is possible for$a_i = w$after$k$steps,$i \gets i + 1$.; Otherwise,$w \gets w + 1$"? •  » » 4 months ago, # ^ | 0 I think so  » 4 months ago, # | 0 C is one of the best and most satisfying problems I've ever seen, and D1 and D2 were also really nice as well. Thanks to authors for making a great contest! •  » » 4 months ago, # ^ | 0 C is good but C's pretest is one of the worst pretest ever.  » 4 months ago, # | 0 can someone tell the time complexity of the code used for calculating if a pair is coprime in the solution of div-2 d2. •  » » 4 months ago, # ^ | +3 Seems to be$O(\frac{\sqrt{n} }{2} \cdot \frac{\sqrt{m} }{2} +\frac{\sqrt{n} }{3} \cdot \frac{\sqrt{m} }{3}+\frac{\sqrt{n} }{4} \cdot \frac{\sqrt{m} }{4}+\cdots)=O(\sqrt{nm}\cdot \sum _{i=2}\frac{1}{i^2})=O(\sqrt{nm}\cdot (\frac{\pi ^2}{6} -1))= O(\sqrt{nm} ) $Anyway, after contest I just tried add an extra judgement of if (gcd(a, b) == 1), and it didn't raise the time complexity too much and got AC as well.  » 4 months ago, # | 0 I don't understand the DIV 2 C tutorial at all. Is it just me?  » 4 months ago, # | -30 I cannot understand why so many people upvoted the annoucement and editorial.  » 4 months ago, # | 0 Can someone please explain div2 C. I was able to figure out that we need to binary search for the number of full segments of [1..n] and answer would be at-least n*(full-1) + 1. But how to handle the remaining elements which can be appended to the prefix and suffix of these full segments. •  » » 4 months ago, # ^ | 0 So once you have got the number of full segments let them be=temp. Now, traverse the input array and make all elements (which are less than temp) equal to temp. and reduce k accordingly. Now if still k>0 then traverse array again and increase all elements equal to temp by 1(why 1? because greedily we just want more no. of elements greater than temp). let no. of elements to be added be num=0. And finally traverse array again and if a[i]>temp do num++. seems a bit complicated lol but you can go through the code 258983345  » 4 months ago, # | 0 I did brute force , and it worked for D1 , i just checked for each a and b , checked their gcd and put it in the formula , just kept increasing a by b in each iteration , that made the complexity (b)*(a/b) which is a , and it worked, didnt understand the answer given here tho :/ my submission link : https://mirror.codeforces.com/contest/1972/submission/258899009  » 4 months ago, # | 0 in problem 2D2/1B2, how$gcd(p + q, q) = gcd(p, q) = 1$helps in droping the term$q$in$(p+q) ∣ (qd)$•  » » 4 months ago, # ^ | +3 I think this is done to find the max values of p and qsince (p+q) can't divide q it doesn't contribute to find the max of p and q such that they can be used to find the solutions hence it is removed .might help  » 4 months ago, # | ← Rev. 2 → 0 We also know that p≥1,q≥1,so p •  » » 4 months ago, # ^ | 0 If p>=d, then p+q>d, then d obviously can't be a multiple of p+q. •  » » » 4 months ago, # ^ | 0 thanks! •  » » 4 months ago, # ^ | +3 div 2 D2: a=pd,b=qd, GCD(a,b)=d => GCD(p,q)=1 b*d=c(a+b) ;c=constant qdd=c(p+q)d qd=c(p+q) qd/(p+q)=c since (p+q) cant divide q as gcd(p+q,q)=gcd(p,q)=1 q(d/(p+q))=c p>=1 and q>=1 max value of (p+q) should be d in order to divide it. to get max of p , fix q to min(1) p+1<=d p<=d-1 p  » 4 months ago, # | +5 Can anyone explain why in div1C the coefficient of a_u in b_v will be the mentioned value?  » 4 months ago, # | 0 I still don't understand why 6th testcase in Div2 C is 32. I currently can only find 31 permutations. •  » » 4 months ago, # ^ | +3 Buy cards so that the array becomes 7 6 4 7 6 4 4 4 4. One of the possible sequences: 1 2 4 5 3 6 7 8 9 (repeat 4 times) 1 2 4 5. Number of permutations = 9 * 4 + 4 - 8 = 32  » 4 months ago, # | 0 oh shit! What have I done? I thought Alice would win if both the number of facing up coins and the number of total coins were odd. I submitted the code using this logic and received a penalty. Had I knew the number of facing of coins being odd is enough for Alice to win the game, it would have been accepted.  » 4 months ago, # | ← Rev. 3 → 0 My solution to 1967A — Permutation Counting using check max_element > (sum_element + k) / (number_of_elements)https://mirror.codeforces.com/contest/1967/submission/258991320  » 4 months ago, # | 0 For div 2 D1 why kd≤⌊n/d⌋+1 ?  » 4 months ago, # | 0 In question E div2 Fenwick Tree. The editorial states that it's easy to prove that the coefficient is Can someone walk me through it because I kept trying on my own and couldn't come up with it... •  » » 4 months ago, # ^ | ← Rev. 2 → +6 In the contest I try generating the fenwick tree and try to come up with the coefficient from the result 0 [100 0 0 0 0 0 0 0]1 [100 100 0 100 0 0 0 100]2 [100 200 0 300 0 0 0 400]3 [100 300 0 600 0 0 0 1000]4 [100 400 0 1000 0 0 0 2000] •  » » 3 months ago, # ^ | +7 you can get a coefficient matrix like: 1 1 1 1 1 1 1 2 3 4 5 6 1 3 6 10 15 21 1 4 10 20 35 56 ... where row_i is k, and column_j is delta_dconsider a_1 in b_1 to b_8  b: 1 2 3 4 5 6 7 8 k=0: 1 0 0 0 0 0 0 0 k=1: 1 1 0 1 0 0 0 1 k=2: 1 2 0 3 0 0 0 4 k=3: 1 3 0 6 0 0 0 10 k=4: 1 4 0 10 0 0 0 20 .... let c_u_k denote the coefficient of a_1 in b_u in f^k(a), then c_8_k = c_1_(k-1)+c_2_(k-1)+c_4_(k-1)+c_8_(k-1), note that c_4_k = c_1_(k-1)+c_2_(k-1)+c_4_(k-1), so we have c_8_k = c_4_k + c_8_(k-1), which is a classic formulate for combination number. •  » » » 3 months ago, # ^ | 0 I understand what you're saying and I actually came up with something similar:for i % 2 == 0: b(k)[i] = a[i] + b(k)[i/2] + b(k-1)[i]for i % 2 == 1: b(k)[i] = a[i]but I guess I'm a bit weak in combinatorics as I still don't know how to draw the general rule. I think I have to work on that.But thanks a lot for explaining it <3 •  » » » » 3 months ago, # ^ | +3 don't take all elements at once， take 8 for example， a_4 a_6 a_7 in b_8 are the same（ dep=1 ）， and then a2 a3 a5（ dep=2， and a2 a3 in b4 is dep=1， a5 in b6 is dep=1） ， then a1 in b8（ dep=3， a1 in b2 is dep=1， a1 in a4 is dep=2）， the rule is about dep and k •  » » » » » 3 months ago, # ^ | 0 Oooooh, I totally get it now. Thanks a lot <3Dealing with the fenwick tree as an actual tree that's a first for me, nice problem indeed.  » 4 months ago, # | ← Rev. 2 → 0 Can someone explain the problem I have? I use Code::Blocks for competitive programming and yesterday I submitted the code (258902555) with error 'out of bounds', but in Code::Blocks it worked correctly unlike system showed that there is the wrong answer on one of the tests of first pretest, so I was confused and decided to rewrite code on Python. Why didn't it show that there is the error and, moreover, worked without error and I got different answers in Code::Blocks and testing system?  » 3 months ago, # | ← Rev. 2 → 0 In the tutorial for D2 :-Can anyone please explain how we got (p+q) | d from (p+q) | qd?My understanding:b * gcd(a, b) = (a + b) * kFrom here we can say that a needs to be a multiple of b hence a = b*xSo, b * gcd(a, b) = (bx + b) * kHence as per the editorial p = x and q = 1 but then why aren't we considering q = 1 in (p+q) | d which will eventually look like (p + 1) | d? •  » » 3 months ago, # ^ | 0 p and q are co-prime if p+q|qd if there is a common divisor between p+q and q lets call it s so now we have s*x=p+q s*y=q; subtracting them we get s*(x-y)=p which means that s divides p, but s already divides q hence it is a contradiction to the fact that p and q are co prime hence there is no such divisor hence p+q|qd----> p+q|q  » 3 months ago, # | 0 can someone explain me how stars and bars is used in problem Div1 C. .  » 3 months ago, # | 0 "We know q=1 because gcd(p,q)=1." how can we say that doesnt this mean p and q both are coprimes? •  » » 3 months ago, # ^ | 0 p=(kd−1)q implies that gcd(p, q) >= q (maybe even gcd(p, q) = q), then q = gcd(p, q) = 1. If q = 2, then p = (kd — 1) * 2, so gcd(p, q) = 2.  » 3 months ago, # | 0 For 1967C — Fenwick Tree, I have a function that computes the inverse factorials under a modulo MOD, but I'm getting different values than the solution above? def factorials(n): fact, inv_fact = [1] * (n + 1), [0] * (n + 1) for i in range(2, n + 1): fact[i] = (fact[i - 1] * i) % MOD inv_fact[-1] = mod_inverse(fact[-1]) for i in reversed(range(n)): inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD return fact, inv_fact It becomes wrong after inv_fact[3] = 166374059, compared to their calculate where inv[3] = 332748118. I've used the function above for many problems, couldn't imagine it is wrong. •  » » 3 months ago, # ^ | 0 I see my mistake, you are not dividing by the inv_fact[d] everytime, and the inv[d] is actually not the inverse factorial, it is 1 / d.  » 3 months ago, # | +28 How to solve E1 using NTT? For the$dp_{i,j}$as mentioned, could understand that$dp_{i-1} \times (x^{-1}+(m-1)x^1) = dp_i$, but the transition has limit at -1 and m. Does it use "circular convolution" trick (on CDQ processing) just like this AT problem? •  » » 3 months ago, # ^ | ← Rev. 2 → +20 You may solve it using a D&C. When you need$a$transforms, the$[a,m-a]$part is easy by using a direct convolution, so you need just deal with the first$a$terms and the last$a$terms, and that's small. •  » » » 3 months ago, # ^ | 0 Can you elaborate on how to deal with first/last$a$terms? I can't figure out how to deal with it in$\tilde O(a)$time. •  » » » » 3 months ago, # ^ | ← Rev. 3 → +18 finally figure out the details.supposed that it only has the lower limit at Y=-1, and do not has the upper limit, we can use the following D&C to solve it:* supposed that we want to calculate$dp_R$, where$dp_L$has been finished (which was used as the input for$dp_R$);* let$len=R-L$, if the size of input is not greater than$len$, we just recurse it: by calculating the middle column first, and then use the middle row to calculate the right part...* otherwise$[dp_{L,len},dp_{L,sz-1}]$can do a direct convolution (add the result to the last column), and the remain part (with length not gerater than$len$) just do sth as the above.when it has lower limit Y=-1 and upper limit Y=M, we can do some similarity:* when the input size not greater than$2len$, we just rucurse it;* otherwise use$[dp_{L,len},dp_{L,sz-1-len}]$to do a direct convolution;* and the two remain parts are exactly on the situation: it has only one lower/upper limit. here is my implemention. •  » » » » » 3 months ago, # ^ | 0 Cool, I thought that algorithm can only handle the case where lower bound exist. Thank you! •  » » » » » » 3 months ago, # ^ | ← Rev. 2 → 0 I did a bit of analysis on it, and it seems such algorithm can handle counting non-decreasing path with limited degree of transition polynomial$f$(let say its degree is$|f|$) with limited adjacent difference of lower bound/upper bound (let's say$L_n, U_n$is respective lower/upper limit sequence and$max(max_{i = 2}^{n}(L_i - L_{i - 1}), max_{i = 2}^{n}(U_i - U_{i - 1})) = D$).Since after we transit the "middle part" at some$(l, r)$using direct convolution, the following called would only need to handle one bound, and this part would cost$O((n + m)\lg (n + m))$Then for the following part handle only one bound (let's say lower part, the analysis for upper is similar), when recurse from$(l, r)$to$(mid, r)$(for$(l, mid)$its degree would be no more than the$(mid, r)$part), it would have to handle a polynomial of degree$(L_r - L_l) + |f|(mid - l) \leq (r - l)(D + |f|)$and do at most one convolution on it, so this part would cost$O(n(D + |f|)\lg (n(D + |f|))\lg n)$So the complexity of this algorithm is$O(n(D + |f|)\lg (n(D + |f|))\lg n + (n + m)\lg (n + m))$. And it would be fast enough as long as$m$and$n(D + |f|)$are small enough.  » 3 months ago, # | 0 Yo guys, I am currently reading the editorial for D1. I understood everything up until this last section. I understand why we are enumerating d from 1 to m (since d is essentially just b since q is 1). I am not sure how p becomes floor(n / d). Since p * d = a, don't we have to also enumerate all a's up to n? Why are we just greedily using n (the bound for a) over all d's? •  » » 3 months ago, # ^ | 0$a=pd=(kd-1)d$, so we enumerate$a$by enumerating$k$.$k$can be any positive integer from 1 to$\lfloor(\lfloor n/d\rfloor+1)/d \rfloor$(unless$d=1$, when 1 must be omitted), so we add$\lfloor(\lfloor n/d\rfloor+1)/d \rfloor$to the count. •  » » » 3 months ago, # ^ | 0 In D2, Why does$gcd(p, q) = 1$implies$q = 1$? •  » » » » 3 months ago, # ^ | +3 It doesn't in D2. In D1, it's because$q|p$.  » 3 months ago, # | 0 For E1/E2, if you work in the ring of power series modulo$x^{2(m+1)}-1$, then the number of failing$a$-sequences is the constant coefficient in$(x^{-1} - x) x^{b_0 + 1} (m - 1)^{-b_0/2} \frac{m^n - (m - 1)^{n/2} (x + x^{-1})^n}{m - \sqrt{m - 1} (x + x^{-1})}.$Using this together with fast exponentiation-type algorithms and FFT convolution, you can get an$O(m \log m \log n)$method, although it doesn't seem to be faster than the editorial method unless$n/m$is quite large.  » 3 months ago, # | 0 I could not comprehend the solution for Div1C (Fenwick Tree). Could someone please elaborate on the solution, or suggest any resources that could aid in my understanding?P.S.: I am familiar with the basic Fenwick Tree •  » » 3 months ago, # ^ | +11 To calculate$\textrm{coefficient}\cdot a_u$in$b_v$, think about how many ways$a_u$can reach$b_v$. Say,$a_5$can reach into$b_{16}$via$b_6, b_8, b_{16}$. Now, the number$3$came from the depth difference of$5$and$16$being$3$. And you want to cover this$3$distance using$k$steps, where in each step you either propagate forward or stay in place.If you don't know stars and bars method, a short explanation is that$n$things can be divided into$m$portions (where a portion is allowed to have$0$things in it) by inserting$m-1$separators, thus the number of ways become$\binom{n+m-1}{n}$(treat the separators also as "things", then make any valid arrangement).Now, if you piece it together, using the example,$a_5$can reach$a_{16}$by first staying in$5^{th}$place or propagating, in fact even staying in place for$k-2$steps and propagating twice, or any other way. Every different choice represents a coefficient of$a_5$in$b_{16}$. This number of ways should be$\binom{3+k-1}{3}$, using$k-1$separators between$3$propagation actions. Replace$3$with$\Delta d$and you got the formula.  » 3 months ago, # | 0 In div2/ D2, How this formula enumerate each (p,q), in the solution of editorial? min(n/(a+b)/a,m/(a+b)/b); •  » » 3 months ago, # ^ | ← Rev. 3 → 0 From the editorial you see that p + q | d, so d/(p+q) must be an integer. Furthermore, p and q must be coprime and less than sqrt(n) and sqrt(m) respectively.For each valid couple (p, q) how many values of d satisfy that d/(p+q) must be an integer? d = a / p <= n / p and d = b / q <= m / q. Therefore d can assume values from 1 to min(n/p, m/q). How many of these are multiple of p + q? floor(min(n/p,m/q)/(p+q)).  » 3 months ago, # | 0 In 1967B1 — Reverse Card (Easy Version) Tutorial, I got till the point where count of values of a is floor(n/d), but after that why the answer is floor((floor(n/d)+1))/d). Can anyone explain? •  » » 3 months ago, # ^ | ← Rev. 2 → 0 The condition$b⋅gcd⁡(a,b)│a+b$is equivalent to (p+1)=kd so (p + 1)/d must be an integer. Since q=1, d=b=gcd(a, b), therefore d has the same range as b: from 1 to m.For each possible value of d, we can count how many couples (a, b) satisfy the condition (p + 1)/d=k. Since p=a/d<=floor(n/d), p + 1 <= floor(n/d)+1. So (p + 1)/d can assume values from 1 to (floor(n/d)+1)/d. How many are them? (floor(n/d)+1)/d.We need to subtract one at the end because for p = 0 and d = 1 we get (p + 1)/d = 1 but that's not ok because p must be greater than 0.  » 3 months ago, # | +3 div1C can be also considered in a linear algrebra perspective. Notice each time of BIT is simply a linear operation. And it is so spartial that we can apply some optimization on it. For each index$x$, thinking the chain$b_1 = x, b_2 = b_1+(b_1 \text{&} -b_1), b_3 = b_2 + (b_2 \text{&} -b_2) ...$(which length at most$O(\log n)$) chain.Define$ A := \begin{pmatrix} 1 & 0 & 0 & ... & 0 \\ 1 & 1 & 0 & ... & 0 \\ 1 & 1 & 1 & ... & 0 \\ ... & ... & ... & ... & ... \\ 1 & 1 & 1 & 1 & 1 \end{pmatrix} $If contribution of index$x$($a_x$) for location at each$b_j$($a_{b_j}$) after$T$round is$v^T = (v^T_1, v^T_2, ..., v^T_{\log n})$, then after one more round, it is:$v^{T+1} = A v^T$. That is, the contribution of$a_x$to each$b_j$after$K$op is$A^K \begin{pmatrix}1 \ 0 \ 0 \ ... \ 0\end{pmatrix}$.$A^K$can be simply calculated with pre compute$A^1, A^2, A^4, ..., A^{2^{30}}$in$O((\log m)(\log n)^3)$, and evaluate in$O(\log K (\log n)^2)$(segmv is$O((\log n)^2)$).Then for each index$b_j$except first one, just have$b_j \gets b_j - v_j^K \times a_x$as the contribution, at the end it will ends with desired answer, which is$O(n \log n)$.Total complexity is$O((\log m) (\log n)^3 + n\log n)$•  » » 3 months ago, # ^ | 0 Hi , I had some trouble understanding your solution , more precisely : how did you manage to make the sizes of the A and v logn , I think thats something you did with the chain optimization you mentioned but I couldnt understand that either :/ Can you explain that more elaborately.Thanks in advance •  » » » 3 months ago, # ^ | 0 Because for each index$x$, it only has at most$n$parents in a BIT. Therefore, we only need to care about those$\log n$ancestors instead of all of the nodes.We are calculating the contribution of$a_x$(before all operations) to the$b_j, 1 \leq j \leq n$(after all operations) separately. Due to the good property of a tree, if$y$is ancestor of$x$,$z$is ancestor of$y$, then$z$is an ancestor of$x$. So we could imaging the contribution of$a_x$kind of only "floating up" due to the operations. So the only ones contributed by$a_x$is all its ancestors, where there is$\log n\$ of them.
 » 3 months ago, # |   0 I'm not sure to understand the tutorial for 1967A — Permutation Counting because of this edge case:Assume you had:n = 6 and k = 0with cards: 1 1 1 2 2 2 3 3 4 4 4 5 5 6 6 6 (that is 3 3 2 3 2 3)then the array we will make is: 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 ; plus one 4 that we have to use. Without the 4, there are 10 permutations to this array. However, I don't know where to place the last 4 to generate the answer 11, the answer the algorithm would give this problem: cnt = 2 (for 3 and 5) lst = 2 (because 3 and 5 both have 2) ans = n*lst - cnt + 1 = 6*2 - 2 + 1 = 11Why is the answer 11?
•  » » 3 months ago, # ^ |   0 Because you can place the cards as 1 2 4 6 3 5 1 2 4 6 3 5 1 2 4 6.
•  » » » 2 months ago, # ^ |   0 I spent 3 Hrs figuring this sh*t out. Thank you, your comment saved me.
•  » » » » 3 weeks ago, # ^ |   0 Thank God, I saw your comment. Otherwise, I would have wasted 3 hours too.Also, I think this should be mentioned in the tutorial
 » 3 months ago, # | ← Rev. 5 →   0 1967B1 — Reverse Card (Easy Version)What if I set p = 1, How should I proceed from qd | (p + q)?
•  » » 2 months ago, # ^ |   0 I can't come up with a useful bound for k if I set p = 1. Could you please help me how we can solve this considering p = 1? My understanding was that because gcd(p , q) = 1, so we can set either q = 1 or p = 1.
 » 2 months ago, # |   0 For problem Long Way to be Non-decreasing there is a simpler way to group each element without using DSU  mroot := make([]int, m+1) var getroot func(i int) int getroot = func(i int) int{ if mroot[i]==0{ mroot[i]=i mroot[i] = getroot(getparent(i)) } return mroot[i] } 
 » 2 months ago, # | ← Rev. 2 →   0 can anyone tell me why this solution is giving some wrong answers
 » 2 months ago, # |   0 .
 » 2 months ago, # |   0 .
 » 3 weeks ago, # |   0 Great editorial
 » 6 days ago, # |   0 Can the problem Permutation counting be solved using Binary Search. ( I am trying binary search on the number of subarrays. Where am I going wrong.) Code  ll n,k; std::cin >> n >> k; vector v(n); for(auto &val : v){ std::cin >> val; val--; } ll l = 0; ll r = 2E12+1; ll ans = -1; while( l <= r ){ ll mid = l + ( r - l ) / 2; auto check = [&](int goal) -> bool { int curr = k; goal--; int times = goal / n; int left = goal % n; for(int i = 0 ; i < n ; i++){ if ( v[i] >= times ) continue; else{ int diff = times - v[i]; curr -= diff; } } for(int i = 0 ; i < left; i++){ if ( v[i] <= times ) curr--; } return curr >= 0; }; if ( check(mid) ){ ans = mid; l = mid + 1; } else{ r = mid - 1; } } cout << ans << endl; 
 » 6 days ago, # |   0 cute rui_er