I believe ARCs and AGCs are announced by Maroonrk, while ABCs are announced by atcoder_official

I have seen LGMs skipping A

The A of AGCs are smarter than me. Maybe I can actually struggle on A for 3 hours >_<

It's intended, see This post

they changed it

ARCs are now 1200+ as well

That's disappointing :( But at least you got some GP30 points towards AWTF rating!

It follows from the following lemma that was previously known to me: ...

How to prove this?

My approach is roughly the same. This is reminiscent of the classical inclusion-exclusion recurrence formula for counting DAGs.

I don't see what you mean. Seems finished to me?

Below are some details based on my understanding.

$$$f(n):=a_n$$$

If there exists $$$x<y$$$ such that $$$f(x)=f(y)$$$，then $$$f(y)|f(x) \Rightarrow y|x$$$, contradiction.

Let $$$P$$$ be the set of all prime numbers.

$$$x|y \iff \forall p\in P: v_p(x)\leq v_p(y)$$$

$$$n|m \iff f(n)|f(m) \Rightarrow v_p(f(n))\leq v_p(f(m))$$$

$$$f(2u)/f(u)\geq 2$$$, so it contains some prime factor at least $$$p_1=2$$$.

If $$$f(2^{n+1})=b_n\cdot f(2^n)\neq 2\cdot f(2^n)$$$, then $$$b_n>2$$$.

Since $$$f(x)\leq Cx$$$, there are only a finite number of $$$b_n\neq 2$$$.

So $$$\exists n_1: \forall n>n_1 : f(2^{n+1})=2\cdot f(2^n)$$$.

So $$$\exists N_1,c_1: \forall n>N_1 : f(2^{n})=2^{n-c_1}\cdot f(2^{c_1})$$$.

If for $$$p_1,p_2,...,p_{k-1}$$$ we have

(1) $$$f(p_i\cdot u)/f(u)$$$ contains some prime factor $$$\geq p_i$$$, and

(2) $$$\exists N_i,c_i$$$ such that $$$f(p_i^n)=p_i^{n-c_i}\cdot f(p_i^{c_i})$$$. ($$$\star$$$)

Let $$$X$$$ be a product of powers of some of $$$p_1,...,p_{k-1}$$$,

so $$$p_k\cdot u \not| X\cdot u \Rightarrow f(p_k\cdot u)\not| f(X\cdot u) \Rightarrow \frac{f(p_k\cdot u)}{f(u)}\not| \frac{f(X\cdot u)}{f(u)}$$$

We can pick $$$p_i^{t_i}$$$ for $$$X$$$ s.t. $$$v_{p_i}(f(p_i^{t_i}))>v_{p_i}(f(p_k\cdot u))$$$.

Then $$$\forall i<k: v_{p_i}(f(X\cdot u))\geq v_{p_i}(f(p_i^{t_i}))\geq v_{p_i}(f(p_k\cdot u))$$$

Then $$$\forall i<k: v_{p_i}(\frac{f(X\cdot u)}{f(u)})\geq v_{p_i}(\frac{f(p_k\cdot u)}{f(u)})$$$

So as $$$\frac{f(p_k\cdot u)}{f(u)}\not| \frac{f(X\cdot u)}{f(u)}$$$, there must exists an $$$i\geq k$$$ s.t. $$$v_{p_i}(\frac{f(p_k\cdot u)}{f(u)})>v_{p_i}(\frac{f(X\cdot u)}{f(u)})$$$

So $$$v_{p_i}(\frac{f(p_k\cdot u)}{f(u)})\geq 1$$$, $$$\frac{f(p_k\cdot u)}{f(u)}$$$ contains some prime factor at least $$$p_k$$$.

Then $$$f(p_k^{n+1})/f(p_k^n)\geq p_k$$$, due to the restriction of $$$C$$$, only a finite number of $$$n$$$ can achieve $$$f(p_k^{n+1})/f(p_k^n)>p_k$$$.

So $$$\exists n_k: \forall n>n_k: f(p_k^{n+1})=p_k\cdot f(p_k^n)$$$.

So $$$\exists N_k,c_k$$$ such that $$$f(p_k^n)=p_k^{n-c_k}\cdot f(p_k^{c_k})$$$.

Now we have completed the induction ($$$\star$$$). We have:

(1) For all $$$p\in P: f(pu)/f(u)$$$ contains some prime factor $$$\geq p$$$, and

(2) $$$\forall p_i: \exists N_i,c_i$$$ such that $$$f(p_i^n)=p_i^{n-c_i}\cdot f(p_i^{c_i})$$$.

Then we want to prove: If $$$v_p(x)<v_p(y)$$$ then $$$v_p(f(x))<v_p(f(y))$$$. (*)

Consider what happens if $$$v_p(t)=0$$$ in the $$$f(p\cdot u)=t\cdot f(u)$$$.

Pick all the prime factors of $$$t\cdot f(u)$$$ except $$$p$$$ and let $$$X$$$ be a product of powers of them.

For $$$p_i$$$ we can pick $$$p_i^{t_i}$$$ for $$$X$$$ s.t. $$$v_{p_i}(f(p_i^{t_i}))\geq v_{p_i}(t\cdot f(u))$$$.

Then $$$v_{p_i}(f(X\cdot u))\geq v_{p_i}(f(p_i^{t_i}))\geq v_{p_i}(t\cdot f(u))$$$.

Now $$$f(p\cdot u)=t\cdot f(u)|f(X\cdot u)$$$, but $$$p\cdot u\not| X\cdot u$$$, contradiction.

So $$$p|\frac{f(p\cdot u)}{f(u)}$$$.

If there exists $$$x$$$ and $$$y$$$ s.t. $$$v_p(x)<v_p(y)$$$ but $$$v_p(f(x))\geq v_p(f(y))$$$.

Take the min $$$x$$$ and $$$y$$$.

$$$p^{v_p(x)+1}|y \Rightarrow f(p^{v_p(x)+1})|f(y)\Rightarrow v_p(f(p^{v_p(x)+1}))\leq v_p(f(y))\leq v_p(f(x))$$$.

So $$$y=p^{v_p(x)+1}$$$. Let $$$a=v_p(x)$$$, then $$$y=p^{a+1}, x=p^a\cdot B$$$.

Pick prime factors of $$$f(y)$$$ except $$$p$$$ to make an $$$X$$$ s.t. $$$f(y)|f(x*X)$$$, but $$$y=p^{a+1}\not|x*X$$$, contradiction.

Proved (*).

So we can check $$$v_p(i)$$$ and $$$v_p(A_i)$$$ for each $$$p\leq N$$$, and make sure $$$v_p(f(x))<v_p(f(y))$$$ when $$$v_p(x)<v_p(y)$$$. This guarantees the case where $$$n\not|m$$$. And check $$$f(n)|f(m)$$$ when $$$n|m$$$.

For the infinite sequence, let $$$v_p(f(n))=\max\lbrace v_p(f(x))+v_p(n)-v_p(x): v_p(x)\leq v_p(n)\rbrace$$$. It is good.

This problem had a strong vibe of "IMO P3/6" style to me :p

I proved (or think I proved) everything in a pretty straightforward way as only condition 2 at first.

If we ignore condition 1, then it turns out you need sequences $$$S_p = (r_{p^i}, e_{p^i})$$$ where $$$p$$$ is prime, with the following meaning: $$$A_j$$$ is divisible by $$$(r^e)_{p^i}$$$ iff $$$j$$$ is divisible by $$$p^i$$$. Very importantly, all the sets $$${S_p}$$$ must be disjoint. Of course, for the same value of $$$r$$$, the exponents must be increasing, while there's no extra connection between $$$e$$$ of different $$$r$$$.

Condition 1 just says that all the values (there's at least one) occurring in $$$S_p$$$ an infinite number of times must be $$$\le p$$$. With the disjointness, that means $$$r_{p^i} = p$$$ and checking the condition is super simple.

I found necessary condition $$$j|i \to (\frac{i}{j}|\frac{a_i}{a_j})$$$, and guessed solution from that: just expanded it for all pairs $$$(i,j)$$$ to be like $$$\frac{i}{gcd(i,j)}|\frac{a_i}{gcd(a_i,a_j)}$$$, and it turned out to be sufficient for some reason. submission

Your linked code appears to be correct.

The final value(color) $$$a_i$$$ of each position is determined by the last operation interval contains $$$i$$$.

For each array $$$a$$$, it can be generated if there exists an operation sequence $$$(p:w) = [L_{p_1},R_{p_1}]:w_1, [L_{p_2},R_{p_2}]:w_2, ..., [L_{p_M},R_{p_M}]:w_M$$$ to generate it.

Try to select the interval for the operation sequence(which generates $$$a$$$) from the last to the first:

For operation $$$M$$$, final colors of elements in the chosen interval $$$[L_{p_M},R_{p_M}]$$$ must be the same, we choose $$$w_M$$$ be this color. If $$$a$$$ can be generated, then there exists an operation sequence $$$(q,w') = [L_{q_1},R_{q_1}]:w_1', [L_{q_2},R_{q_2}]:w_2', ..., [L_{q_M},R_{q_M}]:w_M'$$$. If it is not end with $$$[L_{p_M},R_{p_M}]$$$, we move the $$$[L_{q_t},R_{q_t}]=[L_{p_M},R_{p_M}]:w_t'=w_M$$$ to the end, then the final result outside the interval $$$[L_{q_t},R_{q_t}]$$$ will not change, and inside the interval is just the color we need. So there exists an operation sequence end with $$$[L_{p_M},R_{p_M}]$$$.

For operation $$$j$$$, elements in the chosen interval $$$[L_{p_j},R_{p_j}]$$$ that haven't been determined(covered) by operation $$$>j$$$ must be the same. We can pick any interval satisfies this for operation $$$j$$$. And if we know there exists an operation sequence $$$(q:w')$$$ end with $$$[L_{p_{j+1}},R_{p_{j+1}}]:w_{j+1}, ..., [L_{p_M},R_{p_M}]:w_M$$$, move $$$[L_{q_t},R_{q_t}]=[L_{p_j},R_{p_j}]$$$ to $$$j$$$ will not change $$$a$$$, we can deduce that there exists an operation sequence $$$(q:w')$$$ end with $$$[L_{p_{j}},R_{p_{j}}]:w_{j}, ..., [L_{p_M},R_{p_M}]:w_M$$$.

So the sequence $$$a$$$ can be generated if and only if it can be covered "greedily". That is, any current choice in the reverse operation sequence will not affect whether $$$a$$$ can be generated.

If an interval doesn't cover new elements, we can ignore this operation. So we can just chooce the "valid" interval that some new element is going to be determined by it.

Consider the last valid interval $$$[l,r]$$$ in the reverse operation sequence: Before it works, we have covered $$$[l_1,r_1],[l_2,r_2],...,[l_k,r_k]$$$. Then $$$[l,r]$$$ covers all the gaps so that $$$[1,n]$$$ is completely covered. We can cover each interval independently since covering $$$[l_i,r_i]$$$ only needs intervals within it.

Let $$$f[l][r]$$$ be the number of different subarrays $$$a[l..r]$$$ that can be generated by intervals $$$\subseteq [l,r]$$$. Then $$$f[1][n]$$$ will be the answer.

For any $$$a[l..r]\in C^{r-l+1}$$$, cover it greedily until no interval $$$\subseteq [l,r]$$$ is valid. Assume we end up with $$$[l_1,r_1],[l_2,r_2],...,[l_k,r_k]$$$ covered(The interval set is uniquely determined by $$$a[l..r]$$$ as we can move the curent operation interval in the other operation sequence to the same position of our selected operation sequence each time and finally make two operation sequence consistent). Then $$$f[l][r]$$$ is the number of $$$a[l..r]$$$ end up with $$$[l..r]$$$. All other interval sets have some element uncovered. Let $$$g[l][x][r]$$$ be the number of subarrays $$$a[l..r]$$$ that if we cover it greedily by intervals $$$\subseteq [l,r)$$$, then $$$[x,r]$$$ is the widest range with the right endpoint $$$r$$$ that all uncovered elements in it are the same.

To calculate $$$g[l][x][r]$$$, consider the nearest uncovered element $$$a[i]$$$ on the left of $$$a[r]$$$:

(1) If $$$x\leq i< r$$$, then $$$a[i]=a[r]$$$. Extend $$$[l..x..i]$$$ to $$$[l..x..r]$$$. There are $$$g[l][x][i]*f[i+1][r-1]$$$ extended subarrays. And if there exists an interval $$$[L_t,R_t]\subseteq [l,r)$$$ covers some new element, it must covers $$$i$$$. Then $$$L_t\in [x,i]$$$ as $$$a[x-1]\neq a[i]$$$. Check whether there exists $$$[L_t,R_t]\in [x,i]\times[i,r)$$$ to determine whether these subarrays should be counted in $$$g[l][x][r]$$$;

(2) If $$$l\leq i<x$$$, then $$$i=x-1$$$. Extend $$$[l..j..x-1]$$$ to $$$[l..x..r]$$$. There are $$$g[l][j][x-1=i]*f[x=i+1][r-1]*(C-1)$$$ extended subarrays. Check whether there exists $$$[L_t,R_t]\in [j,i]\times[i,r)$$$;

(3) If no such $$$i$$$, then $$$x=l$$$. $$$g[l][l][r]+=f[l][r-1]*C$$$.

To calculate $$$f[l][r]$$$, just substract all the $$$a[l..r]$$$ that counldn't be covered completely from $$$C^{r-l+1}$$$. Enumerate the rightmost uncovered position $$$i$$$, extend $$$[l..x..i]$$$ to $$$[l..x..r]$$$. There are $$$g[l][x][i]*f[i+1][r]$$$ extended subarrays. Check whether there exists $$$[L_t,R_t]\in [x,i]\times[i,r]$$$.