maroonrk's blog

By maroonrk, history, 4 months ago, In English

We will hold AtCoder Regular Contest 136.

The point values will be 300-400-500-600-800-1000.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +135
  • Vote: I do not like it

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

oh , yes maroon-senpai go as hard as you always go >,<

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

why A has so long code

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

How to solve D?

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

    I used a 6-dimensional Fenwick tree. And laughed out loud when it got AC.

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

    While you are thinking about D,I am working my head off on B without success.

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

      I think the operation was equivalent to performing a simple swap operation 2 times. So, if an element occurs twice in array A, you can always make the array A equal to B. Otherwise check if you can make it equal by doing even number of swaps.

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

    You need to hold for each $$$X$$$ the number of elements $$$Y$$$ where for all $$$i$$$ in digit representation of $$$X$$$ and $$$Y$$$ $$$Y_i <= X_i$$$, You can do that by using inclusion-exclusion for example let's call the number of correct elements $$$F(x)$$$ so $$$F(99) = F(98) + F(89) - F(88)$$$.

    Now the answer is $$$\sum_{i=1}^{n} F(999999 - a_i)$$$ with some case handling for the $$$i < j$$$ part.

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

    SOS DP but with multisets.

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

    Maybe,you can use High-dimensional prefix sum(I got this name from translation,so it may be strange). This is my code:D

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

      Yeah,that's a good way to solve such problems

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

      Please explain your code or share some resources

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

        For example,you do as follows to get the 2-D prefix sum:

        for (int i=1;i<=n;++i)
        	for (int j=1;j<=n;++j)
        		a[i][j]+=a[i-1][j];
        for (int i=1;i<=n;++i)
        	for (int j=1;j<=n;++j)
        		a[i][j]+=a[i][j-1];
        

        After the first part,$$$a_{i,j}$$$ means $$$\sum_{x\le i,y=j}num_{x,y}$$$ .And when the second part is finished,$$$a_{i,j}$$$ means $$$\sum_{x\le i,y\le j}num_{x,y}$$$ .

        So when you do the k-D prefix sum,you can use the similar way to get the prefix sum from 1-D to k-D.

        In my code,I don't want to make special judge at the bound(when it meets 0,it's impossible to decrease by 1),so I add 1 on every digital which leads to the code may be strange.

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

          You can modify the bounds of your loops.

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

      wow, I always knew only O(2^D) way to build D-dimensional prefix sums...

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

      I also used High-dimesnsional prefix sum but in a noob way (it will make your day better) and your code looks like magic to me.

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

    You can also use meet-in-the-middle, that is:

    1. Define $$$dp[i][j]$$$ where $$$i, j < 1000$$$, for how many number in array $$$A$$$ whose first 3 digits are equal to $$$i$$$ and last 3 digits are smaller than $$$j$$$'s 3 digits respectively. You can fix $$$i$$$ and enumerate for $$$j$$$ to compute $$$dp[i][j]$$$.
    2. Then define $$$dp2[i][j]$$$ for how many number in array $$$A$$$ whose first 3 digits are smaller than $$$i$$$'s 3 digits respectively and last 3 digits are smaller than $$$j$$$'s 3 digits respectively. Now you can fix $$$j$$$ and enumerate for $$$i$$$ to compute $$$dp2[i][j]$$$ using $$$dp[i][j]$$$.
    3. Lastly, compute the answer.

    It seems that we need calculate $$$10^9$$$ times, but it turns out that we only need about $$$3 \times 10^8$$$ times. My code is here https://atcoder.jp/contests/arc136/submissions/29758496

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

    My approach was a bit different than the editorial.

    First calculate for each $$$1 \leq j \leq 1000000$$$, $$$dp[j]$$$ where $$$dp[j]$$$ means the number of elements in the array which have all digits greater than or equal to $$$j$$$. This part can be done by PIE.

    Let's now calculate the number of bad pairs instead. For each element, lets do inclusion-exclusion over the digits which will lead to carry-over. For example, in $$$21631$$$, digits $$$6$$$ and $$$2$$$ will lead to carry over if and only if the number to be added is of the form $$$y_{1}x y_{2} xx$$$ where $$$x$$$ can be any digit and $$$y_{1} \geq 8$$$ and $$$y_{2} \geq 4$$$. The number of such integers is stored in $$$dp[80200]$$$. Hence we perform PIE.

    Code

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

    I used a 6-dimensional prefix sum, which can solve this problem in $$$O(N)$$$ time.

    Here is my code: D

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

This is by far the worst ARC ever.

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

    I also had bad difficulties to solve B and C. Both where not simple because they looked like we could implement simulation, but turns out simulation is comlecated and actually not needed at all...

    That where kind of "better think twice" problems, which are not so bad, I think.

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

Thanks for such brilliant E! I was shocked by its beauty when I opened the editorial.

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

B: 40AC 3WA gang, checking in...

so close, yet so just wrong...

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

I think B is a good problem, which is even harder than D.It's pity that the data of B seems to be a little weak, and several of my friends got AC with wrong algorithm.

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

    B can be solved in O(n^2) time (when counting inversions).

    If we had to use some kind of tree (eg. Fenwick) to get nlogn it would have been way harder.

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

      Or is my solution wrong? (it got AC)

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

      But counting inversions can also be done by merge sort, which is O(nlogn).

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

        ah didn't know — but still it's not needed

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

      May I see your code write by counting inversions, because I got WA in this way...

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

        It's not only about counting inversions — if there are two values that are the same then you don't have to care about parity of inversions.

        But here is my code if you want it: https://atcoder.jp/contests/arc136/submissions/29743627

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

          oh! I see, not only missed the two values are the same situation, but my implementation of counting inversions break at that time..., thanks~

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

          This problem really made me frustrated. I can't match this with inversion parites. How you come up with the solution during contest? or is this a well-kown puzzle that I miss?

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

            it's pretty standard tbh

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

              Never thought about the use of inversion ~ really tough to figure it out by myself

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

                I mean with the operation given in task you never change parity of inversions.

                So if initially parity of inversions is odd it will never be even and the other way around.

                So I guess linking the task to inversions is fairly forcing.

                What's hard is 'proving' that from every odd state you can reach every other 'odd' state.

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

                  Maybe it's not hard actually.

                  Like I don't know, I guess once you see similar problem you're going to link it to inversions pretty fast.

                  But maybe if you've never seen anything similar (both in cs and math) then it might be hard, I agree.

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

                  Thanks for sharing!

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

            Indeed, it is a variant of the well-known puzzle called eight-puzzle, we can convert the task in it from matrix into a sequence to discuss. But this task is give you the sequence initially.

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

              Really helpful. I see some related issues on GeekforGeeks.

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

Shouldn't the definition of $$$e_n$$$ in problem F be starting from the given input state?

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

Hello, Can anyone explain the solution for problem B? I spent more than an hour to get no clue. I read the editorial but not very much clear. What is parity of the inversion number of an array?

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

I think the following statement in $$$C$$$'s editorial for the case in which $$$M=D$$$ is incorrect:

"Thus, it can be seen that an operation choosing a minimal segment containing all Ms will decrease both M and D by 1."

Instead, I think we should find $$$2$$$ occurrences of $$$M$$$ where the region in between them has no $$$M$$$'s (call that region $$$reg$$$), then decrease all the array (except $$$reg$$$) by $$$1$$$. This should decrease both $$$M$$$ and $$$D$$$.

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

can anyone hack my solution of B ?

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

Problem B was a lot like 1591D - Yet Another Sorting Problem (which I find amusing because that contest generated a lot of controversy for using a problem that appeared on Atcoder). Also, problem C happened to be on the team round of the Harvard-MIT Mathematics Tournament which occurred last week (but the problems aren't posted yet). However, I still enjoyed this contest a lot, especially problem E.

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

    Thanks. In the past few hours, I was trying to look for this problem 1591D. I remember such a question appeared which is like today's ARC 136B, and was trying to find out where did I see it.

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

I wonder what "carry" means in problem D...QwQ

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

I think problem C is more difficult than problem D. The order of the two problem should be exchanged.

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

    Could I ask why the solution counts the absolute differences of adjacent elements?

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

      I don't know, too. I use the solution that calculate max(0,a[i]-a[i-1]) .

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

Have a similar problem with C?

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

    Maybe you can try USACO2022 Dec Bronze. The second problem is similar with C.

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

How should I solve problem B? Can someone give me some guidance?

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

In A, O(n) is even giving tle in python while in C++ it got ac in just 16ms that's why C++ is always better than any other language. (https://atcoder.jp/contests/arc136/submissions/29802542)