maroonrk's blog

By maroonrk, history, 6 months 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

»
6 months 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.

»
6 months 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:<

  • »
    »
    6 months 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

    • »
      »
      »
      6 months 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.

      • »
        »
        »
        »
        6 months 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.

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

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

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

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

      • »
        »
        »
        »
        6 months 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.

»
6 months 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.

  • »
    »
    6 months 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.

    • »
      »
      »
      6 months 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.

  • »
    »
    6 months 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.

  • »
    »
    4 days 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]

»
6 months 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.

»
6 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Struggled to solve even A :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

solution to A? lol.

  • »
    »
    6 months 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.

»
6 months 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 :(

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

learned a important lesson today . Since atcoder doesn't show number of participants ho solved a particular problem , I tried to solve A but couldn't , so I switched to B instead And solved B and C .

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

    Can you explain your solution to B?

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

      from the given set of constraints ( c(i,j) = a(i) + b(j) ) we can get these set of equations : c(1,1) = a1 + b1 , c(1,2) = a1 + b2 , .... , c(1,n) = a1 + bn c(2,1) = a2 + b1 , c(2,2) = a2 + b2 , .... , c(2, n) = a2 + bn . . . c(n,1) = an + b1 , c(n,2) = an + b2 , .... , c(n,n) = an + bn ;

      from this we can see that c(i,j) — c(1,j) = ai — a1 and c(i,j) — c(i,1) = bj — b1 . i.e they increase row-wise and column-wise differences between off all elements in a column or in a row is same . if this condition is violated answer is "no" , if this condition is not violated , Since all elements are non -negative e can take that smallest column ( i.e column containing all the min elements among other columns ) and call it the array b ; and for a we do this a1 = c(1,1) — b1 , a2 = c(1,2) — b2 , ..... solution

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve E ?