Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

maroonrk's blog

By maroonrk, history, 12 months ago,

We will hold ACL Contest 1.

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!

• +234

 » 12 months ago, # |   0 Hoping for an amazing round!!
 » 12 months ago, # |   +122 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!
•  » » 12 months ago, # ^ | ← Rev. 2 →   +7 As a beginner-intermediate coder, i’m not sure the contest was beginner friendly, if it was intended to be fun for beginners.
 » 12 months ago, # |   0 Video on how to use Atcoder library. Looking forward for the contest!
 » 12 months ago, # |   +3 Please also kindly update kotlin version to 1.4.0. Thanks in advance
 » 12 months ago, # |   +10 Kinda 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?
•  » » 12 months ago, # ^ |   +14 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.
•  » » » 12 months ago, # ^ |   0 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.
•  » » 12 months ago, # ^ |   +51 Yeah, the codeforces system where your rating is determined by last 5 rounds is better :sarcasm:
•  » » » 12 months ago, # ^ |   +40 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.
•  » » » 12 months ago, # ^ |   0 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.
•  » » » » 12 months ago, # ^ |   +34 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?
•  » » » » » 12 months ago, # ^ |   +25 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.
•  » » » » » » 12 months ago, # ^ |   +29 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.
•  » » » » » » » 12 months ago, # ^ |   +15 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.
•  » » » » » » » » 12 months ago, # ^ |   +15 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.
 » 12 months ago, # |   +8 What is the full form of ACL? Like we have ABC (Atcoder Beginner Contest). What does ACL stand for?
•  » » 12 months ago, # ^ |   +3 We will publish AtCoder Library (ACL).SourceBy that convention, ABC should be ACBC.
•  » » 12 months ago, # ^ |   +38 It stands for AtCoderContestAsHardAsAGC Coder Libray
•  » » » 12 months ago, # ^ |   0 Its really "AsHardAsAGC" :3.
 » 12 months ago, # |   0 editorial plzz
•  » » 12 months ago, # ^ |   0 Already published https://atcoder.jp/contests/acl1/editorial
•  » » » 12 months ago, # ^ |   0 yup peace!
 » 12 months ago, # | ← Rev. 3 →   0 Can I use DSU to solve A? Why it is wrong? code/* {By GWj */ #pragma GCC optimize(2) #include #define rb(a,b,c) for(int a=b;a<=c;++a) #define rl(a,b,c) for(int a=b;a>=c;--a) #define LL long long #define IT iterator #define PB push_back #define II(a,b) make_pair(a,b) #define FIR first #define SEC second #define FREO freopen("check.out","w",stdout) #define rep(a,b) for(int a=0;a>a #define R2(a,b) cin>>a>>b #define check_min(a,b) a=min(a,b) #define check_max(a,b) a=max(a,b) using namespace std; const int INF=0x3f3f3f3f; typedef pair mp; /*} */ const int MAXN=200000+20; int fa[MAXN],is[MAXN],siz[MAXN]; int n; mp cit[MAXN]; int root(int x){ if(fa[x]==x) return x; return fa[x]=root(fa[x]); } void merge(int u,int v){ if(root(u)==root(v)) return ; siz[root(v)]+=siz[root(u)]; fa[root(u)]=root(v); } int main(){ fastio; R(n); rb(i,1,n){ R2(cit[i].FIR,cit[i].SEC); is[cit[i].FIR]=i; } rb(i,1,n) fa[i]=i,siz[i]=1; sort(cit+1,cit+1+n); set s; set :: IT ite,nex; rb(i,1,n){ ite=s.lower_bound(II(cit[i].SEC,i)); if(ite!=s.begin()){ ite--; while(1){ if(ite==s.begin()){ merge(is[i],(*ite).SEC); s.erase(ite); break; } merge(is[i],(*ite).SEC); ite--; nex=ite; ite++; s.erase(ite); ite=nex; } } s.insert(II(cit[i].SEC,is[i])); } s.clear(); rl(i,n,1){ ite=s.lower_bound(II(cit[i].SEC,i)); if(ite!=s.end()){ while(1){ merge(is[i],(*ite).SEC); ite++; nex=ite; ite--; s.erase(ite); ite=nex; if(ite==s.end()) break; } } s.insert(II(cit[i].SEC,is[i])); } rb(i,1,n) cout<
•  » » 12 months ago, # ^ |   +9 I solved it via monotonic sets, I didn't try for any other approach though
•  » » 12 months ago, # ^ | ← Rev. 2 →   +10 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$. Codecin>>n; for (int i=1;i<=n;++i) { int x,y; cin>>x>>y; gd[x]=i; h[x]=y; } reverse(h+1,h+n+1); reverse(gd+1,gd+n+1); int ma=0,kad=0; for (int i=1;i<=n;++i) { ma=max(ma,h[i]); if (ma==i) { int re=i-kad; for (int j=kad+1;j<=i;++j) an[gd[j]]=re; kad=i; } } for (int i=1;i<=n;++i) cout<
•  » » » 12 months ago, # ^ |   0 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!!
•  » » 12 months ago, # ^ |   +7 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
•  » » 12 months ago, # ^ |   +6 A has the same idea and solution basically as Moo Particle, a problem from a recent USACO contest here: link
 » 12 months ago, # |   0 Thank You for the super fast editorial!
 » 12 months ago, # |   0 What is "doubling" from problem D's editorial?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 like binary lifting, I guessbut can somebody explain what is a and b? UPD: I got it — first and last chosing
•  » » 12 months ago, # ^ |   0 Binary lifting.
•  » » 12 months ago, # ^ |   0 The editorial has been fixed. (s/doubling/binary lifting/g) Thanks!
 » 12 months ago, # |   +5 This is the tutorial for AUnfortunatly 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.
• »
»
12 months ago, # ^ |
-6

I think there's something wrong with the Editorial, you can check my solution of dsu.

code
•  » » » 12 months ago, # ^ | ← Rev. 7 →   0 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/16918995BTW for B we can do better than sqrt with bitmasks
•  » » » 12 months ago, # ^ | ← Rev. 3 →   0 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 :(
•  » » 12 months ago, # ^ |   0 What do they even mean by a(n) ? Is that some fancy way to denote logarithm and slower functions?
•  » » » 12 months ago, # ^ |   +6
•  » » » 12 months ago, # ^ |   0 It is in that problem to denote the complexity of the dsu operations.
•  » » 12 months ago, # ^ |   +3 you can refer my code link- https://ide.geeksforgeeks.org/ZV03mZTlG2
 » 12 months ago, # |   +3 can someone please explain me the solution of problem B
•  » » 12 months ago, # ^ | ← Rev. 6 →   +7 (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. Codeimport java.io.*; import java.util.*; public class B { static ArrayList arl; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); long N=2*Long.parseLong(br.readLine()); arl=new ArrayList<>(); fact(N); int n=arl.size(); long ans=N-1; for (int i = 0; i < (1<0){ A*=arl.get(j); } } long B=N/A; long x=inv(B,A); //System.out.println(A+" "+B+" "+x); if(x*B>1){ ans=Math.min(ans,x*B-1); } } System.out.println(ans); } public static void fact(long i){ for (int j = 2; j <= Math.sqrt(i); j++) { long cur=1; while(i%j==0){ i/=j; cur*=j; } if(cur>1){ arl.add(cur); } } if(i>1){ arl.add(i); } } public static long inv(long a, long b){//Computes modular inverse of a mod b //Assume b>a and gcd(a,b)=1, if(a==1)return 1; long q=b/a; long r=b-q*a; long y=-inv(r,a); return ((b*y+1)/a)+b; } }
•  » » » 12 months ago, # ^ |   +3 You saidWe can now easily compute ... $k+1 = x \cdot \frac{2N}{P_s}$ worksWhy? 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$?
•  » » » » 12 months ago, # ^ |   +3 Yes, sorry for a typo
•  » » » » » 12 months ago, # ^ |   +3 Got it now, thanks!
 » 12 months ago, # |   +16 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. :(
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 same graph — 50ms (used atcoder implementation)
•  » » 12 months ago, # ^ | ← Rev. 3 →   +16 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/16916600I would be grateful if someone would explain how to do this using atcoder's template.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Just add edge with cost T+cost, and after all mincost is mincost-T*maxflow
•  » » » » 12 months ago, # ^ |   0 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
•  » » » » » 12 months ago, # ^ |   0 i guess missunderstanding, I mean cost = -distance
•  » » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 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 :(
•  » » » » » » » 12 months ago, # ^ |   +8 yes, different. for each o I calculate distance from o to cell that can be reached and add edge with flow=1 and cost=-distanceflow graph is S -> L -> R -> Twhere L is start positions of 'o'R is possible finishes
 » 12 months ago, # |   +15 Screencast of barely missing out on 69th place :((also video solutions for A-D)
 » 12 months ago, # |   -41 So, you made a maxflow problem for 600 points. Why?
•  » » 12 months ago, # ^ |   +18 why not?
•  » » » 12 months ago, # ^ |   0 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
•  » » » » 12 months ago, # ^ |   +8 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.
•  » » » » 12 months ago, # ^ |   +24 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.
•  » » » » 12 months ago, # ^ |   0 Also, after you do the practice contest max flow problem, this one has almost the same idea anyway.
 » 12 months ago, # |   0 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
•  » » 12 months ago, # ^ |   +3 As with most incorrect greedy solutions, some decisions you make greedily will lead to a greater loss in the future.Test: 4 3 ..o ..o o.. .##
•  » » » 12 months ago, # ^ |   0 Thank you very much @above!
 » 12 months ago, # |   0 ABC > ACL ?
 » 12 months ago, # |   0 rated range ?
 » 12 months ago, # |   -51 Hey guys, I was trying to solve Problem A using DSU but i'm getting WA on 5 testcases.I m following editorials O(N a(n)) approach.. #include using namespace std; #define int long long class DSU { private: static bool verbose; int sz; vector rank, parent, sizes; void printComponent(int id) { cout << "Component " << id << " size: " << getSize(id) << " | "; int p_id = Find(id); for(int i = 0; i < sz + 1; i++) { if(p_id == parent[i]) { cout << i << " "; } } cout << endl; } void printMessage(string s) { cout << "================================" << endl; cout << s << endl; cout << "================================" << endl; cout << endl; } public: DSU(int n) { sz = n; rank.resize(n + 1, 0); parent.resize(n + 1); sizes.resize(n + 1, 1); for(int i = 0; i < n + 1; i++) { parent[i] = i; } if(verbose) printMessage("DSU Initialised."); } int Find(int i) { // use path compression if(i != parent[i]) { parent[i] = Find(parent[i]); } return parent[i]; } void Union(int i, int j) { int i_id = Find(i); int j_id = Find(j); if(i_id == j_id) return; if(rank[i_id] >= rank[j_id]) { if(verbose) printMessage(to_string(i_id) + " size: " + to_string(sizes[i_id]) + " <-------------- " + to_string(j_id) + " size: " + to_string(sizes[j_id]) + " Final Size: " + to_string(sizes[i_id] + sizes[j_id])); sizes[i_id] += sizes[j_id]; sizes[j_id] = 0; parent[j_id] = i_id; if(rank[i_id] == rank[j_id]) rank[i_id] += 1; } else { if(verbose) printMessage(to_string(j_id) + " size: " + to_string(sizes[j_id]) + " <-------------- " + to_string(i_id) + " size: " + to_string(sizes[i_id]) + "Final Size: " + to_string(sizes[i_id] + sizes[j_id])); sizes[j_id] += sizes[i_id]; sizes[i_id] = 0; parent[i_id] = j_id; } } void Print() { for(int i = 0; i < sz + 1; i++) { printComponent(i); } } int getSize(int i) { return sizes[Find(i)]; } static void Verbose() { verbose = true; } }; bool DSU :: verbose = false; int32_t main(int32_t argc, char *argv[]) { if(argc == 2) DSU::Verbose(); int n; cin >> n; vector< pair > arr(n); for(int i = 0; i < n; i++) { cin >> arr[i].first >> arr[i].second; } vector< pair > temp = arr; sort(temp.begin(), temp.end()); DSU dsu(n); // left pass int minm = temp[0].second; for(int i = 1; i < n; i++) { if(minm < temp[i].second) { dsu.Union(minm, temp[i].second); } else { minm = temp[i].second; } } // right pass int maxm = temp[n-1].second; for(int i = n-2; i >= 0; i--) { if(maxm > temp[i].second) { dsu.Union(maxm, temp[i].second); } else { maxm = temp[i].second; } } //dsu.Print(); for(int i = 0; i < n; i++) { cout << dsu.getSize(arr[i].second) << endl; } return 0; } Can anyone tell where i am making mistake :(
 » 12 months ago, # |   0 Can somebody explain the O(N *a(n)) solution for problem A? I didn't understand the editorial.
•  » » 12 months ago, # ^ |   +3 you should refer to my code
•  » » 12 months ago, # ^ |   +3 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
 » 12 months ago, # |   0 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 3o..The answer should be 2 while the code gives me 1I 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/16973939The code used another source and give correct answer: https://atcoder.jp/contests/acl1/submissions/16973807Both of them use the same logic.
•  » » 12 months ago, # ^ |   0 I just explained above in this thread in detail the same issue. TL; DR: You can't add negative cost edges in atcoder library.
 » 12 months ago, # | ← Rev. 2 →   0 please someone tell me why i am geeting wrong ans in my code in problem A. link--https://ide.geeksforgeeks.org/Pwzi10u0Y5
•  » » 12 months ago, # ^ |   0 I got my mistake thank you
 » 12 months ago, # |   -28 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.
•  » » 12 months ago, # ^ |   -10 I don't know why you click the down arrow for me.
•  » » » 12 months ago, # ^ |   -10 I think it is a good advice for you.