By Vladosiya, history, 5 months ago, translation,

1932A - Thorns and Coins

Idea: denk

Tutorial
Solution

1932B - Chaya Calendar

Tutorial
Solution

1932C - LR-remainders

Idea: MikeMirzayanov

Tutorial
Solution

1932D - Card Game

Idea: goncharovmike

Tutorial
Solution

1932E - Final Countdown

Idea: step_by_step

Tutorial
Solution

1932F - Feed Cats

Idea: denk

Tutorial
Solution

1932G - Moving Platforms

Idea: denk

Tutorial
Solution
• +33

 » 5 months ago, # |   +3 Tutorial after 3 days. Why?
 » 5 months ago, # |   0 hii can anyone help me with my solution[submission:247597946] for which I am getting tle for test case 2. My Idea :- I have used cumulative sum to get the number of cats at any position i and prevnum array to point to the index (x) if i use the index (i) to feed my cats , than simply use dp to calculate dp[n] .Plss help me to get past TLE.!!
•  » » 5 months ago, # ^ |   0 I got it, it got accepted :-)
•  » » » 5 months ago, # ^ |   0 :)
 » 5 months ago, # |   0 In F, we consider all values from 1 to N. If we only checked points that are either start of end of an interval, then it gives WA. Why could that be?
•  » » 5 months ago, # ^ |   0 See the case below. It is optimal to pick the middle of the 3..5 segment. 1 7 7 1 3 3 5 5 7 1 1 1 1 7 7 7 7 
•  » » 5 months ago, # ^ |   0 check start and (end + 1) of every interval instead as the state changes at (end + 1) for an interval and not at end
 » 5 months ago, # |   0 Here's a derivation to the solution to E.Let the initial string/number $a_na_{n-1}...a_1$.A change of:-$n$ digits occurs $a_n$ times.$n-1$ digits occurs $9*a_n + a_{n-1}$ times.$n-2$ digits occurs $9*(a_na_{n-1})+a_{n-2}$ times.Thus, the final answer is:-$= n*a_n+(n-1)*(9*a_n + a_{n-1})+(n-2)*(9*a_na_{n-1}+a_{n-2})+...$$= n*a_n+(n-1)*(a_na_{n-1} - a_n)+(n-2)*(a_na_{n-1}a_{n-2}-a_na_{n-1})+...$$= n*a_n-(n-1)*a_n+(n-1)*a_na_{n-1}-(n-2)*a_na_{n-1}+(n-2)*a_na_{n-1}a_{n-2}-...$$= a_n+a_na_{n-1}+a_na_{n-1}a_{n-2}+...+a_na_{n-1}...a_1$
 » 5 months ago, # |   +19 Thanks for very fast editorial
•  » » 5 months ago, # ^ |   0 Really "fast"
 » 5 months ago, # |   0 For F, what if the range of intervals was [1, 1e9]. how can we solve this question then?
•  » » 5 months ago, # ^ |   +14 we could use co-ordinate compression, the number of unique co-ordinates wont exceed 2n
 » 5 months ago, # |   +3 In problem G,my code got a "Wrong Answer" on test 2. Can anyone give me a hack? Many thanks.https://mirror.codeforces.com/contest/1932/submission/247682595
•  » » 5 months ago, # ^ |   0 I had the same issue but then I added 1 to the new step count since its given that moving to another platform counts as a step.
•  » » » 5 months ago, # ^ |   0 I have understood it.Thank you.
 » 5 months ago, # |   0 Very good contest, I hope CodeForces can provide us with more and better games!
 » 5 months ago, # |   +1 I like how they put a "2012" reference in the last test case of problem B.
 » 5 months ago, # |   0 Here's my solution using Segment Tree for Problem F. https://mirror.codeforces.com/contest/1932/submission/247752578
 » 5 months ago, # |   0 i think F has linear time solution https://mirror.codeforces.com/contest/1932/submission/247761658
•  » » 7 weeks ago, # ^ |   +3 Same version of solution, but a little commented :D, if anyone wants explanation https://mirror.codeforces.com/contest/1932/submission/264556949
 » 5 months ago, # | ← Rev. 3 →   +4 Alternative (linear) solution for F: SpoilerRephrase the problem as "you are given $n$ segments, choose any number of points so that no segment covers more than $1$ of them, and the number of segments that cover exactly $1$ point is the maximum possible".Do it with a dynamic programming of the form $dp_i$ — the maximum answer if we considered the points $[0, i-1$], and all segments containing the point $i$ are uncovered (i. e. we can use the point $i$ and all subsequent points).There are basically two transitions: skip the point $i$, going to $dp_{i+1}$; choose the point $i$. Then we add the number of segments covering it (can be either precalculated with difference arrays or maintained "on the fly"), and we are not allowed to use points $i+1, i+2, \dots, x$, where $x$ is the maximum right border of a segment which covers point $i$. But this $x$ is actually the maximum right border among all segments which begin at point $i$ or to the left of it, so we can maintain it in a single variable if for every point, we store the maximum right border of all segments beginning at that point. So, then we transition to $dp_{x+1}$. At first, I thought that we only need to consider segments which cover point $i$, so the maximum right border of them should be maintained with a multiset, but we actually never need to decrease its value. Solution code
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 https://mirror.codeforces.com/contest/1932/submission/248011446i guess i have implemented the same thing, but i have used recursion(stack_overflow), but i am getting runtime error. Any help will be appreciated. Thanks
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Hey! I think I have implemented the same logic in my code but idk why it's giving WA. Here's my submission:249587298nvm I got the mistake.. was a silly one :')
•  » » » 4 months ago, # ^ |   0 which Online Judge you're using to practice problems ?
 » 5 months ago, # | ← Rev. 2 →   0 Hi,Can anyone please help me with debugging this submission for Problem G. https://mirror.codeforces.com/contest/1932/submission/247832499, i am WA at testcase 30. For the same logic but small change in variable assumption it is getting accepted https://mirror.codeforces.com/contest/1932/submission/247832770. The difference is submission 247832499 has dp[i] = steps at which value of connected platforms will become equal i.e. l+s*dp[i] will match with previous platform where dp[i] will be minimum.While submission 247832770 has dp[i] = 1 + steps at which value of connected platforms become equal i.e. l+s*(dp[i]-1) will match with previous platform where dp[i] will be minimum. Both codes are mostly same just dp[i] has shifted with value 1.Sorry for bad formatting of the comment!!
•  » » 5 months ago, # ^ |   0 nvm got the issue. My bad!!
 » 5 months ago, # | ← Rev. 2 →   0 Correction in third last line, in editorial of G..k′=b′−1a′modH --> k′=b′−1a′modH′
 » 5 months ago, # |   0 Can someone help me with C? My code's working, but I keep getting time limit error. The code is written in Python. My submission is: 248030291
 » 5 months ago, # |   0 Can anyone tell me what category of problems does E lie in? And where can I find similar problems?
•  » » 4 months ago, # ^ |   0 these type of problems are implementations
 » 4 months ago, # | ← Rev. 4 →   0 .
•  » » 4 months ago, # ^ |   0 Even though Python can handle large integers (note that every $a_i$ can be as large as $10^4$), operations on them are slow. When following the solution provided by the editorial, i.e. handling commands in reverse order, then you can keep applying mod m which is much faster (as the product stays under $m$).
 » 3 months ago, # |   0 In problem G, why do we take x modulo (H / dd) ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 Using 'auto [dd,x,y] = eucl(b,H)', we got one possible solution to the equation — 'xb+yH=dd' (here (dd is the gcd). Now, we multiply 'a/dd' to the above equation to get — '(x*a/dd)*b + (y*a/dd)*H = a'. Now we have one solution {x0,y0} — {(x*a/dd),(y*a/dd)} to the equation but we want the one having smallest positive x0 value. general solution for the above equation would be — {x,y} = {x0 + k*(H/dd) , y0 — k*(b/dd) }. so the samlest possible 'x' would be 'x%(H/dd)' . check out this for more clarification — https://cp-algorithms.com/algebra/linear-diophantine-equation.html
 » 3 weeks ago, # |   0 For BI tried binary search to find the smallest number greater than previous year and divisible by current ai, but it gave wa on test 3. Can someone help me find the error? Binary search submission for Bint fn(int start, int end, int prev, int x) { int ans = 0; while (start <= end) { int mid = (start + end) / 2; if (x * mid > prev) { ans = mid * x; end = mid - 1; } else start = mid + 1; } return ans; } void solve() { int n; cin >> n; vector a(n); for (auto &x : a) cin >> x; int ans = 0; int prev = 0; for (int i = 0; i < n; i++) { int x = a[i]; if (x > prev) { prev = x; } else { prev = fn(1ll, 1000000ll, prev, x); } debug(prev); } cout << prev << endl; cerr << endl; return; }