Блог пользователя TheScrasse

Автор TheScrasse, 15 месяцев назад, По-английски

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
Разбор задач Codeforces Round 889 (Div. 1)
Разбор задач Codeforces Round 889 (Div. 2)
  • Проголосовать: нравится
  • +196
  • Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

really nice problems and fast editorial, thanks for the contest

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +369 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +106 Проголосовать: не нравится

    it's something new

  • »
    »
    15 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится -30 Проголосовать: не нравится

    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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +83 Проголосовать: не нравится

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

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится -67 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
            Проголосовать: нравится +75 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            15 месяцев назад, # ^ |
            Rev. 3   Проголосовать: нравится -67 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              15 месяцев назад, # ^ |
                Проголосовать: нравится +92 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              15 месяцев назад, # ^ |
                Проголосовать: нравится +37 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            15 месяцев назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +189 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            15 месяцев назад, # ^ |
            Rev. 2   Проголосовать: нравится -63 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              15 месяцев назад, # ^ |
                Проголосовать: нравится +44 Проголосовать: не нравится

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                15 месяцев назад, # ^ |
                  Проголосовать: нравится -45 Проголосовать: не нравится

                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.

            • »
              »
              »
              »
              »
              »
              »
              15 месяцев назад, # ^ |
                Проголосовать: нравится +89 Проголосовать: не нравится

              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.

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +56 Проголосовать: не нравится

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

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится -27 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
            Проголосовать: нравится +50 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            15 месяцев назад, # ^ |
              Проголосовать: нравится -51 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              15 месяцев назад, # ^ |
                Проголосовать: нравится +26 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                15 месяцев назад, # ^ |
                  Проголосовать: нравится -25 Проголосовать: не нравится

                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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  15 месяцев назад, # ^ |
                    Проголосовать: нравится +26 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  15 месяцев назад, # ^ |
                    Проголосовать: нравится +41 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  15 месяцев назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  15 месяцев назад, # ^ |
                    Проголосовать: нравится -32 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +74 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится -14 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +161 Проголосовать: не нравится

    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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +66 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +31 Проголосовать: не нравится

        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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Excellent, insanely fast editorials!

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 4   Проголосовать: нравится +16 Проголосовать: не нравится

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)$$$?

»
15 месяцев назад, # |
  Проголосовать: нравится +228 Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
15 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +232 Проголосовать: не нравится

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!

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится

    Thanks for the feedback! :)

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +67 Проголосовать: не нравится

      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$$$?

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +46 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
            Проголосовать: нравится +28 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            15 месяцев назад, # ^ |
              Проголосовать: нравится +15 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          15 месяцев назад, # ^ |
          Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

          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!

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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)

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What could be the difficulty ratings for all the problems ?

»
15 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
15 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

How to solve div2D in python?

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +181 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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;
           }
       }
      
      • »
        »
        »
        »
        15 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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.

»
15 месяцев назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
15 месяцев назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 ?
  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oooh, thanks! Got it!

    • »
      »
      »
      15 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      5 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

»
15 месяцев назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

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.

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +44 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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)

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
15 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

this is not math, this is magic. really awesome

»
15 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Is there anyway to solve div1B without bitset

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What happened?

»
15 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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?

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thank you, you made me happy.

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How do you know which nodes are in the cycle?

      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
15 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    15 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      15 месяцев назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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
»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    15 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Edited — Got it.

»
15 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
15 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

218706810

Can anyone help here?

getting MLE in testcase 2

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone tell why $$$dp[i][i] = 0$$$ in problem D ?

»
10 месяцев назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

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.

  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

腹肌男,我爱腹肌男