TheScrasse's blog

By TheScrasse, history, 16 months ago, In English

Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round 889 (Div. 1) and Codeforces Round 889 (Div. 2), which will start on Jul/29/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours and 30 minutes to solve them in both divisions.

  • One of the problems will be divided into two subtasks.
  • One of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.

The problems were authored and prepared by akifpatel, dario2994, Kaey and me.

We would like to thank

Score distribution:

  • Div. 1: $$$(750 + 750) - 1500 - 1500 - 2000 - 2750 - 3250$$$
  • Div. 2: $$$500 - 1000 - (1250 + 1250) - 2500 - 2500 - 3000$$$

We hope you'll like the problemset!

Update 1: the editorial is out.

Update 2: congratulations to the winners!

Winners and first solves
  • Vote: I like it
  • +377
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice

»
16 months ago, # |
  Vote: I like it -43 Vote: I do not like it

orz

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

Seems like a really tough div1 from B's points

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

omg TheScrasse round!

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

As a tester, I had a lot of fun testing this round and I hope you enjoy the problems as much as I did. Good luck and have fun!

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

Finally a Div 1 :D. I can learn how to unmaster now.

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

as a tester i can confirm not even the fire emoji can express how hot the problems are

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

Offering equal scores for three problems is a bit unusual--are those problems ordered by the authors' impression of their difficulty, or are the authors completely agnostic regarding the relative difficulty of D1 ABC?

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

    I have an opinion about the difficulty of these problems, but some other authors and testers have very different opinions. Overall, let's say we are agnostic.

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

first time to see div1 abc have the same score. really cool

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

How long is the round actually? It says 2h30 in the announcement but 2h in the contests page.

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

    It's 2 hours and 30 minutes long. The contests page will be updated.

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

When can I get positive delta in a div.1 round?????

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

Deleted. Good luck to all participants!

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

Hello, I'm a newbie and I'm a little confused. Will I gain any ratings on profile from this round or not?

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

orz

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

I hope it will be contest with interesting problems.

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

Break through oneself

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

Please be a good round

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

Why score distribution is 1250+1250 does that ques will have two part

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

    Well it means that the problem will have two version: The easy version, which is C1, and the hard version, which is C2(or, in case of Div 1, A1 and A2)

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

Total 2500 points for Div2. C? Sounds like it will be very tough for it’s place.

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

hopefully to be expert after this contest

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

    Me too (my another account). Good luck to you~

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

Thanks for this round and good luck for everyone :) !

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

I'm excited for this. :pray:

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

what does (1250 + 1250) or (750 + 750) mean?

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

    There will be two versions of Div. 2 C / Div. 1. A, each worth 1250/750 points (so if you solve both versions of Div. 2 C, you get up to 2500 points total). The second version is generally harder than the first; usually the two problems are the same but the hard version allows for larger input sizes.

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

      oh okay I got it. thank you) and if I solve only one version, then I get 1250 pts, right?

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

        Correct.

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

        If you solve C2 the same code is usually correct for C1

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

          This may or may not be true. That's why they specifically mention about it at the start of problem statement.

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

Can anyone tell me, what will be the topics for this contest?

  • »
    »
    16 months ago, # ^ |
      Vote: I like it +59 Vote: I do not like it
    Don't tell anyone else
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to reach blue..

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

Let's see if I reach specialist after this round.

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

Hope to become CM :)

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

Ciao.

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

is round translated on russian?

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

Hope to increase rating

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

Maybe too hard?

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

2hr 30min felt kind of humiliating tbh

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

lol lol

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

What the heck was Div 2B ! lol

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

    You can greedily set the start of the interval to be $$$1$$$. Then just try to extend your interval until you can't anymore.

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

      Until you get Time limit exceeded*

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

        No, you won't because the loop will iterate at most 43 times since $$$\mathrm{lcm}(1, 2, \dotsc, 43) = 9\,419\,588\,158\,802\,421\,600$$$ which is more than $$$10^{18}$$$.

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

can anyone share the intution of C, i thought about adding twice of one element to other element in a certain way would make this pair sorted.. i add twice of element greater in absolute value to element smaller in absolute value like 6 -3 i add (6 * 2) to -3 to make it 9 but couldn't get ahead of this..

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

    my solution (still pending test so take a grain of salt)

    In a nutshell if we can make the array all positive, then it's easy because you can do something like

    for i in range(1, N):
      if arr[i-1] > arr[i]:
        add i-1 to i
    

    The same thing can be said for all negative numbers. You just do it from the end of the array. The operation takes at most N times which is 20.

    Now the difficulties come because array can have positive & negative numbers.

    Imagine if the array has at least 1 positive number. Then we can double that number quickly by adding it to itself. The worst case is for positive number 1, and double it 5 times so it definitely exceeds 20. The operation here is another N which is 20.

    Then we add this number to each number in the array, and we can be sure to have an array of ALL POSITIVE numbers. And you can apply the logic above.

    So in general:

    if not_has_pos:
      do the negative stack from end of the array (20 operations)
    else:
      quickly double the largest positive number until it's > 20 (at most 5 ops)
      use that largest number to add to each of the array number (at most 20 ops)
      do the all positive stack from the beginning of the array (at most 20 ops)
    
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

how to solve D2C?

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

    If all numbers are negative, then just take suffix sum.
    Else take any positive number and keep adding itself to it till it is less than 20.
    Then add that number to all the negative numbers. Now all are non-negative numbers.
    Take prefix sum.

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

    Roughly speaking, make all elements either positive or negative (optimize this a bit), and then it's just prefix/suffix sum

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

    if you have all element as postive then just start appling operations from beginning to a[i],a[i-1].similary for all negeative elements apply operations from last. if array contain both positive and negative you can make any positive element > 60 in atmost 6 moves by appling operation to itself then apply operation on each negative element with this element(>60) and then just solve it for all positive case. maximum moves=6+19+19=44

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

    The main strategy is that if all numbers are not negative you can do:

    2 1

    3 2

    4 3

    5 4 ...

    so in each step every number becomes at least as big as the previous

    if all the numbers are not positive its the otherway around:

    19 20

    18 19

    17 18...

    You take 19 steps to do that. Now the question is: how to make all the numbers non-negative or non-positive?

    If there are >= 13 positive numbers, you can just pick any of them, sum it with itself 5 times (so if the number is 1 it becomes 2, 4, 8, 16 and finally 32) and then sum with all the other negatives, which are at most 7. So you have 5 + 7 + 19 steps <= 31;

    If there are >= 13 negative numbers it is similar as above.

    If there are less than 13 negative and less than 13 positive numbers, just take the one with larger modulu, sum it with all the at most 12 numbers of the opposite signal and do the first process. You have 12 + 19 steps <= 31

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

    If all element is positive, we take its prefix sum, else if all element is negative, we take suffix sum

    Example: 1 4 7 2 8 -> 1 5 12 14 22;

    -1 -2 -1 -> -4 -3 -1

    Let numNeg is number negative element and numPos is number of positive element. We will convert all positive to negative or convert negative to positive.

    I will discuss about first case, the second same.

    • First, double biggest positive number until its abs larger than smallest element' abs. Let number operation need for this process is Kpos.
    • Second, add this number to all negative number (after that we have a positive array)
    • Third, take prefixsum
    • Total cost is: numNeg + Kpos + n — 1
    • Total cost for other case is: numPos + Kneg + n — 1
    • We can proof that either numNeg + Kpos or numPos + Kneg (or both) not larger than 12
  • »
    »
    16 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    for Div 2 C1 you can easily solve it by a greedy approach you are fine with the operations if all numbers are negative, positive or all numbers are 0 then you can easily do it otherwise for 50 operations just spend 5 operations to make any non zero number >abs(20) then add this number to all the numbers to make same parity as it has then simply do like all negative and all positive

    but for Div2 C2 the catch was you have to know how many numbers are positive and negative suppose if you have any of these given count of numbers >=13 then the other numbers count will be at max 7 then in this case you just need to again spend 5 moves for any non zero nubmer from the 13 numbers and spend at max 7 more the make the parity same the number of operations inclusive will be 5+7 =12 and rest you can do 19 operations to make it non decreasing otherwise if maximum count of nagatives and positives <13 then just select a largest non negative element from the array and make all the oppositve parities numbers (which can be maximum 12) to same parity it has then do rest 19 operations on making the array non decreasing

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

Those who can't solve C.Try to think of prefix sum.

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

how to solve Div2 . B?

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

    continuous subarray from 1 that is factor of n

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

      but is not it o(n)? could you show me your code?

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

        It looks like it's $$$O(n)$$$ but it actually isn't because the smallest $$$x$$$ when $$$lcm(1, 2, 3, ..., x-1, x)$$$ $$$>$$$ $$$10^{18}$$$ is very small.

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

        no number can have factors from 1 to n except 1 and 2. so the time complexity would be O(k) where factorial(l)<=n and k=max(l).

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

    You need to use the fact that product $$$n$$$ consecutive numbers is divisible by $$$n$$$. So this kinda works

    rep(i,2,1e18) {
        if (n%i != 0) {cout << i - 1 << "\n"; return;}
    }
    
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div 2C

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

    I don't know if this is the intended solution. I had just not enough time to code it up, but I think it should work.

    Case1) All are zero. Then we're good

    Case2) All are non-negative. Then we're good, just submit {2,1} -> {3,2} etc and you get a increasing array in <= 19 operations.

    Case3) all are non-positive. Then we're also good, just submit {n-1,n} -> {n-2, n-1} and you get an non-decreasing array.

    Case4) There is roughly same number of positive and negative entries (maximum 4 difference in number of negative and positive entries). Then take the element with biggest absolute value and use it to make all entries positive/negative. This takes maximum 12 operations. Afterwards you can do the same as in case2/3. This costs you maximum 19 operations. Together it costs exactly 31 operations maximum.

    Case5) A there is much more positives than negatives or vice versa. Then take one element from the group there is most of, and add it to itself until it becomes 32 or larger in absolute value (this takes maximum 5 operations). Then it is bigger than all other entries, and you can use it to make all the other entires negative/positive. But, there is maximum 7 other elements of opposite sign (else we'd be in case 4). This takes maximum 5 + 7 = 12 operations. But, after this we're back in the situation of case 2/3, which we know takes 19 operations to sort. And again 5 + 7 + 19 = 31, so we can exactly do it even in case 5

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

Proof by AC is the best strategy for this contest

»
16 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I just need 5 more operation on Div2 C2.

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

    Yes, it's a shame, they wouldn't hurt me either.

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

trash round

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

Problem Div1A/Div2C is just telling me: you are a fool with low IQ.

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

    Can't agree more. Internet also gave up on me seeing my iq. Literally fucked up this one

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

I have no idea why my Div2.B AC'ed, lmao

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

    I assume you found the largest $$$r$$$ such that the segment $$$[1, r]$$$ works, right?

    There is an easy proof that this works. Consider any range $$$[l, r]$$$. Let $$$m = r - l + 1$$$, the number of integers in this range.

    We can notice that within these consecutive $$$m$$$ integers $$$l, l + 1, l + 2, \dots, l + m - 1$$$, exactly one integer is a multiple of $$$m$$$. Within the first consecutive $$$m - 1$$$ integers $$$l, l + 1, l + 2, \dots, l + m - 2$$$, exactly one is a multiple of $$$m - 1$$$ and so on, until the first consecutive $$$1$$$ integers $$$l$$$ (trivially) has exactly one being a multiple of $$$1$$$.

    This means that within the original range $$$[l, r]$$$, there is a multiple of each of $$$1, 2, \dots, m$$$ (where $$$m = r - l + 1$$$) and thus, we get that $$$n$$$ is also a multiple of each of $$$1, 2, \dots, m$$$. This way we get a new range $$$[1, m]$$$ which is as long as the original one, but starts at $$$1$$$.

    Suppose the answer to the problem (for specific $$$n$$$) is $$$x$$$; this means that there exists some good range $$$[l, l + x - 1]$$$. But as we showed above, the range $$$[1, x]$$$ must then also be good. This proves that we always can find an optimal range by setting $$$l = 1$$$.

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

      My solution is a lot dumber actually. I checked from 1 to some r, and I just took a rough estimation of max r possible for the time constraint, lol.

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

      How do I learn to prove my solutions? I came up with the solution of taking the largest r such that the segment [1,r] works, purely through intuition, but failed to prove it mathematically.

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

can I check something because I has C1 pass pretests at 1.04 but C2 pass at 1.26 and I decided to submit the C2 solution in C1 and my C1 is now recorded as +2 and 1.26 instead of +1 and 1.04. Will this change back when system testing is done or did I make a mistake?

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

Really interesting problems,thank you!

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

problems are amazing thanku everyone , i dont know why i am getting wa2 on div2/c

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

For div1E I simply assumed that there's some answer that uses some number of 1, some number of 2 and numbers > 30. Did anyone actually prove their solution for this problem?

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

Suspicious submissions in C1 problem (Div.2), almost around 1500 solution in last 10 min. I mean some people could have solved the problem but 1500 is pretty odd and many of them havent even solved 2nd?

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

interesting 1a-hard but hardly implementation :(

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

u may know a word in Chinese, niu-bi, which means "wonderful", "strong". Now I think it's suitable to the problem A2 in div.1. So fantastic the Constructive Problem is.

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

Maybe it's atypical (for me) that C is divided into two subtasks, but all in all a good round. if I had more will to start working D...

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

    And I liked in div2C division of the task into subtasks

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

can someone share how to solve div 2B .Please

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

    The longest interval is always 1, 2, 3, ...

    You can get it just by writing it down. Let's say the longest interval is actually some other, let's say it has 13. Well, the starting interval always has 1. If you add 14 to your interval, you also add 2 to the starting interval. If 12, you also add 3 and 4. So if you increase your chosen interval, the starting one also increases in size (by that number or more). So you only have to check when 1, 2, 3, 4, 5.. fails.

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

Too hard for me. Although I was lucky enough to solve 1A, there were too many penalties.

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

That 32 operations in Div2C2 :(

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

    Assuming that the maximum value is greater than the opposite of the minimum value, and when the number of numbers less than 0 is less than or equal to 12, we can add the maximum value to all numbers less than 0, and then make a prefix sum (12+19). Otherwise, we can multiply any number less than 0 by 5 times and add it to all numbers greater than or equal to 0, and then make a suffix sum (5+7+19)

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

rainboy didn't solve 2F, sad.

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

big difference between 31 and 50. Interesting problem

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

IF I FAIL SYSTESTS ON D

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

Why Div1D non adaptive?

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

    Because there is no clear strategy for an adaptive grader. So, it may punish some specific solutions, but let other solutions ask less queries.

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

      So no elegant randomized solution :(

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

        The intended solution is not randomized. There are some randomized solutions that ask more queries than the intended solution (but still less than 2000), so we decided to let them pass.

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

How to do 1E? I tried putting some number of 1s, and then filling the rest with >30 by taking nCr greedily, (I try with all possible numbers of 1) but based on my runs, I can only do <70 for most at best.

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

    I did it by trying 1s and 2s then doing the same thing. Let's see if it FSTs. In my opinion this problem should have hacks disallowed because even the intended solution doesn't seem to have any proveable expected runtime bounds.

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

      did you do the coinchange subproblem greedily? (i cant see of a fast way to do that part fast, so I just do greedy)

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

        Yes, I ordered the ways of reaching values [0, 29] with the 1s and 2s then greedily used them.

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

How to solve D1B?

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

    You can see that if you know the range of card unlocked, you can calculate the profit (sum element subtract number element). We will handle case the last unlock operation over n by append $$$n$$$ number $$$0$$$ to array.

    We will take a subset for first operation and take all other $$$v$$$ in the range we unlocked. But not all subset valid. Same as knapsack problem, let $$$dp[i][j]$$$ true if there is a valid subset of first $$$i$$$ element and sum is $$$j$$$. First, $$$dp[0][1] = true$$$

    $$$dp[i][j] = dp[i-1][j] | dp[i-1][j - a[i]]$$$

    But after that we cannot use subset with sum $$$i$$$ to update $$$dp[i+1]$$$ because the condition for us to use $$$a{i+1}$$$ is that previous subset must have sum greater equal to $$$i +1$$$. Just make set $$$dp[i][i] = 0$$$ before go to step $$$i+1$$$

    Use bitset to speedup

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

My best approach for div2 C2 could do it in <= 35 steps, could not make it till <= 31 till the end :(. I will check number of positive and negative elements, and those who have majority, I will make all the elements with same parity of parity of majority element.

Let's say positive numbers > negative numbers. Then I will make maximum positive number > 20, this will take 5 operations. Now I will add this positive element to remaining at max 10 negative elements this will take 10 operations. Now I will take prefix sum so at max 20 operations. 5 + 10 + 20 == 35.

Same if negative numbers > postive numbers. Is this correct approach?

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

    You can think of another way. What if you already have the maximum absolute number? Then you don't need to do doubling. If all is positive/negative, you only need 19 operations, so you can use your biggest to fix at most 12 elements before doing that. (so you can have 12 positive/negative where the biggest is not at) Suppose then, there is 7 and 13. Then you use your approach of doubling (which is 5 operations) then 5 + 7 + 19 = 31

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

    Actually I think you have to come up with a different C1 Solution to solve C2. (Well, it's only my personal opinion.)

    Spoiler

    If $$$a \geq 8$$$, then $$$2n - a - 1 \leq 31$$$ is small enough. Then, in case of $$$a \leq 7$$$, we consider getting a negative number with a maximum absolute value. It takes at most $$$5$$$ operations because $$$-1 \times 2^5 = -32 \lt -\lvert 20\rvert$$$ is small enough.

    Then Let's add the $$$a$$$ non-negative numbers by the newly generated negative number. Then, respectively, do a suffix sum.

    It takes at most $$$(n - 1) + 5 + a = 31$$$ operations too.

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

How to solve div2D?

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

Can you share your strategy and story under so unusual score distribution?

My strategy

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

    Here is the story you asked:

    • Initially div2C was only one, with $$$36$$$ queries. Then, in this order, div2E and div2D.

    • Testers complained about the gap between div2B and div2E (which was in div2D position at that time).

    • Since coming up with new problems is hard, we decided to split div2C in two subtask: one clearly easier and one clearly harder.

    • Some more testers' feedback arrived and we decided to swap div2E and div2D.

    • Testers felt like solving div2C1+C2 was as has as the following problems.

    • Since different people had different opinions on the relative difficulty of the problems, we decided to go for the score distribution div2C=div2D=div2E.

    Taking into account that before the round one has limited information, it seems to have been a reasonable call.

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

    I would be really interested to see what the solve statistics would look like under a different ordering of the problems; I think that the difficulty ordering is highly subjective, and the order in the round may be the main reason that e.g. A2 has more solves than B. Too bad it isn't possible to give A, B, and C to each contestant in a random order...

    (fwiw, my personal difficulty ordering is A1 < B <= C < A2, but I think I tend to perform best on tasks like C. I think C is probably harder than B if you're being objective, and likely harder than A2.)

    Re: the original question, my strategy going in was to read A and immediately type A1 if it seemed free and either A2 seemed time-consuming or I was pretty sure the A2 solution would involve direct modification of the code for A1. I didn't want to spend time on A1 separately otherwise because the points I'd gain from solving A1 a few minutes faster would be outweighed by the points I'd lose from being a few minutes slower to the later tasks. After assessing and possibly solving part or all of A, I planned to read B and C, attempt one based on solve statistics, and go from there.

    In-contest, I figured out A1 pretty much instantly and decided to think about A2 rather than typing A1. Luckily, I figured out the trick for A2 not too long afterwards for a quick AC. I attempted B before reading C because after I finished A2, I saw that B had several solves and C had none. After finishing up B and C fairly quickly, I moved on to D and E. At the time both problems were unsolved, and because E was worth far more points than D I assumed that D would be much easier. Thus, I solved D before reading E and finished E up afterwards. (In retrospect, it would have been a bit better to do E first, but ah well--not the end of the world.)

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

https://atcoder.jp/contests/abc081/tasks/arc086_b

I think Div. 2 C1 is equal to this problem I solved a few weeks ago, but I still got a lot of WA on pretest 2. Can anyone help me? The following two submissions are almost the same.

https://codeforces.net/contest/1855/submission/216291552

https://atcoder.jp/contests/abc081/submissions/42020794

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

why i found a same problem (div2 C and div1 A) in https://atcoder.jp/contests/arc086/tasks/arc086_b

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

    -120 by CF Predictor

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

    It's a coincidence, sorry. It also happened in the last educational round. In both cases, the statement was short and many people can come up with such statements independently.

    Fun fact: I also solved that AtCoder problem more than 2 years ago, but completely forgot about it.

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

    It is same as easier version but not harder so I think it is fine.

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

No matter how hard they are, I love short and precise statements like this round. Hopefully next rounds's will be short just like this.

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

Thank you for this round! I solved D1ABC and (if no FST) I should be getting back to GM, yay. And honestly, I loved all of the problems I solved.

I think A had a nice idea; first subtask is simple, but second one requires you to act differently in different cases, and the operations are just barely enough (at least in my solution).

When I looked at B, it was quite obivous (to me) that the answer was to use bitsets. The details weren't difficult but they also weren't trivial; it was fun thinking about the solution (even though I got 2 WA, sad).

Problem C was beautiful! I love probability questions, they usually require some nice observations (and math, which I also like). Btw, why were the constraints $$$m \le 500$$$? I think most people found the $$$O(m^2)$$$ answer explained in the editorial using linearity of expectation, was there some other solution you also wanted to pass (editorial doesn't mention anything)?

And also, I have to thank you for short and clear problem statements. You didn't include any unnescessary stories in the statements. And the stories you did include weren't annoying, but they made sense in the setting of the problems. I think they were good.

Overall, I think this was an amazing round, at least on the Div.1 side of things. It seems like the problems might've been a little difficult, especially for Div.2, but I can't say anything about Div.2. I definitely enjoyed participating, and I would love to see more rounds from you guys!

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

    Thanks! :)

    The intended solution in problem C is quadratic, but some contestants wrote a cubic solution, and we didn't want to cut it off.

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

fstforces xd

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

week pretest

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

how to solve C2 in Div2?

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

    Getting Div2. C2 accepted is a proof in itself, you can't get that problem AC without a proof.

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

      I mean how to solve it

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

+123 -111 +202 in last 3 contests. My ratings are on a roller coaster.

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

Great contest, I love it.

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

I enjoyed the contest.

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

1A2 tests are a little weak, I just hacked my own solution.

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

Sorry but I don't like E because my solution (no-proof-at-all heuristic) passed...

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

HELP — Why does 216311224 gives wrong answer for Div2C/Div1A.

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

Tests in D are poor. My (and if I'm not mistaken for example tourist's) submissions are incorrect. I find a segment of length $$$k$$$ on the cycle, and then I do rounds with parameters like $$$k$$$ and $$$2k$$$ and if $$$4k \geq n$$$ I hope that it's enough, but it isn't. If something is attached to the cycle at the beginning of the first segment, I won't find it.

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

    Trying to hack these solutions I get unexpected verdict, but there's something worse. tourist's submission won't even work if there is a path of length 499 attached to the cycle made only of the first vertex (or I messed something up), but hacking says that the hack is incorrect. My solution solves it correctly, so I guess there is no such test, but I think that it means that the model solution might be wrong?

    UPD: Nevermind here, it works on codeforces, but it somehow behaves this way on my machine, so most likely I've messed something up.

    UPD2: Ok, I get it now, he's tricky, he's correct on this test :P

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

      One of the testers' solution is wrong. The official solution works correctly on that test.

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

This round feels more like atcoder. Not my favorite style but problems were still interesting.

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

https://codeforces.net/contest/1855/submission/216345919

why am i getting memory limit exceeded?

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

    I had the same problem. Try using long long.

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

      no still getting mle

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

        It seems as though you haven't considered the case in which all elements are not positive (<= 0). This means your loop that increases each element either keeps adding nothing or subtracting, and also adding that "operation" to a vector, so you get MLE before TLE.

»
16 months ago, # |
  Vote: I like it -6 Vote: I do not like it
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Got c*cked by edge case of all negatives during contest for C2 and thus couldn't solve it in time (would have been a real rating boost). I had 1h+ to implement... GG

Accepted solution: https://codeforces.net/contest/1855/submission/216347323

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

Cheaters part 2:

link 1

link 2

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

Div2 C2: who are getting WA on test 2 try this:

1 20 -1 20 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 20

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

    I got WA cause i misplaced i with j in 1 place

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

The ratings in Div1 are updated, but not in Div2? Is it because of more participants in Div2?

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

can someone please explain div2B solution interval [l,r] contains at least one multiple of x for each 1≤x≤r−l+1

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

    Consider some value of $$$x$$$, say $$$x = 5$$$. Let's look at the multiples of $$$5$$$:

    $$$1, 2, 3, 4, \underline{5}, 6, 7, 8, 9, \underline{10}, 11, 12, 13, 14, \underline{15}, \dots$$$

    Notice that if we take any $$$5$$$ consecutive integers, exactly one of them will be a multiple of $$$5$$$:

    $$$[1, 2, 3, 4, \underline{5}]$$$

    $$$[2, 3, 4, \underline{5}, 6]$$$

    $$$[3, 4, \underline{5}, 6, 7]$$$

    $$$[4, \underline{5}, 6, 7, 8]$$$

    $$$[\underline{5}, 6, 7, 8, 9]$$$

    $$$[6, 7, 8, 9, \underline{10}]$$$

    and so on.

    This is true in general: if we take $$$x$$$ consecutive integers, exactly one of them will be a multiple of $$$x$$$.

    Notice that a range $$$[l, r]$$$ contains $$$r - l + 1$$$ consecutive integers. This means that the range $$$[l, r]$$$ contains a multiple of $$$r - l + 1$$$. But the range also contains a smaller subrange $$$[l, r - 1]$$$ with length $$$r - l$$$; this range must contain a multiple of $$$r - l$$$, and so on. Since the range $$$[l, r]$$$ contains smaller subranges for all lengths between $$$1$$$ and $$$r - l + 1$$$, it must contain a multiple of every integer $$$1, 2, 3, \dots, r - l + 1$$$.

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

Turned cyan today.:)

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

Hello!

I participated in this contest after registering when the contest started, and I started maybe around 30-40 minutes late. I solved two problems. But I don't see any rating change. It says the contest was unrated.

Please help me understand the situation.

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

    It will take a while for the system to update rating. P/s : at the time I commented, both div1 and div2 got updated

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

I like E very much! I think that such problems check creativity, but what's important, it's elegant. I'd probably set lower limit on m, so it'd be easier to prove that the solution is correct on all the cases (with a code of course, not on paper).

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

I hate E very much! The intended solution doesn't have any proved (expected time) bound for the given constraints, so we can't be sure that it actually solves all possible inputs that are within the constraints or not. Even if you prove that it solves them by running it over all possible inputs, that's ugly af and the process of "solving" it is more like solving the cases that were set and hoping that the case that's bad for your solution isn't in the systest instead of solving the problem by itself (since during the contest it's not efficient to spend minutes to hours verifying that your construction works for all cases). In that type of problem, you should at least disallow hacks and make pretests the same as the systest (which seems to be the case here) since it's not inconceavable that the expected solution gets hacked.

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

    I think that both your feedback and Radewoosh's one are valuable (and also hos.lyric, I read it only now). Thank you! This kind of discussions need to happen in the community. If anyone else has an opinion, please share it, it can have an effect on future problem sets!

    I will make some comments partially related to tfg's comment.

    • There is a strong (enough for me) intuition which suggests why the official solution shall be fast enough on all inputs. This is not a proof, but is better than nothing. In particular I would not bet my hand that the official solution works on all $$$m\le 10^{10}$$$ but I am absolutely certain that some simple variation of it (like just changing the seed or changing a $$$5$$$ with a $$$6$$$) does.

    • It is possible to check the correctness over all inputs in a reasonable amount of time (but this was not done).

    • The main reason why I lowered the constraint from $$$m\le 10^{10}$$$ to $$$m\le 10^{11}$$$ is that I was scared. Is this a good thing to do in general? No. Am I regretting it? No.

    • Pretests = Tests in E. Exactly for the reasons you mention. Not allowing hacks seems a good idea for the next time. (it would not have changed anything this time)

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

      I am very sad to see "We don't know any provably correct solution" in the editorial. Now the problem is not only of my taste but also incomplete.

      • I believe "a strong intuition" is equal to nothing for authors' side in a serious competition. A proof with a reasonable working probability would be more than nothing.
      • If it is possible to check the correctness over all inputs in a reasonable amount of time, please do.
      • I knew from your comment that Pretest = Tests. That's why I stopped improving my code, unfair? In addition to not allowing hacks, explicitly mentioning Pretest = Tests (maybe with the number of tests) would be better.

      Where to pose these kind of problems? Some suggestions.

      • Heuristic competition like TopCoder Marathon or AtCoder Heuristic.
      • Unrated joke competition or something.
      • Cf Div.1 with much lower constraints so that one can check the correctness during the competition quickly before submitting.
      • [?] ICPC-style competition. At least we don't need to care pretests or hacks. The situation is similar for geometry problems with unproven precision, which seem to be accepted there. (Maybe because there are many problems in a contest?)
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +86 Vote: I do not like it

      If anyone else has an opinion, please share it

      Well, it wouldn't be a surprise for you that I hate this problem (and maybe every problem Petr feels like he could have come up with ).

      Actually, I hate it maybe even more than the usual problems of this type. I knew (or rather expected) that I can't prove anything on paper, and I have to try some things and see if they work. Literally the first thing I implement is the eval function. Then I play with some parameters, look at the outputs and... it doesn't look like it's working! Not for me. There are big gaps between the values I get as dp[60], by an order of magnitude bigger than dp[29] which I would have to use to fill the gap. So I abandon the problem thinking "maybe I tried the wrong thing" (which happened to me several times while solving problems actually set by Petr, so I'm kinda used to not seeing what is strongly suggested by intuition to everybody else). I go and solve D, and only have 15 minutes left. With nothing better to do and nothing to lose I implement restoring the answer in my abandoned code for E and submit. My reaction. I genuinely hoped that it would fail systests because otherwise I don't get why this problem exists. The limitations are big enough so you can't run the solution on all tests (even though I guess my solution is better suited for that than the model one, since I do the precalculation once and then solving for one $$$m$$$ is relatively fast, but it still would take hours to run on $$$10^{10}$$$ values of $$$m$$$). It doesn't even look like it's working (to me). I literally got accepted with the code that was written an hour before submit and abandoned because I didn't think it works.

      I don't know what to take from it. I understand that I'm on the extreme end of the "do I believe in miracles" spectrum. I can't say that it is a bad problem. I'm not a person for whom this problem is meant to be enjoyable.

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

I'm neutral towards E very much! I haven't read the problem.

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

Tell me how you figured out Div2B. 1. Find out the solution logically (roughly know the reasoning or proof) 2. Printing and observing and guessing

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

my perform was so bad for this contest, i got MLE like 6 time just because a silly mistakes. Very good problem btw :D

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

Didn't know that bitset can pass 1e5, while A2 getting fst... this feels so bad [:cry:]

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

Thank you for the round! I love each of Div.1 ABCD.

A1 is the same as ARC086B, but this is not an issue. (that's why I had first solve :D

I am not a fan of 1E: I think at least hacks should be disabled for this kind of unproved/unverified problem (and maybe specify that pretests = tests).

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

Great probset btw!!

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

O(n^2/w) for n=10^5,,, so it is an acceptable complexity...?

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

    $$$w$$$ can be as large as $$$256$$$ on Codeforces.

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

      wow, that surprises me. Now it is a reasonable solution for me, thx.

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

How 2E?

»
16 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Why do I have lower initial score, higher rank, but obtain fewer score than others? hxsj: 1213 + 176 = 1389 rank:912 dxh074: 1291 + 182 = 1473 rank:916

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

Please debug my submission https://codeforces.net/contest/1855/submission/216449340 I am getting Memory limit exceeded on test 2 again & again...

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1
    5
    0 -1 -2 -3 -4
    

    Fixed Solution.. Made changes in "if and else if" conditions.. added >= and <= . Work out the test case I gave and you'll be able to figure it out.

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

MikeMirzayanov

I've received a message from system that

Attention!

Your solution 216335447 for the problem 1854A2 significantly coincides with solutions Imdie/216281838, Changyu/216335447. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

It seems like a coincidence, but both Imdie and me are completely innocent. We haven't cheated or violated any rule in the contest. We even didn't know each other then.

It's been about one year since my last OI contest where I got an NOI silver medal. I participated in the CF contest only for fun and had no motive to cheat. And it's also impossible for me to copy others' code during a contest.

Imdie and all my friends can verify what I said above. I hope the violation record can be revoked and I can get my rating added.

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

why my submission is TLE? https://codeforces.net/contest/1855/problem/B Problem B : My submission : 244680296