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

    111

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

    yes.

    you are AC.

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

    zc

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

    zc

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

    Chinese love peace.Chinese don't afraid of wars.

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

    zc

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

    I didn't manage to get the perfect score on ABC on the 81st anniversary of the victory of the War of Resistance against Japan to show the Japanese what Chinese people can do... So frustrating

    How F?

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

      Don't be discouraged, I believe you will be fine. But playing ABC really has nothing to do with the War of Resistance Against Japan, and Takahashi did nothing wrong.

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

        I know, a_small_OIer. I didn't mean to attack or insult anyone。

        I heard someone say that if I solve F, I can reach cyan, but I lost a ton of rating…
        • »
          »
          »
          »
          »
          3 недели назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится

          I know you didn’t mean to attack other ethnic groups or countries; I just wanted to say that this wasn’t the original intention or purpose of ABC.

          Hugs to you – I’m sorry to hear about the rating points you’ve lost; they’ll come back next time.

          You’re about to AK ABC.

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

          我去 %%%

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

            ……

            I'm so bad at this, how can I accept being worshipped?

            我如此菜,如何接受膜拜?

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

              %%%英语大佬

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

                Nonono my English is only $$$114.5/120$$$(whk), in Codeforces you need to use English.

                I 又双叒叕(again and again) lost a lot of ranting... I am a big  .

»
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