### maroonrk's blog

By maroonrk, history, 18 months ago,

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!

• +168

 » 18 months ago, # |   +41 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.
 » 18 months ago, # |   +2 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:<
•  » » 18 months ago, # ^ | ← Rev. 3 →   +15 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 H2) 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
•  » » » 18 months ago, # ^ |   0 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.
•  » » » » 18 months ago, # ^ |   0 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.
•  » » » » » 18 months ago, # ^ |   0 Thank @ivanzuki
•  » » » » 18 months ago, # ^ |   0 Okay well it doesn't work for odd-sized odd-degree vertices
•  » » » 18 months ago, # ^ |   0 wait, why are we multiplying by 2^{back_edges}?
•  » » » » 18 months ago, # ^ |   0 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.
•  » » » 9 months ago, # ^ |   0 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 :/ ?
 » 18 months ago, # | ← Rev. 2 →   +13 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.
•  » » 18 months ago, # ^ |   +8 Could you share that solution. I was thinking about a segment tree too but could not implement it.
•  » » » 18 months ago, # ^ |   +3 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.
•  » » 18 months ago, # ^ |   0 Yeah, the basic idea is standard and it has nice/ugly solutions depending on how much pain you enjoy.
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 Can you explain solution E in the editor? I don't understand the k in dp [pos] [k]
 » 18 months ago, # |   +8 I remember E is in some other contest in the past. But I have forgot where it is.
 » 18 months ago, # |   +21 Struggled to solve even A :(
•  » » 18 months ago, # ^ |   0 Me too！haha
 » 18 months ago, # |   0 solution to A? lol.
•  » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # | ← Rev. 2 →   -11 This ARC is much harder than I think. I even struggled to solve A :(
 » 18 months ago, # |   0 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 .
•  » » 18 months ago, # ^ |   0 Can you explain your solution to B?
•  » » » 18 months ago, # ^ |   0 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
 » 13 months ago, # |   0 Can anyone explain how to solve E ?