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!
In the next ABC contest, I will try the following strategy.
1. If the remaining time is more than 10/15 min, solve D or E.
2. Otherwise solve ABC
ABC problems are so easy yet, they consume more than 30 min and get me out of mood. I think it will be fun solving ABC under 10 min.
It's been a long time since I last did the problem, now I have time to do it
GL && HF!
Hope to solve more problems.
Harder D Easier E
D is easier...
Only 631 on clist.
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
Have fun & Good luck!
What are you guys f**king? Easy ABCDEF and hard G , 180+ competitors solved F in 40 min.Harder F,Pls!!!!!!
Why? Please consider the remaining ~9000 competitors!
But it make it a speed contest to the most of competitors,including the remaining ~9000 competitors!
Never judge other people in your own opinion. For low rated competitors, DEF are indeed not so easy for them.
Yeah but you will find that accepted(f)/accepted(e)~=0.75,and it is rising higher and higher which means that most of solvers of e could solve f,and what i'm talking is just what i think.Sorry for not consider others feelings,sorry.
me crying with E, any hints?
Sorry for not consider your feelings but no hints < (_ _)>
Maybe easy for you bro, I'm struggling to solve E.
Update: Fenwick tree for E :skull:
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
( i<j and a[i]>a[j] ) sort of inversion counting ?!
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!
I think F is a graph problem(apparently),you can use BFS or DFS. Like this:
I solved it after the contest ended,i'm so angry about spending too much time on E.
P.S.:Sorry about my weak English.
how to write this code optimally for problem E:-
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 got TLE from atcoder, can someone help me? I think my complexity of time is right.
How do you find the number of AC submissions for a problem during a contest?
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.
ohh thanks!
Can anyone help me out with why my code gives wrong answer for some tc in question F? Here is my submisiion link https://atcoder.jp/contests/abc378/submissions/59440996
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))$$$.
thanks for the reply but I did not get anything form your explanation or from your code ! Can you explain in more details please , if possible ?
Anyone solved E using divide and conquer?