r[r.length() — 1]++; I guess this line is what causing error when r="" that is length = 0, r[-1] will give segmentation fault

+1 thanks

Don't spam the editorial blogs with these dead memes dude.

pow() doesn't always give the right answer, because it was intended to work with doubles, not integers

if u want to use pow for high powers u can typecast with long long int , whichs works quite effectively.

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-2

In 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>a

Then ab+1-a-b > ab-a-b > ab-2b (because a<b)
So you now saw first case gives bigger product than 2nd case.

Similarly you can prove for other pair of cases too.

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*a

I guess you can see why decreasing one as much as possible is optimal.

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.

$$$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)$$$.

You can binary search to find the maximum index can reach from each index i and store data in two arrays X, Y

first 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 end

the 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.net/contest/1409/submission/91933328

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

I think pts2 = upper_bound(all(xc),xc[next_ind]+k) — (xc.begin()+next_ind); should be replaced with a suffix MAX array

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:)

This is the same time complexity as the intended solution.

It can also be solved with binary search.

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?

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!

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).

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.

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.

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.

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 ¯\_(ツ)_/¯

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.

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).

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.

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] = b

there 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 :))))

dig can be 0 as well so (10-dig) will give you pw*10 instead it should be pw*0

Thanks for sharing your code. I did pretty much the same thing but get TLE https://codeforces.net/problemset/submission/1409/99688938

pranshukas Because you sumbit your code again in your alt account anonymouse_13 to hack them afterword.(Remember hacks in div3 give no points).

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 point

After 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.

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 — a

because 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.

LL stands for long long data type. It basically returns 1 as a long long instead of integer default.

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.