### awoo's blog

By awoo, history, 12 months ago, translation, 1342A - Road To Zero

Idea: BledDest and adedalic

Tutorial
Solution (Roms)

1342B - Binary Period

Idea: adedalic

Tutorial
Solution (adedalic)

1342C - Yet Another Counting Problem

Idea: BledDest and adedalic

Tutorial
Solution (BledDest)

1342D - Multiple Testcases

Idea: BledDest

Tutorial
Solution (pikmike)

1342E - Placing Rooks

Idea: BledDest

Tutorial
Solution (BledDest)

1342F - Make It Ascending

Idea: Neon

Tutorial
Solution (Ne0n25)  Comments (183)
 » Thanks! It answered my questions!
•  » » Quite literally xD
 » thanks for the editorial. C was bit tricky.
 » Can anyone please elaborate inclusion-exclusion part for E?
•  » » 12 months ago, # ^ | ← Rev. 4 →   Suppose we just try to place the rooks in the $c$ columns we've chosen. There are $c^n$ possibilities, because we can place each rook in any of $c$ columns and there are $n$ rooks. (We will see this is when $i=0$.)However, we've accidentally counted some arrangements where some columns aren't used. Let's subtract all arrangements where one column is empty. We choose the empty column ($c \choose 1$), and the rooks go in the remaining columns ($(c-1)^n$). Like in the first case, some other columns might be empty; we just know for sure the column we've chosen is. So, there are ${c \choose 1} (c-1)^n$ combinations we want to subtract. (This is $i=1$.)Now, consider combinations where two rows are empty. For each pair of rows $a$ and $b$, we've already subtracted those combinations in the case $i=1$. Actually, we've subtracted them once for the case where $a$ is for certain empty, and once for the case where $b$ is for certain empty. We've overcompensated, so we will add back in the combinations where two rows are empty, so add ${c \choose 2}(c-2)^n$. ($i=2$)I think we need another iteration to clarify why we can just alternate. For $i=3$, consider rows $p$, $q$, and $r$. (__r i p n a m e s p a c e s lol__) We've accidentally added it once at $i=0$, subtracted it for $p$, then $q$, then $r$ for $i=1$, added it for $p, q$, then $p, r$, then $q, r$ for $i=2$. So, we need to unadd it back.And just keep going.So, it turns out it works because of that weird alternating binomial property. But we don't really need to know that, as long as we can find the pattern.
•  » » » The "alternating binomial property" can be proven easily enough. The number of combinations we've already counted so far for some $i$ is $\displaystyle\sum_{j=0}^{i-1} {(-1)^j {i \choose j}}$. (See case $i=3$ in my other post for the reasoning.) This is just $\displaystyle\sum_{j=0}^{i} {(-1)^j {i \choose j}} - (-1)^i {i \choose i}$. The summation is just a binomial expansion, so this simplifies to $(1-1)^i - (-1)^i {i \choose i} = 0^i - (-1)^i = -(-1)^i$, This means we have overcounted by that much, so we add $(-1)^i$ to the answer to correct it.
•  » » » » can E's solution be also written as S(n,n-k)*(n-k)! .where S(i,j) is stirling number?
•  » » » » » Exactly
•  » » » » » How did you conclude that?I mean it's true from the mathematical perspective, but is there any intuition for it?
•  » » » » » » In our case, $S(n, n-k)$ represents number of ways to distribute $n$ rooks into $n - k$ nonempty columns. This number doesn't consider the order of columns (e.g. distribution $[[1,2],]$ is the same as $[, [1,2]]$). However, these are two different distributions for us. That is why we multiply the number by $(n - k)!$, the number of permutations of $(n - k)$ columns.
•  » » » » » » » 12 months ago, # ^ | ← Rev. 3 →   Wait what does $n-k$ mean, $n-k$ may be negative here! Although I also was thinking about stirlings. First some background on what I understand:In particular if $k \neq 0$ (for $k = 0$ answer is $n!$) then we calculate all ways for $n$ rooks to span all $n$ rows, call it $W$. Our answer will be $2W$ (replace row with column)Now as you say, since $k\neq 0$ some columns will be repeated. So we group them by columns. Stirling number $S(n,p)$ will give set of all partitions of $n$ into $p$ groups. Now pairings in this question depends on the size of groups right, say $p = 2$ and $n = 4$ then there may be 3-1 partition or 2-2 partition where in the first case pairings will be $\binom{3}{2}$ and in second case it will be $\binom{2}{2}\cdot\binom{2}{2}$ so how stirling will help herePlease tell me if I misunderstood it, Thanks a lot.
•  » » » Nice, detailed explanation. It was too hard for me to get this inclusive-exclusive approach by myself.Just one note about this part: " We've accidentally counted it once at i=0, subtracted it for p, then q, then r for i=1, added it for p,q, then p,r, then q,r for i=2. So, we need to add it back. " Isn't it supposed to be subtraction for i = 3, not add it back ? If it is so , than I got it.
•  » » » » Yes, he meant subtracting it for i = 3.
•  » » » » Oh, oops! Thanks, I'll correct that.
•  » » » We want k pairs so lets group first (k+1) elements, they will have n options, next rook will have n-1, next will have n-2 and so on.So the answer is n*(n-1)*(n-2)*...*(k+1)What is wrong with this answer??
•  » » » » I don't know if I understand your answer, but I think you don't account for arrangements where two different attacking pairs are in different columns.For example, I don't think your way counts the following arrangement for $n = 4$, $k = 2$. R . . . R . . . . R . . . R . . 
•  » » » 12 months ago, # ^ | ← Rev. 3 →   Hey this is a very clear explanation thank you. I was wondering if you came up with a to define sets that fulfill this expression. For example if you let S(i) be the set of configurations where at least i columns have no rooks, we have$S(i) = {c \choose i} \cdot (c - i)^n$And $S(n) \subset S(n - 1) \subset ... \subset S(1) \subset S(0)$ which implies $S(0) / S(1)$ is the answer. This is incorrect because $S(i)$ double counts some configurations and throws them away. I was wondering if you had a set definition that worked?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   Thanks for the explanation.
•  » » » Consider n=3, k=1|r| | ||r| | || |r| ||r| | || |r| ||r| | |here, in both the arrangements column 1 has 2 rooks, column 2 has 1 rook and column 3 has no rook.How have we considered the above two cases different? It seems we just distributed n rooks in c columns each being non-empty. I cannot understand. Please explain!
•  » » » Hey Russell_Emerine so as you said to place $n$ rooks in $c$ columns initially we get $c^n$ arrangements, what I think this is is that for every rook we have $c$ options to place to but why don't we consider the permutation among the rows? Say, for example, a column contains $k$ rooks then these $k$ rooks can be spread throughout $n$ rows so arranging $k$ rooks in that column(which has $n$ rows) hence $C_{k}^{n}$ possibilities for that column similarly why are we not considering the arrangement of those rooks among the rows for each column? I hope you understand my question, Thanks in advance.I might sound like a novice but am not good at combinatorics so I'd be grateful for any help :)
•  » » » » This is because the rooks are not distinct, it dosen't matter if first rook goes to first row, or last row both cases are same configurations. Only thing that matters is all rows should be filled. So we won't consider nCk
•  » » » » » But the thing is there might be less than $n$ rooks in a row in the arrangement, so in that case, the arrangement does matter, consider it like we know every row is gonna be filled but which row must be filled with which column varies hence my question.
•  » » » » » » There can be no case where there is less than n rooks, this is the first assumption we are taking that, all rooks must be in all different rows so that they attack all non empty cells(columns as well as rows). After that assumption we are just playing around with the column positions. If that was the case the question would be much harder to solve.
•  » » » » » » » I don't think you understood my query, I know all $n$ rows are filled but which rows is filled in which column will differ, every $(n-k)$ column will have at least $1$ rook, but rest rooks are distributed arbitrarily among them, hence a column will have less than $n$ rooks for sure so I was wondering about arranging them in $n$ rows, but nevermind I understood my flaw, thanks for your time.
•  » » » » 12 months ago, # ^ | ← Rev. 4 →   Even I had the same doubt but got cleared somehow.Just consider assigning numbers to each rook (virtually) R1, R2, R3, ...Rn denoting the row number to which this rook will belong.Note: since all rooks are similar, it does not matter which rook is assigned which row number.So, consider n-3, k=1|r1| | || |r2| ||r3| | |and|r1| | ||r2| | || |r3| |In this way we consider them different. Since we were assigning column to each rook independent of the other. we have already counted this. I hope this was useful.Give a thumps up if you agree.
•  » » » » » Ohh now I understood thanks buddy, rraj0510 so we assign each rook an id corresponding to its row that rook is to be placed in that row only that way all possibilities are covered with $c^n$, Now I got the intended intuition.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   I am still confused , after we consider all c^n possibilities and then subtract the possibility that one of the columns is completely empty using cC1 , how are we overcounting that exactly 2 columns are empty ? Edit: got it , thanks for good explanation.
•  » » » what about the arrangements of rooks within each of these columns, how is that accounted for ?
•  » » » »
•  » » » » » thanks!
•  » » » I wish This could also be included in the editorial for additional explanation
•  » » » Hey, I just wanted to ask if the rooks are numbered ? For example, if there are 3 rooks and 3 columns, Does it make any difference if the rooks go to columns {1, 2, 3} respectively instead of {2, 1, 3} ?
•  » » 12 months ago, # ^ | ← Rev. 2 →   Russell does a good job of explaining IE if you're not familiar. If you are familiar, if we take the IE formula from wikipedia: $\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i •  » » My solution with explanation in comments, https://codeforces.com/contest/1342/submission/78619750  » Please someone tell me faster approaches for Problem C. •  » » 12 months ago, # ^ | ← Rev. 2 → if$a \leq b$, and lcm(a,b) is L. Then from b to L-1 every number satisfies. Therefore we don't even need to check which numbers are good between 0 and L-1 individually and it will always be (L-b). Then just answer each query in O(1) time. Here is my code for reference. •  » » » would you please explain this proof ? •  » » » » I tried to prove it Here See if that makes sense! •  » » » » » instead of lcm(a,b) can we have a+b? •  » » » » » » I don't think that'll work. •  » » » » » » » but why? I have spent enough time disproving, could you please help. Thanks •  » » » 12 months ago, # ^ | ← Rev. 3 → hey! I also tried a very similar approach to the questions, so basically I exclude the numbers in which the condition ((x%a)%b == (x%b)%a) is satisfied from the range [l,r]. These numbers would be of type in (N*lcm(a,b)+max(a,b)-1) for N in {0,1,2,3...}. Now I just need to calculate numbers like these which lie in [l,r] and subtract it from the total (l-r+1).Is this approach right? If so could you please help me with why this solution is getting a wrong answer (https://codeforces.com/contest/1342/submission/78349599)?Thanks a ton in advance! •  » » » » Your code fails on this Test case: 1 1 1 1 1 1  •  » » » » » 12 months ago, # ^ | ← Rev. 2 → I fixed it, but still, I am getting a wrong answer verdict. https://codeforces.com/contest/1342/submission/78359260 I really am stuck, is it an implementation problem or is the logic incorrect? Sorry to bother yet again! •  » » » » » » Hey! Thanks for the help! Actually I figured it was an implementation mistake! Thanks a ton again! •  » » » https://codeforces.com/contest/1342/submission/78237660 My code is failing for test case 3 . can you please tell me for which test case it is failing.I can"t find any test case doubleux •  » » » that's what i thought too but my implementation kept on not working :( do u know where i went wrong code •  » » » 11 days ago, # ^ | ← Rev. 3 → Hi, please can you give an idea of why taking the range between l and r is incorrect in comparison to your solution, taking first 1 to l-1, and 1 to r. I can not find a counterexample.Here is my submission: 112327238UPD: AC 112369657  » 12 months ago, # | ← Rev. 3 → Can we build the array required in C with LCM(a,b) instead of building it for a*b ? •  » » Yes, that is exactly what I did. Although worst-case complexity will be same, since$LCM(a,b)=a*b$if$a$and$b$are co-prime. •  » » 12 months ago, # ^ | ← Rev. 2 → Yes, C can also be solved using LCM(a, b). Here's my solution with no pre-processing and O(1) space: 78178389 •  » » » Hey @aditya.vallabh , nice solution. Can you explain these two lines *** if(l%lcm < a) { res += a — l%lcm; } if(r%lcm < a) { res -= a — r%lcm — 1; } *** •  » » » » Basically all the numbers which fall in the range of [k*lcm, k*lcm + max(a,b)] (k is any integer) have equal moduli. If l or r falls in the middle of such a range, the numbers either have to be included or excluded which is handled in these two statements. •  » » » » » Got it. Thanks. •  » » » » » Can you please provide the proof for your statement dedsec7 •  » » » » » Can you please check what is wrong with my code? HEREI have used the same logic but cannot figure out the mistake.  » How ((ab + x) mod a) mod b = (x mod a) mod b . Can anyone please explain ! •  » » ab % a == 0 so we have ( (0 + x ) mod a ) mod b •  » » just take any two a and b and print 1 to 100 numbers satisfying the property and you will see a pattern. And I guess it will give you a good intution towards the problem.  » 12 months ago, # | ← Rev. 2 → The problem F can be passed by$\mathrm O(n^24^n)$algorithm. Enumerate a set$s$to be removed, then denote$f(i,\,S)\;(0\leq i\leq n-|s|,\,S\in s)$as the minimum$a_i$when the set of elements which is used is$S$. The transfer is very simple. •  » » I don't quite understand how your algorithm is different from the reference solution. Do you have code? I'm also quite surprised that$O(n^2 4^n)$works because I had quite a lot of trouble not getting TLE for my$O(n^2 3^n)$solution (I had to use a profiler to shave constant factors).  » There's another approach to solve C (in fact it solves a harder version of it). Let's suppose we are given$a,b$and the interval$[l,r]$in each test case. It suffices to solve the problem for the interval$[0,r]$and the interval$[0,l-1]$and substract.Notice that if we fix that$a\leq b$then$(x \text{ mod } a) \text{ mod } b$is just$x\text{ mod } a$. Therefore, if one wants that$(x\text{ mod } a)\text{ mod } b = (x\text{ mod } b)\text{ mod } a$, this amounts to verify that$x\text{ mod } a = (x\text{ mod } b)\text{ mod } a$or equivalently, that:$ x \equiv x\% b\pmod{a}.$So, we want to know how many$x\in [0,r]$are such that the above congruence is true.From the division algorithm, we have that there is a$q$and$r'$such that$ x = qb + r'$and$0\leq r'
•  » » Can you please explain how to deduced then what we want is x−r′=qb to be a multiple of a from x≡r′moda ?
•  » » » Because $x \equiv qb + r'$ so $x - r' \equiv qb$. Also $x \equiv r' \mod a$, so $x - r' = qb$ must be a multiple of $a$.
•  » » That's exactly what I did
•  » » Excellent explanation! Can someone further explain: This amounts to have q a multiple of a / gcd(a, b)? Thanks!
•  » » Really amazing solution and explanation. Thanks
 » "The property given in the statement holds for x if and only if it holds for x mod ab." , couldn't get this line. Can anyone explain?
•  » » Let's say $X = x + kab$If $(X\%a)\%b = (X\%b)\%a$ then $((x+kab)\%a)\%b = ((x+kab)\%b)\%a$ that means $(x\%a)\%b =(x\%b)\%a$ (Recall that $p + tq \mod q = p\mod q$)So if $X$ satisfies the condition, so does $X \mod ab$
 » 12 months ago, # | ← Rev. 7 →   The equality to the solution of problem E is actually Stirling Number of the second kind(How many possible ways can we put n different things into k indifferent boxes such that the order of things in each box doesn't matter and each box must have atleast one thing?) multiplying it with k!.
•  » » Hi, I replied on a similar comment above concerning with stirlings. I am unable to solve this question for some time now. Here is what I understand:--- If $k \neq 0$ (for $k = 0$ answer is $n!$) then we calculate all ways for $n$ rooks to span all $n$ rows, call it $W$. Our answer will be $2W$ (replace row with column)Since $k\neq 0$ some columns will be repeated. So we group them by columns. Stirling number $S(n,p)$ will give set of all partitions of $n$ into $p$ groups. Now pairings in this question depends on the size of groups right, say $p = 2$ and $n = 4$ then there may be 3-1 partition or 2-2 partition where in the first case pairings will be $\binom{3}{2}$ and in second case it will be $\binom{2}{2}\cdot\binom{2}{2}$ so how stirling will help herePlease tell me if I misunderstood it, Thanks a lot.
•  » » » 12 months ago, # ^ | ← Rev. 12 →   EDIT : You need to find number of arrays that has n−k distinct numbers, not k. My bad ;_;Let's consider only the case some columns are repeated (we can multiply the answer with 2 to make up for the other case.)We will place the rook of row $i$ at column $A[i]$.For example, if $n = 4$ and $k = 2$, we will have something like this $A = (1,1,2,2)$ or $A = (4,4,4,1)$ or $A = (3,1,1,1)$Now, you can see that in case $k = 2$, there are 2 distinct numbers.Which means if we want k pairs of rooks fighting, we need to build an array that has k distinct numbers.That means if you want to find how many ways we can place the rook for $(n,k)$, Just find how many ways we can build an array that has $k$ distinct numbers instead.Combinatorics time! : How many ways can we choose k distinct numbers? $C_{n,k}$How many way can we arrange n different index into k distinct numbers?That is when our stirling number comes to a play.$Stirling(n,k)$ = How many ways can we arrange n different index into k indifferent boxesTo make k indifferent boxes into k different boxes is just to multiply it with k!So, $Stirling(n,k) *(k!)$ = How many ways can we arrange n different index into k distinct numbersTherefore, the number of arrays that has $k$ distinct numbers is $C_{n,k}*Stirling(n,k) *(k!)$ And the final answer is $2*C_{n,k}*Stirling(n,k) *(k!)$(The $Stirling(n,k)$ can be calculated in $O(k*log(n))$ time using the formula in the wikipedia.)
•  » » » » Thank you for reply, I think my confusion was because of given constraint in question that $k \le \binom{n}{2}$ whereas in reality $k \le n-1$. I was thinking that if $3$ rooks appear in a col then pairings is taken as $\binom{3}{2}$. But it is only $2$. In general if there are $m$ rooks in a col then pairings is $m-1$ right!This confusion got cleared when I read your second line with sample $A$. Now everything makes perfect sense. So reflecting my understanding, I now see if we have all $n$ in a col then we always get $n-1$ attack pairs. If we split it in 2 col then we have $n-2$ pairs of attacks no matter what the distribution.In general we need $k$ pair attack so we have $S(n,n-k)$ ways to make partition into $n-k$ group. Now multiplied by $\binom{n}{k}$ to signify which col those group denotes. Upto this is ok. Why multiply by $(n-k)!$ also
•  » » » » Don't worry dude now I got it, We use $(n-k)!$ to shuffle between which group from partition corresponds to which selected col.
 » 12 months ago, # | ← Rev. 2 →   I have used the following greedy approach for problem D. Start iterating from the smallest element and assign all the frequencies of it in one array till the time the capacity of array allows or we have exhausted all the frequencies. If we have exhausted the frequency of that particular element, move on to the next element, if the capacity of the array is allowed.It fails on test case 11. Can anyone please help me figure out what's wrong with the approach?
•  » » 12 months ago, # ^ | ← Rev. 2 →   Sorry, made a small error in the previous version.
•  » » » Did you figure out what's wrong with the approach?
•  » » Try the example, $M = [1, 1, 2, 2]$ and $C = [2, 1]$The correct answer is we can group like $[1, 2], [1, 2]$ but your greedy leads to the groups $[1, 1], , $.If you go from largest element to smallest element, I believe the greedy works but you have to worry about TLE on a case with $\sqrt{n}$ distinct values with $\sqrt{n}$ each (I used some similar greedy with optimization).
•  » » » Thank you so much! That helped.
 » I have a weird solution for D that's more complicated but also simpler than the editorial's. Instead of precalculating the bounds, I construct the answer directly.I have a vector> $t$ that will represent my testcases, and a position $p$ that will represent the testcase I'm adding to. $p$ will always go from the back of $t$ to the front. Also, I will add in each array in order of decreasing length.Suppose I want to add in an array of length $m$. $t[p]$ consists only of arrays of length greater than or equal to $m$, so they all contribute to $c[m]$. If there's still room for $m$ there, go ahead and add it. If there isn't (i.e. $|t[p]|=c[m]$), we can for the sake of argument consider $t[p]$ "filled up" and decrement $p$, or set $p$ to the back of $t$ if $p=0$. Note that we can only move on from a $t[p]$ when it is filled up.Now, $p$ is one less. The last time $t[p]$ was filled up was when $p$ cycled through $t$ earlier. The $c$ at that time was either less or equal to now. If it was less, great! there's more room for our $m$. If not, we know the whole $t$ has been travelled through with the same value of $c=c[m]$. This means we can't place $m$ anywhere in $t$ because all the testcases are filled to the same $c$! Our only option is to add a new testcase and place $m$ there. Set $p$ there too.Make sure to account for when $t$ is completely empty as well.Since we only add testcases when it's impossible to place $m$ anywhere else, the solution must be optimal. Furthermore, for every $m$ we only use append and size operations on at most two distinct locations $p$, so every $m$ is $O(1)$. This means the runtime of the main process is $O(n)$, and total runtume with sorts and everything is $O(nlog(n)+k)$, just like in the official solution.Find it here: 78200438
•  » » for (int i = 0; i < n; i++) { if (t.empty()) t.push_back({m[i]}); else if (t[p].size() < c[m[i]]) t[p].push_back(m[i]); else { if (p == 0) p = t.size(); p--; if (t[p].size() < c[m[i]]) t[p].push_back(m[i]); else { t.push_back({m[i]}); p = t.size() - 1; } } } If an element doesn't fit into current t[p] , you do a p-- . So how do we know that current i will either belong to p-1 or p+1(new testcase). Don't we have check over entire p = 0 to p-1 and then add it into new testcase ?
•  » » » I think solution is working once from top to bottom and then goes bottom to top... Here is my thinking why does an element either belong to p or p-1 or p+1 (i.e, creating new testcase)...If we observe first larger elements of sizes of array are fixed from top to bottom. Like this, arr_sizes = [3,3,3,2,2,2,2,1,1,1] and arr_k = [3,2,1] So after first top to bottom session, ans = [,,] and p=2 Now array size changes to 2, here we have three choices, p,p+1,p-1 So we added 2 to p So now ans = [,,[3,2]] Again we have to add 2, we can add new testcase i,e. p+1 and ans = [,,[3,2],] (Wrong answer) but it would not generate minimum answer. We cannot add 2 to p and make ans = [,,[3,2,2]] (Wrong answer) since there should only 2 array>=2 We have all arrays filled up with exact size except last one, so now we will look for upper half, now it's time to move bottom to up ans = [,[],[]] p=0 (Go top to bottom) ans = [,,[]] p=1 ans = [,,] p=2 ans = [,,[3,2]] p=2 ans = [,[3,2],[3,2]] p=1 (Go bottom to up) ans = [[3,2],[3,2],[3,2]] p=0 ans = [[3,2],[3,2],[3,2],] p=3 (We hit p==0 condition pf code) ans = [[3,2],[3,2],[3,2],[2,1]] p=3 ans = [[3,2],[3,2],[3,2],[2,1,1]] p=3 ans = [[3,2],[3,2],[3,2,1],[2,1,1]] p=3 (Go bottom to up) This shows when we move from top to bottom we are make all inner vectors of same sizes. When we hit to the end we make the last vector size greater then all vectors and when that vector is filled we go bottom to up for making such vectors of same size as last one.... It was a great observation by Russell_Emerine. I wish if would have done that..Hope you get the intuition
•  » » » » Oh yeah, I see now, it goes to the top and drops directly to bottom I see I see. Thanks buddy! I guess this question WAS tough for me after all.
 » 12 months ago, # | ← Rev. 2 →   Can anyone explain the editorial of 1342D — Multiple Testcases.Specifically how it is proven Let the number of the arrays of size greater than or equal to i be gi. The answer is a maximum ⌈gi/ci⌉ over all i from 1 to k. You can prove that you can't fit gi arrays in less than ⌈gi/ci⌉ testcases with the pigeonhole principle
•  » » The upper bound is because we can distribute all the numbers $\geq k$, then all the numbers $\geq k - 1$, etc. For the lower bound, assume by way of contradiction that we use $ans$ testcases and there is some $i$ such that $\lceil g_i / c_i \rceil > ans$. Then by the extended pigeonhole principle, one of the testcases must have more than $c_i$ arrays of size $\geq i$, which is a contradiction (alternatively, you can think of it like trying to distribute the g_i cases among $ans$ testcases is impossible).
 » How to solve E with FFT?
•  » » Please help on this one, it has fft tag and no one's talking about it.
•  » » »
 » for the problem D I am not able to understand why my solution https://codeforces.com/contest/1342/submission/78247111 is correct while https://codeforces.com/contest/1342/submission/78247043 is wrong. the only difference is the 2 solution is that I have used 1e10 as a multiplier in the first and 1e11 in the second . since the constraints were 2*1e5 I don't think replacing 1e10 with 1e11 should be an issue , but it turns out it is . It will be really helpful if anyone can explain reason behind failure of later second submission
•  » » I don't understand your solution method at all, but could it be floating point rounding error?
•  » » » Thanks for your help, Yes it was floating point rounding error. Thanks again.
 » In the Editorial for Problem D. I am not able to understand this thing, "Let the number of the arrays of size greater than or equal to i be gi. The answer is a maximum ⌈gi/ci⌉ overall i from 1 to k". Can somebody explain how is this working? I am able to form some intuition about it after reading the Editorial but it is still not completely clear to me. If somebody can explain it in a little more detail it will be highly appreciated.
•  » » I mean there's really no more detail to that. You want to place these $g_i$ arrays somewhere. What's the minimum number of testcases required to do that if you can't put more than $c_i$ in each of them? So you put $c_i$ into the first one, $c_i$ into the second one and so on until you have no more arrays left. You will use exactly $\lceil \frac{g_i}{c_i} \rceil$ testcases with that.That idea by itself does not really account for the placement of individual arrays of these sizes exactly, so the actual construction is more complicated than the proof for the minimum bound.
•  » » » Thank you
•  » » » Hi I understood most part of the solution by this line is confusing me. forn(i, n) res[i % ans].push_back(a[i]); I understand you are assigning the elements into ans arrays and in a sort of cyclic order. But how do you guarantee that the element in the array will follow the constraint. I tried some test cases and it does!!Is there some sort of proof or something. Even some intuition might do as well. Thankyou very muchPS: it was nice editorial
 » problem A stated that our task is to get x and y equal to 0 simultaneously. This costed me 2 incorrect submissions until that was clarified. Anyway this was one of the few div 2 contest where D problem felt easier and within the range.
 » I tried problem C, although wasn't able to get it correct and looked up the tutorial. But I have my code for the same which is not so efficient and correct (but should run). What bugs me is when I try and run it (I use sublime text 3), it gives me "'filename' is not recognized as an internal or external command, operable program or batch file. [Finished in 3.7s with exit code 1] " message without showing any errors in code, and I'm not able to quite pin point what's causing it. Please help me with this. Code: https://pastebin.com/f87wxz80
 » I am unable to find what is wrong in my code. I have calculated all values from l to r for which (x%a)%b == (x%b)%a using lcm(a,b) and simple multiplication and then subtracting it from (r-l+1). But my code is stuck at 2nd test case. Here is my code code.
•  » » Same. I don't understand why. The restricted range should be [nl, nl+b) where l is the lcm and nl is a multiple of lcm and b is the larger of (a,b). Mine also fails at 2nd test case.
•  » » 1 4 15 1 59 73your output : 0 correct output : 1
 » How does https://codeforces.com/contest/1342/submission/78244632 pass but https://codeforces.com/contest/1342/submission/78244302 fails? There is only one line change, and that line never gets executed. The 'cout << "???"' line never gets executed, since the test passes.
 » Can anyone help with TL on problem F?) https://codeforces.com/contest/1342/submission/78328093
•  » » 12 months ago, # ^ | ← Rev. 2 →   You probably need to remove the first innermost loop, which can be replaced with something like int lower_than_j = s & ((1 << j) - 1); if (lower_than_j == 0) continue; msb = 31 - __builtin_clz(lower_than_j); This also replaces the if statement.Other micro-optimizations you could try is if you iterate over j from high to low, I think you can break instead of continue when msb == -1. Also, I think k's maximum value is __builtin_popcount(s) + 1 since you can't have more groups than on-bits.It took me a while to not get TLE, though I had a slightly different setup. Hope this helps.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   Thank you) But, unfortunately, it doesn't help. I have one of the submissions, where I precalculate msb for all masks and bits. The thing that helped was to change backward DP behavior (where I subtract submask) to forward DP (where I add submask of superset). It also changed some of the if statements
 » for D problem: why do we need to assign indexes by sorting in decreasing order..will doing same in increasing order work?
•  » » Both work fine
•  » » » I used the exactly same logic as in tutorial..used both increasing and decreasing but its not working.. what wrong with the code 78370972
 » For D, why does inserting the (i mod ans)th testcase always optimally construct the testcase array? Like is there any proof or intuition to understand/come up with it ?
•  » » The intuition is basically something along the lines of "add stuff in such a way that it's packed as tightly as possible". Like given the fixed number of testcases, put arrays of all big sizes so that each testcase has as few of them as possible. And the modulo does exactly this. It puts arrays like $1,2,\dots,k,1,2,\dots,k,\dots$, which only has $\lceil \frac{n}{k} \rceil$ arrays put in the worst testcase if there are $k$ testcases and $n$ arrays.
•  » » 12 months ago, # ^ | ← Rev. 3 →   I think we can come up with the solution by thinking in this way. Taking just a single constraint, if suppose the count of arrays with size = k is 11 and constraint on k = 3, then we would need at least ceil(11/3) = 4 testcases. We would then distribute them as follows: tc0 = k k k ; tc1 = k k k ; tc2 = k k k ; tc3 = k k ; If we fill it in a circular manner, then we can fill the testcases in the most efficient manner satisfying the single constraint. Expanding to more than one constraint, if we take maximum of all such ceil(count/constraint), "ans" , we can distribute all arrays with whatever be the sizes among 0 to ans-1 testcases in a circular manner satisfying all the constraints.
 » Video solution for C.
 » War. War never changes. Can you do something about it Neon? My submissions to F •  » » I don't even understand now, how do my optimizations work.
 » C- Yet Another counting problemAn alternate O(1) for each query solution. Let's denote a as the smaller one of (a,b) and b as larger one of (a,b). Any number lying in the range [0, b) would satisfy ((xmoda)modb)=((xmodb)moda). Let's denote LCM of a and b as l. The range [0,b) would imitate itself for the range [l, l+b), [2l, 2l+b), [3l,3l+b).... So we can count the multiples of l in the given range and also find the restricted range by adding b to it. It is also possible that a multiple of l might fall outside the given range but yet some numbers fall in the range [nl, nl+b), so we need to take extra care for that.My code doesn't work. Maybe somebody could help me figure out the mistake in the logic?
•  » » I believe this submission 78156490 will show you a clearer view of your idea
 » You can do C in $O(1)$ per query and $O(q)$ per test case with no precomputation required. I believe in the small problems like A,B,C the intended solution should be the fastest one. Even if the explanation is a bit longer and not that beautiful. Here is my solution. https://codeforces.com/contest/1342/submission/78195420
•  » » Your solution is not O(q) per test case, since you calculate the gcd: https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency So it's around O(q + log(a))
•  » » » $почему$ $столько$ $грусти?$
 » Here's a terrible overkill solution for E, as an alternative to inclusion-exclusion. We want to count the number of ways to distribute $n$ rooks into $m = n - k$ fixed columns, such that all of them remain non-empty and there's one in every row. Assume that we fix the ordered tuple $a_1, a_2, \dots, a_m$ of how many rooks we place in each column. Then the number of ways to place the rooks is $\frac{n!}{a_1!a_2! \dots a_m!}$This formula counts the number of ways to arrange the $n$ rooks if they're labeled and then eliminate the order from all rooks in the same column. Thus the problem is reduced to calculating $\displaystyle\sum_{a_1 + \dots + a_m = n} \frac{1}{a_1!a_2! \dots a_m!}$Which we can interpret as the coefficient of $x^n$ in $\left(x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}\right)^m$. We can calculate this in $O(n \log^2 n)$ with binary exponentiation and NTT, which is enough to pass with a few constant factor optimizations.
•  » » I am not very familiar with NTT. Can you please share some resources to learn about it.
•  » » Hey I am not understanding some comments in this regard: Why are we choosing $n-k$ columns? I mean there may be case where $k > n$ in that case how can we select $n-k$ columns. Also am I correct in saying that your answer will be multiplied by $2$ because same thing be done by replacing row with column?
•  » » I wanted to see if there was a simpler closed form for the PIE summation in the editorial, and looked to this comment for inspiration.Your polynomial set off my $e^x$ detector, so I thought it would work out pretty simply and proceeded as follows: we want the coefficient of $x^n$ in $n! (e^x - 1)^m$, which we can find by differentiating $n$ times and dividing by $n!$.I expanded this to $\sum_{k=0}^m \binom{m}{k} e^{kx}x^k (-1)^{m-k}$, and differentiating $n$ times gives us $\sum_{k=0}^m \binom{m}{k} k^n e^{kx} (-1)^{m-k}$, which looks awfully familiar. So that didn't work, but gave a different route to the same destination. xD
 » Can anyone explain me why ((ab+x) mod a) mod b == (x mod a) mod b I am a beginner and don't know much about modular arithmetic... If there are some proofs of modular arithmetic that I should know as a competitive programmer can you please mention such resources Thanks in advance :)
•  » » This is because (ab%a)%b==0
•  » » » Can you explain why this property creates cycle from 0 to ab-1 then ab to 2ab-1 and so on??
•  » » » » Well, because the cycle has length ab. Because if we add ab to x, the result of the formular is the same.This is more or less the definition of the length of the cycle. Which number do we have to add to allways get the same result? Answer is: That one which allways creates result 0, because 0 is the neutral element of addition.
•  » » First, since both a and b divide ab, ab % a = ab % b = 0. Thus (ab % a) % b = 0 % b = 0 = 0 % a = (ab % b) % a. Note that the above holds if we replace ab with lcm(a, b).
 » In problem D what's wrong for test case 1 if I give the answer as 4 1 2 2 3 as c1 can have 4 elements greater than 1???
•  » » because if you chose array of size 1 then you have no. of arrays of size>=1 is 1. just next if you choose 2 then you have no. of arrays of size>=2 is 1. and then if you choose 2 again then no. of arrays of size>=2 is 2 now. but it is mentioned that no. of arrays of size>=2 can't exceed 1 ( as c=1 ).I hope you get it now..
 » 12 months ago, # | ← Rev. 6 →   For problem F. Why did you decide to put such bounds on your max test? I calculate the following lower bound on your max test number of operations -- $4500 \cdot f(5) + 400 \cdot f(8) + 50 \cdot f(10) + 25 \cdot f(11) + 15 \cdot f(12) + 7 \cdot f(13) + 2 \cdot f(14) + f(15)$, where $f(n) = n^2 3^n$. That is, according to my python $9 ~163 ~838 ~367$. Why did you put 7 seconds on that? Cause my solution jumps between TL and AC just when I change backward DP to forward DP and change a couple of if statements correspondingly.
•  » » We usually set the limits in harder problems depending on the behaviour of the model solution. In this problem, the model solution runs in $1.4$ seconds on the worst case (and it may be even faster on $64$-bit compiler, which cannot be used in Polygon), so we thought that it was fine that the time limit is $5$ times larger than the runtime of our solution.$f(n) = n^2 3^n$ is just a close estimate of the number of required operations, since some states may be unreachable (for example, a state where $cnt$ is greater than the number of $1$-bits in the mask is impossible).
 » Can anyone told me what's wrong with my code for problem div2 C. My Source code is here. I have found the pattern that after LCM of a and b say LCM all b numbers will follow the equality x%a%b==x%b%a these numbers would be [0,b) [LCM,LCM+b),[2*LCM,2*LCM+b) I have tried to remove all these numbers. Here b refers to the big number. Somehow I am getting the wrong answer. If anyone could help, it would be a great pleasure.
 » 12 months ago, # | ← Rev. 2 →   Can anyone correct me if I'm wrong or say that I'm right? In Ques C, we may notice that all numbers $x\in[k\cdot lcm(a,b), k\cdot lcm(a,b)+max(a,b)-1]$ where $k\in \mathbb{Z}$ follow $(x \mod a)\mod b = (x \mod b)\mod a$. We can count all other numbers in the range $[l,r]$ in $O(1)$ time. Thus, the time complexity can be reduced down to $O(q)$ per test case.
 » I have an issue about ceil. Can anyone tell me why the submit is incorrect? https://codeforces.com/contest/1342/submission/78388627 Thank you.
•  » » 12 months ago, # ^ | ← Rev. 2 →   Don't use ceil, It's always better to not mess with floating points as much as possible. If you wanna find the ceil(p/q) use (p+q-1)/q instead.Also you're ceil doesn't work because your cnt[i+1]/cnt[i] is converted into an integer(int/int) before it is ceiled. Use ceil((float)cnt[i+1]/cnt[i]) and your code will work.
•  » » » Thank you! I sometimes forget floating points.
 » Problem E has fft tag, how to solve it using fft?
 » 12 months ago, # | ← Rev. 2 →   can someone plz help me in problem D?? how to approach to solve this problem?? didnt understand the editorial
 » Can somebody Please Explain Why I am getting WA on Problem C Submission.
•  » » 1 4 15 1 63 79your output: 17 correct output: 5
 » Thanks for editorial! It helped me a lot
 » 12 months ago, # | ← Rev. 2 →   Problem E How to calculate the number of ways to distribute the rooks into $c$ columns? One of the options is to choose the columns we use (the number of ways to do this is $C_n^c$), and then use inclusion-exclusion to ensure that we are counting only the ways where each column contains at least one rook. Why "each column contains at least one rook" not equal to $C_{n-1}^{c-1}$ — number of distributions of $n$ not different items into $c$ not empty groups?
•  » » This would work if we treated all rooks as equal. But they are not — each row contains exactly one rook, so each rook is uniquely represented by its row index (so they are different).This formula does not distinguish, for example, between these sets of positions: $[(2, 1), (1, 2), (3, 2)]$ and $[(1, 1), (2, 1), (3, 2)]$.
 » 12 months ago, # | ← Rev. 2 →   I tried a different approach but it is failing on testcase 11. The checker says that jury has better answer, but I don't think that is possible. Please helpMy Approach: I have sorted the m array(size of array of original input) in decreasing order. I have taken frequency of every element entered in m and stored in a hashmap.Now, I also maintain a variable alpha which keeps track of number of element in the new array. when c[m[left]-1]- alpha<=0 I start a new array. This means that when the allowed limit of the element found at left index - no of element already in the list <=0 I start a new array for example if the input array is 1 2 2 3 then after sorting it will be m=[3 2 2 1] So in the first iteration, the left=0 the frequency of m[left]=1 so I put it in the array and decrease its frequency by 1 and increase left by 1 now in the second iteration of inner loop, left=1 and the frequency of m[left]=1 Also, alpha is 1 now. so c[m[left]-1]-alpha is equal to zero and I terminate. Now in the the second iteration, left=2 and the freq of m[left]=2 Alpha=0 as new iteration started. so now I add it again to the new array now in the second iteration of inner loop, left=3 and the frequency of m[left]=1 Also, alpha is 1 now. so c[m[left]-1]-alpha is equal to zero and I terminate. And for the third iteration, left=3 and the freq is 1. alpha=0 so I add it to the new array and left=4. now since the limit is more than 1... I do not terminate and the new array has [2, 1] inside. Thus, the final list is , , [2,1] Now what I think is that this way leads to the optimal solution. Please explain why does it fail for test 11The link to the code is as follows: https://codeforces.com/contest/1342/submission/78422553 @pikmike
•  » » ok I understood it. Cannot delete it now. sad.fails for test case [1 1 2 2] [2 1]correct ans= [1 2][1 2] my ans= [1 2]  
 » 12 months ago, # | ← Rev. 5 →   In Problem DInput 7 7 1 2 3 4 5 6 7 2 3 2 1 2 1 1 In the above input, the editorials output is: 4 2 7 3 2 6 2 2 5 1 1 4 which says we need min 4 testcases, i think the min number would be 3 using the following distribution of arrays: 3 2 5 7 3 2 3 6 2 1 4 PLEASE, correct me if I am wrong.
•  » » "The third line contains k integers c1,c2,…,ck (n≥c1≥c2≥⋯≥ck≥1); ci is the maximum number of arrays of size greater than or equal to i you can have in a single testcase." in input you are not following constraints... it is mentioned that n>=c1>=c2>=c3...>=ck>=1..
•  » » » Ah Sorry , I didn't notice that. Thank You.
•  » » In your second array $[2, 2, 3, 6]$, there are three elements that are $\geq1$, which violates the input (there's also a typo as the size is three, not two).
•  » » » Got it..! :) Thanks. (Corrected the typo).
 » Can anyone explain the E part second test case as for 3x3 chessboard and exactly 3 pairs why|R|R|.||R|.|.||R|.|.|is not one of the valid solution? I think in this 3 pairs are attacking each other.
•  » » you need to place n rooks only, in your case rooks are 4.
 » In case anyone need div2 D explanation,code and example Here
•  » » tnx bro it helped :)
 » 12 months ago, # | ← Rev. 2 →   2
 » 12 months ago, # | ← Rev. 2 →   ((ab+x)mod a)mod b == ((x)mod b)mod a for problem C
 » I was surprised that $O(n^23^n)$ solution passed in F. I have $O(n^22^n+n3^n)$ solution.Notice, that if $cnt_1 > cnt_2$, then $dp_{cnt_1,mask,pos} < dp_{cnt_2,mask,pos}$ for any $mask, pos$ in valid state. Thus, there is no need to recount from all dynamics states. For each $mask$ and $pos$ find the largest $cnt$, that $dp_{cnt,mask,pos}$ valid, and update $dp_{cnt,smask,pos}$ for all $smask$ that don't intersect with $mask$.We need $O(n^22^n)$ for find largest $cnt$ for each $mask$ and $pos$ and $O(n3^n)$ for update dynamic.
•  » » Can you please explain why that inequality holds?
 » For Div2D, I converted given array into a map sorted with descending order keys, and then I traverse the map from largest key to smallest, trying to make a set of testcases,while decreasing the frequency of which I am using and deleting those whose freq becomes 0. I keep on doing this until, map becomes completely empty. I am getting runtime error on tc 1, which is working fine locally. Can anyone suggest how to carefully iterate over a maps keys from desc to asc order while deleting some keys based on some condition ? I think the logic is correct, becoz if I use array instead of maps, while increasing the time complexity since I loop from max no to 1 everytime, I am getting TLE on tc16.
•  » » I might be wrong but something similar has happened to me before, when you check for a value in the map, even if it's not an entry in the map, an entry for it gets created against the value 0/NULL, so when you're traversing the map, you also go through the new entries.
 » In problem F i fail to understand what is dpcnt,mask. what is meant by mask in editorial?I cant understand the state of DPPlease help
 » 12 months ago, # | ← Rev. 3 →   @Neon: For problem F, what does order stand for in the statement "Suppose we don't have any constraints on the order of elements," Is it for the number of elements?Also in the statement "This runs in O(n*(3^n)), if we use an efficient way to iterate on all masks that don't intersect with the given mask.",how did you derive the O(n*(3^n))I am pretty new to competitive programming and your reply would be of great help to me.
 » For the forth problem, can somebody explain and help me figure out whats wrong in my code. I am getting WA for the test case 11. Though i am correctly determining the minimum number of testcases required, but maybe doing some mistake in filling the arrays for the test cases. int main(){ BOOST(); int n,k; cin>>n>>k; vectormi(n); vectorci(k+1); for(int i=0;i>mi[i]; for(int i=1;i<=k;i++)cin>>ci[i]; sort(mi.begin(),mi.end()); int size=INT_MIN; int cnt; for(int i=1;i<=k;i++){ cnt=n-(lower_bound(mi.begin(),mi.end(),i)-mi.begin()); size=max(size,(cnt+ci[i]-1)/ci[i]); } vectorfinal[size+1]; int flag=1; int cntr=0; while(flag<=size){ final[flag].pb(mi[cntr]); int left=ci[mi[cntr]]-1; // left denotes how many more numbers i can still fill after filling mi[cntr] for(int i=cntr+1;i
•  » » If you can't debug your code , How can we ??
 » 12 months ago, # | ← Rev. 4 →   I will be explaining how I attempted question D but was not able to get it accepted because of reasons unknown to me; if you realise what's wrong in my code please let me know. Firstly, I sorted m and began traversing from the last position. I checked how many arrays can be greater than this array's size using array c and incremented my counter which was initially 0 and appended it to my ans array. now I went to the second last element of m and subtracted count from the value of c at this position since I have already used an array of size greater than this arrays i.e I did c[m[i]-1]-=count. now if still the c[m[i]-1] was greater than 0 I appended this array size into my answer array and kept on traversing backwards. if my c[m[i]-1] would have been less than 0 I would have finished the process of making this test case and start making the process of the new test case from this position onwards. Also, I again initialised count to 0 and made a new copy of c. this is the basic idea. I submitted my code and got WA at TC11. Let me know what's wrong in my idea for the question.link to my solution: https://codeforces.com/contest/1342/submission/78349009link to question: https://codeforces.com/contest/1342/problem/D
•  » » 11 months ago, # ^ | ← Rev. 2 →   Edit: It took me a day to realise that I was only appending elements in descending order and broke the loop whenever I encountered an array size which cannot be appended. Therefore I started traversing the whole array and appending the possible array size but in doing so I ended up with the worst-case complexity of O(n^2) when each array can have only one element.This time I got a TLE on TC16. Please help me out; I wanted to edit in the previous comment itself but I felt that it's better this way since this would make you realise the persistent approach building process I went through.link to the updated solution: https://codeforces.com/contest/1342/submission/79016398link to the question: https://codeforces.com/contest/1342/problem/D Again, I know a lot of you have solved the question so please help me find out where I am going wrong and how to reduce time complexity.
 » 11 months ago, # | ← Rev. 3 →   Another solution for D using priority queue Codeint n, k, c[MAX]; vector m; vector> ans; struct cmp { bool operator()(int i1, int i2) { return ans[i1].size() > ans[i2].size(); } }; int main() { FAST; cin >> n >> k; m.resize(n); for (int i = 0; i < n; i++) cin >> m[i]; for (int i = 1; i <= k; i++) cin >> c[i]; sort(m.begin(), m.end(), [](int i1, int i2) { return i1 > i2; }); priority_queue, cmp> pq; ans.resize(1); pq.push(0); int cnt = 1; for (int i : m) { int idx = pq.top(); pq.pop(); if (ans[idx].size() + 1 <= c[i]) { ans[idx].push_back(i); } else { ans.resize(cnt + 1); ans[cnt].push_back(i); pq.push(cnt); cnt++; } pq.push(idx); } cout << ans.size() << '\n'; for (vector v : ans) { cout << v.size() << " "; for (int i : v) cout << i << " "; cout << '\n'; } } 
•  » » can you please explain the approach using priority queue?
 » From the editorial for F (first paragraph): "To model transitions, we simply iterate on the mask of elements that will be merged into a new one, and check if its sum is greater than the last element we created."I'm kind of lost here. Is there any mathematical formulation of the DP transition that could potentially clarify this? (trying to upsolve this since this is the only problem in the contest idk how to do).
 » 11 months ago, # | ← Rev. 3 →   if you don't know the formula for ceil function it is given in D
 » i'm confused about the prefixes. in some cases, you'll have ends hanging from both the left and right, and because the mod is not uniformly distributed, if you calculate it by "the amount of mods that worked previous to this index" then what will happen if you have like 5 integers hanging from the left and 7 from the right? the 7 can be calculated easily true but what about the 5 on the right? if you calculate it using prefixes, then instead of getting the correct index you'll get prefix[a*b-5]. or do additive shifts not affect mods at all, and therefore there's no hanging left integers?
 » Hello!! I was attempting Problem D and my approach was as follows:- I first sorted the array a in increasing order and then started traversing in the reverse direction. If for some a[i] I could find a test case whose size is less than a[i]'s capacity then I will add that element to that test case and if no such test case exists then I will make a new test case.It is getting wrong answer at Testcase 17. I would appreciate if someone could help with the bug in my logic. (Neon BledDest adedalic awoo) Here is my solution: 80590063
»

Hey for problem C, can we use this logic?

let max be the greater number of a and b. So. the numbers from (multiple of lcm(a,b),multiple of lcm(a,b)+max) are to be subtracted from the given range.

Here's the code

# include<bits/stdc++.h>

using namespace std;

int gcd(int a,int b) { int max=0; for(int i=2;i<sqrt(a*b);i++) { if(a%i==0 && b%i==0 && i>max) max = i; } if(max==0) max=1; return max; }

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin>>t;

while(t--)
{
int a,b,q;
cin>>a>>b>>q;
int lcm = a*b/gcd(a,b);
//cout<<lcm<<endl;

if(a>b)
{
int temp = a;
a=b;
b=temp;
}                                                   // a<b always now

long long ans[q]={0};
for(int i=0;i<q;i++)
{
long long l,r;
cin>>l>>r;

if(lcm==b)
cout<<0<<" ";

else
{
long long count = r/lcm - (l-1)/lcm;
//cout<<count<<endl;

ans[i] = r-l+1 - b*count;
//cout<<ans[i]<<endl;

if((l/lcm)*lcm <l && (l/lcm)*lcm + b >= l)
{
ans[i] = ans[i] - ((l/lcm)*lcm + b - l);
}
//cout<<ans[i]<<endl;

if((r/lcm)*lcm + b > r)
{
ans[i] = ans[i] + ((r/lcm)*lcm + b - r -1);
}
cout<<ans[i]<<" ";
}
}cout<<endl;
}

}

 » What is wrong in this Submission for Problem C??SubmissionThanks a ton in advance!!!!
 » https://ideone.com/VTSzgt alternative solution for problem C with time complexity O(log(a)) for query(because of gcd)
 » 10 months ago, # | ← Rev. 4 →   Good contest
 » In problem C, I figured out that if lcm(a, b) = l, then first b(Assuming b > a) numbers from l * k (k = 0,1...) will not satisfy the conditions. So, now I just need to exclude them from my queries. I'm still getting a wrong solution. Can somebody figure out the problem pls ? Thanks. My Submission : 84942234
 » In problem B:Why printing out the string twice is not a correct answer?
 » " Otherwise, it's also quite obvious that any string t is a subsequence of 0101...01 (1010...10) of 2|t| length."for problem B, I dont find this sentence obvious at all. Could someone please explain it to me (and others)?
 » 7 months ago, # | ← Rev. 2 →   Can someone help me with C. My idea for this problem was the value of (x%a)%b and (x%b)%a repeats itself for every lcm(a,b) distance. So i thought i could iterate through the first lcm(a,b) numbers(from l) and add all the multiples till r to the answer. But it TLEs... can someone help on improving the complexity of my solution. Thanks in advance!! Link to My Submission
•  » » A better understanding of this C problem is in the editorial. its ,this wayinstead of a*b , just take upto lcm(a,b)explaination:: take t=lcm(a,b) for numbers :: 1,2,3,4.....t,t+1,t+2,t+3.....2*t,2*t+1,2*t+2......3*t,3*t+1.....4*t,...NOTE:: t=lcm(a,b);the question is why lcm(a,b)? soln:: is right in the editorial. lcm(a,b)%a%b==0 same for lcm(a,b)%b%a. this is the 2nd leat value after 0 for which it becomes 0. but 0 is not there in the range the value of l and r is from 1 to 1e18.so, use a prefix array for which this holds true;len = a * b;// here just do lcm(a,b)-->tym will be less p = 0; for(int i = 1; i <= len; i++) { p[i] = p[i — 1]; if((i % a) % b != (i % b) % a) p[i]++; }
•  » » » Thanks. Got it!!
 » In question C, the main idea was to see, ((ab+x)mod a) mod b = (x mod a) mod b. This would imply (x mod a) mod b = (x mod b) mod a holds if and only if it holds for x mod ab.I wasn't able to see this condition, I was trying to prove things mathematically. I think if I had tried thinking intuitively, I would have found this 'trick' (and I believe most of the people who solved C wouldn't have gone the mathematical way). How can we mathematically try to prove that x mod ab is the necessary condition for (x mod a) mod b = (x mod b) mod a? I was struggling to do so, maybe some one could help. Also, in general in these kinds of problems, is it better to think intuitively or it may be better to work things out using a pen and paper?