We will hold AtCoder Regular Contest 182.
- Contest URL: https://atcoder.jp/contests/arc182
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240811T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: sounansya, hirayuu_cf
- Tester: maspy
- Rated range: — 2799
The point values will be 500-500-600-700-800-1000.
We are looking forward to your participation!
500 A is scary.
Don't know about SNUKE, but I am definitely crying :| .
Please somebody help me understand the first problem :|
TestCase1 Walkthrough :
N = 8 , Q = 3
Lets 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 ?
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
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 ?
I mean single operation means doing all $$$Q$$$ operations
Operations have to be carried out in order.
Got it, thanks. I misunderstood that part.
Can you please explain above part ? which I have asked in other comment ?
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 :) )
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:
Really clever!
sorry, i really don't understand why the solution work. Can you help me?.
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
I don't really understand the transition in editorial, Could you explain the transition in more detail?
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
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
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
The $$$\iota$$$ index can be seen in the editorial as the $$$(1\ll \mathrm{MAX_{}PRIME})$$$ index of the $$$\mathrm{mat}$$$ variable.
This will help
thank you, it's look really cool.
Why does A even have n as input? It's completely irrelevant
Exactly, lol. you can push both left and right to infinity and the answer will be same, n doesn't matter at all.
To hide solution probably
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.
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.
C can be solve in time irrelevant to $$$n$$$, so $$$n$$$ can actually be up to $$$10^{10^5}$$$
Could you explain?
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.
Problem D for $$$M=3$$$ with the same solution. https://atcoder.jp/contests/agc052/tasks/agc052_e
how to make spj for problem B. I did one,but i think too slow
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.