Блог пользователя atcoder_official

Автор atcoder_official, история, 5 дней назад, По-английски

We will hold AtCoder Beginner Contest 378.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +21
  • Проголосовать: не нравится

»
5 дней назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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.

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

GL && HF!

Hope to solve more problems.

»
4 дня назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Harder D Easier E

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope to get to 1200 in this contest.

I am 1190 now.

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Have fun & Good luck!

»
4 дня назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

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

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится +50 Проголосовать: не нравится

    Why? Please consider the remaining ~9000 competitors!

    • »
      »
      »
      4 дня назад, # ^ |
        Проголосовать: нравится -23 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 дня назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 дня назад, # ^ |
            Проголосовать: нравится -17 Проголосовать: не нравится

          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 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

    me crying with E, any hints?

  • »
    »
    4 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    Update: Fenwick tree for E :skull:

  • »
    »
    4 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    go and partipate in AGC plz

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 дня назад, # ^ |
    Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

    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 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 дня назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve last problem?

»
4 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 дня назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think F is much easier than E.

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
46 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
43 часа назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ?

»
5 часов назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone solved E using divide and conquer?