maroonrk's blog

AtCoder Regular Contest 115 Announcement
By maroonrk, history, 4 years ago, In English

We will hold AtCoder Regular Contest 115. Please watch out for the unusual start time (1 hour earlier).

The point values will be 300-400-500-600-700-1000.

We are looking forward to your participation!

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

Comments Comments (21)
| Write comment?
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Thanks to this unusual start time, this contest will now end(UTC 13:00) before Codeforces Round 709 (scheduled at UTC 13:05), allowing contestants to participate in both! Thank you.

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

I only solved three problems during the contest, as I got a lot of wrong attempts, I don't get a very high rank, but I think I have tried my best.

By the way, how to solve D? I try to solve it with a $$$\Theta(n^2)$$$ DP, but failed:<

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +15 Vote: I do not like it

    HINTS :

    1) For a tree (G) if we know the set of odd degree vertices in our subgraph(H) , there is unique way to select edges for H

    2) Above thing can be expanded to any "connected" graph , by first selecting ANY subset of back edges and then select the UNIQUE subgraph in the remaining DFS tree.

    3) Given a connected graph there are {n}choose{k} * (2^{back_edges}) ways to select a subgraph with k odd degree vertices .

    4) Combining DP for connected components can give you the result for the whole graph G

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

      1) For a tree (G) if we know the set of odd degree vertices in our subgraph(H) , there is unique way to select edges for H

      I'm not sure I understand this. What if a have a tree with edges (1, 2), (2, 3), (3, 4) (4, 5) and my set of odd degree vertices is 1, 3, 5? There seems to be no way to select Edges to satisfy the conditions.

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

        It's never possible to have a set of odd size of odd vertices.

        Why: Think about including an edge. An edge is always incident to two vertices. When the edge is included, the parity of both is changed, so the size of your "odd degree" set of vertices changed in size by +2, 0, or -2. Size = 0 is always possible (don't include any edge), and from then you can only move (+2,0,-2) as I described.

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

        Okay well it doesn't work for odd-sized odd-degree vertices

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

      wait, why are we multiplying by 2^{back_edges}?

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

        Let's say in graph G you decided to have some set of vertices K as the ones having odd degree.

        I want to claim that there is unique way of selecting edges for each subset of back edges.

        Fix a subset of back edges BE , and put in graph G (notice that it may happen that adding some of these edges will make degrees of some vertices odd and some even , but this only means that your set K gets modified (if some vertex was in K and now its degree is even it remains in K , and if some vertex was not in K and now its degree is odd it is added to K ) So we can obtain a new K' which we can satisfy using the "tree edges" (satisfying K' is unique using tree edges by (1))

        So for each subset of back edges there is unique way to have degree of vertices in K odd. As there are 2^{back_edges} subsets therefore we multiply it.

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

      I just want to know how can anyone even make such an observation that "For a tree (G) if we know the set of odd degree vertices in our subgraph(H), there is a unique way to select edges for H"? Was it known to you already or, you just made that observation out of the blue :/ ?

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

I really think E is a rather standard and educational problem...

I saw the editorial, the standard solution is very nice. But my dumb segtree solution is really standard.

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

    Could you share that solution. I was thinking about a segment tree too but could not implement it.

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

      Let $$$f_{i,j}$$$ be the number of sequences $$$a_1 \sim a_i$$$ and $$$a_i=j$$$.

      Then $$$f_{i,j}=\sum_{k\ne j}f_{i-1,k}$$$ $$$(j\le A_i)$$$.

      So we basically do the following to f when moving from $$$i-1$$$ to $$$i$$$:

      • Let sum be $$$\sum_{i} f[i]$$$.
      • Multiply $$$f[A_i+1\dots\infty]$$$ by 0.
      • Multiply $$$f[1\dots A_i]$$$ by -1.
      • Add $$$f[1\dots A_i]$$$ by sum.

      We can use a lazy segment tree that supports range add and range multiply.

      By the way, can anyone please explain the editorial of F? I'm not able to understand it.

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

    Yeah, the basic idea is standard and it has nice/ugly solutions depending on how much pain you enjoy.

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

    Can you explain solution E in the editor? I don't understand the k in dp [pos] [k]

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

I remember E is in some other contest in the past. But I have forgot where it is.

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

Struggled to solve even A :(

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

solution to A? lol.

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

    For any two students, if the parity of number of 1s in one students choice is different than that of other students choice then it is impossible for them to score same. If the number of 1s are odd or even for both of the students at the same time, then it is possible for them to score same.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

This ARC is much harder than I think. I even struggled to solve A :(

→ Reply