Artyom123's blog

By Artyom123, history, 6 months ago,

Solution
Code

Solution
Code

Solution
Code

Solution
Code

Solution
Code

1928F - Digital Patterns

Solution
Code
• +127

 » 6 months ago, # | ← Rev. 2 →   +75 Why do the authors set $\sum c_i\le 2\cdot 10^5$ in problem D? There exists both $\mathcal O(n\log \max c_i)$ and $\mathcal O(n\sqrt{\max c_i})$ solutions. Why do the authors set $\sum s \le 2\cdot 10^5$ in problem E? A init function can precalc the dp array. And the limit for $\sum s$ made it hard to hack brute-force solutions, for example, just simply do dfs. And the tests are quite weak that some dfs solutions passed the ST. Most of them can be uphacked with the test: 1 673 0 1 200000 However, we can't hack 245835914 with the test above, can anyone help to hack it? :)Anyway, I found most of the problemset nice. Kudos to the authors & coordinator!
•  » » 6 months ago, # ^ | ← Rev. 4 →   +32 Because the $O(n \log {\max c_i})$ solution with binary search is hard to prove. This works, but we didn't expect contestants to prove it during contest. I agree, maybe removing $\sum s \leq 2 \cdot 10^5$ would have been better. Anyway, the difficulty of problems D and E as they are seems adequate for their position.
•  » » » 6 months ago, # ^ |   +1 is the link you provided correct? is seems to be a diffrent problem. is the problem simular to problem d?
•  » » » » 6 months ago, # ^ |   +1 Yes, the formula used in that problem is the same up to rescaling.
•  » » » » » 6 months ago, # ^ |   +1 thank you.
•  » » » 6 months ago, # ^ |   -8 I think nobody proved, frankly it was incredibly intuitive for me.
•  » » » » 6 months ago, # ^ |   +1 not to me sadly :( can you explain how you thought of it? I guessed it was convex of course, but i couldn't feel that with my heart.
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Me too, but then I wrote linear search and I looked every k, it seemed it was convex. I tried and it worked.Also, you can see my first linear search submission which gets TLE.
•  » » » » » » 6 months ago, # ^ |   -8 did u solve as indicated in tutorial and got tle?
•  » » » » 6 months ago, # ^ |   +4 Bruh ur rating chart is kinda unique tho :)
•  » » » » » 6 months ago, # ^ |   +3 Thanks, lol :D
•  » » » 6 months ago, # ^ |   0 Isn't that precisely the issue? When you set a problem with a correct solution that is easy to come up with and hard to prove you are rewarding the people who implemented without proving it. Which probably shouldn't be the case?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +8 Is it even possible to prevent solving problem without proving? besides, there is time penalty for WA verdict. especially in cp, almost no one tries to prove the logic. I think it's the contestant's job to keep the balance between intuition(for time) and proof(to reduce risk of WA, stupid impl) while competing
•  » » » 6 months ago, # ^ |   0 Perhaps it's difficult to definitively prove it, but it's quite intuitive. One increasing function is how much the power increases, another is how much it decreases, added together they make a convex function.
•  » » » 6 months ago, # ^ | ← Rev. 4 →   +4 Nope. We can prove the ternary search solution more easily. Suppose the number of squids is $x$. The contribution of each $c_i$ is a convex function of $x$. Since the sum of several convex functions is also convex, the statement is proved. Additionally, the $\sum c_i\le 2\cdot 10^5$ allowed a brute force to pass the problem — just by noticing that there are at most $\mathcal O(\sqrt{n})$ different $c_i$-s.
•  » » » » 6 months ago, # ^ |   +8 Yes, but why is the contribution of each $c_i$ convex? The only proof we found is the one in the linked comment.
•  » » » » » 6 months ago, # ^ | ← Rev. 3 →   +38 I thought it was well known (I also missed the $\sum c_i$ constraint), for example, here goes:Let $f(k) = (c \% k)\left\lfloor\frac{c}{k}+1\right\rfloor^2 + (k - c \% k)\left\lfloor\frac{c}{k}\right\rfloor^2$ be the function that we want to prove being convex. If we replace $c\% k$ with $c - k\left\lfloor\frac{c}{k}\right\rfloor$, then we can consider this as a function not of positive integers, but of positive reals. I claim that this function is now piecewise linear, continuous, and convex.Indeed, if $k\in \left(\frac{c}{a+1}, \frac{c}{a}\right]$ for some nonnegative integer $a$, then $\lfloor c/k\rfloor = a$, and $f(k) = ka^2 + (c - ak)(2a + 1)$ is linear in $k$ on this half-interval with the slope $-a(a + 1)$. Therefore, if we prove that $f$ is continuous, then it's convex because the slopes are nondecreasing.To prove that it's continuous it suffices to check that $f(c/a - 0) = f(c/a + 0) = ac$ (exercise for the reader).
•  » » » » » » 6 months ago, # ^ | ← Rev. 3 →   +8 I think in this problem $f(k)=\binom{c \bmod k}{2}\left\lfloor \frac{c}{k} + 1 \right\rfloor^2 + \binom{k - (c \bmod k)}{2}\left\lfloor \frac{c}{k} \right\rfloor^2 + (c \bmod k)(k - (c \bmod k))\left\lfloor \frac{c}{k} + 1 \right\rfloor \left\lfloor \frac{c}{k} \right\rfloor$, but I think your proof still works.And to prove the function is continuous, I think we should check if $\lim_{x \to (c/a)^+} f(x) = f(c/a)$.And thanks for the proof anyway, it was very enlightening.
•  » » » » » » » 6 months ago, # ^ |   +8 Your expression is how much each race contributes to something that we want to maximize. You can notice that if we split $c$ guys of a certain race into groups $c_1$, $\ldots$, $c_k$ (in our case they are almost equal), then your value is $\sum\limits_{i •  » » » » » » » » 2 months ago, # ^ | 0 How to be you •  » » 6 months ago, # ^ | 0 I only solved D, so I am replying to problem D only.I think it affects the difficulty of the problem significantly.I came up with an easy solution that depends on the array's maximum number of different elements, which is feasible due to this constraint.My idea is that the maximum number of different elements would be achieved by an array that looks like 1 2 3 4 5 .... n. which would sum to n*(n+1)/2. So using the summation constraint you can easily prove that the max number of different elements is about 700.Which makes trying each possible squad size for every element feasible.Here is a link to my solution, I hope it helps someone.https://codeforces.com/contest/1928/submission/245866373 •  » » 6 months ago, # ^ | 0 Can you share O(nsqrt(max ci)) solution ? •  » » » 6 months ago, # ^ | 0 •  » » » » 6 months ago, # ^ | +5 Its not O(nsqrt(max ci)) dear •  » » » » » 6 months ago, # ^ | +21 dear 💀  » 6 months ago, # | 0 thanks for fast editorial  » 6 months ago, # | +10 Great problems overall, but felt that statements were often convoluted and difficult to comprehend. Still, thanks for the great contest.  » 6 months ago, # | 0 can anyone hack my solution? •  » » 6 months ago, # ^ | 0 no, it is correct solution (hint:$f(k) - f(k-1) \geq f(k+1) - f(k)$)  » 6 months ago, # | 0 Thanks for fast editorial! :)  » 6 months ago, # | -26 bad F :( •  » » 6 months ago, # ^ | +9 Peopls disliking bro's cmnt thinking that he is a newbie •  » » » 6 months ago, # ^ | 0 well aren't the people right? •  » » » » 2 months ago, # ^ | 0 Tell me you are clown, without telling me you are clown.  » 6 months ago, # | 0 Can we solve D by binary search? •  » » 6 months ago, # ^ | ← Rev. 2 → +1 yes we can do that take minm squads as 1 and maximum can be max(c[i]) then we can easily see that value of our predicate function first increases and then decreases so it's like we have to find peak value in rotated sorted array which could be solved by binary or ternary search ,here is model solution using ternary search https://codeforces.com/contest/1928/submission/245874386 hope it helps •  » » » 6 months ago, # ^ | +3 Let's say that we have to calculate the max value of h(k)where h(k) = f(arr, k)-g(k)g(k) = (k-1)*xf(arr, k) is the total number of pairs after optimal distribution.I get that k will be in the range: [1, max(arr[i])] but cannot understand why h(k) will be a unimodal function. Can you prove? •  » » » » 6 months ago, # ^ | 0 for each element i of the array (lets name it arr), when you increase the number of squads k, you are distributing the creatures more and more, which means that you are increasing the total number of pairs.On the other hand, when x is greater than 0, it keeps decreasing the score when k increases.So, you can see the score as a combination of an increasing function and a decreasing function.One last thing to observe is that when k increases, the increasing function will increase slower and slower. This is because, for every element i of arr, we cannot distribute the creatures in more than arr[i] squads. Meanwhile, the decreasing function is always constant. As a conclusion of this, the total score function will either be always decreasing (when the decreasing function keeps decreasing faster than the increasing function even from k=1) or will increase then stop and start decreasing.I hope this helps you. •  » » » » » 6 months ago, # ^ | 0 While your statements don't imply that the function is unimodal, they still prove why ternary search works(f(x) = f(x + 1) is only possible for x where f(x) is maximum). Thanks a lot! •  » » » » » » 6 months ago, # ^ | 0 could you precise why it doesn't imply that the function is unimodal? is there anything wrong? or is it because I didnt formulate my statements well? •  » » » » » » » 6 months ago, # ^ | ← Rev. 2 → 0 Unimodality requires precisely one 'x' for which the function monotonically increases and decreases before and after.Consider a case where increasing bins adds exactly k to the answer. (For example, take k = difference due to increasing the number of pairs for some x bins). In this case, f(x) = f(x + 1), which means f(x) is not unimodal.This wouldn't generally work for ternary search because if f(x) = f(x + 1) for some point other than maxima, we might remove the region of interest in the answer. However, since it only happens at maxima in the question(your statement proves this), we never remove the region of interest and ternary search works! •  » » » » » » » » 6 months ago, # ^ | 0 Okay I get it.I personally used binary search to solve this problem and it worked fine. Why is everyone using ternary search tho? •  » » » » » 6 months ago, # ^ | 0 I understood it in a different way. h(k) = f(arr,k) + g(k)We know that f(arr,k) is a concave function. (it inc. and stays const., and never decreases)g(k) = (1-k)*x, which is a straight line (also a concave function).the sum of several concave functions is also a concave function.the sum of several convex functions is also a convex function.We can use ternary search on concave/convex functions to find max/min. •  » » » » » » 6 months ago, # ^ | 0 that's correct. its the same reasoning, you only used more technical words. •  » » 6 months ago, # ^ | 0 It's an upside-down parabola. So ternary search.  » 6 months ago, # | 0 is there any way to download the test case where answer is getting wrong ? •  » » 6 months ago, # ^ | +3 one hack is to just output the test case which is causing problem For example: if test-case 3213 is causing problemcin>>t while (t--) if (t==total-3213) cout< •  » » » 6 months ago, # ^ | 0 signed main() { #ifndef ONLINE_JUDGE freopen("input1.txt", "r", stdin); freopen("output1.txt", "w", stdout); #endif fast_io; int t; cin >> t; while (t--) { if (t==total-3) cout< •  » » » » 6 months ago, # ^ | 0 You need to read input has well in the if case then output that input on stdout, also while printing on stdout, make sure there are no spaces, you can put some special character like ':', ',' as delimiter, otherwise CF judge will not show you what's after whitespace •  » » » » » 6 months ago, # ^ | ← Rev. 2 → 0 Can you please give me an example Actually I can't understand the syntax •  » » » » » » 6 months ago, # ^ | 0 Suppose input is a string and your program fails at tc=3213 and there are 10000 test cases  cin>>t; while (t--) { if (t==10000-3213) { string s; cin>>s; cout< •  » » » » » » » 6 months ago, # ^ | 0 thanks brother hope this will help me a lot  » 6 months ago, # | 0 Thanks for fast editorial ! I find my bad math for c question :(  » 6 months ago, # | 0 Thank you for crushing my spirits  » 6 months ago, # | ← Rev. 6 → +9 Problem C: "To consider the second case, it is necessary to proceed similarly with the number n+x−2"How does it come (n+x-2) for the second case ! •  » » 6 months ago, # ^ | ← Rev. 5 → +18 (2k − 2)⋅t + k + k − x = n (2k — 2).t + 2k = n + x (2k — 2).t + 2k — 2 = n + x — 2 (2k — 2)(t + 1 ) = n + x — 2 •  » » » 6 months ago, # ^ | +1 You are a pretty good mathematician. •  » » » 6 months ago, # ^ | 0 The Problem C bother me in this Round. •  » » 6 months ago, # ^ | +1 Here is a video editorial: https://www.youtube.com/watch?v=AM6pz2H6JzQ&t=29s •  » » 6 months ago, # ^ | 0 You can check out my comment for a very detailed explanation.  » 6 months ago, # | +1 D using ternary search: solution  » 6 months ago, # | ← Rev. 2 → 0 Problem B: the difference between the maximum and minimum does not exceed n−1 , can become equal.. Is any mathematical proof available to prove that all such sets can always be satisfied?P.S. Thank you for the fast editorial •  » » 6 months ago, # ^ | 0 We can add permutation of$1..n$.$max(1..n) - min(1..n)=n-1\blacksquare$•  » » » 6 months ago, # ^ | 0 thank you  » 6 months ago, # | 0 thanks, it was a very good contest  » 6 months ago, # | 0 Can someone help me look at problem B? I can't find my mistake 245895448 •  » » 6 months ago, # ^ | 0 Take a look at Ticket 17337 from CF Stress for a counter example. •  » » » 6 months ago, # ^ | 0 Thank you very much  » 6 months ago, # | +15 Artyom123 Code for problem B has two main functions, probably you could edit that. Thanks for the tutorial!  » 6 months ago, # | 0 Please explain C. I have been trying it for like 2 hours and dont get it. The editorial is so unclear •  » » 6 months ago, # ^ | 0 and yeah i HATE the code for it. Was it really necessary to write this way? •  » » » 6 months ago, # ^ | ← Rev. 2 → 0 The problem could be simplified to "count the number of distinct integers which divide n — x and n + x — 2".My submission: 245894639 •  » » » » 6 months ago, # ^ | +1 yeah thanks, gonna try it tomorrow •  » » » » 5 months ago, # ^ | 0 Can u explain why are we checking if factor is greater than x * 2 — 2? •  » » 6 months ago, # ^ | ← Rev. 5 → +15 I did it using periodicity of the function. You can see that the whole pattern$1,2,3,..,k,k-1,...,2$starts repeating after$2k-2$terms. So basically, the graph looks like: where$t$axis denotes the person number$(1,2,..)$and$y$is the label assigned. So, now for this graph to have intersection with$y=x$one condition will be:$k \ge x$. Now, we have two cases:$1.x=n$is in one of such "rising" lines. From this, we get an equation like:$x+p \cdot (2k-2) = n$, where$p \in \mathbb{Z}$, from here we simply get$(2k-2) | (n-x)$, now you can find all factors of$n-x$, and impose two conditions, first it should be even (as$2k-2$is even), and second, that$k = (f+2)/2 \ge x$.$2.$If$x=n$in one of the "falling" lines, then you will get$2k-x + p \cdot (2k-2) = n$, which again can be manipulated as$(p+1) \cdot (2k-2) = n+x-2$(not so trivial like the first case)$\implies (2k-2) | (n+x-2)$, then again you have to check for factors of$n+x-2$and do the same thing as in case$1$!I think I thought very mathematically but I guess the logic should be clear to you now!My submission: 245852020 •  » » » 6 months ago, # ^ | 0 can you please explain how did you get this equations in brief.Please •  » » » » 6 months ago, # ^ | ← Rev. 6 → 0 It's just applying definitions of a periodic function:$f(x)$is periodic with periodicity$T$if$f(x+n \cdot T) = f(x)$for any$n \in \mathbb{Z}$.Now onto my solution: The$t$axis is the person number and$y$axis is the label assigned (I have shown a continuous graph, but actually it will have points). Now, according to the question we want$f(n) = x$, where$f(1) = 1,..., f(k) =k,...,f(2k-2) = 2, f(2k-1) = 1,..$so you can see$f(t+(2k-2)) = f(t) \, \forall t \in \mathbb{N}$, so$2k-2$is precisely the periodicity of the given function. Now, if I have$k < x$, then this can never have intersection with the line$y=x$, hence we need to have$k \ge x$. After this condition is imposed, if I look in the interval$[1,2k-2]$, I have two "principle" solutions namely,$t = x$and$t = 2k-x$(As it is symmetric about$t=k$). Thus, for the two cases we get two different set of solutions:$x + p \cdot (2k-2) = n2k-x + p \cdot (2k-2) = n$where$p \in \mathbb{Z}_{+}$Side note:$sinx$is a periodic function, so the solution for the equation$sinx =1$is in an infinite set {$\frac{\pi}{2} \pm n \cdot 2 \pi \, ; n \in \mathbb{Z}$}, where$2 \pi$is the periodicity of$sinx$and$\frac{\pi}{2}$is a principle solution.I think, this is the greatest depth I can explain my solution in, if you are still not sure, I would recommend you to read about periodic functions. •  » » » » » 6 months ago, # ^ | 0 thank you •  » » » 6 months ago, # ^ | ← Rev. 2 → 0 Those who might be confused why we need to check two conditions.1. 2k-2 is an even divisor you can't express any odd number by this expression.2. k=(f+2)/2≥xAssume, we have n = 100, x = 10 for k = 2: 1 2 1 2 1 2 ... for k = 3: 1 2 3 2 1 2 3 ... so on, can we get x number? No.  » 6 months ago, # | ← Rev. 2 → 0 Can anyone please point out the error in my logic to find out the maximum length of the subarray? Even after doing multiple dry runs i am not able to figure out the logical error. 245902899 •  » » 6 months ago, # ^ | 0 On the line 26 of your solution,replace arr with v.It seems that you confuse arr with v  » 6 months ago, # | ← Rev. 2 → +20 P.S. A solution in$O(q\sqrt(n))$will not work due to a large constant. I tried very hard to rule it out :D. My (n+m+q)(log(n)+log(m)) collaterally died :(  » 6 months ago, # | 0 I had a question regarding problem D. Lets call the array containing count of races "cnt" and sort it. Lets say cnt[3]=3 and cnt[4]=6 in a given test case. Is it ever beneficial for us to select number of squads=4 or 5? What I want to know is that is it ever beneficial for us to choose number of squads!= some cnt[i]. •  » » 6 months ago, # ^ | -10 Interesting question! I don't think 4 or 5 squads would be of any use in this case. •  » » » 6 months ago, # ^ | 0 Why?  » 6 months ago, # | 0 Great solution for D!Sadly I didn't solve it,I'm too bad:(  » 6 months ago, # | 0 any one can help and explain how did they reach the solution of problem B not the solution but how did you reach to that solution? •  » » 6 months ago, # ^ | 0 you need to add a permutation to an array, and you want to maximize the number of equal elements. Since all elements in a permutation are distinct, there is no need to keep duplicates in our intiial array.Now, suppose we have extracted all distinct elements from our initial array. if we take a look at two different elements at indexes i and j (1<=i,j<=n). if arr[i]  » 6 months ago, # | +10 In C why divisors of n+x-2 •  » » 6 months ago, # ^ | 0 Check my comment !  » 6 months ago, # | +10 I will appreciate if someone could either prove or hack this greedy solution to Ehttps://codeforces.com/contest/1928/submission/245926933See https://codeforces.com/blog/entry/125652?#comment-1115429 for an explanation of the greedy approach.  » 6 months ago, # | 0 Two main functions in solution of B?? signed main() { int q = 1; cin >> q; while (q--) solve(); return 0; } signed main() { int t = 1; cin >> t; for (int i = 0; i < t; ++i) { solve(); } return 0; } :(  » 6 months ago, # | +13 Curious to know why there are couple of comments as "bug1" and "bug2" in the code solution of 1928C — Physical Education Lesson. Are there any flaws in the code implementation ?  » 6 months ago, # | +29 245940869 my$q\sqrt n$works (: •  » » 6 months ago, # ^ | ← Rev. 2 → +8 Someday I will definitely learn how to cut off the$\sqrt n$ones. The battle is lost, but the war is not over.  » 6 months ago, # | ← Rev. 2 → 0 For the code solution to problem B, the code contains 2 instances of signed main() Just a minor typo though.  » 6 months ago, # | ← Rev. 4 → +13 Another approach for Div2 D [ Note that this approach does not rely on the sum of$c_i$being bounded by$2e5$]Let's notice the formula for a particular$c_i$if$k$(number of squads) is fixed. If$q = c_i / k$and$r = c_i \mod k$, then the number of extra pairs is$c_i(c_i - 1) / 2 - [(k-r)*q*(q-1)/2 + r*q*(q+1)/2]$[Idea: Subtract the bad pairs from total number of pairs). We need to sum this up for all$i$from$0..(n-1)$The first term is easy, we can precalculate the sum and store it. Focus on the next two terms inside square bracket. Upon simplification:$k*q*(q-1)/2 + qr$. We have to sum this for each$i$.Let's fix$k$and all multiples of$k$[This can be done easily]. Consider the multiple$mk$. For all values of$c_i$in the range$[mk ... (m+1)k)$the quotient is$m$and the remainder is$c[i] - m*k$. We just have to sum them up by plugging in the formula above. The term$k*q*(q-1)/2$is easy. It is constant. For$q*r$, we will need prefix sums of$c$. Locating the values of$c$in the range can be done using binary searchTime complexity:$O(\max{c_i} \log (\max{c_i}) \log n)$. Iterating through the multiples and doing binary search to find the range of c.  » 6 months ago, # | 0 What is the name of the category in which problems like D — > Lonely Mountain Dungeons lies? Can someone please share a list of problem of similar nature for practice? •  » » 6 months ago, # ^ | 0 439D - Devu and his Brother has similar 'weight' function and can be solved with similar approach. •  » » » 6 months ago, # ^ | 0 Thanks for the help. If you get some more examples do mention them.  » 6 months ago, # | ← Rev. 2 → 0 .  » 6 months ago, # | +8 P.S. A solution in$O(q\sqrt{n})$will not work due to a large constant. I tried very hard to rule it out :D. Sorry, I didn't know (I think it would be faster if didn't choose a random block size) •  » » 6 months ago, # ^ | 0 Can you explain your solution? Could it be that there will be$O(q \sqrt[3]{n})$real calculations here? •  » » » 6 months ago, # ^ | ← Rev. 2 → 0 As in the official solution, we have some (multiset$H$of) horizontal blocks and some vertical blocks$V$. The answer is then$\displaystyle\sum_{s=1}^{\infty}\sum_{x\in H}\max(0, x - s + 1)\sum_{y\in V}\max(0, y - s + 1).$For each$s$, I maintain$h_s = \sum_{x\in H}\max(0, x - s + 1)$and$v_s = \sum_{y\in V}\max(0, y - s + 1)$, as well as the$\sum h_iv_i$. Sometimes I have events of sort "one horizontal/vertical block of length$x$appeared/disappeared". Each such event is equivalent to the query "for each$i$from$1$to$x$, add$sgn\cdot (x + 1 - i)$to$h_i$/$v_i$", where$sgn = \pm 1$.So first I wanted to maintain it with segment tree, storing in each node the following: if the corresponding (horizontal/vertical) blocks on this segment are$a_0$,$\ldots$,$a_{l-1}$, then I store$\sum a_i$and$\sum i\cdot a_i$, and also the dot product$\sum h_iv_i$. But then it occurred to me that pushing delayed operations is kinda nontrivial. That's why I split everything into blocks of$K$, and each event is now "add some arithmetic progression to about$n/K$whole blocks, and also maybe on the prefix of another block". This can be done quite easily, if we remember for each block the current arithmetic progression to be added (and also what I wanted to store for the segment tree). So yes, this works in something like$O(q(n/K + K)) = O(q\sqrt{n})$, and I just set$K = 300$and submitted. I think$K = 600$or so would probably be better, idk.  » 6 months ago, # | 0 Can anyone explain what is my mistake in task B? 245838570 •  » » 6 months ago, # ^ | 0 You skip too much possible left ends with k = i •  » » » 6 months ago, # ^ | 0 I don’t understand what you mean, can you give me some kind of test? •  » » » 6 months ago, # ^ | 0 Thank you!I realized my mistake!  » 6 months ago, # | 0 I was looking at the code for problem C (physical education lesson). I think there's a mistake. while populating the unordered_set answer, it should be answer.insert((i + 2)/2). •  » » 6 months ago, # ^ | 0 (i + 2)/2 and 1 + i / 2 are identical:$\displaystyle\frac{i + 2}{2}$$= \displaystyle\frac{i}{2} + \frac{2}{2}$$= \displaystyle\frac{i}{2} + 1= \displaystyle 1 + \frac{i}{2}$•  » » » 6 months ago, # ^ | 0 Why are we populating with 1+i/2 at the first place, could you please explain that ? Thank you •  » » » » 6 months ago, # ^ | ← Rev. 2 → 0 we need to count the # of distinct k's we can get by using divisors that can be written in the form 2k — 2so rewrite 2k — 2 as 2(k-1), and now we know the divisor must be even.for each i that divides (n-x) or (n+x-2), make sure it's evenif it is, then we know i can be written in the form 2(k-1)so i = 2(k-1)i / 2 = k-1k = i / 2 + 1 •  » » » » » 6 months ago, # ^ | 0 Thank you so much  » 6 months ago, # | ← Rev. 2 → 0 for question Bint l=a.size(); int d=n-1; int s=0,e=l-1; while(s<=e){ if(a[e]-a[s]<=d)break; int d1=a[s+1]-a[s]; int d2=a[e]-a[e-1]; if(d1>=d2)s++; else e--; } cout<  » 6 months ago, # | 0 in the problem tag in problem D: there is ternary search. How can we use it in Problem D?? •  » » 6 months ago, # ^ | 0 ternary search the number of squads i think. •  » » » 6 months ago, # ^ | ← Rev. 3 → 0 But how, I don't think the graph formed is unimodal! As per as what i have observed the graph will somewhat be like negetive of sin: -sin(x) type.. Hence how are we doing ternary search. Also this is my submission and it gives tle. Awaiting for ur explaination. https://codeforces.com/contest/1928/submission/245999184  » 6 months ago, # | ← Rev. 3 → 0 Can anyone check my submission in problem D? I cannot demonstrate my solution clearly.Thank you and have a good day! My submission: 245993112  » 6 months ago, # | +3 Can someone prove that the function for D is unimodal? •  » » 6 months ago, # ^ | 0 check my comment https://codeforces.com/blog/entry/125740?#comment-1116388  » 6 months ago, # | 0 not even kidding , problem 3 was running correctly in contest just because of a single if condition (if divisor is less than x than its possible) , accepted after contest.  » 6 months ago, # | 0 Does not the solution to the problem B yield n^2 complexity? Like, for the test case where n = 2x10E5 and a = [1, 2, 3, ... , 2x10E5]. •  » » 6 months ago, # ^ | 0 No, in your case the code while(a[i] - a[pnt] >= n) { pnt++; } will not run.  » 6 months ago, # | 0 Problem C video Editorial : Youtube Video LinkIf you are not able to understand the Editorial then you can refer to this video....I have explained the complete solution in Hindi  » 6 months ago, # | 0 I wrote an in-depth, beginner-friendly solution for 1928A — Rectangle Cutting, complete with detailed explanations and diagrams: https://notes.yxy.ninja/cp/number_theory/(CodeForces)-Rectangle-Cutting. Hopefully someone finds it useful. » 6 months ago, # | Rev. 3 0 Another solution to Problem B if you missed max — min observation Here is a version of the binary search solution to Problem B, since nobody has written it in the comments even though binary search tag is present. Basic intent: for a given$endpoint\;value$, our task is to look at how much we will have to add to each$a[i]$to attain the endpoint value. That, is look at differences$(endpoint - a[i])$. Then, pickup up all unique and eligible differences, i.e differences in range$[1,n]$. This is the best possible answer for the chosen endpoint. Issue: We don't know what the best/optimal endpoint that we should choose is. Greediness: All$a[i]$'s bigger than a chosen endpoint are simply irrelevant since there is no way to decrement anything. Among all$a[i]$'s that are smaller than chosen endpoint, it makes sense(greedily) that we will always be adding lesser to the$a[i]$'s closer to the endpoint and more to the$a[i]$'s that are farther (or much smaller) than chosen endpoint. Thus chosen endpoints are always of the form$(a[i] + 1), \forall i$. Resolution to Issue: If we can somehow reuse the differences we calculated for one chosen endpoint, then we can try out all endpoints while only adding a linear factor to our time complexity. Combining Everything: Lets sort all$a[i]$. And, lets begin by considering the max element as the chosen endpoint, i.e$endpoint = (a[n] + 1)$. Evaluate and store all differences$(endpoint - a[i])$. How to reuse differences evaluated: Purely mathematical. In our sorted array of$a[i]$'s, lets say we transition chosen endpoint from$(a[j] + 1)$to$(a[k] + 1)$for any$(j > k)$. Also, lets call$a[j] - a[k] = delta$. Then, all differences are related as:$endpoint_j = (endpoint_k + delta)$. Also, it follows that if the eligible range of differences that we can pickup are related as:$if\; eligible_j = [low,high], \;then\; eligible_k = [low+delta, high+delta]\$. Thus, we can simply binary search with modified limits in the already calculated differences.

Code1: 246326560

 » 6 months ago, # |   0 nice contest
 » 6 months ago, # |   0 How to solve E using graphs?
 » 6 months ago, # |   0 I wrote an in-depth, beginner-friendly solution for 1928B — Equalize, complete with detailed explanations: https://notes.yxy.ninja/cp/greedy/(CodeForces)-Equalize. Hopefully someone finds it useful.
 » 5 months ago, # | ← Rev. 2 →   0 .