### maroonrk's blog

By maroonrk, history, 5 weeks ago,

We will hold AtCoder Regular Contest 182.

The point values will be 500-500-600-700-800-1000.

We are looking forward to your participation!

• +65

 » 4 weeks ago, # |   +17 500 A is scary.
 » 4 weeks ago, # | ← Rev. 6 →   -19 Don't know about SNUKE, but I am definitely crying :| . Please somebody help me understand the first problem :| TestCase1 Walkthrough : N = 8 , Q = 3Lets say my initial array is [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 ]. Operation 1 : (p1,v1) => (1,8)Operation 2 : (p2,v2) => (8,1)Operation 3 : (p3,v3) => (2,1)For any operation, we do either of these two. Either set all the values from prefix array ( 1 <= i <= p[i]) or set all the values in suffix array ( p[i] <= i <= N ) equal to v[i]. Make sure, while setting the new values , the old value shouldn't be strictly greater than v[i]. otherwise it invalid sequence of operation. Now, I can do operation 3 on this array, and it will become [ 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] Then, I can apply Operation 1 on this array, and array will become [ 8 , 1 ,1 , 1 , 1 , 1 , 1 , 1 ] Then I can apply Operation 2 on the array, and array stays the same. Why would SNUKE CRY in this sequence of operation ?
•  » » 4 weeks ago, # ^ |   0 You have to do operations sequentially, i.e., $1,2,3,...,Q$. so total number of possible operations are $2^{Q}$. Now task is to find how many of them are correct sequences
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Ok, if what you said is true. Then I have total 8 possible sequences. Sequence 1 : ['operation 1']Sequence 2 : ['operation 2']Sequence 3 : ['operation 3']Sequence 4 : ['operation 1', 'operation 2']Sequence 5 : ['operation 1', 'operation 3']Sequence 6 : ['operation 2', 'operation 3']Sequence 7 : ['operation 1', 'operation 2', 'operation 3']If I perform, just Sequence 1 , WHY WOULD SNUKE CRY ??????? WHY IS THAT INVALID ?
•  » » » » 4 weeks ago, # ^ |   0 I mean single operation means doing all $Q$ operations
•  » » 4 weeks ago, # ^ |   +10 Operations have to be carried out in order.
•  » » » 4 weeks ago, # ^ |   0 Got it, thanks. I misunderstood that part.
•  » » » 4 weeks ago, # ^ |   0 Can you please explain above part ? which I have asked in other comment ?
 » 4 weeks ago, # |   +15 thanks for the round C was a different problem than usual, and it was kinda fun. (I did not believe my solution could be intended but it was :) )
•  » » 4 weeks ago, # ^ |   0 C was really great! I couldn't solve it though.The main thing that was missing from my solution was a nice way to visualize the "product", like this part from the editorial: By the way, the value to be found for each sequence of operations can be rephrased as “the number of ways to choose exactly one block from each tower.” Really clever!
•  » » » 4 weeks ago, # ^ |   0 sorry, i really don't understand why the solution work. Can you help me?.
•  » » » » 4 weeks ago, # ^ |   +8 assuming you know the formula for number of divisors,you can see that formula as "for each prime $2, 3, 5, 7, 11, 13$ pick at most one multiple from array a and pick one of it's power from $ai$"now we can do bit-dp which states primes that are already picked with $dp[n][mask]$ where transitions are like: if a bit in mask goes from 0->1 in index i, pick that prime from $ai$from that you can store transitions in matrix and do matrix-mult
•  » » » » » 4 weeks ago, # ^ |   0 I don't really understand the transition in editorial, Could you explain the transition in more detail?
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +24 Perhaps you already figured out a way to think about it with the Product Trick but since I had already typed out the equations I figured I should post my way of thinking about it anyways. It lacks intuition since I just computed the math formulas but it's easier to see the transitions.Let $\{ p_{i} \}_{i=1}^m$ be the primes $\leq M$ and set $\gamma_{i}(A)=\max\left\{ \nu : p_{i}^\nu \mid \prod_{a \in A}a \right\}$. Then the score of a sequence/multiset $A$ is $f(A)=\prod_{i=1}^{m} (\gamma_{i}(A)+1)$.Expanding $\sum_{A \in\mathcal{A}}^{}f(A)$ where $\mathcal{A}$ are the valid sequences we will see that we will have a huge mess of subsets. This will intuitively help as to assume the function $F_{N}:[m]\to\mathbb{Z}$ which maps a subset of the primes $\{ p_{i} \}_{i=1}^m$ to their contribution in the answer for sequences up to length $N$ (perhaps $N=0$, so in the answer we will that case). If $\mathcal{A}_{N}$ are the valid sequences of length $N$, we have \begin{align} F_{N}(L) &=\sum_{n=0}^{N} \sum_{A \in \mathcal{A}_{n}}^{} \prod_{i \in L}^{} (\gamma_{i}(A)+1) \\ &=1+\sum_{n=1}^{N}\sum_{A \in \mathcal{A}_{n-1}}^{} \sum_{a=1}^{M} \prod_{i \in L}^{} (\gamma_{i}(A\cup\{ a \})+1) \\ &=1+\sum_{n=1}^{N}\sum_{A \in \mathcal{A}_{n-1}}^{} \sum_{a=1}^{M} \prod_{i \in L}^{} (\gamma_{i}(A)+\gamma_{i}(a)+1) \\ &=1+\sum_{n=1}^{N}\sum_{A \in \mathcal{A}_{n-1}}^{} \sum_{a=1}^{M} \sum_{I \subseteq L}^{}\left(\prod_{i \in I}^{}(\gamma_{i}(A) + 1)\right)\left( \prod_{i \in L\setminus I}^{}\gamma_{i}(a) \right) \\ &=1+\sum_{n=1}^{N}\sum_{A \in \mathcal{A}_{n-1}}^{} \sum_{I \subseteq L}^{}\left(\prod_{i \in I}^{}(\gamma_{i}(A) + 1)\right)\sum_{a=1}^{M} \left( \prod_{i \in L\setminus I}^{}\gamma_{i}(a) \right) \\ &=1+\sum_{n=1}^{N}\sum_{A \in \mathcal{A}_{n-1}}^{} \sum_{I \subseteq L}^{}\left(\prod_{i \in I}^{}(\gamma_{i}(A) + 1)\right)G_{L} (I) \\ &=1+\sum_{I \subseteq L}^{} G_{L}(I)\sum_{n=1}^{N}\sum_{A \in \mathcal{A}_{n-1}}^{} \left(\prod_{i \in I}^{}(\gamma_{i}(A) + 1)\right) \\ &=1+\sum_{I \subseteq L}^{} G_{L}(I)F_{N-1}(I) \\ \end{align}so if we look at the functions $F_{N}:[m]\to \mathbb{Z}$ and $\{ G_{L} \}_{L\subseteq [m]}$ as vectors (e.g. $F_{N}\in\mathbb{Z}^{2^m}$) then for an appropriate matrix $G\in \mathbb{Z}^{2^m\times{2}^m}$ we get $F_{N}=GF_{N-1}+\mathbf{e}.$Since we don't like the $\mathbf{e}$ term we want to get around it, we will just suppose that the vector $F_{N}$ has one more fake index $\iota$ such that $F_{N}(\iota)=1$ and extend $G$ accordingly so that $G[\iota][j]=\mathbf{1}[j=\iota]$ and $G[i][\iota]=\mathbf{1}[i=\iota]$. So now $F_{N}=GF_{N-1}=G^NF_{0}.$The $\iota$ index can be seen in the editorial as the $(1\ll \mathrm{MAX_{}PRIME})$ index of the $\mathrm{mat}$ variable.
•  » » » » 4 weeks ago, # ^ |   +8 This will help
•  » » » » » 4 weeks ago, # ^ |   0 thank you, it's look really cool.
 » 4 weeks ago, # |   0 Why does A even have n as input? It's completely irrelevant
•  » » 4 weeks ago, # ^ |   0 Exactly, lol. you can push both left and right to infinity and the answer will be same, n doesn't matter at all.
•  » » 4 weeks ago, # ^ |   0 To hide solution probably
•  » » 4 weeks ago, # ^ |   +5 Part of the problem is figuring that out.Reminds me of an even more troll problem: ARC059_d. The input is just a string but the string doesn't matter at all, only the length.
•  » » 4 weeks ago, # ^ |   +3 Maybe it has a similar effect to something like "after $10^{100}$ rounds" that often appears in game theory tasks, making it easier to describe the meaning of the task.
 » 4 weeks ago, # |   +14 C can be solve in time irrelevant to $n$, so $n$ can actually be up to $10^{10^5}$
•  » » 4 weeks ago, # ^ |   0 Could you explain?
•  » » » 4 weeks ago, # ^ |   +23 Let $a_i=2^{n2_i}3^{n3_i}5^{n5_i}7^{n7_i}11^{n11_i}13^{n13_i}$, then we want to find the sum of $(\sum n2_i+1)(\sum n3_i+1)\cdots(\sum n13_i+1)$ over all $a$. The combinatoric meaning of this formula is taking one element from each of the $6$ sums and times them together, then add everything to get the sum.Since we need to find the sum over all sequences, we can iterate over all $(p_1,p_2,\cdots,p_6)$ where $p_i$ is the contribution of the position in the $i$-th sum. Obviously, only the relative positions of $p_i$ matters, so we can brute force every single one of them, and the only coefficient left would be the number of ways to form a sequence with no more than $n$ elements where some $\le 6$ elements are fixed. This is a simple combinatorics problem and can be done easily.In this solution, we would only need the value of $\binom{n}{k}$ and $m^{n-k}$ where $k$ is a small constant. Thus we only need to find $n\bmod mod$ and $n\bmod (mod-1)$ to solve the problem.
 » 4 weeks ago, # |   +41 Problem D for $M=3$ with the same solution. https://atcoder.jp/contests/agc052/tasks/agc052_e
 » 3 weeks ago, # |   0 how to make spj for problem B. I did one,but i think too slow #include "testlib.h" #include using namespace std; int main(int argc, char * argv[]) { setName("compares two signed integers"); registerTestlibCmd(argc, argv); int vv=inf.readInt(); for(int i=1;i<=vv;i++){ int n=inf.readInt(),k=inf.readInt(); int maxx=(1<SA,SO; for(int qq=1;qq<=n;qq++){ int x=ans.readInt(1,maxx),y=ouf.readInt(1,maxx),t=1; for(int j=0;j<=k;j++){ SA.insert(x/t);SO.insert(y/t); t*=2; } } if (SA.size() != SO.size()) quitf(_wa, "wa on %d th data",i); } quitf(_ok,"right"); } 
 » 9 days ago, # |   0 In E, can we please get an English editorial that links to an English article/editorial instead of what I assume is Japanese? It may be somewhat manageable with focusing on formulas and using autotranslate, but the standard language of communication in computer science is still English.BTW E is solvable with a $O(M+f(N))$ bruteforce for floor sum since $M$ is relatively small and there's no multitest. Some constant optimisation is necessary, but nothing ridiculously hard.