maroonrk's blog

AtCoder Regular Contest 155 Announcement
By maroonrk, history, 22 months ago, In English

We will hold AtCoder Regular Contest 155.

The point values will be 400-500-700-800-900-1000.

We are looking forward to your participation!

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

Comments Comments (30)
| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

omg 400-points-A round

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it
Spoiler : after seen 1st problem me :(
→ Reply
»
22 months ago, # |
  Vote: I like it +17 Vote: I do not like it

TOO HARD

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

0 questions solved in a contest after very long :(

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

Definitely too hard for ARC.
Is this really ARC and not AGC?

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

TOOOO Hard

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

Hi there from the 4th place!

Generally, most definitely, thank you for the contest!! But here's some feedback:

  • As many will moan here together with me, A was too hard for its slot.
  • С is nice, but some parts can be guessed-without-proof. May be, asking for the entire procedure of swaps would be a better check for whether a contestant got all the needed ideas.
  • I solved E, but I do not understand a single thing about its solution. I just guessed what you could possibly ask me to do on position E with a matrix up to 300×300, and then tried to figure out the ±1 ending by chance. That makes me happy with the result but unhappy about its fairness.
→ Reply
»
22 months ago, # |
  Vote: I like it +38 Vote: I do not like it

AtCoder Regular Corner-case, struggled for Problem A and C in the whole contest.

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

Good problems but the samples are too weak. Maybe give a stronger sample the next time?

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

TOOOO Hard！My classmate who get 11st in arc154 did't solve any problem!(I only solve one!) if you don't belive ,than i'll tell you his id :jbwlgvc(look it!)

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

I only solved D, couldn't manage to solve neither A nor B in 40 minutes :D

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

From the editorial of D (evima):

if $$$1 < \gcd (A_i, G) < G$$$ for some $$$A_i$$$, then $$$A_i$$$ always remain on the blackboard

Am I missing something essential? Isn't this obviously false according to the statement? Maybe you wanted to express something else using the word "always"?

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

    I think it means "any $$$A_i < G$$$ is currently on the blackboard".

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

      Well that's a very different meaning!

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

        The editorial does not mean "such A_i will be on the board forever". It means "we can guarantee that such A_i is not yet erased", because G must be a divisor of any erased number.

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

          The problem is that "always" has a very specific meaning, which is distinct from "so far". It's possible to expand upon a short sentence like that so the different meaning is clarified, but Atcoder editorials are way too brief and tend to not do that, so they only help understand solutions to those who already more or less know the solutions. In addition, that statement is obvious to anyone with half a brain, which makes it extra misleading — if an editorial is quite short, then everything in it should be important enough to mention.

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

I solved D using a simple dfs . But the time complexity may be wrong .

https://atcoder.jp/contests/arc155/submissions/38465395

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

Problem A was Too hard.

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

    Problem A was Too hard.
    Problem C was Toooo hard.

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

      Too many Corner-cases on A and C.

      Tooooo Hardddddddddd!

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

Weird screencast

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

Problem A is really treasure! I think my idea is quite close to the editorial (reduce large k to small one and handle the case with O(N) size), but I have never thought about using mod=2*n.

This may sound a little bit sad but I have considered using n or 3n, which gave me nothing :(

→ Reply
»
22 months ago, # |
← Rev. 4   Vote: I like it +82 Vote: I do not like it

An algebraic approach on F (sketch):

Imagine the edge between $$$i$$$ and $$$j$$$ has weight $$$x_i + x_j$$$, we want to compute the coefficient of $$$x_1^{d_1} \cdots x_n^{d_n}$$$ among the total weight of all spanning trees. We can apply the matrix tree theorem.

Let $$$s = \sum x_i$$$, $$$\boldsymbol x$$$ be the vector of $$$x_i$$$ s, $$$\boldsymbol 1$$$ be the all-one vector.

Therefore, the Laplacian matrix is

$$$ L=\operatorname{diag}(nx_i + s) - \boldsymbol 1\boldsymbol x^{\mathsf T} - \boldsymbol x \boldsymbol 1^{\mathsf T} $$$

Wlog assume $$$d_n = 0$$$, we compute the determinant of $$$L$$$ removing the last row and column. We assume all indices are from $$$1$$$ to $$$n-1$$$ later. Note that $$$\boldsymbol 1\boldsymbol x^{\mathsf T} + \boldsymbol x \boldsymbol 1^{\mathsf T}$$$ has rank $$$2$$$, the expansion of determinant is simple, we have

$$$ Ans = \prod_{i} (nx_i + s) + \sum_i (-2x_i) \prod_{j\neq i}(nx_j + s) + \sum_{i < j}(2x_ix_j - x_i^2 - x_j^2) \prod_{k\neq i,j} (nx_k + s). $$$

For the first term, we have

$$$ [x_1^{d_1}\cdots x_{n-1}^{d_{n-1}}]\prod_{i} (nx_i + s) = T\left( \prod_{i=1}^{n-1} \left( n\frac{x^{d_i-1}}{(d_i-1)!} + \frac{x^{d_i}}{d_i!} \right) \right), $$$

where $$$T$$$ is the linear functional, mapping $$$x^\ell$$$ to $$$\ell!$$$.

The rest terms can be treated in a similar way.

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

Problem A was Too hard that a person whose rating 2700+ cant' solve it!.

https://atcoder.jp/contests/arc155/standings?watching=Barichek

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

Hack on problem D:

Input:

6
2 2 6 15 30 30

Expected output:

Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki

Output of hacked solution:

Takahashi
Takahashi
Aoki
Aoki
Takahashi
Takahashi
→ Reply