Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

TheScrasse's blog

By TheScrasse, 16 months ago, In English

The official implementations of all the problems are here.

1855A - Dalton the Teacher

Author: Kaey
Preparation: akifpatel

Hint 1
Hint 2
Solution

1855B - Longest Divisors Interval

Author: TheScrasse
Preparation: TheScrasse

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1854A1 - Dual (Easy Version)

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1854A2 - Dual (Hard Version)

Author: TheScrasse
Preparation: akifpatel, dario2994

The hints and the solution continue from the easy version.

Hint 5
Hint 6
Hint 7
Hint 8
Hint 9
Solution

1854B - Earn or Unlock

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution

1854C - Expected Destruction

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution

1854D - Michael and Hotel

Author: TheScrasse
Preparation: akifpatel

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1854E - Game Bundles

Author: dario2994
Preparation: akifpatel, dario2994

Hint 1
Hint 2
Hint 3
Solution

1854F - Mark and Spaceship

Author: dario2994
Preparation: akifpatel, dario2994

Hint 1
Hint 2
Hint 3
Solution
  • Vote: I like it
  • +196
  • Vote: I do not like it

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

really nice problems and fast editorial, thanks for the contest

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

bitset in the author's solution, why????????????????????????????????????????

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

    it's something new

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

    Has to be one of the most bullshit problems lately.

    Alright, I guess it's not that bad, I just got mad from having the right knapsack approach and not seeing bitsets lol

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

      it's way easier to think of n^2 dp without bitsets

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

        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.

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

          So is problem A. Constant optimizations are fine if they cause big difference in runtime, cp is not purely theoretical...

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

            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 $$$N\sqrt N$$$, not quadratic time.

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

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

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

              Bitsets have already been used in problems. There was a problem with solution that runs in $$$O(N^3 / 64)$$$, where $$$N$$$ was up to $$$1000$$$

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

            It is different because in problem A, we can get the exact number of operations, while in problem B we can only get a rough number. The exact number depends on the language (I think this is the key problem) and how we implement the same algorithm.

            by the way, bitset is acceptable for me. But I still think n=10^5 is a bad idea. Someone told me that w can be 256 on Codeforces, then n=10^5 make sense. But it seems a hardware features? There are many ways to speed up the programs by parallel techniques, and most of them need the support of compiler, language, OS and hardware. I think it is far beyond the scope of Codeforces.

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

          If you assume the values of the problem $$$(0 \dots n)$$$ fit into an integer, then implicitly you assume that the length of the integer data type you are using is $$$\geq log(n)$$$. That means that if you apply bitsets, you are guaranteed to at least divide the runtime by a $$$\log(n)$$$ factor. So actually the solution is $$$O(n^2 / \log(n))$$$ or better. Another justification for this lowerbound of $$$\log(n)$$$ on the word size is here: https://en.wikipedia.org/wiki/Word_RAM.

          This means that it is better than quadratic.

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

            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.

            Edit: Lol

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

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

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

                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.

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

              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.

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

        How is it possible to do as n was given 10^5

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

      I disagree. If $$$O(n^2)$$$ passes, then people could formulate a dp without noticing the connection to knapsack.

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

        the bitset is still O(n^2)...

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

          its atleast O(n^2/logn) as pointed out by jeroenodb

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

            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

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

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

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

                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.

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

                  based on your arguments won't log(max(a[i])) be constant aswell ?, then isn't the complexity O(nlog(max(a[i]))) just O(n) ?

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

                  n <= 10^5, so n^2 <= 10^10, which is constant, hence our complexity is actually O(1)

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

                  that's fair, but i think ive always just considered the complexity to be based solely on the constraints given in the problem. with a bitset, the optimization isn't actually based on the max size of the constraint, but rather the max size of our fixed data structure, so its not counted as part of the complexity in terms of n. that's why its always represented as O(n^2/w) and not O(n^2/log(n)), as the w does not actually come from taking the log of n, but the fixed size of the container. ig another thing is that O(n^2/log(n)) for n=1e5 comes around to 6e8, which is far too high regardless.

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

                  to expand on this, big O notation is defined as the worst case, in terms of n, regardless of how it's constrained in the problem. As we scale up n, the worst case time complexity becomes equivalent to O(n^2/w), where w is a constant, rather than O(n^2/log(n)), so it makes sense to me to call it as O(n^2).

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

          it should be o(n^2/w)? and in bitset w always be 32 or 64? qwq

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

    Does this mean it cannot be solved in any language other than C++

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

    can't agree more!!!!!!!!!!!!!!!!!!

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

    No, no one is retarded and your post is offensive. There is nothing inherently bad/wrong with bitsets.

    By the way, if any author of a problem whose solution uses bitsets were retarded, then you are offending someone unexpected.

    p.s. There is the possibility that you were sarcastic and I am a boomer.

    p.p.s. The first problem I linked is the problem that taught me bitsets.

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

      people who didn't understand from the links, Author of the editorial is Lord Tourist.

      https://img.atcoder.jp/agc020/editorial.pdf

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

      Sorry bro, didn't mean to be offensive, I was too emotional when I wrote this(because of my skill issue), I changed my comment to what I actually meant

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

        to answer your question, why not? its a perfectly valid optimization and the complexity is only around 1.5 x 10^8, which is very reasonable for 3 seconds.

        There are atleast 2 observations that would not be required to solve the problem if n <= 5000 or similiar

        1) you can find victory points by doing sum of prefix unlocked — (prefix size — 1), instead of storing max victory points in a dp state

        2) you only ever need to open atmost 2n things

        for instance, the solution dp[index][prefix opened] = maximum victory points needs neither observation and is much easier than the current intended solution.

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

    Since, bitset is used, I think it is worth bringing up how powerful bitsets really are :p

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

Excellent, insanely fast editorials!

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

Can someone explain the bitset part for Earn or Unlock? What is $$$dp_{i, j}$$$? How to update it?

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

    $$$dp_{i,j}$$$ is similar to knapsack $$$dp$$$. $$$dp_{i,j}$$$ says if it's possible to unlock exactly $$$j$$$ cards after first $$$i$$$ moves (in knapsack it says if the sum of weights can be $$$j$$$ if we look on first $$$i$$$ elements). In knapsack you can see that to count all values of $$$dp_i$$$ you only need values of $$$dp_{i-1}$$$, and it can be further optimised to one-layer dp. So, in other words, knapsack $$$dp$$$ can be written as $$$dp_i |= dp_{i-a_j}$$$, where we iterate $$$j$$$ from $$$0$$$ to $$$n - 1$$$. Consider this $$$dp$$$ as a giant bitmask. Then, when we update dp with $$$a_j$$$, this is equivalent to updating $$$dp$$$ like this: $$$dp |= (dp « a_j)$$$. In this problem $$$dp$$$ is calculated in a similar (not the same) way

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

It was so curiously but cool enough, thank you :)))

But why there were n,m <= 500 in C task if solution works in $$$~O(nm)$$$?

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

    there exists some cubic solutions (like mine) which they wanted to pass as well ig

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

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

nice problems and rly quick editorial with hints(best kind of editorial). thanks for the contest

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

I submitted a solution to B https://mirror.codeforces.com/contest/1854/submission/216340662 in the end of the contest which I knew wouldn’t get AC (I had nothing to lose at this point)

can’t believe the author’s accepted solution is the same but using bitset :\ . I can already see a day the author’s solution is gonna require some #pragma optimiza_some_bs. Really didn’t like this question at all.

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

    unlike pragma, bitsets are not constant time optimizations in some sense

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

    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 $$$64$$$ times faster

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

I really liked div2C2, it is a well-rounded problem, and discovering why k=31 is the worst case was really fun!

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

    I was stuck at 34 moves, how did you come to the k=31 soln

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

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

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

This was an amazing round, thank you for the nice problems :D

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

Feedback on the Div. 1 round:

tl;dr ACD are great problems; BE are mid. The problem statements were great, but there were numerous FSTs that probably could have been avoided. Overall, the round was pretty good.

A: Great problem, although I think the n <= 50 subtask should have been worth a bit less since the observation that the problem is easy when all numbers are positive/negative was a lot more obvious to me than the observation that we can make all numbers positive/negative in 12 moves and then finish in 19.

B: Not an awful problwem, but coming up with the DP is pretty trivial and the hardest part is just confirming that bitset will be fast enough. Not my favorite task.

C: Nice little EV problem. n <= 500 baited me into thinking intended may be O(n^3), but the DP is cute and it's a nice linearity application.

D: Fun interactive; I really enjoyed trying different ideas to puzzle this one out. Probably my favorite problem of the round.

E: The idea to trying to start with a bunch of small numbers and then add in some big ones to make the desired answer felt pretty standard, so the main new part here is that even if any individual starting set might not work for all N, we can quickly try a bunch of different starting sets until we find one that's valid. (fwiw, my implementation is a lot simpler than what the editorial describes--I literally just brute force starting sets in a reasonable order and end up ACing in 15ms.) This felt a bit like a guessing game and didn't feel satisfying or clever to come up with. I think I (mildly--it's not a terrible problem by any means) dislike this problem for the same reason I dislike B: the solution is basically just to tweak something stupid rather than to make a clever observation.

F: Didn't read. (fwiw, I think this and the last round are maybe a reason to have Div. 1.5 rounds rated for, say, 1600-3000 or something, and/or to have five-problem Div. 1 rounds--problems like this one are relevant to only a handful of people in the contest pool and it might allow for more contests if not every round needs to have a really hard problem at the end.)

Feedback on preparation: I liked that pretests = systests on D/E (I think, anyway), and the problem statements were all clear, short, and easy to parse. However, I think A should have had a higher test limit (I don't see why 1-2k tests per input would be infeasible?) and B and C should have been multitested. (I don't think multitesting makes the complexity calculation weird for either of those problems or allows unintended solutions to pass.)

Thanks to the authors for the round!

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

    Thanks for the feedback! :)

    Problem B does not have multitests because there is no easy way to declare variable-length bitsets.

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

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

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

        That's true, I missed it. So it would have made sense to make multiple testcases, sorry.

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

          No worries, thanks for the response and for preparing the contest!

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

          Well bitset would still work in $$$O(maxN / w)$$$, so multitests could be diificult to include here

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

            Yes, but that's ok, because the complexity becomes $$$O(n \cdot \text{MAXN}/w)$$$ per testcase and $$$O(n^2/w)$$$ in total.

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

can someone explain what is the factor "w" in the complexity of 1854B ?

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

    $$$w$$$ is the system word length (basically, the number of bits the processor stores in one unit; generally either 32 or 64).

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

      Thank you, but how does that complexity could pass the n<=1e5 constraint?

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

        With $$$n \leq 10^5$$$, we have $$$\frac{n^2}{32} \approx 3 \cdot 10^8$$$, 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.

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

          I mean when seeing the constraints and the time limit, i knew the complexity would be really weird, but never have thought of that. Thank you!

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

tourist's solution for E seems not randomised although I don't really understand what it does and why there is some magic constant defined in it (216302036)

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

    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 $$$dp[sum]$$$ to get each sum up to 60, then adding additional values. In particular, I iterate over $$$i$$$ from $$$60 - hi$$$ to $$$60$$$, where $$$hi$$$ is the number we can get in the most distinct ways. Then, while $$$dp[60-i] + dp[60] \leq m$$$, I add one copy of $$$i$$$ to the solution. If this process generates a valid solution, we can output it.

    Checking a given base set takes $$$O(60^2)$$$ 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.

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

What could be the difficulty ratings for all the problems ?

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

My solution for E:

Use $$$c_a$$$ times of $$$a$$$ and $$$c_b$$$ times of $$$b$$$, where $$$1\leq a<b\leq 30$$$. And for every $$$x$$$ from $$$31$$$ to $$$60$$$, we'll put an $$$x$$$ in if the total count does not exceed $$$m$$$. Because $$$x>30$$$, we can't include $$$2$$$ latter type numbers into one set, so the total count will be trivial to calculate. The time complexity is $$$O(60^5)$$$.

I don't know why this is correct but it actually got Accepted. Submission: 216320776.

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

Can you help me with d2D? I have a bit different approach with dp: dp[i].first = minimal cost of cards to unlock ith card, dp[i].second = max j that jth card can be unlocked using same set of cards as ith card can. I recalc dp with segtree. Why this idea can lead to WA?

https://mirror.codeforces.com/contest/1855/submission/216348756

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

Dont know why this worked, so please can someone explain me how i got this lucky to pass all system test in this solution 216290096

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

    Your solution basically checks all ranges between $$$[1, 10\,000]$$$ and finds the longest one.

    We can prove that this will always find the correct answer.

    Fact 1: We can show that the range $$$[1, r]$$$ will be optimal for some $$$r$$$. In other words, if (for given $$$n$$$) the longest good range has length $$$x$$$, the range $$$[1, x]$$$ must also be good. For proof of this fact, check my comment here.

    Fact 2: We can show that the answer never exceeds $$$42$$$ (for $$$n \le 10^{18}$$$).

    Proof: Suppose the answer for some $$$n$$$ is $$$x$$$. What do we know about this $$$n$$$? We know that $$$n$$$ is a multiple of each of $$$1, 2, \dots, x$$$, according to Fact 1 (and this is a sufficient condition for such an $$$n$$$ to exist with answer $$$x$$$). This means that $$$n$$$ is a multiple of $$$\text{lcm}(1, 2, \dots, x)$$$. But notice that $$$\text{lcm}(1, 2, \dots, 43) = 9\,419\,588\,158\,802\,421\,600 \approx 9 \cdot 10^{18} \ge 10^{18}$$$, so such $$$n$$$ doesn't exist for $$$x = 43$$$ within the constraints of the problem. This means that the maximum answer will be $$$42$$$, and your solution will find it. $$$\square$$$

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

My approach for C2 was a bit different. Let's suppose the maximum absolution value is mx. If mx is from positive, we'll first modify the array like this: v3-v1 >= mx, v5-v3 >= mx, v7-v5 >= mx ... For this, we'll kind of use 2 moves for each position, so we'll need n/2*2 = 20 moves.

After that, for each of v2, v4, v6... we can find a valid value (v[i-1] <= x <= v[i+1]) using only one move, except for if the last unmodified value is the nth index, for that we'll use 2 moves. So total = 20 + 9*1 + 2 = 31

We'll do the same if mx is from a negative value, but the other way around.

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

How to solve div2D in python?

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

Can you help me with 216358050. Why it is failing on pretests

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

How is a formal proof to the model solution of a problem in a competitive programming contest NOT required?

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

    This is the next codeforces phase.

    From Mathforces to Guessforces to Hopeforces.

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

Can anyone please explain the solution for problem Div2-D ? I read the editorial but didn’t quite understand it.

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

Can someone Please explain div2 B , I saw few codes in which brute forcing <= 100 works but I am unable to understand what is going on and how this thing works ? kindly explain please

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

    If you found an interval from l to r of length s such that every number in the interval divides n, there is an interval starting from 1 with the same length such that every number in it divides n. Demonstration: Analyzing the remainders mod i (1=<i<=s) of all the numbers in the interval [l,r] you can see that for every i there is at least one number x in [l,r] such that x=0 mod(i), which implies that i also divides n.

    So it is enough to find the largest interval starting from one that holds the condition. That interval will not be so long because n is divisible by lcm(1,2,3,...,s) and hence n must be greater than the lcm(1,2,3,...,s) (being s the length of the interval), and if n=100, lcm(1,2,...,s) will be greater that the product of every prime less than 100, which is greater than 10^18(You can implement the sieve of Eratosthenes in order to check that last thing).

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

Does anyone know how to apply the solution for the A?, I'm trying with cpp but it doesn't work.

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

    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.

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

      I was strying smthng like this

       #include<bits/stdc++.h>
       using namespace std;
      
       int main(){
          ios_base::sync_with_stdio(false);
          cin.tie(NULL);
          cout.setf(ios::fixed);
           int t;
           cin >> t;
           while(t--){
               int n;
               cin >> n;
               vector<int>v(n);
               for(int i = 0; i < v.size() ;i++){
                   cin >> v[i];
               }
               int sad = 0;
               for(int i = 0; i < v.size(); i++){
                   if(v[i] == (i+1)) sad++;
               }
               cout << ceil((sad/2)) << endl;
           }
       }
      
      • »
        »
        »
        »
        16 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You need to learn how division works in c++. In particular int divided by int is int, result is rounded down. If you want to use ceil function, (int)ceil(sad/2.0f) will give you the right answer. But you can use formula for integers, (a + b — 1) / b. In this case, (sad + 1) / 2.

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

any one to explain this more please?: (div2 hard C)

Therefore, you need additional $$$min(x_1+x_2,y_1+y_2)$$$ moves. Since $$$x_1+x_2+y_1+y_2 \leq 25$$$, $$$min(x_1+x_2,y_1+y_2) \leq \lfloor 25/2 \rfloor = 12$$$, as we wanted. Now you can simulate the process in both cases (positive and negative), and choose one that requires $$$\leq 31$$$ moves in total.

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

    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

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

    Here's an alternate explanation without so many equations:

    As in the model solution, we want to make everything positive or everything negative in at most 12 queries. If there are at most 12 positive numbers and at most 12 negative numbers, this is easy: pick the number with the largest absolute value and add it to every number (at most 12) of the opposite sign.

    If there are at least 13 positive numbers (the solution is the same with at least 13 negative numbers), pick a positive number and add it to itself five times. The resulting number will be at least $$$32$$$ (the worst case is if we start with $$$1$$$), and we can then add that to the negative numbers to make them positive. There are at most seven negative numbers, so this takes at most $$$5 + 7 = 12$$$ queries.

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

My solution to Div. 1 A2 / Div. 2 C2 differs from the editorial and uses at most 30 moves:

https://mirror.codeforces.com/contest/1855/submission/216373889

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

B's solution is too abstract. Can anyone prove it

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

    Note that the interval $$$[l,r]$$$ contains at least one multiple of $$$x$$$ for each $$$1 \leq x \leq r-l+1$$$.

    This is the only observation you need and its trivial to prove.

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

I never think bitset as official answer. When I came up with bitset, I rather think of $$$O(nlogn)$$$ solution and got stuck for hours. Upset when reading editorial :(

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

For 2C. Can someone explain why this code needs to include a special judgment for sorting

https://mirror.codeforces.com/contest/1855/submission/216393543 (AC)

https://mirror.codeforces.com/contest/1855/submission/216393849 (WA)

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

Editorial of D using the term "type" when saying about each move (it said use moves of type 1, 2,..., x), but I don't get it. Could anyone explain for me what actually the "type" mentioned here?

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

In Div 2 problem B, can you prove that multiple from 1 to r — l + 1 statement Thanks

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

Some clarifications, some doubts -- (regarding Problem B, div. 1) Clarifications :

  • In case you are trying the greedy method (I did too, during the contest). The approach would be that if you can move forward with an increase in your total points, that means you should do it. While this is fine when you are traversing the array, once the array is finished you would need the minimum points spent to open all the cards(which could be more than the no. of cards), and then calculate the score (sum of all cards — (used points — 1)) — so this doesn't work (greedy approach will not necessarily give you the minimum points, and there are also more arguments as to why this approach can't work).

  • Now, according to the model solution : say we arrive at the card with index i, if we could find a way to make i points using the cards with less than index i, then that means we can update the answer with (sum(till i) — (i)).

Doubt :

  • Why do we set the i th bit back to zero ? If we found a way to reach i, shouldn't it be kept as a possible sum ?
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If $$$dp_{i,i} = 1$$$, it means there is a way to unlock exactly $$$i$$$ cards using the first $$$i$$$ cards. This means the game is finished, because all the unlocked cards have already been used. In that case, you can't use the following cards, so you have to discard that case from the DP before processing card $$$i+1$$$.

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

      Oooh, thanks! Got it!

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

      TheScrasse may you provide a proof for the first claim the card problem is making that is order of card taking will not effect the answer ? As in suppose I choose first card which says to take 4 more cards , then I choose the 3rd card after 1st card is removed which I take and claim it I will get suppose 6 points , 2nd card I didn't consider but it was having 10 points I then take that but this time choose to draw 10 cards , so will this not affect the final points I am getting ?

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

        Suppose you don't use the cards in order. If you use them in order instead (but you don't change the type of move you perform with each single card $$$i$$$), both the number of victory points and the number of unlocked cards don't change.

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

      but why 2*n cards i cant come up with anything upd: i get it whatever the sum of first n numbers be any two number sum will lie between o to 2*n

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

My solution to Div.1 A2 uses $$$1+\lceil1.5n\rceil$$$ operations.

Assume that $$$\max a_i + \min a_i\ge 0$$$, and $$$a_p=\max a_i$$$. First, set $$$a_p\gets 2a_p$$$. Then, iterate $$$i$$$ from $$$1$$$ to $$$\lfloor 0.5n\rfloor$$$, for each $$$i$$$, we can do $$$\le 3$$$ operations that will only change $$$a_{2i-1}, a_{2i}$$$ to make $$$a_{2i}\ge a_{2i-1}\ge a_{p}$$$ (after these operations, we set $$$p\gets 2i$$$).

let $$$x=[a_{2i-1}<0], y=[a_{2i}<0]$$$.

  • If $$$x+y<2$$$, do $$$(1+x)$$$ times $$$a_{2i-1}\gets a_{2i-1}+a_{p}$$$, then do $$$(1+y)$$$ times $$$a_{2i}\gets a_{2i}+a_{2i-1}$$$.
  • If $$$x+y=2$$$, do $$$2$$$ times $$$a_{2i}\gets a_{2i} + a_p$$$, then do $$$a_{2i-1}\gets a_{2i-1}+a_{2i}$$$. Note that $$$a'_{2i-1}=a_p+(a_p+a_{2i-1}+a_{2i})\ge a_{p}$$$ since $$$a_p + 2\min a_i\ge 0$$$.

Finally, if $$$n$$$ is odd, do $$$2$$$ times $$$a_n\gets a_n+a_p$$$. The case $$$\max a_i+\min a_i<0$$$ is symmetric.

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

My solution for Div1 E:

Let $$$dp_i$$$ be the number of ways to sum up to $$$i$$$ with $$$a_1, ..., a_k$$$, then adding a number $$$x$$$ will let $$$dp_j \leftarrow dp_j+dp_{j-x}$$$. So we can construct $$$a_1, ..., a_k$$$ by letting $$$dp_i$$$ form a geometric progression in the very beginning and non-decreasing afterwards (also be aware to keep $$$dp_{60} <= m$$$). Setting the geometric progression factor around $$$3$$$ seems to be a good choice in practice.

The code is very short: 216442010

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

couldnt ubderstood why the EV of 1. element reaching the 2. + EV of 2. reaching the 3. = EV of 1. reaching the 3. in div2E/div1C ( I need some intuition on linearity of expectation)

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

    For some intuition, consider $$$n = 2$$$ (so, there are $$$3$$$ blocks, and the last one is in position $$$m+1$$$). The general case is similar.

    Here, the expected value moves required for block $$$1$$$ to reach block $$$3$$$ is equal to the final answer, which is also equal to the expected total number of moves, which is the sum of the expected number of moves of blocks $$$1$$$ and $$$2$$$.

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

I really liked the contest. Tasks A-D. Were very pleasant to solve. True, I didn't have time to solve them all, but still. I think the gap between C and D is too big, but still tolerable. I also don't understand why many people are against using bitset in the author's solution. After all, such a solution, with adequate implementation, fits in 0.6 seconds, which is very good.

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

How does "One can verify that to handle correctly all points with coordinates up to 1000 it is necessary to compute Ak for 0≤k≤62." work?

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

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

Why the following is true: "If you consider a single pair of blocks, every block moves with probability 1/2"?

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

    The other blocks don't affect neither the position of the two considered blocks nor the number of moves that we are calculating, so we can ignore them. Since the two remaining blocks move equiprobably, they move with probability $$$1/2$$$.

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

Since x1+x2+y1+y2≤25, min(x1+x2,y1+y2)≤⌊25/2⌋=12

this is not math, this is magic. really awesome

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

Is there anyway to solve div1B without bitset

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

    No, because there is no way to solve that type of knapsack without bitset.

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

What happened?

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

I’m a huge fan of dario2994. He created so many smart, innovative and elegant adhoc problems. Just curious: what does the id mean? Was him born in 2994?

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

    Thank you, you made me happy.

    Dario is my (unofficial) second name, 29 is the day of my birthday, '94 is the year.

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

For the solution of problem 1854D, where it says "Now you know $$$2k$$$ nodes in the cycle". Shouldn't that be "Now you know $$$2k$$$ nodes in the component with node $$$1$$$"?

I don't think getting a "yes" response from querying $$$(i,k,C)$$$ guarantees that node $$$i$$$ is in the cycle $$$C$$$. It just guarantees it's in the same component.

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

    I've updated the editorial.

    After a batch of queries $$$(i, k, C)$$$, you know all the nodes whose distance from $$$C$$$ is at most $$$k$$$.

    • If the cycle does not contain nodes with distance $$$> k$$$ from $$$C$$$, you find the whole cycle.
    • If the cycle contains at least one node with distance $$$> k$$$ from $$$C$$$, it also contains nodes with distances $$$1, 2, \dots, k$$$, so you will find at least $$$k$$$ new nodes in the cycle.
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you know which nodes are in the cycle?

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

        You don't need to know which nodes are in the cycle. But you will be sure that you have found the whole cycle if the number of nodes in $$$C$$$ isn't at least doubled.

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

i think the tutorial of the problem "1854B Earn or Unlock" have some problems(maybe im wrong and stupid) the dp translation"dp[i]=dp[i−1] << ai" should be "dp[i]|=dp[i−1] << ai"? add a "or" operation to it? qwq

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

Update: Just figured it out. I misunderstood the editorial.

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

    I was not able understand what hints means in problem expected destruction . can you please explain this?

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

      The main idea was to think of it as blocks moving on the number line (removing and adding X+1 is like moving right).

      Hint 1
      Hint 2
      Hint 3
      What the three hints allude to
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello, i am confused about "1854B — Earn or Unlock"

the forth testcase goes as follows:

10

4 3 1 5 5 3 4 9 7 0

the answer should be $$$33$$$.

the first card has to be use to unlock or we end up with a value of $$$4$$$. if we don't unlock with one of the fives we only can get the next $$$4$$$ cards with values $$$3+1+5+5=14$$$ if we use one of them to unlock we can "earn" the rest that follows afterwards so we get a total of:

$$$3+1+5 \ + \ 3+4+9+7+0= 32$$$

have i missed something or is the testcase wrong?

i would be very thankful for help.

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

    We can use the first three cards (with values $$$4$$$, $$$3$$$ and $$$1$$$) to unlock $$$4+3+1=8$$$ more cards (all cards except for the last card with value $$$0$$$) and use all remaining cards to get a score of $$$5+5+3+4+9+7=33$$$

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

In problem div2 E, russian statements says "What is expected number of seconds until S is NOT empty" in 6 line.

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

Edited — Got it.

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

Interesting that in some sense both div1B and div1E are problems about subset sum.

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

UPD: Nevermind, I assumed that "using" was using the card to unlock, but it's about using it for either option

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

218706810

Can anyone help here?

getting MLE in testcase 2

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

    my solution was also giving MLE initially . Try this test -1 -1 -1 0 0

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

I must say dual(hard version) is a pretty good prblm

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

Dual(Easy Version) -> 220885517 dual (Easy + Hard Version) -> 220968157

»
11 months ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

TheScrasse where is proper justification for problem B,why interval starting from 1 always give answer??, this is what will happen if highschool studets become problemsetters.they probably dont know importance of proof of correctness whiile stating something.please dont state something in open air without justification.

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

    Fortunately I'm not a high school student anymore.

    Anyway, the proof is in the above paragraph. If the answer is $$$x$$$ because there is a valid interval of length $$$x$$$, that interval contains one multiple of $$$1$$$, ..., one multiple of $$$x$$$, so $$$[1, x]$$$ is also valid. In other words, any interval which does not start from $$$1$$$ is useless because it can be replaced with an interval which starts from $$$1$$$.

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

In question B, im unable to understand this intuition that — find the smallest x that does not divide n. The answer is x−1. i tried reading editorial, but didn't understood, plz help anyone. thnks:))

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

腹肌男,我爱腹肌男