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

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

We will hold AtCoder Beginner Contest 471.

We are looking forward to your participation!

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

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Let me introduce an experience to you. "The point values" are generally mentioned in the announcement. You can see that those with a big gap are very difficult. Usually, the difference between E-F-G is smaller. It looks normal this time.

(Maybe F will be a little more difficult this time.)

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится -59 Проголосовать: не нравится

81 years ago ...

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Hope I'll solve F/G again. Can I fly?

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +28 Проголосовать: не нравится

fuck,my classmate use my own account!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

In the last contest,I only solve A to D.And I want solve 5 problems this time.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Wait, I think I need to give a quick heads up for some people

We know what day it is today. Don't send things like that or flood the comments pls.

This should be a place for discussing problems, not for stirring up ethnic hatred OK?

Hope no one talks about nationalism in today's discussion. Avoid that pls.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Please don't post any extreme nationalist comments, and don't forget how many people got heavily downvoted last December 13.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

Please note that Codeforces is NOT a website for political discussion.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

I hope I can solve F.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Wish everyone can AK ABC!

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

Please don’t vote before the contest starts

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

I hope I can solve E and F.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

I AK IOI

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

If you believe that this time, the ranking of the difficulty for these questions is correct, DOWNVOTE me.

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

Do not publish content unrelated to algorithms/data structures on CodeForces.

qwq

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Chinese Can Fly.

I hope I solve A,B,C,D,E.

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

Hope I can solve at least five problems and improve my AtCoder rating.

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I was wrong,I'm sorry for that.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Chinese people can fly!!!

I am a beginner in OI, so I hope I can solve A, B, and C in this contest. Good luck to everyone!

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

QP

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

Good luck and have fun everyone!!!!

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +4 Проголосовать: не нравится

Today is August 15th, and many Chinese people know what day it is. World peace is everyone's desire. But I don't think it's correct to send relevant content on atcoder, not to forget national humiliation, rather than to provoke ethnic conflicts. This is just a programming website, it just holds ABC on Saturdays as usual, and you obviously shouldn't provoke ethnic conflicts and ethnic opposition here. Extreme nationalists have almost achieved it.

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

the discuss of ABC is in CF? So crazy

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

i m chinese ,i can fly !

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

Hope i can solve ABCDEF

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

Thanks to my teacher,I need to leave at 9:10 p.m. But I must solve A-E. What can I say?

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I can solve A~D.

Accessing AT is very stuck now, and there may be some obstacles.

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

I hope I can solve ABCDE.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

In spite of the fact that it's August 15th, the 81st anniversary of Japanese invasion, world peace is what we all like and AtCoder just provides a programming contest as usual. No ethnic nationality bias should appear. Takahashi does not do anything wrong.

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

I want gold perf! I want blue name!

»
3 месяца назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I solved A, B, D so far

D is so easy, isn't it?

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

    wow,l also solve A,B,D

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

    My perf is 954 now. -- ac-predictor

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

      Hi, can you send the link for the extension pls?

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

      bro,l only solve A,B,C,D.l think E is to diffcult for me.

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

        l solve A,B,C,D,E now.

        E is very esay,isn't it(copy the OP)

      • »
        »
        »
        »
        3 месяца назад, скрыть # ^ |
        ← Rev. 2  
        Проголосовать: нравится 0 Проголосовать: не нравится

        In E, you can see that for a sequence $$$x_1, \dots, x_k$$$,

        $$$\left(\sum_{i=1}^{k} x_i\right)^2 = \sum_{i=1}^{k} x_i^2 + 2\sum_{i = 1}^{k}\sum_{j = i + 1}^{k} x_ix_j$$$

        So the problem transfers to calculate this:

        $$$\left(\sum_{\{x_1, \dots, x_k\} \subseteq \{a_1, \dots, a_n\}} \sum_{i=1}^{k} x_i^2\right) + \left(\sum_{\{x_1, \dots, x_k\} \subseteq \{a_1, \dots, a_n\}} \sum_{i = 1}^{k}\sum_{j = i + 1}^{k} 2x_ix_j\right)$$$

        You can see that in the first term

        $$$\sum_{\{x_1, \dots, x_k\} \subseteq \{a_1, \dots, a_n\}} \sum_{i=1}^{k} x_i^2$$$

        , each $a_i^2$ is counted exactly $$$\binom{n - 1}{k - 1}$$$ times, because there are exactly $$$\binom{n - 1}{k - 1}$$$ subsets of $$$a_1, \dots, a_n$$$ that contain $$$a_i$$$.

        So the first term is:

        $$$\binom{n - 1}{k - 1}\sum_{i = 1}^{n}a_i^2$$$

        Similarly, you can see that the second term

        $$$\sum_{\{x_1, \dots, x_k\} \subseteq \{a_1, \dots, a_n\}} \left(2 \sum_{i = 1}^{k}\sum_{j = i + 1}^{k} x_ix_j\right)$$$

        can reduce to:

        $$$\binom{n - 2}{k - 2}\sum_{i = 1}^{n}\sum_{j = i + 1}^n 2a_ia_j = \binom{n - 2}{k - 2}\left(\left(\sum_{i = 1}^na_i\right)^2 - \sum_{i = 1}^na_i^2\right)$$$

        because for each pair $(i, j)

        Unable to parse markup [type=CF_MATHJAX]

        , there are $$$\binom{n - 2}{k - 2}$$$ subsets of $$$a_1, \dots, a_n$$$ that contain $$$a_i$$$ and $$$a_j$$$.

        After all, the problem reduces to calculating:

        $$$\binom{n - 1}{k - 1}\sum_{i = 1}^{n}a_i^2 + \binom{n - 2}{k - 2}\left(\left(\sum_{i = 1}^na_i\right)^2 - \sum_{i = 1}^na_i^2\right)$$$

        Time complexity is $$$O(n)$$$.

  • »
    »
    3 месяца назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Well, I solved C in the last 15 seconds

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

Good problems, ran out of time solving $$$F$$$ :(

»
3 месяца назад, скрыть # |
← Rev. 4  
Проголосовать: нравится -8 Проголосовать: не нравится
»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Man, I was stuck on C... can anyone explain how to solve?

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится
»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why so many NTT?

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

Why this is not working ??? for Problem D got wrong at some hidden test cases

void Solve(){
    ll q,v;cin>>q>>v;
    priority_queue<pair<ll,ll>>maxx;
    while(q--){
        ll t,w;
        ll que;cin>>que;
        if(que==1){
          cin>>t>>w;
          if(!maxx.empty()){
            ll x = maxx.top().first;
            ll y = maxx.top().second;
            ll ele = x + abs(y-t);
            ele = min(ele,v);
            if(ele > w){
                maxx.pop();
                maxx.push({ele,t});
            }
          }
          maxx.push({w,t});
        }
        else{
            cin>>t;
            if(maxx.empty()){
                cout<<-1<<"\n";
                continue;
            }
            ll x = maxx.top().first;
            ll y = maxx.top().second;
            ll ele = x + abs(t-y);
            cout<<min(v,ele)<<"\n";
            maxx.pop();
        }
    }
}

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

What's the difficulty of ABC today?

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

F is so dirty and G is an NTT template.

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

Well, I think F do not fit very well in ABC.

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

Can You please tell me for which case it is failing for Problem C

https://atcoder.jp/contests/abc471/tasks/abc471_c

// This is code
#include <bits/stdc++.h>
using namespace std;
#define ll long long

void solve()
{
    ll n;
    cin >> n;

    vector <int> lw, rw;

    ll l = 0, r = 0;
    
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;

        if (x < 0) 
        {
            lw.push_back(x);
            l++;
        }
        else 
        {
            rw.push_back(x);
            r++;
        }
    }

    lw.push_back(-INT_MAX);
    rw.push_back(INT_MAX);

    ll ini_pos = 0, g = 0, h = 0;
    ll ans = 0;

    sort(lw.rbegin(), lw.rend());
    sort(rw.begin(), rw.end());

    while (g <= l || h <= r)
    {
        ll ld = abs(lw[g] - ini_pos), rd = abs(rw[h] - ini_pos);

        if (g < l && ld == rd)
        {
            ini_pos = lw[g];
            ans += ld;
            g++;
        }
        else if (g < l && ld < rd)
        {
            ini_pos = lw[g];
            ans += ld;
            g++;
        }
        else if (h < r)
        {
            ini_pos = rw[h];
            ans += rd;
            h++;
        }
        else break;
    }
    
    cout << ans << endl;
}

int main()
{
    int t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }
}
»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to submit an after-test(a hack)?

There is a hack on F:

in:

3 2
15
000
001

out:

15001

Some submissions' out is 1000,such as——

https://atcoder.jp/contests/abc471/submissions/78428374

https://atcoder.jp/contests/abc471/submissions/78420018

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

I do not wish to see politically related content in the comment section, as this is an academic programming exchange platform. Unfortunately, I saw such comments in a very prominent position near the top of the comment section.

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
//this is code
#include <bits/stdc++.h>
using namespace std;
#define Int __int128
#define ll long long
const __int128 mod = 998244353;

Int modpow(Int a, Int b) {
    Int ret = 1;
    while (b) {
        if (b % 2) ret = ret * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ret;
}

Int com(Int n, Int b) {
    b = min(b, n - b);
    Int num = 1, den = 1;
    for (Int i = 1; i <= b; i++) {
        num = num * (n - i + 1) % mod;
        den = den * i % mod;
    }
    return num * modpow(den, mod - 2) % mod;
}

Int com2(Int n, Int b) {
    b = min(b, n - b);
    Int num = 1, den = 1;
    for (Int i = 1; i <= b; i++) {
        if (i != 1) num = num * (n - i + 1) % mod;
        den = den * i % mod;
    }
    return num * modpow(den, mod - 2) % mod;
}

vector<ll> v;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n, k;
    Int sumall = 0, ans = 0;
    cin >> n >> k;
    if (n == 1) {
        ll num;
        cin >> num;
        cout << num * num % (ll)mod;
        return 0;
    }
    v.resize(n);
    for (ll& x : v) {
        cin >> x;
        sumall += x;
    }
    Int nCk = com(n - 1, k - 1);
    Int nCk2 = com2(n - 2, k - 1);
    for (Int i = 0; i < n; i++) {
        ans = (ans + nCk * v[i] * v[i]) % mod;
        ans = (ans + nCk2 * (sumall - v[i]) * v[i]) % mod;
    }
    cout << (ll)ans;
}

can u guys pls tell me why this wrong in E????

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

In my view Problem F is harder than G :(

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

Good job task E, make me imprisoned for an hour!

»
3 месяца назад, скрыть # |
 
Проголосовать: нравится -24 Проголосовать: не нравится

Again an AtCoder contest blog and again Japanese Invasions ._.

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

How did you solved E problem Editorial didn't give much ideas

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

I sucked at implementing E :/,

Can someone help me in finding the error in this code , i'm getting WA on random test cases,

Code