We will hold ACL Contest 1.
- Contest URL: https://atcoder.jp/contests/acl1
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200920T2100&p1=248
- Duration: 150 minutes
- Number of Tasks: 6
- Writer: maroonrk, yosupo, rng_58
- Tester: maroonrk, yosupo, sigma425
- Rated range: 1200 — 2799
The point values will be 300-600-600-800-900-1800.
As mentioned in this blog, you may use the library in the contest. However, it's not mandatory to install the library or learn C++; I've verified that all problems can be solved with python(pypy3).
I also tried hard to ensure the quality of the problems, and I believe that you can enjoy tasks as a usual AtCoder contest, rather than yet another practice contest. In addition to that, I would like to mention the last problem, which is unusually hard for ARC-rated contests, and we welcome >2800 coders to challenge it.
We are looking forward to your participation!
Hoping for an amazing round!!
Our initial plan was to prepare tasks that require standard applications of the contents of the library, and make a practice contest for intermediate people while advertizing the library.
However, we changed the plan because we want to advertize it for strong people too, and improved the quality of the problems to make a contest that is worth participating for them too. maroonrk even refused to use some fine tasks that are acceptable for ARCs.
So, expect something between an AGC and an ARC!
As a beginner-intermediate coder, i’m not sure the contest was beginner friendly, if it was intended to be fun for beginners.
Video on how to use Atcoder library. Looking forward for the contest!
Please also kindly update kotlin version to
1.4.0
. Thanks in advanceKinda unrelated but do you have any plan to change the rating system so that we don't get 0.00000000001 delta for accounts with lots of rated contest participation?
Isn't atcoder's less shaky rating system better in some cases? For example, it prevents extreme positive delta from ABC. It also prevents extreme negative delta for one bad performance (can happen for network error, power loss etc.). As Atcoder has different time penalty from other OJs, contestants can easily submit at end of contest / when certain that their rating won't drop much. I think a less shaky rating system encourages participants to not worry about rating much.
Yes it's better in those very specific cases I suppose..
I don't see any reason to make participants not worry about their rating. All that they have to do for that is make a throwaway account and participate with it.
Yeah, the codeforces system where your rating is determined by last 5 rounds is better :sarcasm:
I don't think CF's system is better, but I think on AtCoder the effect is too strong. If I recall correctly, old contests from 2017 hold me back by about 100 points despite being mostly irrelevant.
I think your current rating is supposed to represent how good you are now, not how good you were in the past (we have the rating graph for the latter). So I actually do think that determining your rating based on the last 5 rounds is better.
My rating was 3548 on 29.04.19, 3001 on 21.06.19 and 3494 on 23.09.19. What's more likely in your opinion: I went from one of the strongest CPers to almost-not-nutella and back in 5 month or CF rating is broken?
I'd say it's more weird for you to not lose bunch of rating from 3.5K when you had few 3K performances in a row.
Like suppose if an orange coder starts participating with your account. In my opinion, a "decent" rating system should be able to detect it from recent few performances that the guy is orange-level and adjust the rating of your account accordingly, not get stuck at high rating just because that account has huge number of past rated contest participation.
I don't agree. Rating is a measure of your strength. Obviously everyone has stronger and weaker sides, and it can happen that there are several rounds in a row where one has bad performance, and it shouldn’t disturb the rating a lot. Of course, it should gradually become lower, but overall the rating should be stable against several bad or good contests in a row.
I'm not sure why do you think that one's rating should be stable. One's strength (in CP) can fluctuates depending on his condition at the time he's taking the contest.
It could be because of unfavorable contest time, or maybe he ate some food gone bad, or he could have some bad performances on one of recent contests and can't think straight because of it.
In this regard, I'd argue that any rating system which tries to adjust this fluctuation artificially, does not reflect one's strength at that time well.
Ok, we have different views on rating. I don't understand yours to be honest, but that's fine with me, I don't care.
What is the full form of ACL? Like we have ABC (Atcoder Beginner Contest). What does ACL stand for?
We will publish AtCoder Library (ACL).
Source
By that convention, ABC should be ACBC.
It stands for AtCoderContestAsHardAsAGC Coder Libray
Its really "AsHardAsAGC" :3.
editorial plzz
Already published https://atcoder.jp/contests/acl1/editorial
Can I use DSU to solve A? Why it is wrong?
I solved it via monotonic sets, I didn't try for any other approach though
If you think of it as a permutation, reverse it, now each connected component is an interval of both indices and values so a component ends every time the maximum of the first $$$i$$$ elements is equal to $$$i$$$.
Yes! Thank you very much! My solution is realy close to the yours.But I don't know why I didn't realize this mistake during the contest!
Problem A took me 2 hours:(,And after I solved B ,there is no time left!!
Instead of inserting the current secondary (which is not used in sorting) co-ordinate we have to insert the minimum secondary co-ordinate of the set in which the current index belongs. My Submission
A has the same idea and solution basically as Moo Particle, a problem from a recent USACO contest here: link
Thank You for the super fast editorial!
What is "doubling" from problem D's editorial?
like binary lifting, I guess
but can somebody explain what is a and b? UPD: I got it — first and last chosing
Binary lifting.
The editorial has been fixed. (s/doubling/binary lifting/g)
Thanks!
This is the tutorial for A
Unfortunatly I do only understand the $$$O(N^2a(n))$$$ solution. Can somebody explain the $$$O(Na(n))$$$? That loop looks like $$$N^2$$$ to me, I get something wrong.
I think there's something wrong with the Editorial, you can check my solution of dsu.
include<bits/stdc++.h>
define re register
using namespace std; struct node{ int x,y,id; bool operator <(const node &a){return x<a.x;} }p[200002]; inline int read(){ re int t=0;re char v=getchar(); while(v<'0')v=getchar(); while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar(); return t; } int fa[200002],siz[200002],stk[200002],tp,mx[200002],n; inline int root(re int x){return x==fa[x]?x:fa[x]=root(fa[x]);} inline void merge(re int x,re int y){ if((x=root(x))==(y=root(y)))return; if(siz[x]>siz[y])x^=y^=x^=y; fa[x]=y,siz[y]+=siz[x];mx[y]=min(mx[y],mx[x]); } int main(){ n=read(); for(re int i=1;i<=n;++i)p[i].x=read(),p[i].y=read(),p[i].id=i,fa[i]=i,siz[i]=1; sort(p+1,p+n+1); for(re int i=1;i<=n;++i){mx[p[i].id]=p[i].y; while(tp&&p[i].y>mx[root(p[stk[tp]].id)])merge(p[i].id,p[stk[tp]].id),--tp; stk[++tp]=i; } for(re int i=1;i<=n;++i)printf("%d\n",siz[root(i)]); } ...
My algorithm for A (TLEs) is similar to the dsu editorial, and Id say use the same complexity.
Here is my submission https://atcoder.jp/contests/acl1/submissions/16918995
BTW for B we can do better than sqrt with bitmasks
I think the $$$ O(N\alpha(N))$$$ solution in the editorial indeed should be more clear.
Suppose I have $$$(1,N),(2,N-1),\cdots,(N,1)$$$, the algorithm must traverse every pair of points, which is $$$O(N^2)$$$ and would TLE.
I actually feel bad because I found the $$$x_i=i$$$ idea but couldn't finish :(
What do they even mean by a(n) ? Is that some fancy way to denote logarithm and slower functions?
inverse of ackermann function
It is in that problem to denote the complexity of the dsu operations.
you can refer my code link- https://ide.geeksforgeeks.org/ZV03mZTlG2
can someone please explain me the solution of problem B
(If you have any suggestions or corrections feel free to comment below, I'll fix)
Notation: $$$A\backslash B=$$$ the set of elements contained in A that are NOT in B.
I actually found the official solution quite unintuitive, so here is my (slightly faster) approach.
Factorize $$$2N=\prod_{i=1}^n p_i^{e_i}$$$, where $$$p_1,\cdots,p_n$$$ are distinct prime factors of $$$2N$$$. For convenience, let $$$q_i=p_i^{e_i}$$$ for $$$1\le i\le n$$$.
Let $$$[n]$$$ be the set of positive integers from $$$1$$$ to $$$n$$$
We need $$$\prod_{i=1}^n q_i \mid k(k+1)$$$. Since $$$\gcd(k,k+1)=1$$$, suppose $$$S\in [n]$$$, $$$q_i\mid k$$$ if and only if $$$i\in S$$$, then since $$$\prod_{i\in [n]\backslash S} q_i\mid k(k+1), \gcd(\prod_{i\in [n]\backslash S} q_i,k)=1, \prod_{i\in [n]\backslash S} q_i \mid k+1$$$.
Let $$$Q_S=\frac{2N}{P_S}$$$.
We can now easily compute $$$k+1$$$ with modular inverses; let $$$P_S=\prod_{i\in [n]\backslash S} q_i$$$, then $$$\gcd(P_S, Q_S)=1$$$, suppose $$$x\equiv Q_S^{-1} (\bmod\; P_S)$$$, then $$$k+1=xQ_S$$$ works because $$$\frac{2N}{P_S}\mid k+1$$$ and $$$xQ_S\equiv 1(\bmod\; P_S)$$$ by the definition of modular inverse.
There are less than fifteen distinct primes that can divide an integer $$$\le 2\cdot 10^{15}$$$, so this can be done in approximately $$$\omega(2N) \cdot 2^{\omega(2N)}\le 15\cdot 2^{15}$$$ operations, which is fast enough.
You said
We can now easily compute ... $$$k+1 = x \cdot \frac{2N}{P_s}$$$ works
Why? How did you reach that conclusion? Also, what do you mean by the notation $$$i \in [n]$$$ \ $$$S$$$? All the elements in $$$[n]$$$ but not in $$$S$$$?
Yes, sorry for a typo
Got it now, thanks!
Could someone kindly explain approach with $$$O(KNM log(NM))$$$ complexity mentioned in official tutorial? Thanks in advance!
btw, I built graph with $$$O(K+NM)$$$ vertices and $$$O(KNM)$$$ edges and run mincost-maxflow on it during contest, but it turns out to be TLE. :(
same graph — 50ms (used atcoder implementation)
From the source, add edges to pieces with capacity 1 and cost 0. From all the feasible final positions to destination, add edges with capacity 1 and cost 0. From a feasible position to another feasible position to the down or right, add an edge with capacity infinity and cost -1. (Feasible position is any a[i][j] != #).
Find the minimum cost flow in this graph. I am unsure how to implement this with atcoder's min cost flow (I spent 15 mins thinking about why it isn't working, and the answer is because they require cost >= 0).
Anywya, here's my in contest implementation: https://atcoder.jp/contests/acl1/submissions/16916600
I would be grateful if someone would explain how to do this using atcoder's template.
Just add edge with cost
T+cost
, and after all mincost ismincost-T*maxflow
But then the minimum cost would be when the pieces don't move from their initial position at all. It wouldn't flow through the edges as it doesn't reduce the cost
i guess missunderstanding, I mean
cost = -distance
Is it possible for you to do a submit and send it here? Sorry, but I don't fully get your point, and the code is really short after using atcoder library.
Unsure if you are referring to this idea: https://atcoder.jp/contests/acl1/submissions/16752194 which is a bit different, I guess
Edit: rereading your comment, I guess you do mean the submission I referted above. Never mind then, that doesn't fully resolve my initial question :(
yes, different. for each
o
I calculate distance fromo
to cell that can be reached and add edge withflow=1
andcost=-distance
flow graph is S -> L -> R -> T
where L is start positions of 'o'
R is possible finishes
Screencast of barely missing out on 69th place :(
(also video solutions for A-D)
So, you made a maxflow problem for 600 points. Why?
why not?
If 600 point problem is supposed to 1900-2100 rated problem then why there should be maxflow? I was recommended to learn maxflow after reaching master
Because you don't need to know how max flow works, only what it does(in this case finding max weight bipartite matching); the implementation is in the atcoder library.
Well this contest is specifically named "ACL" which means anything in the atcoder library can appear.
Also, I think the advices like "do not learn ~~ until you reach master" should be interpreted as "it's better to focus on 'thinking' side of problem solving rather than knowledge side to reach master", which is true. Do not interpret it as "learning is bad till master" because that's not true. I bet majority of the people who learns flow in this planet don't even have a cf account.
Also, after you do the practice contest max flow problem, this one has almost the same idea anyway.
I feel like B is the easiest and the most straightforward, but A quite challenging.
BTW, can anyone hack the following "greedy" algorithm for C? It WAs but I can't find a counterexample.
The algorithm: scan points by rows from bottom to top, on a row I scan from right to left. Suppose I encounter a piece. I place it in the furthest place from it such that below and to the right are either an obstacle or a piece.
If this is not specific enough, see my code: https://atcoder.jp/contests/acl1/submissions/16920848
As with most incorrect greedy solutions, some decisions you make greedily will lead to a greater loss in the future.
Test:
Thank you very much @above!
Can somebody explain the O(N *a(n)) solution for problem A? I didn't understand the editorial.
you should refer to my code
link- https://ide.geeksforgeeks.org/ZV03mZTlG2
Basically i sort the position array according to x cordinates and then for any particular y cordinate i check if any less than the current y cordinate exist or not if it exist then merge them in dsu
Does anyone have problems solving C with min cost flow? I used the code in the Atcoder Library and it gives wrong answer for even a simple test case like this:
1 3
o..
The answer should be 2 while the code gives me 1
I used the same logic but change the code to cp-algorithms.com and it gives the correct answer.
The code used Atcoder Library: https://atcoder.jp/contests/acl1/submissions/16973939
The code used another source and give correct answer: https://atcoder.jp/contests/acl1/submissions/16973807
Both of them use the same logic.
I just explained above in this thread in detail the same issue.
TL; DR: You can't add negative cost edges in atcoder library.
I think the ACL Round is useless.
You cannot use the ACL in big contests like IOI or some other websides like codeforces. If you use the ACL for a long time, you will forget the algorithms quickly.
So I think you shouldn't learn to use the ACL.
I don't know why you click the down arrow for me.
I think it is a good advice for you.