We will hold AtCoder Regular Contest 147.
- Contest URL: https://atcoder.jp/contests/arc147
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220904T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: PCTprobability, blackyuki
- Tester: Nyaan
- Rated range: — 2799
The point values will be 300-500-600-700-800-1100.
We are looking forward to your participation!
As one of the Writers, I hope all participants enjoy the contest. Good luck!
As one of the writers, good luck and have fun!
I tried first time at Atcoder , i realised that problems level is higher than codeforces. is it?
It wasn't this time
But there might be a small problem of time,becase COMPFEST 14 — Preliminary Online Mirror will begin at 21:35(UTC+8 for me)
Does anyone see the tasks?
include <bits/stdc++.h>
using namespace std; signed main() { int n; cin>>n; vector vv; for(int i=0;i<n;i++) { int x; cin>>x; vv.push_back(x); } int total=0; sort(vv.begin(),vv.end()); while(vv.size()>1) { int a1=vv[vv.size()-1]; vv.pop_back(); reverse(vv.begin(),vv.end()); int a2=vv[vv.size()-1]; if(a1%a2!=0) vv.push_back(a1%a2); reverse(vv.begin(),vv.end()); total++; } cout<<total<<"\n"; }
ATCODER A
Cheater?
Is problem E a famous problem ? djq_fpc solved it in 10min ...
It's a simple greedy
E is an enhanced version of this problem https://www.51nod.com/Challenge/Problem.html#problemId=1328
great problems
can we see tags of Problem at Atcoder ,someone please?
Idk why but problems A and B felt very familiar to me. I even thought I opened some old contest by mistake.
Would anyone like to share more details about problem C? I think I have reached the step that the distance between the leftmost point and rightmost point should be as small as possible, but could not figure out how to handle the other n-2 points.
Do your process recursively to minimize $$$(N-1)(x_N-x_1)+(N-3)(x_{N-1}-x_2)+(N-5)(x_{N-2}-x_3)\cdots$$$.
Can you please elaborate?
When $$$x_1\le x_2\le \cdots \le x_N$$$, the answer is:
You just need to organize this well. Each row $$$i$$$ means $$$\displaystyle \sum^N_{j=i+1}|x_j-x_i|$$$.
Sorry for my bad english.
I put two wrong submissions submission1 and submission2 together and got an accepted submission. Can someone provide a hack and put it in the after_contest_tests? Thanks a lot.
O((2N + Nlog₂N) ∙ 2log₂1e7) solution for C using a weird kind of Binary Search.
submission
I think it's possible because the graph is convex. I considered about it at first, but I didn't dare to succeed with binary search, so I chose a different way.
i notice someone use a ternary search, so maybe it does have something to do with convex
Really strange. My ternary search get WA.
If I change that code and use l=0,r=1e7 instead of l=min{L},r=min{R}, it can't even pass the sample.
For the first test case, if you use l=0 and r=1e7 as the bounary of ternar search, you will get lmid=3333334 and rmid=6666667, and the function you check will get the same anwser (which is 6), it won't help you to choose which part will be removed.
Yes. But can l=min{L},r=min{R} work forever(for any testcases)? Are the testdatas too weak?
Some kind of ternarysearch could be hacked, if they calc the total distances in ternarysearch. Because the function of total distances could have a platform in searching before geting the minimum region.
Below test case should return 493, but the passed code return 496.
To handle this problem, we should carefully choose the proper function in ternarysearch.
My code here could be work.
Orz
Can you please explain your approach?
Since the dissatisfaction level is related to every pair of people, the optimal solution will be to let everyone stand as close to a single point as possible.
After experimenting around with the points, we can see that as we increase our chosen point, the total score will decrease to a trough, then increase again.
Therefore, we can implement a modified binary search that compares neighboring values (or a ternary search) to find the point that minimizes the value of this upward-concave curve, which will be the minimum dissatisfaction value.
In editorial of C, how to recursively calculate C?
let i be the index for which minimum of R exist and j be the index for which maximum of L exists. If we do not consider those two then i and j will be not in the optimal solution. let A[i] = R[i] = minimum of all R and B[j] = L[j] = maximum of all L. assuming A[i] < B[j], all other k where k != i and k != j we can do x[k] — A[i] + B[j] — x[k] = B[j]-A[i]. so the cost = B[j] — A[i] + (N-2)*(B[j]-A[i]) + C = (N-1)*(B[j]-A[i]) + C
Explanation of C: Now waht we need do is solve the same problem for all others except i and j that is to find the minimum of R and maximum of L for the indices k where k != i and k != j. This is C as far as i understood.
looking forward to some alternative solution to C.
the one in editorial is elegant but hard to come up with (
You can use the fact that the answer is minimized when there is some $$$p$$$, all $$$x$$$ is placed as close to $$$p$$$ as possible. This can be proved by contradiction. To calculate the answer, consider rewrite the answer as $$$\sum\limits_{i=-\infty}^{\infty} ((\sum\limits_{j=1}^n[x_j\leq i])\cdot (\sum\limits_{j=1}^n[x_j>i]))$$$, then we can iterate over all possible $$$p$$$ and calculate the answer. You can also find that the answer is optimized when $$$p=L_i$$$ or $$$p=R_i$$$ or $$$p=R_i+1$$$ for some $$$i$$$, then the solution is $$$O(n\log n)$$$.
thanks for sharing. i agree with your general idea, but i still don't understand the specific solution. especially your formula that i tried several ways to understand but none of them seems reasonable, it's a little strange for me(the square bracket is one reason and does $$$\cdot$$$ really mean multiply here?). also why we need to consider $$$R_i + 1$$$ ? what about others ?(maybe L-1?,etc)
sorry that the question I ask might seem kind of stupid, hope for reply
Consider the $$$x_i$$$ are coordinates on the number line. Then the original formula means the distance between all pairs of points. We consider all segments of length $$$1$$$ on the number line, say $$$[i,i+1]$$$, then the contribution of it to the original formula is the number of points to the left of $$$i$$$ multiplies the number of points to the right of $$$i+1$$$, which is the formula above.
Actually I'm not sure what are the key values that $$$p$$$ will choose. During the contest I just implemented a solution run in $$$O(10^7)$$$, and I implemented the $$$O(n\log n)$$$ solution later. I picked keypoints based on changes in variables, so maybe some of $$$p=L_i, p=R_i,p=R_i+1$$$ are not necessary, but these must be sufficient.
got it, thanks a lot
Does anyone get why the reverse works in problem F editorial [2]? I tried calculating some cases and it works but it seems there is some intuitive explanation that cannot be found by the formulas.