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
raitng++raitng++raitng++raitng++raitng++
This is my first time participating in the AtCoder competition, and I hope it can be a great start.
GL&HF!
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
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
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://mirror.codeforces.com/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.
In Task D, is there any solution for the below test case:
Any help is welcomed.
0 2 1 -5
Bro what if there are multiple incoming edges for the same vertex like exaple input 3 how would you do that
You don't need to, just assign any value to any node. Rest of the connected component gets fixed values.
In this case, difference between 1st and 4th vertex numbers should be 4, but as per answer it will be -5, which is wrong.
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
Is this condition mentioned in the question all paths from a->b will have same weight?
Yes, it is in the problem that a valid solution does always exist
Problem F's Statement is unclear.
Problem F's Statement is unclear.
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 .
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
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?
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.