A great competition with hacking :)

Сразу видно, что тесты русский писал. Кроме 1337 и 69, еще присутствует 228 :)

Can someone explain one of the multiset solutions to E? Thanks!

Nice problems, but the gap between problem ABCD and EF seems too large.

Good problems!(But E,F is too difficult!) And I get to expert！

Still don't understand editorial of D, can anybody explain the two pointer technique?

galen_colin too

I submitted 120147862 for Problem-C. It gave a wrong result on test 62 in GNU C++17. When I submitted the same code in C++11, it was accepted (120149347).

It would be helpful if anyone tells me what went wrong in my code.

The difficulty range is very large,

For example, D through E

The difficulty range is very large,

For example, D through E

In problem E, i thing that it's hard to come up with such dp state. Does anyone have a more natural idea for this problem ?

120173484 I am getting runtime error on test 23 in problem C. Unable to understand if it is due to seg fault or overflows. Can someone pls explain

Can anyone check my submission for D. Its giving TLE at tc 11 and it seems that its because of initial sorting itself (and not even entering while loop).

I found D to be a lot easier to think about using binary search (which solves in $$$O(n\log(10^{14}))$$$. Similar to the editorial, sort with respect to $$$b_i$$$. Now, let $$$x$$$ be the number of items with price $$$1$$$ and $$$y$$$ be the number of items with price $$$2$$$. Then, our answer is equal to $$$x + 2 \cdot y = y + \sum_{i = 1} ^ {n} a_i$$$, so it suffices to minimize $$$y$$$.

Let's binary search on this. Suppose we set $$$y = k$$$. How do we know if this is enough? First we make two simple observations:

• We buy all $$$k$$$ items at the very beginning.

• We buy all $$$k$$$ items from a suffix of the sorted array.

Why does this work? Well, if you are going to buy $$$k$$$ items of price $$$2$$$, you should do it earlier than later, because then we might have more $$$b_i$$$ opened up that gives us items of price $$$1$$$. Similarly, we should be buying our items from a suffix because that way we can maximize the number of items of price $$$1$$$ we get (and, subsequently, minimize the number of items of price $$$2$$$).

From here it's simple to solve with binary search. To test $$$y = k$$$, start a counter for the number of items bought and an index at $$$0$$$. While the counter is greater than $$$b_{\text{index}}$$$, add $$$a_{\text{index}}$$$ to the counter (since we're getting all of those for price $$$1$$$) and increment the counter. If $$$k$$$ is enough, then the counter should be $$$\geq$$$ the number of items we have in total.

This explanation may seem a bit complicated, but the ideas involved are simple to arrive at and the implementation is very clean: my submission here.

I have a different way of implementing problem D that is more concise. Considering buying items backwards, we want to the last item we buy is the item with the highest discount requirement(which can be achieved). Which means all we need to do is suppose we have already bought all the items and the number of items is $$$num$$$. Sorting $$$b_i$$$ in non-decreasing order, skip the items that are impossible to get a discount on and take $$$num_i = \min(num-b_i,a_i)$$$ as the number of $$$item_i$$$ which we can buy with a discount. Remember to substract $$$num_i$$$ from $$$num$$$. After iterating $$$i$$$ through all the items, the sum of $$$num_i$$$ is the total number of item that we can get a discount on.

The code goes like this:https://paste.ubuntu.com/p/8mwW8n2yfQ/

Test:

5
3 10
2 12
1 11
3 10
1 8

Submission: 120129309

Output : 20 Correct Output: 19

This submission is getting accepted but however the above test case shows wrong output. Correct Output should be 19, instead of 20.

mutant

Problem D

Proof that buying more items of some product than needed doesn't make the answer better. Let's suppose we have already achieved an product (say product A) which we can buy at discount. Now consider we have to buy next product (say product B).

N be the number of product B we have to buy, and d be the total purchases required before discount and c be the amount of items we have already purchased. Then,

Case I (buy more of product A and then B)

Total cost for buying product B = (d-c)*1 + (N*1) = d-c+N

Case II (only buying product B)

Total cost for buying product B = 2 * (d-c) + ( N-( d-c ) ) = d-c+N

So both the cases cost the same. But this is a special scenario. If we had different percentage of discount, then the above cases wouldn't be equal.

If we say m as discount percentage and x as normal price then,

Case I

mx(d-c) + Nmx

Case II

x(d-c) + (N-d+c)mx

Equating both cases, we get m = 0.5 or 50%..

So only when the discount percentage is 50%, buying more of a discounted product or buying only the required quantity of each products doesn't matter. Hence also in this case, doesn't matter.

Sorry for writing just the obvious algebra but wanted to share anyway :)

in E

• Card in query i fits constraints on value written on card in left hand in queries with indexes [i,j).

i think it's [i,j] isn't it ? Because we have card in i for query j too

hai.. where my code gone wrong..? please help me..
for problem C
thx code

Explanation to E sounds like it would be possible to explain it in an understandable way.

If there is an item which costs 1, then we will not make the answer worse by buying this item.

Why is that? For example, consider a situation where we've already bought all items, except for one, and it costs 2, and to make it cost 1 we need to buy 2 more items. In that case it would be cheaper to buy one left item and spend 2 instead of buing two more random items at cost 1 and finally buing one last item, spending 3 in total.

Although E and F was more difficult than the rest, the contest was great. First time reach to Expert!!

Sr about my bad Eng :p

Hey, can anyone help me with problem C. Don't know why is it giving WA on test 10. Below is my submission — 120223010. I have used the same approach, except that I have taken The number of elements required to fill the gap as floor((d-1)/x).

Can anyone tell me where am I doing wrong? I am getting wrong answer on test case 10. Problem C. Submission : 120227942

Can someone please tell me what my mistake is in problem D? My submission Thanks in advance!!

Can someone help me with Problem D? My submission is

https://mirror.codeforces.com/contest/1539/submission/120232784

Thanks in advance!

In problem C i ran the code in PyPy3 the code got TLE in test case 18 but when I ran the same code in Python3 the code got accepted Can anyone clarify why did that happen?

In problem C Java solution with Long[] array gets accepted, but long[] array solution gets TLE. (16th line in both solutions)

ACC: https://mirror.codeforces.com/contest/1539/submission/120284760
TLE: https://mirror.codeforces.com/contest/1539/submission/120284797

Could someone explain me why reference type works faster than primitive in this example?

I had a hard time understanding the tutorial for problem E. This is my attempt at making it easier to understand.

Easier problem: jump game

Consider this easier problem: you have an array $$$x$$$ where $$$x[i]$$$ means what the farthest is that you can jump from position $$$i$$$. Is it possible to reach the last element in the array if you start from position 0?

We can solve it with a DP where $$$dp[i]$$$ = can we reach the end if we start from position i? The solution to the problem is then equal to $$$dp[0]$$$. The transitions are like this: $$$dp[i]$$$ = $$$dp[i + 1]$$$ $$$||$$$ $$$dp[i + 2]$$$ $$$||$$$ ... $$$||$$$ $$$dp[i + x[i]]$$$. There are $$$N$$$ states and the transitions are $$$O(N)$$$ so this runs in $$$O(N^2)$$$.

We can make every transition $$$O(1)$$$ with a greedy insight. Instead of checking $$$dp[i + 1]$$$, ..., $$$dp[i + x[i]]$$$ we only need to check $$$dp[j]$$$ where $$$j$$$ is the leftmost position from which we can reach the end. The reason this works is that the leftmost position from which we can reach the end has the best probability of being within our jumping range. We can keep track of this leftmost position as we compute each state in a bottom up fashion.

int leftmost_possible = N - 1;
for (int i = N - 2; i >= 0; --i) {
  if (leftmost_possible <= i + x[i]) {
    dp[i] = true;
    leftmost_possible = i;
  }
}

Back to problem E

We can again solve this with an $$$O(N^2)$$$ DP where $$$dp(x, y)$$$ = can we finish if card with index $$$x$$$ is in the left hand, and card with index $$$y$$$ is in the right hand (and we have just answered query $$$max(x, y)$$$).

We can notice that we can reduce the number of states to $$$N$$$. Because if we are at $$$dp(x, y)$$$ (WLOG $$$x \gt y$$$) then

• either we will keep replacing the card in the left hand until we reach the end
• or at some point we have to take something in the right hand and we transition to state $$$dp(k, k + 1)$$$

So if we are at state (x, y) then in the next step either we are done, or we will transition to $$$dp(k, k + 1)$$$. Therefore (since we start at state $$$dp(0, 1)$$$) we will only visit states of the type $$$dp(k, k + 1)$$$ (and $$$dp(k - 1, k)$$$), and there are only $$$O(N)$$$ of those.

The transition is now $$$O(N)$$$ because we have to consider every $$$k$$$ such that $$$dp(k, k + 1)$$$ works. But with the same greedy insight as in the jump game problem we can reduce that to $$$O(1)$$$. Again we can store "the leftmost k that works" as we compute the states and therefore we can find the transition in $$$O(1)$$$.

Now of course in this problem another hard part is to compute the "maximum jump length" at every position. In the jump game problem this was given in the input, whereas here we have to compute it. For sure you can do it in logarithmic time with a segment tree (I saw it in Colin Galen's video). But apparently you can also do it in $$$O(1)$$$ since the solution runs in O(N) according to the tutorial. I didn't think about optimizing that part yet.

I have used 2 the same method as used by most of the other coders but my code is giving tle. Can please someone look and tell me why it is? 120407076

How to achieve time to be O(n) in question E? I'm very confused.

Can someone please help me with problem A?? Can't understand the solution give.

I'm glad I didn't participate in this one officially. Problem C was easy but I kept getting a TLE for stupid language-specific reasons:

• My Python solution got TLE on test 18 with PyPy3, but the same code passed with Python 3.

• My Java solution got TLE on test 61, but passed if I changed long[] to Long[]. (This is kind of my fault for not knowing Java uses a worst-case O(n^2) sort for primitive arrays.)

• My C++ solution passed with no special optimization.

In my opinion that's an indication that the time limit is overly strict, especially for an ABC problem.

122552751 why my solution A is not correct ? ans1 is Editorial solution ans2 is my solution

I checked my ans2 in many times. but ans1 equals ans2..
~~~~~ import random k = int(input()) for _ in range(k): n = random.randint(1,2*1000000000) x = random.randint(1,2*1000000000) t = random.randint(1,2*1000000000) tmp = t//x ans1 = max(0,n-tmp)*tmp + min(n-1,tmp-1)*min(n,tmp)//2 ans2 = tmp*n — tmp*tmp + tmp*n — ((2*n-tmp+1)*tmp)//2 if ans1 != ans2: print(ans1,ans2) ~~~~~

Is it possible to implement D using ternary search ??

is it possible to implement D using ternary search ??