We will hold AtCoder Beginner Contest 373.
- Contest URL: https://atcoder.jp/contests/abc373
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240928T2100&p1=248
- Duration: 100 minutes
- Writer: sotanishy, MtSaka, evima
- Tester: MMNMM, cn449
- Rated range: ~ 1999
- The point values: 100-200-250-400-500-550-600
We are looking forward to your participation!
Thanks for the contest. I hope my raitng++.
I love to give contests on atCoder because of short written and educational problems. CF sucks.
No,I love CF
CF is always late to Chinese...
That's true.I always get poor performance because I am sleepy.But when I vp the same problems,it will be better.
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.
Chinese too,but CF is a great OJ
Wish I solve 6 problems.
Problem G is UVA1411.
Problem C was on the level of problem A.
Why Editorial Video show it "FINAL"? Why is this the last one?
May be the final video, the updated and finalised to post.
解説するぜこれまだやってたの今回が最後
This is the last one.
Sorry, not the native speaker of the language, but translated it; where did you get the information?
how to F?
For E, ans is 0 when m == n.
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.
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
how can i Report bad behavior?
What do you mean by streamer? Do you guys get to stream in contests? And why are you guys sitting together?
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.
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
we were at school and the teacher organized us to play the contest so we are in the same computer room
I mean, is there a offical way to accuse the cheating behavior?
How to count elements strictly greater than a given number optimally which is used in problem 5 , any other techniques ?
Binary search
Can you explain your approach
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
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$$$.
looks similar to my solution https://codeforces.me/blog/entry/134408?#comment-1203032
I think it is the same solution.
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.
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.
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".
Yes, I think so.
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