atcoder_official's blog

By atcoder_official, history, 5 weeks ago, In English

We will hold AtCoder Beginner Contest 378.

We are looking forward to your participation!

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

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.

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

It's been a long time since I last did the problem, now I have time to do it

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

GL && HF!

Hope to solve more problems.

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Harder D Easier E

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

Hope to get to 1200 in this contest.

I am 1190 now.

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

Have fun & Good luck!

»
4 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

What are you guys f**king? Easy ABCDEF and hard G , 180+ competitors solved F in 40 min.Harder F,Pls!!!!!!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    Why? Please consider the remaining ~9000 competitors!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      But it make it a speed contest to the most of competitors,including the remaining ~9000 competitors!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Never judge other people in your own opinion. For low rated competitors, DEF are indeed not so easy for them.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it -17 Vote: I do not like it

          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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -6 Vote: I do not like it

    me crying with E, any hints?

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it -28 Vote: I do not like it

      Sorry for not consider your feelings but no hints < (_ _)>

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Maybe easy for you bro, I'm struggling to solve E.

    Update: Fenwick tree for E :skull:

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Absolutely agree. It would be better to not have A and B and instead to have something between F and G.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    go and partipate in AGC plz

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

Any hints regrading E and F ? (Contests have Ended!)

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ( i<j and a[i]>a[j] ) sort of inversion counting ?!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          okay got it

          but still something is missing idk what but thanks for pointing out first mistake

          https://atcoder.jp/contests/abc378/submissions/59402108

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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...$$$

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              yeah wrongly formulated

              btw thanks for helping it got accepted

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Help

      Problem 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?

      15
      1 15
      11 14
      2 10
      1 7
      9 8
      6 9
      4 12
      14 5
      4 9
      8 11
      7 4
      1 13
      3 6
      11 10
      Output: 6
      

      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.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        8 7

        8 6

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 3   Vote: I like it +1 Vote: I do not like it

          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:

          6 -> 10 (cycle with node 8 has deg 2, not possible)
          6 -> 14 (cycle with node 8 has deg 2, not possible)
          6 -> 8
          6 -> 7
          8 -> 7
          10 -> 14
          8 -> 14
          8 -> 10
          

          Conclusion: Edges contributing in the formation cycle requires to have a deg of 3.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think F is a graph problem(apparently),you can use BFS or DFS. Like this:

    //Author:RaShalGul
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=2e5+5;
    int n,k,ans;
    int a[N],l[N];
    vector<int> g[N];
    void dfs(int x,int fa){
    	if(l[x]==2){
    		a[x]=1;
    	}
    	for(int v:g[x]){
    		if(v==fa){
    			continue;
    		}
    		dfs(v,x);
    		ans+=a[x]*a[v]-(l[x]==2&&l[v]==2);
    		if(l[x]==3){
    			a[x]+=a[v];
    		}
    	}
    }
    signed main(){
    	ios_base::sync_with_stdio(false);
    	cin.tie(nullptr);
    	cout.tie(nullptr);
    	cin>>n;
    	for(int i=1,x,y;i<n;i++){
    		cin>>x>>y;
    		l[x]++,l[y]++;
    		g[x].emplace_back(y);
    		g[y].emplace_back(x);
    	}
    	dfs(1,0);
    	cout<<ans;
    	return 0;
    }
    

    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.

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

how to write this code optimally for problem E:-

#define vi vector<ll>
#define rep(i, a, b) for(ll i = (a); i < (b); i++)
void solve() {
    ll n,m;cin>>n>>m;
    vi p(n+1);
    rep(i,1,n+1) {
        cin>>p[i];
        p[i]+=p[i-1];
    }
    ll ans =0;
    ll prev =0;
    rep(i,1,n+1){
        prev = p[i-1];
        rep(j,i,n+1){
            //cout<<p[j]-ki<<endl;
            ans+=(p[j]-prev)%m;
        }
    }
    cout<<ans<<endl;

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

how to solve last problem?

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

Can you guys find the WA problem with my submission for E?

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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$$$.

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

I got TLE from atcoder, can someone help me? I think my complexity of time is right.


#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define fi first #define se second using namespace std; int a[200010], sum[200010] = {0}, n, m; struct fw_tree { int tree[200010] = {0}; int lowbit(int x) { return x & (-x); } void modify(int x, int k) { for (int i = x; i <= m; i += lowbit(i)) tree[i] += k; } int query(int l, int r) { int sum1 = 0, sum2 = 0; for (int i = l - 1; i; i -= lowbit(i)) sum1 += tree[i]; for (int i = r; i; i -= lowbit(i)) sum2 += tree[i]; return sum2 - sum1; } }tr; void solve() { cin >> n >> m; int res = 0, SUM = 0; for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = (sum[i - 1] + a[i]) % m; for (int i = 1; i <= n; i++) { res += i * sum[i] - SUM + m * tr.query(sum[i] + 1, m); SUM += sum[i]; tr.modify(sum[i], 1); } cout << res << endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How do you find the number of AC submissions for a problem during a contest?

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

I think F is much easier than E.

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

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!

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

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

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

I did not get the solution of problem E. Can anyone please explain me the solution of problem E in details ? ( details explanation )

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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))$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

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

Anyone solved E using divide and conquer?