atcoder_official's blog

AtCoder Beginner Contest 393 Announcement
By atcoder_official, history, 8 days ago, In English

We will hold AtCoder Beginner Contest 393.

We are looking forward to your participation!

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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does this have so many downvotes?

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    It may be because some people see the symbol of 'downvote' as a symbol of 'unfolding content'.

    I am Chinese, so the expression may not be too accurate.

    → Reply
  • »
    »
    7 days ago, # ^ |
    ← Rev. 3   Vote: I like it -15 Vote: I do not like it

    Judging by now, this ABC is likely to get a lot of downvotes in the future. (Reason: A~F is quite easy. But now no one passed G.)

    Update: A contestant passes G! Such a strong programmer!

    → Reply
»
7 days ago, # |
  Vote: I like it +26 Vote: I do not like it

Hope this round can be harder and more interesting than last one. Please do not make standard problems any more!

Wish Atcoder Beginner Contest will not be 「AI Beat Contest」.

By the way, it seems AGC disappeared.

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Wish AtCoder Beginner Contest won't be "AI Beat Contestant". Also, there's AGC071 on March 30th.

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

    《AI Beat Contest》

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

      Which AI solved it? The 4th looked some typical leetcode type, but chatgpt gave me wrong solution. Then I left.

      → Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    "Please do not make standard problems any more!"

    Why? As name of the contest suggests it's the contest for beginners. There is a rule against AI in ABC contests, so one shouldn't care about AI and just enjoy the problems

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

      Actually, if you do want to solve standard problems, you have many choices better than ABC.

      Most people, like me, just want to see more interesting and enjoyable problems in AT contests. These boring problems and more and more AI participations truly annoy me.

      → Reply
      • »
        »
        »
        »
        7 days ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        I can say the same, if you want to solve interesting and enjoyable problems, you have many choices better than ABC. You should understand these "standard" problems aren't standard for beginners and this contest mostly designed for them

        → Reply
    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I agree with you ! As a complete newbie to this platform, I am grateful such problems exist so that I too can reach the experienced level in the future just like others who find these problems easy or unexciting.

      → Reply
»
7 days ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Terrible speedcoder. Took <40min to AK Div 4 in disguise. The last problem is just extra...

Screenshot-from-2025-02-15-14-05-22

→ Reply
»
7 days ago, # |
  Vote: I like it +52 Vote: I do not like it

If next ABC as shit as this, I will ban you.

→ Reply
»
7 days ago, # |
  Vote: I like it +29 Vote: I do not like it

maybe we should call this: AI Beginner Contest

→ Reply
»
7 days ago, # |
  Vote: I like it +18 Vote: I do not like it

it this a AI Beginner Contest?

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

    We will hold AI Beginner Contest 393 for younger AI training.

    → Reply
  • »
    »
    7 days ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    so awsome.it's Gemini's showtime

    → Reply
  • »
    »
    7 days ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    if they set non-AI solvable contest, it won't be ABC anymore. Why are you complaining? It's not authors fault that "contestants" don't follow the rules

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

      if the authors counld not hold a fair contest,it will be better choice for me to take an other contest.ABC is one of the best contests for beginner,so i hope atcoder will find a way to stop this.

      → Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

"Who has better AI" contest

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

GPT-4o solved A,B,C and OpenAI o3-mini (Free Tier) solved D,E,F, but only 1 participant solved G (until 21:15).

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Who can hold a better contest on every Saturday evening?

Our coach orders us to take part in ABC.I want an other contest instead ：(

→ Reply
»
7 days ago, # |
  Vote: I like it -10 Vote: I do not like it

Oh, maybe G should be used in AHC, not ABC.

→ Reply
»
7 days ago, # |
  Vote: I like it -14 Vote: I do not like it

ez ac ABCDEF,Im vegeableness

→ Reply
»
7 days ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it

The length of the solution is 30,000 characters!!!It's unbelievable!!!

Update:The problem is G.

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How G

→ Reply
»
7 days ago, # |
  Vote: I like it +40 Vote: I do not like it

Looking at the editorial to G, I wanna kill myself.

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

    +1(The solution left me broken and repeatly shouting "F**K!")

    → Reply
»
7 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Great contest. Upvoted. I have no excuse why I could not solve E and wasted all my time on it. But great problems.

→ Reply
»
7 days ago, # |
  Vote: I like it +11 Vote: I do not like it

Terrible contest :( I would prefer quality over quantity if this is happening due to more frequent ABCs. Such contests are ruining the overall leaderboard as well.

→ Reply
»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Why can not we use simplex method to solve problem G?

I haven't tried it yet, has anyone tried it?

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Because they intentionally made simplex infeasible with uncanny error tolerance (as mentioned in the last sentence of the editorial). This is the best I got.

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

      Thank you for your response. I have carefully re-read the editorial for problem G. In fact, it said if the precision of the simplex solver is sufficiently high, it is possible to accept this problem. There is a publicly available high-precision simplex solver on the Universal Online Judge's simplex template problem. I plan to find some time to try using this solver to attempt to pass the problem.

      → Reply
»
7 days ago, # |
  Vote: I like it -18 Vote: I do not like it

I believe G is too hard as an ABC G, but since ARC and AGC both focus on thinking, and AHC shouldn't contain problems solvable in deterministic time, I think it should take place as the hardest problem in an ICPC Contest.

IT SHOULDN'T APPEAR HERE!!!!!!

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved ABCDE lightning fast lol. Weren't they kind of really easy?

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

    how did you solve E? I tried various factoring methods but couldn't figure it out.

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

      my solution is similar to sieve of eratosthenes

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

        I calculated the smallest prime divisor for each number in [1, 1e6] to be able to quickly factor any number in there. This precalculation is done in a sieve-like way. Then I go over all the elements of the array and factor it using the prime factorization computed using the sieve. Now I would have a map “cnt” from any factor in the range [1, 1e6] to how many elements in the array are divisible by that factor. Then, for some current i, we go over its factors and find the biggest one that has cnt >= k. But since this involves factorization, i guess the time is o(N*sqrt(A_i))

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

          since the maximum number is only 1e6, you don't need map to store them, an array with size 1e6 is enough, since each operation for map is O(logn) with a not small constant, and also the TL in this problem is tight.

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

            Breh I don’t understand why this always happens with these factoring problems. I always shoot just above the time limit because of some small BS detail lol.

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

    No. I solved ABCDF. I think E > F.

    → Reply
»
7 days ago, # |
  Vote: I like it +10 Vote: I do not like it

We can classify ABC problems into two categories: 1. Standard / classical (a.k.a trash speedrun AI-friendly problems) 2. PHD level (you may encounter it once in your whole CP-career, not worth learning) In short, both are trash.

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

    so why do you participate?

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

      I didn't. I stopped participating in ABC ever since they remove the E-x problem. I just have a look at the last problem after the contest was done to see if there's any interesting thing to learn.

      → Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve F?

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    O(nlogn) lis + dealing queries offline

    → Reply
»
7 days ago, # |
  Vote: I like it -8 Vote: I do not like it

G can easily be harder than an AHC problem

→ Reply
»
7 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Although I didn't like the contest much, I appreciate the effort on preparing the editorial for Problem G.

On a side note, is it a standard problem if we consider the total cost cannot exceed some non negative integer P (not sure about the bounds) and we can only choose some positive integer x in Problem G.

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

F!HELP ME!

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e6+5;
int n,q,a[N],b[N],c[N],dp[N],ans[N];
int t[N];
struct qquery{int r,x,id;}qu[N];
int lb(int x){return x&(-x);}
int query(int x)
{int res=0;for(;x>=1;x-=lb(x))res=max(res,t[x]);return res;}
void update(int x,int y)
{for(;x<=n;x+=lb(x))t[x]=max(t[x],y);}
signed main()
{
	cin.tie(0)->sync_with_stdio(0);
    //离散化a
	cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
    int m=n;
    for(int i=1;i<=q;i++)
    {
        int r,x;
        cin>>r>>x;
        qu[i].r=r;qu[i].x=x;
        qu[i].id=i;
        b[++m]=x;
    }
    sort(b+1,b+m+1);
    m=unique(b+1,b+m+1)-b-1;
    for(int i=1;i<=n;i++)
        c[i]=lower_bound(b+1,b+m+1,a[i])-b;
    for(int i=1;i<=n;i++)
    {
        dp[i]=query(c[i]-1)+1;
        update(c[i],dp[i]);
    }
    memset(t,0,sizeof(t));
    sort(qu+1,qu+q+1,[](qquery a,qquery b){return a.r<b.r;});
    int it=0;
    for(int i=1;i<=q;i++)
    {
        qu[i].x=lower_bound(b+1,b+m+1,qu[i].x)-b;
        for(int j=it+1;j<=qu[i].r;j++)
            update(c[j],dp[j]);
        it=qu[i].r;
        ans[qu[i].id]=query(qu[i].x);
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}
→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved problem D for the first time in ABC!

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the solution for problem E?

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

AI Better Contest, huh?

→ Reply