maroonrk's blog

AtCoder Regular Contest 182 Announcement
By maroonrk, history, 4 months ago, In English

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!

  • Vote: I like it
  • +65
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

500 A is scary.

→ Reply
»
4 months ago, # |
← Rev. 6   Vote: I like it -19 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Operations have to be carried out in order.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it, thanks. I misunderstood that part.

      → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain above part ? which I have asked in other comment ?

      → Reply
»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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 :) )

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry, i really don't understand why the solution work. Can you help me?.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't really understand the transition in editorial, Could you explain the transition in more detail?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
            ← Rev. 2   Vote: I like it +24 Vote: I do not like it

            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.

            → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        This will help

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you, it's look really cool.

          → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does A even have n as input? It's completely irrelevant

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Exactly, lol. you can push both left and right to infinity and the answer will be same, n doesn't matter at all.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To hide solution probably

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

C can be solve in time irrelevant to $$$n$$$, so $$$n$$$ can actually be up to $$$10^{10^5}$$$

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain?

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.

      → Reply
»
4 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Problem D for $$$M=3$$$ with the same solution. https://atcoder.jp/contests/agc052/tasks/agc052_e

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to make spj for problem B. I did one,but i think too slow 

#include "testlib.h"
#include<bits/stdc++.h>
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<<k)-1;
    	set<int>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");
}
→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply