AtCoder Beginner Contest 478 Announcement

Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

→ Pay attention

Contest is running
Codeforces Round 1132 (Div. 2)
00:19:18

Before contest
Codeforces Round 1133 (Div. 1)
22:04:18
Register now »

*has extra registration

Before contest
Codeforces Round 1133 (Div. 2)
22:04:18
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

View all →

→ Find user

→ Recent actions

Detailed →

atcoder_official's blog

AtCoder Beginner Contest 478 Announcement

By atcoder_official, history, 5 weeks ago, In English

We will hold AtCoder Beginner Contest 478.

Contest URL: https://atcoder.jp/contests/abc478
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20261003T2100&p1=248
Duration: 100 minutes
Writer: MMNMM, KumaTachiRen, toam
Tester: harurun4635, kyopro_friends
Rated range: ~ 1999
The point values: 100-200-300-400-475-525-625

We are looking forward to your participation!

atcoder_official
5 weeks ago
46

Comments (46)

Write comment?

swastik_P

5 weeks ago, hide # |

UwU!, aiming to solve till D this time

→ Reply

swastik_P

5 weeks ago, hide # ^ |

mission accomplished

→ Reply

zhang_zihao816

5 weeks ago, hide # |

I hope I can solve A to E.

→ Reply

Jerryhello

5 weeks ago, hide # ^ |

Me too.

→ Reply

314zbl

5 weeks ago, hide # ^ |

Good luck for you!

→ Reply

marvyzy

5 weeks ago, hide # |

aiming to solve D this time!

→ Reply

lhr1219

5 weeks ago, hide # |

Hope I can perform well in this contest and get >=1200 rating,so that my username can become cyan

→ Reply

K.S.A

5 weeks ago, hide # |

Hopefully I will AE this contest.

→ Reply

jqcyx

5 weeks ago, hide # |

Hope not NTT round or Maths Round.

→ Reply

PotatoForces

5 weeks ago, hide # |

Hopefully I can solve A-D this time, good luck to everybody!

→ Reply

zhang_zihao816

5 weeks ago, hide # ^ |

good luck to you too.

→ Reply

yueyixuan1

5 weeks ago, hide # |

I hope I can solve A to E.

→ Reply

NRG_Ethan

5 weeks ago, hide # |

$$$E$$$ has an easy idea but hard to implement :(

→ Reply

guoweichen

5 weeks ago, hide # |

Rubbish contest

→ Reply

lilingshengdyh

5 weeks ago, hide # ^ |

Why do these comments always receive upvotes?I heared lots of comments

→ Reply

PotatoForces

5 weeks ago, hide # |

I am so mad, i spent so long on fricking B, this has never happened before, i could have solved C way faster... couldnt even look at D :(

→ Reply

politetrex

5 weeks ago, hide # ^ |

i spent lots of time fracking C

→ Reply

errors_69

5 weeks ago, hide # ^ |

If you just looked at the conditions of B. O(n^3) solution was straight frwd.

→ Reply

PotatoForces

5 weeks ago, hide # ^ |

Yeah ikrr it was just O(N^3) but I didn't see it, and then after the contest i realised and now i am beating myself up. It's alright tho, next time!!

→ Reply

marvyzy

5 weeks ago, hide # ^ |

yeah, B was irritating (i didnt even give the contest, and did a rated register, my rating fell down, but i upsolved)

→ Reply

Tideva

5 weeks ago, hide # |

I solved A to C at last.I realy need to improve my coding ability

→ Reply

longyitongxue

5 weeks ago, hide # |

I just solved ABCD in 60 minutes, and then I couldn't continue to solve E

→ Reply

xzy_caiji

5 weeks ago, hide # |

now atcoder is full of AIer (((

It's not a good academic environment for human (and their rating). In fact, if you have a great prompt, AI's code is very similar to human's.

→ Reply

_IBXY_

5 weeks ago, hide # ^ |

Those guys are just deceiving themselves. We play games to be happy and improve ourselves, and using AI doesn't give us either of these benefits

→ Reply

DuyMinh3005

5 weeks ago, hide # |

← Rev. 3 →

What's the solution for C? I spent like an hour implementing 2 segment trees (and debugging of course) and still got 6 WAs

→ Reply

DuyMinh3005

5 weeks ago, hide # ^ |

And I ragequitted btw

→ Reply

t_tanya

5 weeks ago, hide # ^ |

← Rev. 3 →

I feel you man..., if you let A = X + Y + Z, where Y is window of size K you only need to check if max(X) <= min(Y) and max(Y) <= min(Z), if so then answer is "Yes" just check it for all window of size K.

edit: also check if X, Y is already sorted !!!

X and Z can be precal with prefix min and suffix max on array, that Y part can be well whatever you like I use multiset and queue.

→ Reply

DuyMinh3005

5 weeks ago, hide # ^ |

← Rev. 2 →

I just watched Errichto's video and realize it...

→ Reply

errors_69

5 weeks ago, hide # ^ |

can you please share the link of his video please

→ Reply

DuyMinh3005

5 weeks ago, hide # ^ |

Here

→ Reply

errors_69

5 weeks ago, hide # ^ |

Thanks alotttttttttt

→ Reply

PotatoForces

5 weeks ago, hide # ^ |

I compared sorted version of A and original and check the window where they were different, if that window length is greater than K then no solution

→ Reply

FitGirl

5 weeks ago, hide # ^ |

ac in py

# cook your dish here
from collections import deque
n,k=map(int,input().split())
a=list(map(int,input().split()))
p=[1]*n;s=[1]*n
for i in range(1,n):p[i]=p[i-1] and a[i-1]<=a[i]
for i in range(n-2,-1,-1):s[i]=s[i+1] and a[i]<=a[i+1]
mn=deque();mx=deque()
for i,x in enumerate(a):
    while mn and a[mn[-1]]>=x:mn.pop()
    while mx and a[mx[-1]]<=x:mx.pop()
    mn.append(i);mx.append(i)
    if i>=k:
        if mn[0]<=i-k:mn.popleft()
        if mx[0]<=i-k:mx.popleft()
    if i>=k-1:
        l=i-k+1
        if (l==0 or p[l-1]) and (i==n-1 or s[i+1]):
            if (l==0 or a[l-1]<=a[mn[0]]) and (i==n-1 or a[mx[0]]<=a[i+1]):
                print("Yes")

→ Reply

lsxAKCSP

5 weeks ago, hide # |

How terrible the problem E!In this and last ABC, I only had 5 WA status ans couldn't AC the problem at last.

→ Reply

freedom_wang

5 weeks ago, hide # |

F <<<<<<<<<<<<<<<<<<<<<<< E

→ Reply

lilingshengdyh

5 weeks ago, hide # ^ |

but F is hard to think,it took me 30minutes to think ,and 4minutes to code

→ Reply

freedom_wang

5 weeks ago, hide # ^ |

It onlt took me 10 min to think and code

→ Reply

tinyfold

5 weeks ago, hide # |

Today's e is a disaster. It is most obvious to me that it is a template difference constraint system. I implemented and repeatedly got tle (10 attempts). It turns out that the intended solution is SCC, and is clearly, not nearly as obvious as difference constraint system. Either make the difference constraint solution allowed, or adjust the problem so that SCC is more applicable. Better testing is needed for these ABC contests.

→ Reply

FitGirl

5 weeks ago, hide # ^ |

I think the key observation is that a t=1 edge cannot exist inside an SCC: following paths around the SCC would force an impossible strict increase. After contracting SCCs, the graph is a DAG and the answer is just a longestpath DP

ac in py

# cook your dish here
import sys
sys.setrecursionlimit(1<<20)
input=sys.stdin.readline
n,q=map(int,input().split())
g=[[]for _ in range(n)];r=[[]for _ in range(n)];e=[]
for _ in range(q):
    t,u,v=map(int,input().split());u-=1;v-=1
    g[u].append((v,t));r[v].append(u);e.append((u,v,t))
z=[0]*n;o=[]
def f(v):
    z[v]=1
    for u,_ in g[v]:
        if not z[u]:f(u)
    o.append(v)
for i in range(n):
    if not z[i]:f(i)
c=[-1]*n
def f(v,k):
    c[v]=k
    for u in r[v]:
        if c[u]<0:f(u,k)
k=0 # kosaraju <3
for v in o[::-1]:
    if c[v]<0:f(v,k);k+=1
for u,v,t in e:
    if c[u]==c[v] and t:
        print("No");break
else:
    g=[[]for _ in range(k)];d=[0]*k;deg=[0]*k
    for u,v,t in e:
        u,v=c[u],c[v]
        if u!=v:g[u].append((v,t));deg[v]+=1
    q=[i for i in range(k) if not deg[i]]
    for u in q:
        for v,t in g[u]:
            d[v]=max(d[v],d[u]+t);deg[v]-=1
            if not deg[v]:q.append(v)
    print("Yes")
    print(*[d[x]+1 for x in c])

→ Reply

SliceOfCake1538

5 weeks ago, hide # ^ |

2245D1 A similar question which came in one of the recent codeforces contests

→ Reply

drikbest

5 weeks ago, hide # |

-8

F is actually soo gooodd. Beautiful observation and such simple solution

→ Reply

t_tanya

5 weeks ago, hide # ^ |

yeah better than E where it require you to know ball more than thinking.

→ Reply

_IBXY_

5 weeks ago, hide # |

I used SPFA ,which can`t pass all the datas of E.I think it might be educational.

→ Reply

drikbest

5 weeks ago, hide # ^ |

spfa is actually have a anti test which makes it runs in v * e complexity u know, the solution of that problem is scc compression and a little bit of DAG processing

→ Reply

dckx

5 weeks ago, hide # ^ |

Actually, SPFA can pass with some weird optimizations. I passed with SPFA by changing the queue to a stack.
Submission with: queue | stack

→ Reply

KuangZhong

5 weeks ago, hide # |

Is this contest a rubbish? E is Yuanti.

→ Reply

The only programming contests Web 2.0 platform

Server time: Nov/06/2026 19:30:43 (g2).

Desktop version, switch to mobile version.

Supported by