atcoder_official's blog

AtCoder Beginner Contest 471 Announcement
By atcoder_official, history, 3 weeks ago, In English

We will hold AtCoder Beginner Contest 471.

We are looking forward to your participation!

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
3 weeks 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.)

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it -59 Vote: I do not like it

81 years ago ...

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

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

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

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

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

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

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

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

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

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

fuck,my classmate use my own account!

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

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

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

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

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

→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I hope I can solve F.

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

Wish everyone can AK ABC!

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

Please don’t vote before the contest starts

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

I hope I can solve E and F.

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

I AK IOI

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

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

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

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

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

I was wrong,I'm sorry for that.

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

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

QP

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

Good luck and have fun everyone!!!!

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

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

    111

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

    yes.

    you are AC.

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

    zc

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

    zc

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

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

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

    zc

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

    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?

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

      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.

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

        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…
        → Reply
        • »
          »
          »
          »
          »
          3 weeks ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          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.

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

          我去 %%%

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

            ……

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

            我如此菜，如何接受膜拜？

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

              %%%英语大佬

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 days ago, hide # ^ |
                 
                Vote: I like it 0 Vote: I do not like it

                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 .

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

the discuss of ABC is in CF? So crazy

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

i m chinese ,i can fly !

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

Hope i can solve ABCDEF

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

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

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

I hope I can solve ABCDE.

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

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

    Don't see Takahashi as Takaishi (?)

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

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

I want gold perf! I want blue name!

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

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

    wow,l also solve A,B,D

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

    My perf is 954 now. -- ac-predictor

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

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

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

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

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

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

    Well, I solved C in the last 15 seconds

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

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

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

bruh WA on 1 test case...

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

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

    Just implement it

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

    → Reply
»
3 weeks ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Solution discussion: https://www.youtube.com/watch?v=mL5MxaOwdo8

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

Why so many NTT?

→ Reply
»
3 weeks 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();
        }
    }
}
→ Reply
»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What's the difficulty of ABC today?

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

F is so dirty and G is an NTT template.

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

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

→ Reply
»
3 weeks 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();
    }
}
→ Reply
»
3 weeks 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

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

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

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

In my view Problem F is harder than G :(

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

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

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

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

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

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

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