chokudai's blog

AtCoder Beginner Contest 140 Announcement
By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 140.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

Comments Comments (35)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

How to solve E?

D — Let a be the number happy people initially, answer would be min(n-1, a+2*k) because at every step you increase at most 2 happy people.

F — Just simulate the process greedily. Start with the maximum produce the second maximum with it then 3rd and 4th maximum using 1st and 2nd respectively. At any step, if it is not possible to then answer is No else Yes. Submission

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain sample test case 3 of problem D?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just flip the RRRRR block so the result is all LLLLLLLLLL.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can take L = 6, R = 10. The string will become LLLLLLLLLL

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To solve E you can iterate all the i that in some array the second largest is i

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if i appear at is[i] you need to find the nearest j that bigger than i in the left and second nearest k in the left also the nearest and the second nearest in the right

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And I use set::lower_bound to do this

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can read my solution by searching handle:Gary in the contest

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please send a link to your submission.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For F, I used the same thing you said: simulated the process using priority_queue but got WA. Here's my submission: Submission

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 4   Vote: I like it +9 Vote: I do not like it

    For every element $$$x$$$ ,try to calculate $$$t(x)$$$ ,the number of intervals which $$$X_{L,R}=x$$$ .

    The answer is $$$\sum_{x=1}^n x\cdot t(x)$$$ .

    If $$$a_p=x$$$ ,let $$$pre1$$$ be the largest $$$i$$$ that $$$1\le i<p,a_i>a_p$$$ ,and $$$pre2$$$ be the second largest $$$i$$$ .

    Let $$$suf1$$$ be the smallest $$$i$$$ that $$$p<i\le n,a_i>a_p$$$ ,and $$$suf2$$$ be the second smallest $$$i$$$ .

    Then $$$t(x)=(pre1-pre2)\cdot (suf1-i)+(suf2-suf1)\cdot (i-pre1)$$$ .

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you share the code?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Here's my submission.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Which technique did you use in this problem?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Binary search and segment tree.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              It's out of my knowledge, I will update soon =))

              → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      too good! but i had problem in implementation when pre2 doesnt exist. can you help me with it ?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well,as you can notice in my code, $$$pre1-pre2$$$ means we that can choose $$$pre2<L\le pre1$$$ .

        So if $$$pre2$$$ doesn't exist,we set $$$pre2=0$$$ ,then the inequality is $$$1\le L\le pre1$$$ ,which means we can choose any $$$L\le pre1$$$ .

        Similarly,we set $$$suf2=n+1$$$ when it doesn't exist to avoid discussion.

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      May I ask what is the complexity of this solution? If you do this for all n, each of which results in a linear scan, would the solution be quadratic? Thank you so much!

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I use binary search and segment tree to calc them.My code.

        The complexity of the solution is $$$O(n\log^2 n)$$$ .

        I guess there's a linear approach,but I haven't got it yet.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem D, why the output in the sample input #4 is 7 instead of 6, thanks in advance

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you consider one based indexing then change the 4th indexed 'L' and 6th indexed 'L' then the string will be RRRRRRRLL and number of happy people will be 7.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You swap the two left L into R, then result is RRRRRRRLL, whichs value is 7.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found some problems harder to understand than usual.

Needed like 30 minutes to get the fact that L turn to R and vice versa in D, not just the possitions swap.

I understood the way of reproduction in F after the contest, not within.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Geothermal's Solutions https://mirror.codeforces.com/blog/entry/69629

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A solution — Just need to print n*n*n B solution — https://atcoder.jp/contests/abc140/submissions/7385892 . C solution — https://atcoder.jp/contests/abc140/submissions/7390408 . D solution — https://atcoder.jp/contests/abc140/submissions/7399771 .

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All solutions by me. If any doubt in any of these do comment

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong in this submission for F?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F:why I get WA on test_69 and test_71 in this submission?

Could someone help me?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

When would be editorial published for English readers? And also where is the link of English editorial provided?

→ Reply