We will hold AtCoder Beginner Contest 378.
- Contest URL: https://atcoder.jp/contests/abc378
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20241102T2100&p1=248
- Duration: 100 minutes
- Writer: sotanishy, nok0, physics0523
- Tester: Nyaan, math957963
- Rated range: ~ 1999
- The point values: 100-200-300-425-475-500-650
We are looking forward to your participation!
Hope to get to 1200 in this contest.
I am 1190 now.
I think getting 1200 in atcoder is greater than 1200 in cf, isn't it?
yes
Damn it ! 1195, still green !
What are you guys f**king? Easy ABCDEF and hard G , 180+ competitors solved F in 40 min.Harder F,Pls!!!!!!
me crying with E, any hints?
Sorry for not consider your feelings but no hints < (_ _)>
Absolutely agree. It would be better to not have A and B and instead to have something between F and G.
go and partipate in AGC plz
Any hints regrading E and F ? (Contests have Ended!)
E：consider ai=(sigma (j from 1 to i) aj)%m and count the pair of i,j which (i<j) and （ai>aj）
F: consider that the deg of the path will be 2 3 3 3 3...3 3 3 2 and this is a dp
can you help me finding the error in my logic in Problem F i just considered it as a rooted tree and applied dp on trees
if degree of node is three finding the number of 2s in each child (as i can choose one node from each child) or if it is 2 then sum number of nodes with degree 2 https://atcoder.jp/contests/abc378/submissions/59397976
If i'm not mistaken you are also counting adjacent nodes which have degree 2 which violates the first condition that is graph must be simple
okay got it
but still something is missing idk what but thanks for pointing out first mistake
https://atcoder.jp/contests/abc378/submissions/59402108
your degree 3 multiplication logic is wrong. I'm actually surprised how it passed 34 TC's. Multiplying the number of suitable nodes having degree 2 in each child subtree Doesn't give the number of pairs. It should be something like
$$$a_1*a_2 + a_1*a_3 + .. +a_1*a_n + a_2*a_3 + a_2*a_4...$$$
yeah wrongly formulated
btw thanks for helping it got accepted
F : all we want is the number of pairs of nodes with degree 2 that have one or more nodes of degree 3 between them
My approach : divide the tree into connected components that have degree 3 and leaves of degree 2 (easily done using dfs) , now all we have to do is count number of pairs of degree 2 node ( n*(n-1)//2 where n == number of degree 2 leaves connected to current connected component ) add up the answers of all connected components and we are done!
HelpProblem ABC378 F: https://atcoder.jp/contests/abc378/tasks/abc378_f
Hi there,
Could you/anyone please share the edges which will result in cycle with degree 3 for the below example?
I was unable to find all and here is my finding:
11-14 (already a cycle, given)
6-10
6-7
10-7
Total: 4
Thank you in advance.
8 7
8 6
Got it thank you, without your help it wouldn't be possible.
BTW I've drwan the graph incorrectly.
Here is my findings,
Deg[2] = {10, 14, 8, 6, 7}Connecting edges:
Conclusion: Edges contributing in the formation cycle requires to have a deg of 3.
how to solve last problem?
Can you guys find the WA problem with my submission for E?
use #define int long long
Code
alright, thank you! ^_^
I followed a different approach than the editorial to solve F. First, I merge adjacent nodes that have degree 3 in the original graph. Let $$$A$$$ denote the subset of nodes of the new graph that correspond to a group of adjacent nodes of degree 3 in the original graph. On the new graph the solution is $$$\sum_{v \in A} {cnt_v \choose 2}$$$ where $$$cnt_v$$$ is the number of neighbors of degree 2 of $$$v$$$.
I think F is much easier than E.
https://atcoder.jp/contests/abc378/submissions/59414779 Can someone help me check why my solution for problem E is wrong? I can't figure it out. Thank you!
It's an integer overflow problem on line 87. Here's the fixed code.
I did not get the solution of problem E. Can anyone please explain me the solution of problem E in details ? ( details explanation )
E can be solved using divide and conquer: Let $$$f(l,r)$$$ be the result when considering the array from $$$l$$$ to $$$r$$$. Consider $$$mid=(l+r)/2$$$. We know that $$$f(l,r) = f(l,mid)+f(mid+1,r)\ +$$$ (sum of all arrays formed of by merging a non-empty suffix of $$$[l,mid]$$$ and a non-empty prefix of $$$[mid+1,r]$$$, each array has its sum under modulo $$$M$$$). We take every non-empty prefix of $$$[mid+1,r]$$$, sort them by (their sum modulo $$$M$$$). For each non-empty suffix of $$$[l,mid]$$$, let $$$suf$$$ be the sum of the suffix modulo $$$M$$$, we count the prefixes that have value less than $$$M-suf$$$ directly. Else we subtract the result by $$$M$$$ for each prefix that is greater or equal to $$$M-suf$$$. (since $$$suf$$$ + (a prefix modulo $$$M$$$) is less than $$$2*M-1$$$). To calculate this fast for each suffix we use binary search and prefix sum. Code: https://atcoder.jp/contests/abc378/submissions/59455453. Complexity: $$$O(nlog^2(n))$$$.
Anyone solved E using divide and conquer?