ch_egor's blog

By ch_egor, 6 months ago, translation, In English

Thanks for the participation!

1539A - Contest Start was authored and prepared by grphil

1539B - Love Song was authored by jury and prepared by _tryhard

1539C - Stable Groups was authored by Artyom123 and prepared by Artyom123 and shishin

1539D - PriceFixed was authored by Helen Andreeva and prepared by Siberian

1539E - Game with Cards was authored and prepared by TeaTime

1539F - Strange Array was authored and prepared by Tikhon228

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +79
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

A great competition with hacking :)

»
5 months ago, # |
  Vote: I like it +34 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you show any multiset solutions which passed ?

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    Consider dpL[i][j] (different from the one from the editorial) as equal to 1 if it's possible to take the first i cards, ith one in the left hand, and j being the last card we took in the right hand (j<i). And, dpR[j][i] as equal to 1 if it's possible to take the first i cards, last one in the right hand, and j being the last card we took in the left hand. then, instead of storing the whole array, let L[i] be a set (or multiset) of pairs of <k[j],j> such that dpL[i][j] is 1, (and the same for R[i]). Now, if we're at step i and know L[i] and R[i], let's try to compute L[i+1] and R[i+1]: Let's focus on computing L[i+1], for R[i+1] it's similar: if (i+1)th card can't go in the left hand, then L[i+1] will be empty, let's assume it can go there. Let's also assume that the (i+1)th right hand can take any card, we'll fix that later. Then, first of all, if the set R[i] is not empty, we should add the pair <k[i],i> to L[i+1], that's because we can go from having the cards from (j, i) to (i+1, i) by taking the i+1th card in the left hand. And, let's also add to L[i+1] all the pairs from L[i], because we can get those by going from (i, j) to (i+1, j). Now, I assumed that the (i+1)th right hand can take any card, while in reality it can only take those whose k is between ar[i+1] and br[i+1]. So, let's erase from L[i+1] the pairs that are not valid. Since it's a set, we can just erase the smallest card values and the highest card values from the set which are not in the interval. This might seem like it's too slow, but it's actually amortized, because at each step, we only add at most one new pair to the set ( the pair <k[i], i> ), and delete some of the pairs which aren't valid. I'm not sure if I explained this very well, I hope it's clear.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Ah, I see thanks a lot! It was very clear :)

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for explanation. But I can't understand why I should use dp? Can you please give some idea on this ? Or just tell me the naive approach by which i can solve the problem? Like naive dp approach

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        A naive dp approach using the same dp I described above would be: dpL[i][j] (j<i) is true if, obviously, ith card can stay in the left hand (at step i), and jth card can stay in the right hand (at step i), and either:

        • j < (i-1), and dpL[i-1][j] is true

        • OR j == (i-1), and there exists such k < (i-1) so that dpR[k][i-1] is true

        And similarly for dpR. After calculating this, you can easily recreate the solution from right to left.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it +10 Vote: I do not like it

      How will the following be represented according to these dp states?

      We can pick all the cards upto the ith card in the left hand but none of them in the right hand (in other words, all the queries are answered on the left hand upto the ith card).

      This would imply that there is no j such that dpL[i][j] is 1. But still we can answer all the queries upto the ith card.

      Edit: I thought a lil bit about it and I think we can use 0 as a dummy card (which basically means, by default we'll have 0 as a card in right hand if we don't pick any card in it). And yess, AC. Great explanation OFZ.

»
5 months ago, # |
  Vote: I like it +61 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    I think there is a mistake in the editorial of the Problem F.

    The editorial said if the $$$a_i$$$ is less than or equal to the median element then $$$ans = \left\lfloor\dfrac{cnt_R+cnt_M-cnt_L+1}{2} \right\rfloor$$$, but if I have an array that is $$$[1, 2, 3, 4, 4, 6]$$$, the ans of the number $$$4$$$ should be 1, and if you use the formula mentioned above, you may get a wrong answer 0.

    Could anyone tell me the correct formula?

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      The formula is correct, but it's for when the element come to the left of median. When element comes to right of median, other formula should be used which should give you 1. That's why we should take maximum from left & right.

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Thank you very much. You're right and I have solved this problem by using two distinct formulas.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it -6 Vote: I do not like it

      sorry

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I'm sorry but the median number is 4 according to the Problem F.

»
5 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    First we sort the array according to increasing order of $$$b_i$$$. Now, we maintain 2 pointers one at the start of the array(say $$$i$$$) and other one at the end(say $$$j$$$). Also, let's maintain two variables $$$cur$$$(stores number of products already taken), $$$ans$$$(stores the required answer).

    Now, we run a loop until $$$i\leq j$$$.

    If $$$cur\geq b_i$$$, there is no point to leave this product, so we buy all $$$a_i$$$ products with 50% discount and update our $$$cur$$$ and $$$ans$$$.

    If $$$cur\lt b_i$$$, then we start from second pointer i.e. $$$j$$$ and keep taking $$$min(b_i-cur,a_j)$$$ products for 2 rubles, if $$$cur\lt b_j$$$, otherwise for 1 ruble. We stop once we have $$$cur\geq b_i$$$. Update $$$cur,ans,a_j$$$ accordingly. If $$$a_j=0$$$, decrement $$$j$$$.

    My submission

    In this submission, I ran a loop until $$$i\lt j$$$ and checked $$$i=j$$$ condition separately but that isn't necessary.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      but when cur < bi I wonder if I can choose to continue buying (i-1)th product for 1 ruble or buying j-th product for 2 rubles. Will the 2nd option be more optimal than the 1st option?

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, second case will be optimal. Look at it this way, you have to buy as many products for 50% discount as possible. Now we know $$$i^{th}$$$ product has smaller $$$b_i$$$, so the condition for discount of this product will be fulfilled by taking lesser number of products for 2 rubles. Also it may happen that after taking $$$i^{th}$$$ product for 50% discount, products with higher $$$b_i$$$ can be taken for 50% discount without additional cost of 2 rubles. So, 2nd case will be optimal.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      While $$$i \le j$$$, not "until".

»
5 months ago, # |
  Vote: I like it +97 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Hey there, It is because of precision error differences in C++11 and C++17, So it is always advised to use long double instead of double. You will get AC in both versions with long double.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In these cases use this (val + d-1 )/ d instead of some ceil on double (Try to avoid doubles if you can do the same with int (precision issue)).
    In your case foo[i] = (jar[i] — jar[i-1] + x-1)/x will be good to go.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you. I'll try to avoid doubles in such cases.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I would suggest using a/b+((a%b)!=0) to get ceil value. See if a is divisible by b the brackets will return false which is 0, otherwise true which is 1, which get added to the quotient making the expression return ceil value.

»
5 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Problem B had more submissions than problem A .. Do people dont like adhoc problems ?...

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

The difficulty range is very large,

For example, D through E

»
5 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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 ?

  • »
    »
    5 months ago, # ^ |
    Rev. 7   Vote: I like it +10 Vote: I do not like it

    A more natural idea is to calculate limits for both hands from the end.
    Last move has no limits. The range for both hands of last move is from 0 to m inclusive.
    For the previous move check cases. Initially limits impossible m < k < 0.
    If you can take the card into left hand, then check, could you keep your right hand for the next move? If left card may be kept, limits for the right hand are the current limits for right hand. Otherwise right hand must be kept for the next move, so intersect current limits for right hand with limits for next move.
    The same for the right hand.
    Finally we check limits for initial situation, is pair (0,0) allowed.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't that exponential complexity? (two choices in every move)

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        The time is linear. Only limits for both hands (4 numbers) are calculated for each move

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Just return when the valid array size is 0. You cant use binary search when the size of the valid vector is 0. Reason: v.begin()=points to first element, v.end() points to next element of last ele.

    120176292

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I tried to submit your solution with just by changing the compare function in sort and it worked. Here is the submission have a look just compare it with your solution to see the changes I made.The problem was in how you are defining the compare function in sort. What I have understood is <= or >= is slower than < or > which is causing the problem. For more details please go through this blog

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks it passed. Wish i've known this before

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I also learnt it the hard way. After getting TLE on TC 11 twice during the contest and then submitting the same code in 8 different ways after the contest was able to figure it out.

»
5 months ago, # |
  Vote: I like it +51 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Superb explanation !!! Thanks a lot , One thing I would like to know is if the question constraint that you can buy more than a[i] items of ith item would affect the solution in case we buy more items of x so as to more decrease y

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    This idea is nice, but it's still not too different from the solution, because we still have to make the observation: buying items with higher b_i is better. I can say, your idea is not fundamentally different from the solution's idea. Maybe because this is not a hard problem so we can't see the diversity of the solutions like some others.

    But it sure is a great idea, the thoughts "I should minimize the number of bought items with price 2", "I can binary search the answer on this", ... and more, as you explained, are completely natural and can be thought of. Thank you for your contribution!

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, brilliant explanation

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. In your solution, we finally found a proper position where the things before it were 1 and later than it were 2. So, why not check every possible position and keep some useful information? See my submission, which is theoretically O(N) if we use radix sort instead of qsort.

    Sorry for my bad English : )

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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/

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why does this work? dont 1's also count towards the total items bought. from what i can see from your solution it is just comparing if the number of items left is greater than the b of the current last item, but if there is an item that has a lot more a than it has b, wouldnt it also be useful in increasing the total number bought and thus would have to be used in the total number of items bought?

»
5 months ago, # |
Rev. 2   Vote: I like it -19 Vote: I do not like it

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.

_tryhard

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    Stop tagging me, this task isn't even mine

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good explanation, appreciate it. Thanks.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even if the costs are same, we are buying more products at the end of first transaction as opposed to the next one, so greedily first is the better choice as it makes the required number to get discount lesser for other choices

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please explain, why my code is showing WA on this test case of problem C.

code:- https://codeforces.com/contest/1539/submission/120190093

Test Case :- 2 314159265389793238 1

1 314159265389793241

correct and — 2 my code showing — 1

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Replace your double with long double in ceil function..

    OR , avoid ceil function whole together by replacing with ll req_k = (diff[i]-1)/x;

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    It's [i, j) because card j was already taken in right hand.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    Oh, you are correct, I mistook it with something else. Thanks for noticing!

    Edit: editorial was fixed.

»
5 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You should check line 37.You change d continuously without initializing.The d on the right side of each formula in line 37 should be the d in line 32 instead of the last calculated d.

»
5 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    In your example you are explicitly making the cost of that item by buying more products of other items. But the statement means that if by buying other items and within limits i.e. less that $$$a_i$$$, then you should buy the items of cost 1.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem C: What will be the output for this test case

3 3 2 1 7 10

shouldn't it be 2 ?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Invite students with level 3,5 and 9 :)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Change vector(int)split to vector(llint) split and it gets accepted

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the problem is that you have int[] a instead of ll[] a. Each element can be up to 1e18.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with Problem D? My submission is

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

Thanks in advance!

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    Your solution has not correct comparison in the case of whole buying goods without discount:
    else if (total_bought + products[j].F < products[i].S)
    Correct comparison is:
    else if (total_bought + products[j].F <= products[i].S)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually the problem was in the line

      bool sortbysec(const pi &a, const pi &b) { return (a.S < b.S); }

      Instead of pi, I should have used pll

      https://codeforces.com/contest/1539/submission/120284252

      This gives the correct solution even if I don't implement your suggestion (my reasoning is that it will go into the third condition, make products[j].F = 0 and then in the next iteration j-- would happen)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone explain how problem A can solve using combinatorics.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

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

»
5 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too confused about how to compute maximum jump length in O(1)

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Try to use Long[] array instead of long[]. Also you may read my comment above.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have tried and it got accepted but I have seen in the documentation that sorting method for primitive works faster compared to objects.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1. First consider the case where there are infinite participants. Then each participant would be disturbed by $$$t/x$$$ participants following him.

    2. Then consider the case that $$$n$$$ is finite but large enough, then the first participant would be disturbed by $$$t/x$$$, the same for participant 2, ..., until $$$k$$$.

    For the participants beyond k, the number of participants that would disturb them are decreased by 1 each time, i.e., $$$t/x - 1$$$, $$$t/x - 2$$$, until 0 for the last participant.

    There are $$$t/x$$$ numbers from $$$t/x - 1$$$ until 0, thus we know $$$k = n - t/x$$$.

    So the answer would be $$$(n-t/x) * (t/x) + (t/x-1)*(t/x)/2$$$.

    3. The $$$min$$$ and $$$max$$$ in the answer is to solve the case where n is not large enough, i.e., when $$$n < t/x$$$.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me why am I getting TLE in problem D? Thanks in advance.

Submission: https://codeforces.com/contest/1539/submission/120517993

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Nice Contest

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone explain why the answer of test case 3 is 2

the first difference that is not allowed is (5) between 1 and 6 and the maximum allowed difference for this test is 1 , we need 4 students to reduce the difference between 1 and 6 to the maximum allowed difference , so after that we cant add any students and the differences 6-8 and 8-10 cant be reduced so we will have 2 additional groups the total will be 3 but the right answer is 2 , I also have the same issue with case 7 , 8 and other cases this is the case input first line (10 4 1) second line(10 1 6 10 1 1 6 8 6 8)-- I need help cuz iam newbie

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry I forgot to add one more student when the difference % allowed difference is not equal to zero

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, I am a not very good at this. Can anyone explain what is wrong with my code for Problem C? Here is my code [my code].

Thanks in advance

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please can someone explains the idea of problem F, I can't understand the tutorial and not even where to begin.