We will hold AtCoder Regular Contest 115. Please watch out for the unusual start time (1 hour earlier).
- Contest URL: https://atcoder.jp/contests/arc115
- Start Time: Unusual Start Time (1 hour earlier) http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210321T2000&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: YoshikaMiyafuji
- Tester: maspy, yamunaku
- Rated range: — 2799
The point values will be 300-400-500-600-700-1000.
We are looking forward to your participation!
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.
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:<
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
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.
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.
Thank @ivanzuki
Okay well it doesn't work for odd-sized odd-degree vertices
wait, why are we multiplying by
2^{back_edges}?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.
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 :/ ?
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.
Could you share that solution. I was thinking about a segment tree too but could not implement 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$$$:
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.
Yeah, the basic idea is standard and it has nice/ugly solutions depending on how much pain you enjoy.
Can you explain solution E in the editor? I don't understand the k in dp [pos] [k]
I remember E is in some other contest in the past. But I have forgot where it is.
Struggled to solve even A :(
Me too！haha
solution to A? lol.
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.
This ARC is much harder than I think. I even struggled to solve A :(