atcoder_official's blog

By atcoder_official, history, 3 months ago, In English

We will hold Daiwa Securities Co. Ltd. Programming Contest 2023(AtCoder Beginner Contest 331).

We are looking forward to your participation!

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

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

Atcoder beginner contests are really great.

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I hope I can get better grades than before......

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

D with 450 points… seems scary

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

Guess the order of difficulty among A,B,C,D :)

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

Good luck to everyone!

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

D is more scary than E……

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

我是菜狗

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

    me too

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

    Maybe you should use English instead of Chinese that this is a English website.

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

      I just want to express my powerless feeling. QAQ

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

      how did you make your contribution into a negative number?

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

D seems pretty complex and difficult...

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

Problem F is exactly same as this.

Solution can be found online anywhere, one of the solution is — Solution

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

$$$D$$$ is such a heavy implementation problem ,I took a lot of time in it to solve ,like finding stupid bugs and typos killed a lot of time of mine, then went to $$$E$$$ just to find that it's just a submission bait which I speed ran implementation in last 4 mnts but missed out by fucking 3 seconds , such a stupid performance in the end which could have been a far better contest if I executed implementation well fuck!!

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

Lol I got nervous and solved B by DP, turns out it has better time complexity and almost O(1) space

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

    my solution was $$$O(N^3)$$$ and you did it speaks of bad contest giving style where you overkill an easy problem and kill time , best thing of Atcoder Beginner Contests is that they help you increase speed and improve implementation skills

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

      because I got nervous personally easier for me to think dp than brute force or greedy

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

    I solved B by DFS.

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

I think only problem D and G were smart anyone agree?

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

Atcoder please do not directly copy the CSES problem.

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

D should definitely be worth more points than E

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

    I think this too

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

      How did you solve E?

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

          E is like E in last Atcoder beginner contest, just add one point:

          Enumerate the main dish and find the most expensive side dish, then update the answer.

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

          I have solved it using segment tree with update. https://atcoder.jp/contests/abc331/submissions/48142030

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

        hint: The answer is among the L+1 largest pairs.

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

        I just use simple multiset idea for every element in B make a multiset of elements of A that are not allowed for that B, then from a global multiset of all the values in A remove those from it. Do this for every element in B and take cur + end element of multiset.

        One thing to take care: Don't do this is B has all the elements of A, then it should be skipped as it can't be paired

        code

        I think it's very easy idea maybe

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

          This work and not TLE because L <= min(1e5, N*M-1)

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

          What? Three almost SAME ideas?

          And I can explain that complexity of using just normal set is $$$O(L \log M)$$$.

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

Instead of enumerating solve B in O(n)

low iq
»
3 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Why so many Gs (and Ex when there was Ex) are math?

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

    Is it just me or most of them are about finding the expected number?

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

      why expected value questions are asked most frequently, i am just bad at probability..

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

    +1, adding Centroid Decomp, HLD, CHT or flows sometimes would be good at G.

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

    cause math so good

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

Problem F was copied from CSES. Even the title. 😒

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

Problem A was the hardest TBH.

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

Problem F can be passed by force.

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

no sense between the title and problem statement on problem B.

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

Can someone provide a better explanation for G. The editorial is too tough to understand.