As a beginner-intermediate coder, i’m not sure the contest was beginner friendly, if it was intended to be fun for beginners.

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.

Yeah, the codeforces system where your rating is determined by last 5 rounds is better :sarcasm:

We will publish AtCoder Library (ACL).

Source

By that convention, ABC should be ACBC.

It stands for AtCoderContestAsHardAsAGC Coder Libray

Already published https://atcoder.jp/contests/acl1/editorial

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$$$.

cin>>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<<an[i]<<'\n';

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

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!

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

What do they even mean by a(n) ? Is that some fancy way to denote logarithm and slower functions?

you can refer my code link- https://ide.geeksforgeeks.org/ZV03mZTlG2

(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.

import java.io.*; import java.util.*;
public class B {
    static ArrayList<Long> 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<<n); i++) {//WLOG, n-1 is in the second set
            long A=1;
            for (int j = 0; j < n; j++) {
                if((i&(1<<j))>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;
        
    }
}

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.

why not?

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..
.##

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

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 don't know why you click the down arrow for me.