maroonrk's blog

By maroonrk, history, 17 months ago, In English

We will hold AtCoder Regular Contest 162.

The point values will be 300-500-500-700-700-900.

We are looking forward to your participation!

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

| Write comment?
»
17 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Why some arc have discussions on codeforces but some don't?

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

Long time no see, ARC.

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

Nice problems with small $$$N$$$ s.

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

Interesting and tricky problems!

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

Actually, C can be solved in $$$O(n)$$$.

Screencast with commentary

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

    how?Could you tell me?

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

      I did. If you didn't notice, there is a link to screencast with commentary, where I'm explaining $$$O(n)$$$ solution to C, among other things.

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

        emmmm.....I just thought you can solve the "subtree mex" in O(n)....

        Well I know the O(n) solution for THIS porblem.

        Anyway thank you!

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

        emmmm.....I just thought you can solve the "subtree mex" in O(n)....

        Well I know the O(n) solution for THIS porblem.

        Anyway thank you!

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

I solved A by counting inversions in $$$O(n$$$ $$$log$$$ $$$n)$$$. The idea is creating a new array $$$cnt$$$ where $$$cnt_i$$$ is the number of $$$j$$$ so that $$$i < j$$$ and $$$a_i > a_j$$$. Then the answer is the number of minimum elements in array $$$cnt$$$. However I can't quite explain why it worked.

For problem B I just try to move the number $$$n$$$ to position $$$n$$$, $$$n-1$$$ to position $$$n-1$$$. When you are down to $$$1$$$ and $$$2$$$, if $$$2$$$ is in front of $$$1$$$, the answer is $$$No$$$. The answer is $$$Yes$$$ otherwise.

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

Actrually,I didn't understand problem A's statement even when I passed the problem.

I just guessed what it may wish me to do.