### vovuh's blog

By vovuh, history, 21 month(s) ago,

I'm so thankful to all testers, especially to Gassa and Rox for their invaluable help!

1409A - Yet Another Two Integers Problem

Idea: vovuh

Tutorial
Solution

1409B - Minimum Product

Idea: vovuh

Tutorial
Solution

1409C - Yet Another Array Restoration

Idea: vovuh

Tutorial
Solution (Gassa)
Solution (vovuh)
Solution (Rox)

1409D - Decrease the Sum of Digits

Idea: MikeMirzayanov

Tutorial
Solution

1409E - Two Platforms

Idea: vovuh

Tutorial
Solution

1409F - Subsequences of Length Two

Idea: vovuh

Tutorial
Solution
Solution (Gassa, greedy, O(n^4))

• +107

 » 21 month(s) ago, # |   +11 fastest tutorial <3
•  » » 21 month(s) ago, # ^ |   -6 That's @vovuh for you.
 » 21 month(s) ago, # | ← Rev. 2 →   0 Runtime Error C++ Exit code is -1073741571Can anyone explain what is going wrong in my code that is giving me runtime error?Any help would be appreciatedThanks :)
•  » » 21 month(s) ago, # ^ |   +1 r[r.length() — 1]++; I guess this line is what causing error when r="" that is length = 0, r[-1] will give segmentation fault
•  » » » 21 month(s) ago, # ^ |   0 Thank you very much!!!
 » 21 month(s) ago, # |   0 nice problemset
 » 21 month(s) ago, # |   +19 My screencast + live commentary, enjoy watching :)https://youtu.be/nloGFTpdTJo
•  » » 21 month(s) ago, # ^ |   0 +1 thanks
•  » » » » 21 month(s) ago, # ^ |   0 re_start Test Case2828374536691952768 75348970515787375312 29
•  » » » » » 21 month(s) ago, # ^ |   0 Thanks @mehdi for your suggestion, I got AC
•  » » 21 month(s) ago, # ^ |   0 nice bro
 » 21 month(s) ago, # |   +11 Wonderful problems, tutorials and solutions!Thanks to writers!
 » 21 month(s) ago, # | ← Rev. 2 →   -67 .
•  » » 21 month(s) ago, # ^ |   +30 Don't spam the editorial blogs with these dead memes dude.
 » 21 month(s) ago, # |   0 Why does pow(10,18) return 10^18-1
•  » » 21 month(s) ago, # ^ |   +2 pow() doesn't always give the right answer, because it was intended to work with doubles, not integers
•  » » 21 month(s) ago, # ^ |   0 if u want to use pow for high powers u can typecast with long long int , whichs works quite effectively.
•  » » » 21 month(s) ago, # ^ |   0 I do not know what that is could you show me an example?
•  » » » » 21 month(s) ago, # ^ |   +1 I think he means if you want to do pow(10,x) and not have it mess up, do (long long)pow(10,x) and it will cast it to a long long and will give the right answer.
•  » » 21 month(s) ago, # ^ |   0 Yep the same thing happened to me so instead I made an array to divide the digits according to it's powers.
 » 21 month(s) ago, # |   +7 Why B solution is optimal? I did it, but didn't understand why it worked
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +4 Suppose you have 2 numbers a and b and you can decrement them by 1, 2 times.Then you have 3 options - a-1,b-1 - a-2,b - a,b-2In first case product is ab+1-a-b. In second case product is ab-2b. In third case product is ab-2a.Now let b>aThen ab+1-a-b > ab-a-b > ab-2b (because a
•  » » 21 month(s) ago, # ^ |   +6 If we decrease a 2 times, then you decreased the product by 2*b. If we decrease b 2 times, then we decreased the product by 2*a. If we decrease a once and b once, then we decreased the product by a+b.If a>b, 2*a>=a+b>=2*b, whereas, if b>a, 2*b>=a+b>=2*aI guess you can see why decreasing one as much as possible is optimal.
•  » » » 21 month(s) ago, # ^ |   +1 thanks_wicardobeth_ now i understand why it is optimal;
•  » » 21 month(s) ago, # ^ | ← Rev. 5 →   0 Let p = a + b, f = f(a, b) = ab. b = p - a f(a, b) = ab = a(p - a) = ap - a^2 df/da = p - 2a Hence, the derivative of f equals 0 in case p = 2a. Then: a = p/2 => b = a = p/2 (considering p is even) So f reaches its maximum value when a = b (see [interior extremum theorem](https://en.wikipedia.org/wiki/Fermat%27s_theorem_(stationary_points)) for more details).For example, if you have p = 8 then in order to maximize f you have to take a = b = 4, and in order to minimize f you have to take a = 1, b = p - a = 7. Hope this helps!
•  » » 21 month(s) ago, # ^ |   0 Let the two numbers be a and b. Without loss of generality, let b > a. (The case when both are equal is trivial.) Then we can express b as b = a + k, where k is some positive integer. Consider that we have to make just one move. So we can have either (a, a+k-1) or (a-1, a+k) after one move. The product of two numbers will then be (a^2 + a*k - a) and (a^2 + a*k - a - k) respectively. Clearly, lowering the smaller number gives a smaller product. You can easily extend this argument to n moves, since as we lower the smaller number, it stays smaller and hence we go on reducing it until possible.
•  » » » 20 months ago, # ^ |   0 thanks
 » 21 month(s) ago, # |   0 Can someone tell me why my submission for E doesn't work? It's coordinate compression + greedy. https://codeforces.com/contest/1409/submission/91881485
•  » » 21 month(s) ago, # ^ |   +2 Dont know why you used coordinate compression but greedy wont work for this. Greedily choosing best for one plank might incur loss in overall max answer.
•  » » » 21 month(s) ago, # ^ |   0 Could you give me an example please? I still don't get why greedy won't work. I used coordinate compression beacause the values of the xs and ys could range from 1 to 10^9.
•  » » » » 21 month(s) ago, # ^ |   0 I got why. Thanks anyways!
•  » » » » » 21 month(s) ago, # ^ |   0 Can you explain why it wouldn't work?? I too had a similar approach.
•  » » » » » » 20 months ago, # ^ |   0 Take this case: 6 1 1 2 2 3 3 4 1 1 2 1 2 1 Answer should be 6, but greedily it is 5.
 » 21 month(s) ago, # |   +18 Well, with a little bit of maths, C can even be solved in O(n)
•  » » 20 months ago, # ^ |   0 Can you please explain how?
•  » » » 20 months ago, # ^ |   0 use arithmetic progression and give a try
•  » » » 19 months ago, # ^ |   0 Checkout my submission 95830642I try to find the PA where y is the last element, and is as further away from x as possible by solving(y - x) % (n - i) != 0 trying values of i from 1 to n-1 (the smaller i is, further away y is from x). This comes from PA formula, and i = n-1 always satisfies, but we give a shot for smaller ones.Then, find the PA where y is the last el.Since this PA could contain negative numbers (if the first element is negative), I fix it before printing.
•  » » » 19 months ago, # ^ |   0
•  » » 20 months ago, # ^ |   0 can you please explain a little?
 » 21 month(s) ago, # |   0 Can someone please tell me what's wrong with My Code Problem D
•  » » 21 month(s) ago, # ^ | ← Rev. 8 →   0 dp solution is too slow for this problem. See the constraints, you need to do it faster.
•  » » » 21 month(s) ago, # ^ |   0 this Digit dp solution has same time complexity and it got Accepted : https://codeforces.com/contest/1409/submission/91838952
 » 21 month(s) ago, # |   +4 E can also be solved with a simple DP. First, sort the $x$ array. Then for each $i$ from $0$ up to $n - 1$: Find first such $j$ that either $j = n$ or $x_i + k < x_j$. Notice that $j$ never decreases so there is no additional complexity here. Let $dp^0_i = max(dp^0_i, dp^0_{i - 1})$ and $dp^1_i = max(dp^1_i, dp^1_{i - 1})$ for $i \ne 0$ and $dp^0_i = dp^1_i = 0$ for $i = 0$. Let $dp^0_j = max(dp^0_j, j - i)$ and $dp^1_j = max(dp^1_j, dp^0_i + j - i)$. $dp^0_i$ contains best answer up to $x = x_i$ with one platform, and $dp^1_i$ with two platforms. If you are lazy (like me), just take the maximum of all values. Note that $j$ can be $n$ in the above loop, so the DP array will have $n + 1$ items.
 » 21 month(s) ago, # |   +1 Very nice problems!
 » 21 month(s) ago, # |   +11 Thanks vovuh! Nice contest to learn the basics for noobs like me
 » 21 month(s) ago, # |   0 Amazing problems, enjoyed solving them!
 » 21 month(s) ago, # | ← Rev. 2 →   +4 How to solve E if we have K platforms? $O(KNlogN)$ is fine but better than this??
•  » » 21 month(s) ago, # ^ |   +27 $dp_{i, j}$ — we at the $x=i$ and placed $j$ segments. $dp_{i, j} = max(dp_{i - 1, j}, dp_{i - k - 1, j - 1} + cnt(i - k, i)$ where $cnt(l, r)$ is the number of points between $x=l$ and $x=r$. Can be improved by coordinates compression and two pointers (if the outer loop iterates over $k$ and inner loop iterates over the positions). Total complexity is $O(nk)$.
•  » » » 21 month(s) ago, # ^ |   0 Nice solution, so this works even if we have $q$ platforms, and for each of them, we are given $cost_i$ and $length_i$, and you have a total budget $B$. It's some knapsack then?
•  » » » » 21 month(s) ago, # ^ |   +3 Yes, it's a knapsack, but you need an additional state in your dynamic programming to solve such a problem.
•  » » 21 month(s) ago, # ^ | ← Rev. 7 →   0 You can binary search to find the maximum index can reach from each index i and store data in two arrays X, Yfirst of all you need to sort x points "y points are useless"by using binary search you can search for ind "the maximum index you can reach from index i" and store in X and Y the number of nodes "which is ind-i+1"then you can maximize the elements of X from the back so you have the maximum number of nodes you can take starting from node i to the endthe answer will be max(Y[i]+X[i+Y[i]]) "make sure (i+Y[i]) doesn't go out of the array"O(nLog(n))https://codeforces.com/contest/1409/submission/91933328
•  » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 You should re-read the problem
•  » » » » 21 month(s) ago, # ^ |   0 It was misunderstand.Sorry.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 I'm using similar logic but not sure why the 2nd test case is giving wrong answer. 101451461First I'm compressing the array of Xs, and then for each X[i], trying to find farthest X[j] such that it's at least K units away. Then I'm basically iterating over each X[i] again and evaluating answer for i as max_number_of_points_for_X_i+ max_answer for farthest (eligible_index+1).
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 This test cases drop your code13 1010 100 10001 1 1your code print 3 and the answer here is 2Lower_bound function return you points which is larger than c[i].second+k which makes you count them
•  » » » » 17 months ago, # ^ |   0 to solve this problem i searched in lower_bound for c[i].second+(k+1) to find the smallest number out of my range then decrement ind by 1an accepted solution for your code after this small edit https://codeforces.com/contest/1409/submission/101465446it doesn't work for me with upper_bound on c[i].second+k instead of lower_bound on c[i].second+(k+1), i really don't know why.
•  » » » » » 17 months ago, # ^ |   0 The edit you made makes sense, I missed that caveat while using lower_bound.I too am trying to understand why it's not working with upper_bound, will update if I figure it out. Thank you for the assistance!
•  » » 20 months ago, # ^ |   +1 I believe you can solve this version in $O(NlogN)$ using Alien's trick. Here's a good tutorial on it: http://serbanology.com/show_article.php?art=The%20Trick%20From%20Aliens
•  » » » 20 months ago, # ^ |   0 Wow! This is what I was looking for $O(NlogN)$ solution. Thanks a lot!
 » 21 month(s) ago, # |   0 Yeah, F can be solved in O(n^3).
 » 21 month(s) ago, # |   0 Hey could someone please take a look. I did the same thing as the editorial for Problem E but still getting WA.[Submission here](https://codeforces.com/contest/1409/submission/91884363)any help is appreciated, thanks!
•  » » 21 month(s) ago, # ^ |   +1 I think pts2 = upper_bound(all(xc),xc[next_ind]+k) — (xc.begin()+next_ind); should be replaced with a suffix MAX array
•  » » » 21 month(s) ago, # ^ |   0 I think both of them should yield the same result, is that incorrect? Anyway will try that!Thanks for your help!
 » 21 month(s) ago, # | ← Rev. 2 →   0 can someone help me the tutorial of Problem B ? .. I didnt get it ... or any better soln will be appreciated !
•  » » 21 month(s) ago, # ^ |   0 Well the tutorial says that if we decide decrease a by 1 in the step then it's better to continue to decrease a until we can and then start with b. Similarly if we start with b then keep on decreasing it until we can then start with a. consider both of the above cases and print the smallest product. Hope this helps:)
 » 21 month(s) ago, # |   0 Really Thank you so much SecondThread for your live video editorials. I have upsolved F problem by watching your solution. Live Video Editorital : https://www.youtube.com/watch?v=qgJ4KiQR4QY&t=2635s
 » 21 month(s) ago, # | ← Rev. 2 →   -11 Problem D — Can be solved in constant time (O(18)) ApproachFirst, find the sum of the digits as summMove from the first place digit (ones) to the higher one, check if summ — (sum from ones digit to current position) + 1 <= s(needed sum)if true: the answer n — (number if you make digit after ith 9 and add one to the result) ... Exampleif n = 500 and s = 4 all 3 digits should be 0 to make them zero the number should be increamented until 999 and adding +1 so 500 --> 1000 so the answer will be 1000-500 = 500 ... Python Implementationdef solve(n, s): n = str(n)[::-1] summ = 0 for i in n: summ += int(i) if summ <= s: return 0 else: summ1 = 0 for i in range(len(n)): summ1 += int(n[i]) if summ - summ1 + 1<= s: return int(n[::-1][:len(n)-i-1] + ("9"*(i+1))) + 1 - int(n[::-1]) for _ in range(int(input())): # Multicase n, s = list(map(int, input().split())) print(solve(n, s)) 
•  » » 21 month(s) ago, # ^ |   +27 This is the same time complexity as the intended solution.
•  » » » 21 month(s) ago, # ^ |   -9 I believe the editorial solution is actually O(18*18) as it goes through the array once to calculate the prefix/suffix and it also goes through the array to calculate the sum. To reduce the extra log(N) factor, an int could be used to keep track of the sum and just update it accordingly in between iterations. However, in the grand scheme of things, it doesn't really matter.
•  » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   -10 Yeah! I did the same solution mentioned above. It was really an easy problem for an D statement I guess.
•  » » 21 month(s) ago, # ^ |   0 It can also be solved with binary search.
•  » » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 Can you give me the link for the binary search solution. I thought in that direction during the contest but couldn't come up with the solution??Update: I saw your submission.
•  » » » 10 months ago, # ^ |   0 TimeTraveler Can you please explain how your Binary search solution works here?
•  » » » » 10 months ago, # ^ |   0 For a given number x, we need to check if we can make the sum less than s in moves <= x, i.e is there any number between n and n + x which has sum of digits <= s ? Then we can binary search over the value of x.
•  » » » » » 10 months ago, # ^ |   0 yeah I got it now and your implementation to check if a number lies in the range (n, n + x) whose sum of digits <= s is very clever and clean!. Thanks!
•  » » 21 month(s) ago, # ^ |   0 Please help me I am getting wrong ans in D solution:https://codeforces.com/contest/1409/submission/91972053Instead of making 9 from the digit where we get sum greater than or equal to sum i am increasing the previos value by one and making all zero from that digit .
•  » » » 21 month(s) ago, # ^ |   0 After hours of debugging, I got it.Try this test case:11992 118 can be added to make it 2000In this test case, the previous value is 9 (the first from the left), so when u add 1 to 9 it becomes 10. Then the array will be [1, 10, 0, 0]. when u concatenate these values to string the number will be 11000.Then the answer will be 11000-1992 = 9008 which is incorrect. 8 increments are enough.Hope u find it helpful.
•  » » » » 21 month(s) ago, # ^ |   0 Thank you so much brother
 » 21 month(s) ago, # | ← Rev. 2 →   0 1409E - Two Platforms I do not get the point why the y[] are in the statement. If it is obvious that we do not need them, then they are obviously unnecessary. If it is not so obvious then it is a misleading statement. So, why?
•  » » 21 month(s) ago, # ^ |   +19 spookywooky I do not get the point why this comment is under the editorial. If it is obvious that we do not need it, then it is obviously unnecessary. If it is not so obvious then it is a misleading comment. So, why?
•  » » » 21 month(s) ago, # ^ |   +4 I mean, I don't think this makes sense. Clearly spookywooky thought we do need the comment, so your clever response isn't actually valid.
•  » » » » 21 month(s) ago, # ^ |   -8 I thought this legend needs $y$-coordinates as well as he thought we need this comment.Partially, your answer below is right, this part teaches to notice some probably useless things in the problem and to make some transitions from one problem to another. And yeah, this is essentially not the worst way to allow repeated $x$-coordinates.
•  » » » » » 21 month(s) ago, # ^ |   -19 https://codeforces.com/contest/1409/submission/91894057can somebody please help me with this problem why it is giving the wrong answer? any help would be highly appreciatedThanks
•  » » 21 month(s) ago, # ^ |   +14 The y coordinates are of no use I agree but they are necessary as a part the author to chose to describe the original problem, sometimes some variables are just to help understand the actual statement clearly , but here these y coordinates are not misleading!
•  » » » 21 month(s) ago, # ^ |   +1 I do not think they are necessary in any way. The statement would be much simpler if formulated in 1 dimensional space. "Here are some x[], find two segments of size k covering as most possible of those points on x-axis, how much?"
•  » » » » 21 month(s) ago, # ^ |   +17 Unfortunately problems are not all supposed to be simple. You have to decipher for yourself what is important and what is not. Just because it was obvious to some does not mean that others don't make that connection, at least immediately.
•  » » » » 21 month(s) ago, # ^ |   0 This is not atcoder.
•  » » » 21 month(s) ago, # ^ |   +3 I don't know whether they are misleading or not, but they are definitely unnecessary.
•  » » » » 21 month(s) ago, # ^ |   +4 Unnecessary from readers point of view, think as a setter and you have this question in your mind but you have to plot a frame to fit it into an understandable statement. Now since everyone have different ways to describe the problem thus a statement in order to describe the original point of you may go in various directions. If you were a setter may be you would describe it in an easier fashion. But everyone cannot have same thoughts. Making a perfect problem statement that match thought of every participant is a tough kind of job. When we will jump into it we will realize the importance of clearity!
•  » » 21 month(s) ago, # ^ |   +37 One benefit of $y$-coordinates is that it makes it clear and unambiguous that we can have repeated $x$-coordinates, as well as overlapping platforms. However, the statement said platforms could overlap anyway, so yeah I'm not sure.Also, maybe it was intentional that they're unnecessary because the 2D to 1D transformation is something worth testing/teaching, especially in Division 3. In general, part of the difficulty of Codeforces problems does stem from transforming the problem into an equivalent but simpler one (in a way, this is all problem-solving).
 » 21 month(s) ago, # | ← Rev. 2 →   0 C can be solved in O(n) (approximately) but calculating the factors of the difference in x and y (which are basically possible values for final difference) and then selecting the smallest value that satisfies the conditions. After selecting the optimal smallest difference, the array can be easily constructed.Solution : 91852634
•  » » 21 month(s) ago, # ^ |   0 Yes, I just traverse from 1 to 100 and check two conditions. no need for factors. 91844711
•  » » » 21 month(s) ago, # ^ |   0 Yes, that will definitely work for the given constraints. Cool!I tried to come up with a solution that will work for bigger constraints without any modifications. Also, I couldn't think of such a straightforward and short approach (considering the small constraints) during the contest.
•  » » » » 21 month(s) ago, # ^ |   0 I think this is one of the most intuitive solution in O(n). 91880180
 » 21 month(s) ago, # | ← Rev. 2 →   0 For Problem D: Can anyone tell me what's wrong in the following approach: For example 217871987498122 10, traverse from starting digits, 2,1,7,8 and add them, when sum become greater than or equal to 10, that is on 7. increment one digit before 7 from 1 to 2 and rest all digits after it to 0, the number will become 220000000000000. if it violates on first digit then make 1000... this number. please help?
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 you need to stop when the sum becomes greater than or equal to S. In this test case, you are actually already doing that.Otherwise, the approach looks good to me. I've also implemented an almost similar approach.
•  » » » 21 month(s) ago, # ^ |   0 i had stopped, can you tell me, what's wrong in the code? 91871968
•  » » » » 21 month(s) ago, # ^ | ← Rev. 3 →   +10 I tried stress testing your submission against mine on random inputs and found that your code fails on some inputs. ExampleExample input: 1785120922 34Your Output: -1783335802Answer: 78Upon observing, it fails on all such inputs where the digit at which you stop is 9, so your code tries to increment it, but it fails, and ends up dropping the remaining digits altogether.
•  » » » 21 month(s) ago, # ^ |   0 I have the same kind of approach and with getting the position when the sum of digits from left when it surpasses s.next, I took three cases correspondingly possible to update the number, The solution worked fine in test case 1 & 2, but in 3 it is saying one of the output exceeded int64 format.Can you please help in telling what went wrong? please help? thanks submission:91894618(https://codeforces.com/contest/1409/submission/91894618)
•  » » » » 21 month(s) ago, # ^ | ← Rev. 3 →   0 Your code fails because of two very minor issues.Firstly you are not checking if the sum of digits is already less than S.By Changing if (sum_digits(n)==s) to if (sum_digits(n)<=s)Also, the inbuilt pow function can be inaccurate at large values since it uses floating-point values. By Changing nfinal+= b[k]*pow(10,18-k); to nfinal+= b[k]*( (ll)(pow(10,18-k) + 0.5));After making these changes, I submitted your code and it got accepted. --> 91898574
•  » » » » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Thank you for the help, I had been trying it for many times.:)
 » 21 month(s) ago, # | ← Rev. 2 →   0 O(n) solution for C: my submission: click here
 » 21 month(s) ago, # |   +4 My solution to C was as follows. I "stuffed" as many elements as I could betweeen x and y. Then I calculated this minimum difference and added some elements less than x. I would add as many as I could until I was done or these values became negative. In the case they became negative, I would add the remaining values above y. I believe this should be O(N)
 » 21 month(s) ago, # |   0 https://codeforces.com/contest/1409/submission/91894057can somebody please help me with this problem why it is giving the wrong answer? any help would be highly appreciatedThanks
•  » » 21 month(s) ago, # ^ |   0 In the loop where you work with Sum and carry stuff, you have put the check and increment condition w.r.t j where it should be in respect to i.As a result i is not changing therefore affecting your answer.
•  » » » 21 month(s) ago, # ^ |   0 Brother, You are too good. thanks for showing your generosity towards me. Got AC
•  » » » » 21 month(s) ago, # ^ |   +1 Always happy to help a fellow coder!!
 » 21 month(s) ago, # |   0 Can somebody explain me the greedy approach in problem F please....
•  » » 21 month(s) ago, # ^ |   +29 Let the string $t$ be be (begin and end). Sure, there is also a case where the letters of $t$ are equal, but it can be solved separately, or the solution could be carefully implemented to account for that.Now, suppose that we are going to make exactly $k$ moves. We have two kinds of useful moves: put b somewhere and put e somewhere. Let the number of b-moves be $b$, and the number of e-moves be $e = k - b$.Of all the ways to put exactly $b$ letters b, the most impactful way is to put them into $b$ leftmost places in the string... unless we change some e into b in the process. Let the number of e -> b moves we are going to make be $x$ ($0 \le x \le b$). So, with our b-moves, we pick $x$ leftmost letters e and change them into b, then pick $b - x$ leftmost letters which are not b and not e and change them into b.Similarly, when we are going to put exactly $e$ letters e, the most impactful way to do it is to put them into $e$ rightmost places in the string... unless we change some b into e. Let the number of b -> e moves we are going to make be $y$ ($0 \le y \le e$). So, with our e-moves, we change $y$ leftmost letters b into e, and also change $e - y$ leftmost letters which are not b and not e into e.What remains is to look over all possible tuples of $(b, e, x, y)$. Remember that $e = k - b$, so there are only $O (n^3)$ such tuples. For each of them, simulate the above greedy process (in linear time) and then find the answer (in linear time too). The total complexity is $O (n^4)$. A possible speedup is to precompute the required stuff for prefixes and suffixes, bringing it down to $O (n^3)$ or $O (n^2)$ (didn't actually try).Why we can assume $e = k - b$? If we actually do less than $k$ moves in the optimal solution, it means all the letters become b or e. So we can cheat: for the optimal $e$, we make unnecessary moves from the left, and then overwrite their results by exactly $e$ moves from the right. All in all, this greedy solution requires more observations than the dynamic programming solution, but requires less proficiency to come up with it.
 » 21 month(s) ago, # | ← Rev. 2 →   0 I tried solving problem D with another approach, It passed test case 1 and 2, but in test case 3 it's giving an error for an output which is not in format int64;Can anyone explain what is going wrong in my code that is giving me this error?Any help would be appreciated Thanks :)
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Got the issue fixed.91939751
 » 21 month(s) ago, # | ← Rev. 2 →   +1 1409C - Yet Another Array Restoration can be solved greedily in $O(n)$ instead of $O(n+\sqrt{y})$. Hint Find the largest $k  » 21 month(s) ago, # | +1 In 1409D - Decrease the Sum of Digits, if we maintain the digit sum, time complexity will be reduced to$O(\log n)$. Code (Python 3)import sys def read_int(): return int(sys.stdin.readline()) def read_ints(): return map(int, sys.stdin.readline().split(' ')) t = read_int() for case_num in range(t): n, s = read_ints() a = [0] + [int(i) for i in str(n)] ds = sum(a) cost = 0 idx = len(a) - 1 radix = 1 while ds > s: if a[idx] > 0: cost += (10 - a[idx]) * radix ds -= a[idx] a[idx] = 0 ds += 1 a[idx - 1] += 1 i = idx - 1 while a[i] >= 10: a[i - 1] += 1 a[i] -= 10 ds -= 9 i -= 1 radix *= 10 idx -= 1 print(cost)  •  » » 21 month(s) ago, # ^ | 0 couldn't you add radix *= 10 idx -= 1 to inside the while a[i] > 10 loops since you wouldn't need to consider those indices after you subtract them from them as they should equal 0?  » 21 month(s) ago, # | 0 Hi guys, I'm a python coder and I was wondering if someone could explain to me what's slowing my code down?It should work quite fast since each loop can only go 18 times, and it seems to work fast when I tested it. However, I keep running out of time on test 3. •  » » 13 months ago, # ^ | 0 Number of operations is$2 \cdot 10^4 \cdot 18 \cdot 18 \approx 6.5 \cdot 10^6$operations, and when you include the powers 10**(i+1) and 10**i, as well as the fact that pypy bigint's are pretty slow, it's too much for python to handle I guess.I tried submitting it in Python3 instead, to solve the bigint problem, but that didn't work.It could've been easily fixed by having$100$or$1000$test cases maximum, but ¯\_(ツ)_/¯  » 21 month(s) ago, # | 0 Chinese tutorials updated.  » 21 month(s) ago, # | 0 Can someone tell me why my code is giving the wrong answer, please... Submission: https://codeforces.com/contest/1409/submission/91873431 Thank you.. big help •  » » 21 month(s) ago, # ^ | 0 For$10, 1$, your code if(sum == s && i!=v.size()-1) is triggered at$i=0$, so your shortcut to output "0" if(i == v.size()) fails. •  » » » 21 month(s) ago, # ^ | 0 got it.. thanks •  » » » 21 month(s) ago, # ^ | 0 still its giving wrong answer... after the correction https://codeforces.com/contest/1409/submission/91908966 •  » » » 21 month(s) ago, # ^ | 0 sorry my bad... i did a mistake  » 21 month(s) ago, # | +5 Similar problem to D.https://codeforces.com/problemset/problem/1143/B  » 21 month(s) ago, # | 0 I'm trying to understand the tutorial for Two Platforms, but I don't get what they mean by suffix maximum array and prefix maximum array. If anyone has the code for that in Java/Python that would help too. I'm trying to learn how to do dynamic programming but I still don't really get it.  » 21 month(s) ago, # | 0 Video Tutorial C:https://www.youtube.com/watch?v=FMu64hfwo3AVideo Tutorial B:https://www.youtube.com/watch?v=QJ0bHUT7qOc  » 21 month(s) ago, # | 0 My doubt is pretty naive. Still I want to know why wrapper class Integer/ Long array sorting is faster than primitive data types like int / long ? I know that primitive data type use quicksort internally in Arrays.sort(). Also, when to use primitive for sorting and when to use wrapper for the same.Also look at both of my submissions for E in this contest. Submission 1 getting TLE because of using Arrays.sort() in long[] array. My submission 91904739 Submission 2 passing system tests because of using Arrays.sort() in Long[] array. My submission: 91904938 •  » » 21 month(s) ago, # ^ | ← Rev. 2 → +1 In a nutshell, you can be hacked with an adversarial case that makes quicksort degrade to quadratic. Object sort uses merge sort instead which doesn't have this issue, but wrapper objects are slow and inconvenient.I think the best solution is to randomly shuffle before sorting (I have a prewritten safeSort method, you can see it here: 91830757). •  » » » 21 month(s) ago, # ^ | 0 Thanks for your reply. I got what the actual problem is. By the way, shuffling the array and then sorting it may (very rare) also cause TLE if the array after shuffling comes out to be the worst case for quicksort.  » 21 month(s) ago, # | 0 im new here, somebody knows why i haven't got rated, I got accepted in problem A but didn't get any rating yet, thanks, sorry if I miss anything, thankyou •  » » 21 month(s) ago, # ^ | 0 Wait for one more hour.  » 21 month(s) ago, # | +1 Then let's build suffix maximum array on r and prefix maximum array on l. For l, just iterate over all i from 2 to n and do li:=max(li,li−1). For r, just iterate over all i from n−1 to 1 and do ri:=max(ri,ri+1).In problem E — the editorialist tells to build suffix maximum array on r and prefix maximum array on l. But Why?? I understand the use of the prefix array and suffix array. Why to find the maximum prefix array and suffix array? •  » » 21 month(s) ago, # ^ | ← Rev. 2 → 0 Let's assume the answer is segL and segR (which do not overlap of course). Assume that there is a point midp which lies between two segments but do not overlap. We know segL stands on the left side of the midp and segR stands on the right side of the midp. Note that segR is the best platform possible on the right side of the midp otherwise the answer would contain the better platform (which means segR is not a valid solution). Greedly you can see the score of the best platform that is on the right side of the midp can be found using maximum suffix array. Also the the score of the longest platform that is on the left side of the midp can be found using maximum prefix array. This operation takes O(1) time if you have the prefix and suffix arrays. Now, because we don't know the midp, our goal is to iterate over all possible midps in O(n) time and store the best possible score. Please don't hesitate asking any questions I'm trying my best to make things clearer. •  » » » 21 month(s) ago, # ^ | +1 Thanks for your reply. I understood it.  » 21 month(s) ago, # | 0 Can someone share some thoughts about how$F$can be solved when length of$t$is arbitrary. During contest i didn't read the part that length of$t$is fixed and is 2. I kept trying to solve it for t of arbitrary length and when after the contest i read that length of t is fixed i realised it was trivial (: for length t = 2.  » 21 month(s) ago, # | 0 @vovuh I did array restoration in o(n2) and it is simple https://ide.codingblocks.com/s/328390 •  » » 21 month(s) ago, # ^ | 0 I think 91880180 is more simple. O(n) •  » » » 21 month(s) ago, # ^ | 0 can u explain •  » » » » 21 month(s) ago, # ^ | 0 civil_eng0003 This is more intuitive solution https://www.youtube.com/watch?v=j6r3NYWOrjs  » 21 month(s) ago, # | 0 Question about problem B. How can we proof that we need to decrease firstly one number and only then second one. Why greedy? Why we cannot decrease for example first — second — first -second -second — first ...? •  » » 21 month(s) ago, # ^ | 0 That is because let's say a>b, then consider two consecutive operation. If you decrease the value of b in two consecutive operations, the product value will change by 2*a( a*(b-2)=a*b-2*a --> difference of 2*a ). If you first decrease a and then b, then the product will be (a-1)*(b-1)=a*b-a-b+1. So the decrease in value is a+b-1. Since, a>b then difference is clearly greater in first case.(a+b-1<2*a). •  » » » 21 month(s) ago, # ^ | 0 Thanks! •  » » 21 month(s) ago, # ^ | ← Rev. 3 → 0 That's a shame that the editorial is missing the proof.We claim that in the optimal case all the operations have been applied to a single integer unless it has reached its minimum.Proof by contradiction. Assume that both integers have decreased and none has reached its minimum. Let$a \leq b$. Then if one of the operations is performed on$a$instead of$b$(so that the total number of operations does not increase) the product$ab$will decrease. Indeed$(a-1)(b+1)=ab + a - b - 1 < ab\$.
•  » » » 21 month(s) ago, # ^ |   0 Thank you very-very much!!!
 » 21 month(s) ago, # |   0 A slightly different and a bit easier to understand (maybe?) implementation of E. 91876338. :)
 » 21 month(s) ago, # |   0 Regarding problem E. Two Platforms, I used TreeMap to solve. Them time complexity is also O(N log N), but it is TLE. I got stuck on investigating the cause. Could anyone help me to have a look? thanks.https://codeforces.com/contest/1409/submission/91911507
 » 21 month(s) ago, # |   0 Problem B :Need to press enter for n to get the last test case(Otherwise it just waits for input) for which im getting tle. Code https://codeforces.com/contest/1409/submission/91910842 . Can some1 point out the problem please?
 » 21 month(s) ago, # |   0 Really need help trying to figure what went wrong on test case 3. Was unable to figure out throughout the contest.
 » 21 month(s) ago, # |   0 Solution Videos : problem A : https://www.youtube.com/watch?v=SC_x74jJ2Doproblem B : https://www.youtube.com/watch?v=euDkPcB7bdcproblem C : https://www.youtube.com/watch?v=7fYsv4gFA5QProblem D : https://www.youtube.com/watch?v=sduhfv70VJ0
 » 21 month(s) ago, # |   +4 Why this greedy approache for F is wrong?Can you help me?Detail:Suppose we change i positions into t[0],and i2 into t[1].Let's greedy:The i positions which are changed into t[0] is as small as possible,and the i2 positions which are changed into t[1] is as big as possible. (If s[i]=t[0]/t[1] ,it doesn't need to be changed).Code: Spoiler/* {By GWj */ #pragma GCC optimize(2) #include #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a>a #define R2(a,b) cin>>a>>b #define check_min(a,b) a=min(a,b) #define check_max(a,b) a=max(a,b) using namespace std; const int INF=0x3f3f3f3f; typedef pair mp; /*} */ string s,t; int main(){ int n,k; R2(n,k); R2(s,t); LL res=-1; rb(i,0,k){ rb(i2,0,k){ if(i+i2>k) continue; string cpy=s; int cnt=i; rep(j,n){ if(!cnt) break; if(cpy[j]==t[0]) continue; cnt--; cpy[j]=t[0]; } cnt=i2; rl(j,n-1,0){ if(!cnt) break; if(cpy[j]==t[1]) continue; cnt--; cpy[j]=t[1]; } LL rest=0; int cc=0; rep(j,n) { if(cpy[j]==t[1]) rest+=cc; if(cpy[j]==t[0]) cc++; } check_max(res,rest); } } cout<
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   +6 i did a greedy approach too and it was like you said the t[0] position should be the least and the t[1] position should be the last but there is a problem maybe we have some character t[0] in the end of the string not exactly the last character but lets say the second half of the string lets say t[0] = a and t[1] = bthere can be a situation like this : aaa .. b .... (a) .. bb in this case its better to change (a) to (b) to get more occurrences.in my solution i count if we change the i position to t[0] or t[1] how much we can get and how much we loss as we can see in the sample if we change (a) to (b) then we get 3 more occurrences and loss 2 occurrences and its good but some times its not however my solution got wrong answer in testcase 41 :))))
•  » » » 21 month(s) ago, # ^ |   0 Thank you very much.I have completely understand.
 » 21 month(s) ago, # |   0 For problem D, why do we need to have(10−dig)%10 moves instead of (10−dig) moves? As dig=n%10, is that %10 really necessary?
•  » » 21 month(s) ago, # ^ |   0 dig can be 0 as well so (10-dig) will give you pw*10 instead it should be pw*0
 » 21 month(s) ago, # |   0 For the third question i got tle in the contest...but i submitted the same solution it worked now please check this https://codeforces.com/contest/1409/submission/91922785
 » 21 month(s) ago, # |   0 Runtime error on test case #6 for Quesion D Could someone please explain the reason, I couldn't find . Thanks a lot! Here is the link to my solution : https://codeforces.com/contest/1409/submission/91924509
 » 21 month(s) ago, # |   0 Can someone help me with F. My dp[ind][k][left] states that we are at index 'ind', we can do atmost k changes, and we have left occurances of t[0] from [0:ind-1]. Then my answer will be dp[0][k][0]. My transition are, either change current character to t[0], or t[1] or don't change at all. I am getting wrong answer at testcase 20. My submission 91926014
 » 21 month(s) ago, # | ← Rev. 4 →   0 Binary Search Solution for DFor some reason spoiler isn't working properly.
•  » » 18 months ago, # ^ |   0 Thanks for sharing your code. I did pretty much the same thing but get TLE https://codeforces.com/problemset/submission/1409/99688938
•  » » » 18 months ago, # ^ |   +3 Try using lambda function.
•  » » » » 18 months ago, # ^ |   0 But why should it make a difference?
•  » » » » » 18 months ago, # ^ |   +3 Lambda functions are a bit more efficient.
•  » » » » » 18 months ago, # ^ | ← Rev. 2 →   +3 This submission with your code(with less arguments) got accepted. Also this got accepted. The former with lambda functions ran slightly faster.
•  » » » » » » 18 months ago, # ^ |   0 Never saw this happen before...Thanks though
 » 21 month(s) ago, # |   0 Dear, MikeMirzayanov Please Check Why all my Correct Solutions got Skipped. I had submitted 3 Solutions in Yesterday Div 3. Contest and they were correct but saw today all were skipped which dipped my rating a lot. Please Check why Did it happen.
•  » » 21 month(s) ago, # ^ |   +1 pranshukas Because you sumbit your code again in your alt account enigma_13 to hack them afterword.(Remember hacks in div3 give no points).
•  » » » 21 month(s) ago, # ^ |   0 I know that hacking any solution don't give any points. I was new to it so I thought to learn it. That's Why I just submitted my own solutions form some other ID and give it a try. I thought it was in no way harming any policy and it wasn't any mischief either because I haven't cheated, nor Plagrised. Then Why did my Submissions got Skipped?
•  » » » » 21 month(s) ago, # ^ |   +5 Did you read the rules of the contest before participating ? If not then the last rule says: "I will not use multiple accounts and will take part in the contest using your personal and the single account".
 » 21 month(s) ago, # |   0 Nice Contest! Too much hard for noob like me, but tutorial is very helpfullll. HAPPY CODING.
 » 21 month(s) ago, # |   0 In the solution of Two platforms problem,why are we considering l[i]+r[i+1] rather than l[i]+r[i]?
•  » » 21 month(s) ago, # ^ |   0 Because the range is inclusive, and as we want to maximize the points we save, we never want to overlap the platforms, when going for l[i]+r[i], you're basically overlapping the right border of l and the left border of r, and thus, overcounting and not getting an optimal solution. I think once you read a couple times the last part of the editorial you'll understand.
 » 21 month(s) ago, # |   0 int the problem D we can do the recursive solution as well here is my solution link https://codeforces.com/contest/1409/submission/91941387
 » 21 month(s) ago, # |   0 I don't understand where the author says in problem E that li:=max(li,li−1) will help. Why? How? Can somebody explain it more clearly?
•  » » 21 month(s) ago, # ^ |   +1 Don't forget that you have calculated l and r beforehand.where li is the number of points to the left from the point i (including i) that are not further than k from the i-th pointAfter that you convert the same array to a prefix maximum array (ith element contains best possible value of elements in range(0, i)). By induction you can iterate from left to right and you can say that ith element of maximum array is either i-1th element or the new added element's value. Because the author didn't separate the two arrays it might get a little confusing. They just converted the array to aa prefix maximum array without assigning it to a new variable.
•  » » » 21 month(s) ago, # ^ |   0 oh okay I got it thanks!!basically maximum contribution upto i from left side + maximum contribution from i+1 to end in right side for each i, while i is the fixed barrier between the two segments(worst case they will share a common end).
•  » » » » 21 month(s) ago, # ^ |   0 Exactly. But I don't think worst case is sharing a common end. The algorithm will always run n times on an array.
•  » » » » » 21 month(s) ago, # ^ |   +1 yeah, poor choice of words there actually! I meant extreme case if they share common end not overlap
 » 21 month(s) ago, # |   +1 I think the explanation of Problem E is a little hard to understand. I think the key point of this question was "Dividing the number line into two segments.". The answer is the best platform that lies in the left segment + the best platform that lies in the right segment. Simply iterate over all possible divisions and the best result is your answer. I couldn't understand the solution when I read this explanation but when I watched SecondThread's video I really understood the problem.I also really liked the difficulty levels of the first 4 questions.
 » 21 month(s) ago, # |   0 I was trying to solve problem F. I came up with a solution but don't know if it is correct. I'm having hard time implementing it.The idea is this:Input: n = 7 k = 3 s = "asddsaf" t = "sd" now for s, we calculate 2 arrays, left and right, where, left[i] means how many t[0] appear on left side of s[i] not including s[i] itseld, ans similarly right[i] means how many t[1] appear on right side of s[i] not including s[i].For above test case: a s d d s a f left --> 0 0 1 1 1 2 2 right--> 2 2 1 0 0 0 0now we start changing characters in following way: i -> left pointer, initially at 0 j -> right pointer, initially at n-1; when left[i] < right[i], it means that changing s[i] to t[1] will be good; when left[j] > right[i], it means that changing s[i] to t[0] will be good;In above 2 case, we go with whichever has higher absolute difference when both are equal we try to make counts of t[0] and t[1] equal. if anywhere k = 0 , we stopthen our answer is sum of number of t[1]'s to right side of t[0]'s in our modified s.Kindly tell me if it's correct or where it is wrong.
 » 21 month(s) ago, # |   0 What is the proof for the fact in problem B solution ?
•  » » 21 month(s) ago, # ^ |   0 Assume you are going step by step (decrease 1 at a time) and a > b (you can switch them very easily in code).if you decrease a, the final product will be (a-1)b = ab — b if you decrease b, the final product will be a(b-1) = ab — abecause a > b, decreasing a from ab will result in a smaller product then decreasing b from ab.The problem starts when a=x. After a=x, you start decreasing from b. I don't think you can have a solid proof of which is optimal without starting from a or starting from b after this point. Therefore try both possibilities.
 » 21 month(s) ago, # |   0 What is 1ll in editorialist solution? ans = min(ans, (a — da) * 1ll * (b — db));
•  » » 21 month(s) ago, # ^ |   0 LL stands for long long data type. It basically returns 1 as a long long instead of integer default.
•  » » » 21 month(s) ago, # ^ |   0 Thanks but why it is used here?
•  » » » » 21 month(s) ago, # ^ |   +1 Because both a and b are integers that may be up to 1e9, so the multiplication would be up to 1e18, meaning it would overflow, that's the reason we want to convert it to long long.
 » 21 month(s) ago, # |   0 In the solution code of problem C (Rox); the condition diff/delta + 1 > n Can someone explain it for me?
•  » » 21 month(s) ago, # ^ |   0 i.e x=4, y=16, n=5 when diff=1 you can get 16 — 4 = 12 so you need to have 12 — 1 = 11 integers to fill that gap. Thats why you check if you have enough integers to fill that gap.
 » 21 month(s) ago, # | ← Rev. 2 →   0 I want to verify that the following solution for problem E is correct.First, If we can cover all points, then answer is n. this is easy.otherwise, Let V be a vector of pair such that V[i].first = a given x position. V[i].second = number of points at position V[i].first. This vector is sorted w.r.t. x positions The idea is that we should put the left border of the first platform at one of the positions V[0].first, V[1]. first, ... so we try all of themcur_best := 0left_border_pos = -1 right_border_pos = infFor all i we calculate the last j such that V[j].first <= V[i].first + k using binary searchcount the number of points at position range(V[i].first, V[j].first)if this number is bigger than cur_best then update cur_best and border position variablesend loop Now, we know the best way to put the first platform.I repeat the previous steps for the second platform but I do not allow overlap between the two platforms. If this solution is logically correct, then why this code is not accepted?I know it's very bad written but It's easy to understand I guess.
 » 21 month(s) ago, # | ← Rev. 2 →   0 Please help me I am getting wring ans in D solution:https://codeforces.com/contest/1409/submission/91972053
 » 21 month(s) ago, # |   0 How to solve F with bigger constraints? I was trying to solve for O(n^2) solution but couldn't make significant progress.
 » 21 month(s) ago, # |   0 I found this solution for F to be much simpler to understand than the one in the editorial.
 » 21 month(s) ago, # |   0 prob -D this is my code and please tell me how to remove TLE in my code https://codeforces.com/contest/1409/submission/92060096
 » 21 month(s) ago, # |   0 I felt soo dumb on myself when i did the correct thing but wasted 45 min and 5 WA submissions for erasing the vector for graph only upto n-1 and not n,on question D.
 » 21 month(s) ago, # |   0 In problem 1409E - Two Platforms I couldn't find why my logic is wrong!In the submission page, I can't see the test cases.Here is my submission 92089145. Can anybody give me any test cases for which my approach is wrong?
 » 21 month(s) ago, # | ← Rev. 2 →   0 vovuh Sir can you suggest few problems similar to E
•  » » 21 month(s) ago, # ^ |   0 yeah , i hope that
 » 20 months ago, # |   0 Is there a way to solve Problem C in O(n) time?
•  » » 20 months ago, # ^ |   0 refer my solution its O(n)https://codeforces.com/contest/1409/submission/92122521
 » 20 months ago, # |   0 guys I am newbie..can anyone explain problem D in much simpler way with an example test case
 » 20 months ago, # |   0 92209053 I am getting a time limit exceeded on test case 5, problem E. I am using Java and I am not sure what should I do to avoid this error. Any help please?
 » 20 months ago, # |   0 can you explain why there is line int k = min((y — 1) / delta, n — 1); int a0 = y — k * delta;in question 1409C tutorial 3 example1409C][USER:VOVUH - Yet Another Array Restoration
 » 20 months ago, # |   0 I am not able to understand how dp is working in this question 1409F — Subsequences of Length Two ? I have written the top down dp but bottom up is somehow not making sense to me . Is there any better way to understand it .
 » 20 months ago, # | ← Rev. 2 →   0 del
 » 20 months ago, # |   0 https://codeforces.com/contest/1409/submission/93888937 why it is not working I tried to use the binary search to reach a convenient endpoint for the left and right arrays
 » 20 months ago, # |   0 can anyone explain f, if we take dp[i,k,2] where 2 represents that t[0], t[1] how many times i have got.
 » 20 months ago, # |   0  ~~~~~ ll dp[201][201][2];int main() { fastio; ll n,k; cin>>n>>k; string S,T; cin>>S>>T; dp[0][0][0] = 0; dp[0][0][1] = 0; for(int i=0;i
 » 20 months ago, # |   0 isn't D) part O(log (n)) because the for loop is constant time and sum func takes log10(n) ???
 » 19 months ago, # |   0 Can someone please explain to me why my solution for D doesn't work?https://codeforces.com/contest/1409/submission/96948321It easily passes tests 1 and 2, as well as the edge cases, but returns an error for test 3. I'm basically rounding up to powers of 10 and testing whether the result has a lower or equal digit sum to what is needed.
 » 15 months ago, # |   0 Can anyone explain what the below line in Rox's solution actually checks?if (diff / delta + 1 > n) continue;And also what is the time complexity of his solution?
 » 14 months ago, # |   0 def fn(s,n): chars = [] for c in s: chars.append(int(c)) sums = sum(chars) #print(sums) if sums <= n : return 0 m="" j = len(s)-1 while sums >= n : # print(sums,j,m) sums-= chars[j] m = "0"+m j-=1 if j == -1 : m = "1" + m else : left = s[:j] m = left + str(chars[j]+1) + m # print(m) return int(m) - int(s) for _ in range(int(input())): [s,n] = input().rstrip().split(" ") print(fn(s,int(n))) Can anyone give a single test case where I am failing? Tried with almost 100 cases my answer seems correct
 » 13 months ago, # |   0 How can one justify that the approach in problem "1409B — Minimum Product" will result in minimum product?
 » 11 months ago, # |   0 Here is my solution to help for problem C .. Hope it helps ;) int main (){ fastio();int test =1 ; cin >> test ;while(test--){ ll n ; cin >> n; ll x , y ; cin >> x >> y ; if (x>y)swap (x , y) ; if (n==2){ cout << x << " " << y << nline ; continue ; } ll ra = 0 , rd = 0 , rmin = INT_MAX ; for (int a = 1; a<= x; ++a){ for (int d=1; d<=y ; ++d){ if (a+(n-1)*d < y){ continue; } else if ((x-a)%d==0 && (y-a)%d==0){ rmin = min (rmin , (a+(n-1)*d)) ; if (rmin == (a+(n-1)*d)){ ra = a ; rd = d ; } } } } int tmpn = 1; while (tmpn <= n){ cout << ra+(tmpn-1)*rd << " " ; ++ tmpn; } cout << nline;}}
 » 11 months ago, # |   0 Can somebody help me in memoizing this code for problem F although this is working for all the small constraints that are given in the question. But I am not able to memoize this code for the larger constraints.Link to my code- https://codeforces.com/contest/1409/submission/121002071When I try to memoize this code by taking "i" and "k" as the dp states it is not working. So can anyone please tell my how I can make dp state for the above code.
 » 9 months ago, # | ← Rev. 3 →   0 Sorry, wrong contest. XD