Editorial of Codeforces Round 889 (Div. 1 + Div. 2)

1855A - Dalton the Teacher

Author: Kaey
Preparation: akifpatel

Official implementation: will be posted after the system tests.

1855B - Longest Divisors Interval

Author: TheScrasse
Preparation: TheScrasse

Official implementation: will be posted after the system tests.

1854A1 - Dual (Easy Version)

Author: TheScrasse
Preparation: akifpatel

1854A2 - Dual (Hard Version)

Author: TheScrasse
Preparation: akifpatel, dario2994

The hints and the solution continue from the easy version.

Official implementation: will be posted after the system tests.

1854B - Earn or Unlock

Author: TheScrasse
Preparation: akifpatel

Official implementation: will be posted after the system tests.

1854C - Expected Destruction

Author: TheScrasse
Preparation: akifpatel

Official implementation: will be posted after the system tests.

1854D - Michael and Hotel

Author: TheScrasse
Preparation: akifpatel

Official implementation: will be posted after the system tests.

1854E - Game Bundles

Author: dario2994
Preparation: akifpatel, dario2994

Official implementation: will be posted after the system tests.

1854F - Mark and Spaceship

Author: dario2994
Preparation: akifpatel, dario2994

• 6 hours ago, # ^ | it's something new

• 5 hours ago, # ^ | Has to be one of the most bullshit problems lately. could have been up to 10^4 and the problem would be just as hard but 10 times better.

  • 5 hours ago, # ^ | it's way easier to think of n^2 dp without bitsets

    • 5 hours ago, # ^ | Then something could have been changed so you that the trivial DP solution didn't pass. Bitset is just a constant optimization and not a complexity optimization.

      • 5 hours ago, # ^ | So is problem A. Constant optimizations are fine if they cause big difference in runtime, cp is not purely theoretical...

        • 4 hours ago, # ^ | ← Rev. 3 →   -30 That's different. A pragma can make a code run 2x faster. That doesn't mean there should be pragma problems on contests. Plus, 10^5 is usually intended to be solved in at most , not quadratic time.

          • 4 hours ago, # ^ | Just because bound is in range does not mean solution should be certain subset of complexities. All that matters is if it runs fast or not, and preferably intended runs significantly faster than worse approaches (32x is significant, 2x is not).

            • 4 hours ago, # ^ | but i am bitset-phobic

          • 3 hours ago, # ^ | Bitsets have already been used in problems. There was a problem with solution that runs in , where was up to

      • 4 hours ago, # ^ | ← Rev. 2 →   +68 If you assume the values of the problem fit into an integer, then implicitly you assume that the length of the integer data type you are using is . That means that if you apply bitsets, you are guaranteed to at least divide the runtime by a factor. So actually the solution is or better. Another justification for this lowerbound of on the word size is here: https://en.wikipedia.org/wiki/Word_RAM. This means that it is better than quadratic.

        • 4 hours ago, # ^ | You cannot assume a bound for n when calculating time complexity. Following that logic, since the code will do at most 10^10 operations, then theoretically it's O(1) with an extremely high constant. Sure, on practice you can optimize quadratic in 32 or 64 times, but it's still quadratic.

          • 4 hours ago, # ^ | It's not that you bound the maximum , the actual logic, is, assuming you are going to do testcases with huge values of , you will also upgrade your computer to have a bigger word size, otherwise you can't even store the input inside integers.

            • 4 hours ago, # ^ | That's fair, but the optimization is still limited to your computer's architecture. Your compiler may fit 128 or 256 bits into an integer in a 32 bit architecture, meaning you're still getting x32 optimization.

          • 4 hours ago, # ^ | Complexity depends on what you count as a single operation. The word ram model is probably the most common model where you consider an integer operation as one operation, which is why you are able to divide by factor of lgn in complexity. If you instead want to say every bit flip counts as single operation, you have to multiply lgn complexity of every addition/multiplication every time you do big O complexity, which is almost always not very insightful and annoying.

    • 4 hours ago, # ^ | How is it possible to do as n was given 10^5

  • 5 hours ago, # ^ | I disagree. If passes, then people could formulate a dp without noticing the connection to knapsack.

    • 4 hours ago, # ^ | the bitset is still O(n^2)...

      • 4 hours ago, # ^ | its atleast O(n^2/logn) as pointed out by jeroenodb

        • 4 hours ago, # ^ | no, the time complexity remains as O(n^2), it's simply been optimized by a constant factor of 32-64, which doesn't affect the actual complexity? if my understanding is correct

          • 3 hours ago, # ^ | that 32/64 is coming from log of Integer size (log 10^9 or log 10^18), so its a log factor.

            • 3 hours ago, # ^ | yea its a log of the int size, which is a constant, so its still a constant factor. comparatively, it wouldn't be accurate to say that it runs in O(n^2/cbrt(n)) just because of the fractional constant factor.

• 5 hours ago, # ^ | Does this mean it cannot be solved in any language other than C++

  • 4 hours ago, # ^ | Welcome to codeforces

  • 3 hours ago, # ^ | Sometimes it's difficult to make a problem suitable for other languagues while not nerfing it for C++ enjoyers. When there are problems with solution, there are people who do magic and get AC for solution just because AVX and because stupid solutions have incredible constants while smart solutions have a big constant

  • 2 hours ago, # ^ | No; see this Python solution by misorin. (Congrats on the first Python AC!)

  • 112 minutes ago, # ^ | You can technically write your own bitset in most languages (like this witchcraft: https://codeforces.com/contest/1854/submission/216290667)

• 113 minutes ago, # ^ | cope, it's just skill issue

• 2 hours ago, # ^ | is similar to knapsack . says if it's possible to unlock exactly cards after first moves (in knapsack it says if the sum of weights can be if we look on first elements). In knapsack you can see that to count all values of you only need values of , and it can be further optimised to one-layer dp. So, in other words, knapsack can be written as , where we iterate from to . Consider this as a giant bitmask. Then, when we update dp with , this is equivalent to updating like this: . In this problem is calculated in a similar (not the same) way

• 5 hours ago, # ^ | there exists some cubic solutions (like mine) which they wanted to pass as well ig

• 5 hours ago, # ^ | Take a look at Ticket 17016 from CF Stress for a counter example.

5 hours ago, # |

• 5 hours ago, # ^ |

• 5 hours ago, # ^ | same happened to me , didnt know of that kinda optimization though

• 3 hours ago, # ^ | unlike pragma, bitsets are not constant time optimizations in some sense

• 2 hours ago, # ^ | When using pragmas in different situations you can get different results, sometimes RE or the time even increases. However with bitset you know, that everything with it works times faster

• 5 hours ago, # ^ | It ACs after 42, the answer to life, the universe, and everything :)

• 3 hours ago, # ^ | I was stuck at 34 moves, how did you come to the k=31 soln

  • 2 hours ago, # ^ | The solution when every value is either non-negative or non-positive takes at most 19 moves. For C1 my idea was to convert negatives to positives when there is fewer of them, and vice versa. The converting is done by adding the biggest positive to every negative value. However if the value of the maximum positive is smaller than absolute value of smallest negative, you must waste at most 5 moves by adding it to itself, that is when maxPositive = 1 and minNegative = -20. Worst case scenario is when there is equal number of negative and positive values. So for C1 my solution takes at most 19+5+10=34 moves. I guess you discovered that already. Now, for C2, notice that if the maximum absolute value is positive, you need at most 19+countOfNegatives moves. This strategy only takes 10+19 when the number of negative and positive values is equal. And, it is better than our first strategy as long as the difference between number of negative and positive values is smaller than 5. This means that the turning point is when the number of negatives is 12 and the number of positives is 8. The second strategy then takes 19+12=31 moves! And when the number of negatives is 13, positives 7, the first strategy is better, taking 19+5+7=31 moves!.

    • 2 hours ago, # ^ | your pfp offends me

• 5 hours ago, # ^ | Thanks for the feedback! :) Problem B does not have multitests because there is no easy way to declare variable-length bitsets.

  • 5 hours ago, # ^ | Wouldn't the complexity stay the same if you declare one bitset of size 2e5 and use it for every test case (setting elements to zero after each TC), assuming the sum of was bounded by ?

    • 5 hours ago, # ^ | That's true, I missed it. So it would have made sense to make multiple testcases, sorry.

      • 5 hours ago, # ^ | No worries, thanks for the response and for preparing the contest!

• 5 hours ago, # ^ | is the system word length (basically, the number of bits the processor stores in one unit; generally either 32 or 64).

  • 5 hours ago, # ^ | Thank you, but how does that complexity could pass the n<=1e5 constraint?

    • 5 hours ago, # ^ | With , we have , suggesting that we're fine given the 3s time limit. In practice, bitsets have a pretty good constant factor, and my code passes in about 1s.

• 5 hours ago, # ^ | fwiw, mine is also not randomized. I iterate over the possible "base sets" in an order that's basically just counting in base 60. For a given base set, I check if an answer exists by computing the number of ways to get each sum up to 60, then adding additional values. In particular, I iterate over from to , where is the number we can get in the most distinct ways. Then, while , I add one copy of to the solution. If this process generates a valid solution, we can output it. Checking a given base set takes time. The expected number of base sets we must check is small (intuitively there is no reason any given number will fail for all base sets), and my solution passes in 15ms.

  • 5 hours ago, # ^ | Thanks! It makes sense. tourist's solution seems similar.

• 5 hours ago, # ^ | CLIST usually gives quite accurate problem ratings

• 5 hours ago, # ^ | Take a look at Ticket 17022 from CF Stress for a counter example.

• 4 hours ago, # ^ | ← Rev. 2 →   0 Keep the vector global and reset it before each test.

  • 4 hours ago, # ^ | bro, can you send the code making this modification. I am not getting AC

• 4 hours ago, # ^ | My approach -> Case 1 -> If all the elements are +ve, take prefix sum. We can do it in n-1 steps. Case 2 -> If all the elements are -ve, take suffix sum. We can do it in n-1 steps. Case 3 -> If there are some +ve and some -ve elements, We first try to convert all the -ve elements to +ve. We can do this by adding the max element to the -ve elements. If the maxEle < abs(minEle), then we increase the maxEle by doing the operation {maxIdx,maxIdx} while maxEle < abs(minEle). Then, we add maxEle to all the -ve elements. Now, as all the elements have become +ve, we take prefix sum.

• 3 hours ago, # ^ | Your solution basically checks all ranges between and finds the longest one. We can prove that this will always find the correct answer. Fact 1: We can show that the range will be optimal for some . In other words, if (for given ) the longest good range has length , the range must also be good. For proof of this fact, check my comment here. Fact 2: We can show that the answer never exceeds (for ). Proof: Suppose the answer for some is . What do we know about this ? We know that is a multiple of each of , according to Fact 1 (and this is a sufficient condition for such an to exist with answer ). This means that is a multiple of . But notice that , so such doesn't exist for within the constraints of the problem. This means that the maximum answer will be , and your solution will find it.

• 2 hours ago, # ^ | There is likely no way

• 3 hours ago, # ^ | This is the next codeforces phase. From Mathforces to Guessforces to Hopeforces.

  • 118 minutes ago, # ^ | you forgot about animeforces

• 73 minutes ago, # ^ | Idk what you're trying to do in your solution but answer is just number of i such that pi = i divided by two and rounded up.

• 61 minute(s) ago, # ^ | x1 + y1 <= 5, x2 + y2 <= 20, so x1 + x2 + y1 + y2 <= 25. Let X be x1 + x2, Y be y1 + y2, X + Y <= 25. If a + b = c, then min(a, b) <= c/2, because if min(a, b) > c/2, then с — min(a, b) < c/2, we got a contradiction. min(X, Y) <= 25/2