atcoder_official's blog

By atcoder_official, history, 3 months ago, In English

We will hold AtCoder Beginner Contest 471.

We are looking forward to your participation!

»
3 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it -59 Vote: I do not like it

81 years ago ...

  • »
    »
    3 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +27 Vote: I do not like it

    Please refrain from posting about 8.15,9.3 and 12.13 again. You may refer to this to see what happened the last time. The writers and testers never mentioned Japanese invasion, and AtCoder only hosts these Beginner Contests on their regular weekly Saturday schedule as usual.

    (Partly translate by AI)

    UPD: It seems that comments about 12.13 was removed from here. So I'll tell you that many people sent similar messages like this and got lots of downvotes. At last they can't send comments anymore.

    • »
      »
      »
      3 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it -25 Vote: I do not like it

      That's true . I know this isn't AT's problem.

      • »
        »
        »
        »
        3 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Since you know it isn't AtCoder's problem, why did you still post that? This is an academic platform.

    • »
      »
      »
      3 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it -16 Vote: I do not like it

      First , we should remind people with these history.

      Next , we shouldn't attack anyone who hasn't join these things .

      Then , we need to study and improve ourselves.

      Last but not least , thank you for reply me.

      • »
        »
        »
        »
        3 months ago, hide # ^ |
         
        Vote: I like it +35 Vote: I do not like it

        This is a programming webstite, not a history website. Why do we need to tell people about something that does not fit into the context at all? If I told you that apples are good for your health in a conversation about cheaters, you'd probably be confused, right?

      • »
        »
        »
        »
        3 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        bro's just farming negative contributions or just ragebaiting atp lol

  • »
    »
    3 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +21 Vote: I do not like it

    We're not here to start arguments, and this place is for everyone who loves peace, right? This is Code Forces, we're just gathered here because we share the same interests, it has nothing to do with nationality.

»
3 months ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

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

»
3 months ago, hide # |
← Rev. 2  
Vote: I like it +28 Vote: I do not like it

fuck,my classmate use my own account!

»
3 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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

»
3 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

»
3 months ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

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

»
3 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I hope I can solve F.

»
3 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Wish everyone can AK ABC!

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Please don’t vote before the contest starts

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope I can solve E and F.

»
3 months ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

I AK IOI

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

qwq

»
3 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Chinese Can Fly.

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

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I was wrong,I'm sorry for that.

»
3 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

QP

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Good luck and have fun everyone!!!!

»
3 months ago, hide # |
← Rev. 2  
Vote: I like it +4 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

the discuss of ABC is in CF? So crazy

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i m chinese ,i can fly !

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope i can solve ABCDEF

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I hope I can solve A~D.

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

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope I can solve ABCDE.

»
3 months ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

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 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Don't see Takahashi as Takaishi (?)

  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    You're Right!!! We should approach this competition with a proper attitude, rather than merely using it to promote extreme nationalist rhetoric that is unrelated to the algorithm competition!!!

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I want gold perf! I want blue name!

»
3 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I solved A, B, D so far

D is so easy, isn't it?

  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    wow,l also solve A,B,D

  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    My perf is 954 now. -- ac-predictor

    • »
      »
      »
      3 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

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

      • »
        »
        »
        »
        3 months ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it 0 Vote: I do not like it

        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 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Well, I solved C in the last 15 seconds

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, hide # |
← Rev. 4  
Vote: I like it -8 Vote: I do not like it
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Just implement it

  • »
    »
    3 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    brother if we store cookies position in set then we can know if the left or right cookies from the current position exist and if so then we know what are left right cookies positions, from this you can case work it brother 👍

»
3 months ago, hide # |
 
Vote: I like it +11 Vote: I do not like it
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why so many NTT?

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What's the difficulty of ABC today?

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

F is so dirty and G is an NTT template.

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
//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 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In my view Problem F is harder than G :(

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    difficulty can sometime be subjective to me too, a lot did solved it so fast like ~12 mins whereas it took me like ~30-40 mins to finally notice that it could be contribution per unit😅

»
3 months ago, hide # |
 
Vote: I like it -24 Vote: I do not like it

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

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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