atcoder_official's blog

AtCoder Beginner Contest 373 Announcement
By atcoder_official, history, 2 months ago, In English

We will hold AtCoder Beginner Contest 373.

We are looking forward to your participation!

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

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

Thanks for the contest. I hope my raitng++.

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

I love to give contests on atCoder because of short written and educational problems. CF sucks.

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

    No,I love CF

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

      CF is always late to Chinese...

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

        That's true.I always get poor performance because I am sleepy.But when I vp the same problems,it will be better.

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

I think atcoder is easy than CF but its rating++ is so slowy and CF rating++ is quickly.

The CF contests starts time is so late for me but atcoder contests starts time is just in time.

I am a Chinese people.This article have some grammer questions.Please forgive me.

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

raitng++raitng++raitng++raitng++raitng++

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

This is my first time participating in the AtCoder competition, and I hope it can be a great start.

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

GL&HF!

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

Wish I solve 6 problems.

→ Reply
»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem G is UVA1411.

→ Reply
»
2 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Problem C was on the level of problem A.

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

Why Editorial Video show it "FINAL"? Why is this the last one?

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

    May be the final video, the updated and finalised to post.

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

      解説するぜこれまだやってたの今回が最後

      This is the last one.

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

        Sorry, not the native speaker of the language, but translated it; where did you get the information?

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

how to F?

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

For E, ans is 0 when m == n.

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

    omg TY, that was my issue the whole time ._. I thought that was obvious, but I had gotten 1 WA and that was the WA.

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

user https://atcoder.jp/users/Lydic copied the streamer https://atcoder.jp/contests/abc373/submissions/58234833.

the code is very similar and user 'lydic' sit beside me.

i dont think this is a good behavier

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

    how can i Report bad behavior?

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

      What do you mean by streamer? Do you guys get to stream in contests? And why are you guys sitting together?

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

        he watched a live broadcast during the contest and copied the code, maybe just to increase his rating. I'd just like to report that, as it's exactly a bad behavior.

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

        In brief,we're classmates,but in this contest,he watch the Streamer，and copy his code. Only change code style,i think it should be banned

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

        we were at school and the teacher organized us to play the contest so we are in the same computer room

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

      I mean, is there a offical way to accuse the cheating behavior?

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

How to count elements strictly greater than a given number optimally which is used in problem 5 , any other techniques ?

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

Why the time complexity of problem F is $$$O(W^2\log W)$$$, I think it may be $$$O(NW\log W)$$$

https://atcoder.jp/contests/abc373/editorial/11051

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

Alternate solution to G: Randomly generate a permutation. While intersections exist, find one and uncross them by swapping the corresponding elements in the permutation. https://atcoder.jp/contests/abc373/submissions/58233895

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

Can someone prove or disprove my solution to problem G?

It works by starting with $$$R = [1, 2, \ldots, n]$$$ then perform the following for no more than $$$2n$$$ times. Find any $$$i, j$$$ that $$$P_iQ_{R_i}$$$ intersects with $$$P_jQ_{R_j}$$$ then swap $$$R_i$$$ and $$$R_j$$$. If the solution is not reached then the answer is $$$-1$$$.

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

    looks similar to my solution https://codeforces.net/blog/entry/134408?#comment-1203032

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

    An answer always exists, though. The pairing with minimum sum of segment lengths is optimal.

    If there exist points P1, P2, Q1, Q2 such that P1 is paired with Q1, and P2 is paired with Q2, and segments P1 — Q1 and P2 — Q2 intersect, then pairing P1 with Q2 and P2 with Q1 will decrease the total sum of segment lengths, and remove an intersection point. If the sum of segment lengths of sum pairing is optimal, then there does not exist a pair of intersecting segments.

    What must be proved is that $$$2n$$$ iterations is sufficient.

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

      I think $$$2n$$$ swaps are not insufficient. If the pairing is unique, then “swapping” is same as sorting. Worst case is that it reduces to bubble sort, which will take $$$ O(n^2)$$$ swaps. The way I coded it makes it do many swaps in one iteration, which I do not know would be sufficient, or works with sufficiently high probability.

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

In Task D, is there any solution for the below test case:

4 4
1 2 2
2 3 -1
3 4 -6
1 4 4

Any help is welcomed.

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

    0 2 1 -5

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

      Bro what if there are multiple incoming edges for the same vertex like exaple input 3 how would you do that

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

        You don't need to, just assign any value to any node. Rest of the connected component gets fixed values.

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

      In this case, difference between 1st and 4th vertex numbers should be 4, but as per answer it will be -5, which is wrong.

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

        I just realized, your test case is invalid. 1->2->3->4 , total sum = -5, but 1->4 is 4, hence deeming your Test Case invalid

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

          Is this condition mentioned in the question all paths from a->b will have same weight?

          → Reply
»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Problem F's Statement is unclear.

→ Reply
»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Why in editorial code in task F the graph is being built as bidirectional graph but in problem statement its mentioned that the jth directed edge goes from uj to vj .

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

Problem E statement was a bit unclear. I had trouble to understand whether inequalities were strict. I think it should always be stated "strictly less" or "less or equal".

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

G has an originate problem (and I submitted my code for that problem changing N from 105 to 305), but my code got WA*3. It turned out that, the eps for precision error should be $$$10^{-14}$$$ or something less, which is quite annoying.

Lost my first blood. btw congrats to maspy

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

Thank you for the contest, I really enjoyed solving problem E (after the contest :(

But what exactly is the purpose of problems A, B and C. This is definitely nothing but a simple coding exercise. No problem here and it's not teaching the contestant a lot!

I've been enjoying ABC contests at Atcoder recently but I always get frustrated with first 2 or 3 problems.

Is there a way I can contribute ideas for such problems?

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

Was the editorial solution given for problem F, a standard approach? If it is a standard approach please share some resource to learn/practice the Greedy approach given in editorial for Problem F. I would be very thankful if someone answers.

→ Reply