atcoder_official's blog

AtCoder Beginner Contest 378 Announcement
By atcoder_official, history, 7 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

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

→ Reply
»
7 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

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

GL && HF!

Hope to solve more problems.

→ Reply
»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Harder D Easier E

→ Reply
»
7 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.

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Have fun & Good luck!

→ Reply
»
7 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!!!!!!

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

    Why? Please consider the remaining ~9000 competitors!

    → Reply
    • »
      »
      »
      7 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!

      → Reply
      • »
        »
        »
        »
        7 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.

        → Reply
        • »
          »
          »
          »
          »
          7 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.

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

    me crying with E, any hints?

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

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

      → Reply
  • »
    »
    7 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:

    → Reply
  • »
    »
    7 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.

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

    go and partipate in AGC plz

    → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 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

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

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

      → Reply
    • »
      »
      »
      7 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

      → Reply
      • »
        »
        »
        »
        7 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

        → Reply
        • »
          »
          »
          »
          »
          7 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

          → Reply
          • »
            »
            »
            »
            »
            »
            7 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...$$$

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

              yeah wrongly formulated

              btw thanks for helping it got accepted

              → Reply
  • »
    »
    7 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!

    → Reply
    • »
      »
      »
      7 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.

      → Reply
      • »
        »
        »
        »
        7 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        8 7

        8 6

        → Reply
        • »
          »
          »
          »
          »
          7 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.

          → Reply
  • »
    »
    7 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.

    → Reply
»
7 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;

}
→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve last problem?

→ Reply
»
7 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?

→ Reply
»
7 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$$$.

→ Reply
»
7 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;
}
→ Reply
»
7 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?

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think F is much easier than E.

→ Reply
»
7 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!

→ Reply
»
7 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

→ Reply
»
7 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 )

→ Reply
  • »
    »
    7 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))$$$.

    → Reply
    • »
      »
      »
      7 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 ?

      → Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone solved E using divide and conquer?

→ Reply