I hope +ve delta for me

Excited for the 150th edition of Edu round.

Good luck to everyone participating

Keep learning because life never stop teaching.

A contest after so long! There are two div 2 contests on 18th. Can one of them be shifted to another date?

hello, this will be my first contest on codeforces, any tips??

do you like yuanshen?

if i have a wrong submission without any correct submission then will i get panelty for that wrong submission?

Fun thought experiment for problem setters: Write problem D without using $$$l$$$ and $$$r$$$.

after so many defeats, this is what i call a great comeback

bruh c was kinda... interesting

Very good round, enjoyed it a lot

C was logically clear but was unable to code till the end of contest.

anyone explain the code process for the c question

What is problem C Wrong answer on test 9 ?

I reduced F to this problem: given a set $$$A$$$ of integer coordinates of the form $$$(x, y)$$$, find $$$\displaystyle\max_{S \subseteq A} [(\sum_{(x, y) \in S}x)^2 + (\sum_{(x, y) \in S}y)^2]$$$. Is this something well-known?

D was way easier than C and E is almost equal to C. Anyways, good contest.

Test case 9 or problem C ruined my contest.

I like to see a magic trick where I lose 100 points at a time

Problem F almost = This Problem

Problem F almost = This Problem

My solution for C was to count the number of "positive" numbers before a letter, ie numbers that weren't guaranteed to be negative by an earlier number. Then calculate the "gain" you get by changing letter s[i] to k, by looking at whether s[i] was guaranteed to be negative by looking at the biggest letter strictly above it, and summing over the number of letters before it that would become negative by changing it to that value. Is this correct? I got wrong answer on testcase 10.

Final EDIT: The solution can be negative. Never assume initializing best = 0 will work...

Problem C WA on test 10. Does anyone know what this test is?

Even implemented a brute force solution during the contest and tested on all strings up to length 10 and gives the same result as my solution. What am I missing?

Brute force solution:

def value(s):
    s = [ord(c)-ord('A') for c in s]
    res = 0
    md = 0
    for i in range(len(s)-1, -1, -1):
        if s[i] < md:
            res -= (10 ** s[i])
        else:
            res += (10 ** s[i])
        md = max(md, s[i])
    return res

def generate_replacements(s):
    yield s
    for i in range(len(s)):
        for d in range(5):
            if d == ord(s[i]) - ord('A'):
                continue
            yield s[:i] + chr(ord('A') + d) + s[i+1:]

def brute_force(s):
    return max(value(r) for r in generate_replacements(s))

EDIT: Up to length 10 may not be the best test since 10*D = E, etc. but my code doesn't seem to have issues with things like 100 * 'D' + 'E'.

EDIT2: It does have issues with 100 * 'D' + 'EE' of course...

I use prefix sum concept in problem c and change one by one charcter in string and every time i take maximum of all but got wr0ng answer on test case 9. Lmao what is the test case that missed my code anyone?

Кажется, что задача С — упрощенная версия задачи "Московские числа" (вроде такое название) с какого-то прошлого всероса

SO problem D can be solved by Monotonic stack？

have no testers in educational rounds makes trouble again this time in problem F?

I tried doing a greedy graphy solution to D but didn't work :D.

https://mirror.codeforces.com/contest/1841/submission/209467430

What test case for problem B was this solution failing?

I think E is easier than D, didn't feel like it belongs there though...

C is hard a little but it's very interesting

What's test 10 for C?

Why am i getting Wa 9 at Problem C?? I changed every char from A to E and adjusted the change accordingly?? What am I missing?

A: If n>=5, Alice can combine n-2 ones to make the array {1, 1, n-2}, and Bob can only make it into {2, n-2} then Alice wins. If n<=4, Bob always wins.

B: A beautiful array need to be increasing, or there's an index i where a[1, i] and a[i+1, n] are increasing and a[n]<=a[1]. Therefore, we first need to check whether the queried x[i] is not smaller than the last appended element. When the first time we meet such x[i] doesn't satisfy the condition and x[i]<=x[1], we need to accept it, but we can't accept numbers where x[i]>x[1] from now on.

C: To solve this problem we need to pre-calculate 5 arrays sum[t][i]: the contribution of s[1, i] if s[i+1]==t and s[i+2, n] doesn't exist. We calculate it by the following process: First let cnt[u]=0 where 'A'<=u<='E'. When we see s[i]<t, we let sum[t][i]=sum[t][i-1]-10^(s[i]-'A') directly, since the contribution of s[i] will always be negative. Otherwise, we need to check for u where t<=u<s[i]: We let sum[t][i]-=2*cnt[u]*10^(u-'A') and cnt[u]=0, which means contribution of occurences of u changed from positive to negative. Finally we let cnt[s[i]]+=1. After we calculate the arrays, the problem can be solved by trying every possible change of s[i].

D: We sort ranges by r[i] increasingly and run dp: dp[i]=the maximum number of valid pairs for first i ranges after sorted. The transition is dp[i]=max(dp[i-1], dp[left(i,j)]+1) where j<i, r[j]>=l[i] and left(i,j) = the maximum index k where r[k]<min(l[i],l[j]).

E: Each row is divided into several segments by black cells. By greedy method we want to fill numbers in longer segments (since a consecutive segment of white cells with length k can contribute k-1 to the answer), so we need to calculate for each k, how many segments of length k in the matrix. If we scan the matrix from up to down (from n-th row to 1st row), we can see if a[j]=i, then there's a white segment being cut at position j when we scan to the i-th row. So we can let cnt[n]=n and cnt[t]=0 (1<=t<=n-1) at the beginning, when we scan to the i-th row, we cut segments at position j for all a[j]=i. When we remove a segment of length k, we let cnt[k]-=i, and when we add a segment of length k, we let cnt[k]+=i. We can store these segments by an ordered map. Finally we check segments from length n to length 2, and fill them to get the answer.

That feeling when you solve a problem right after the contest is the worst.

I managed to bruteforce C by checking every possibility at every position and efficiently calculating the updated string value, did anyone else do the same?

Can anyone tell me why my code fails for problem B... 209470922

Can hacks affect penalty time?

Amazing set of problems.

Does anybody know what is testcase 10 for C?

Amazing contest! If you guys feel stuck on any of these problems (Problem A, Problem B, Problem C, Problem D), Please checkout this video editorial on Youtube here

Hi can anyone help me to find a counter testcase where my code gives runtime error. Got runtime error on test 3 and couldn't find the fix till now. Link:- https://mirror.codeforces.com/contest/1841/submission/209481108

What's the technology used in F? I figured out the goal is to maximize $$$(\sum a - \sum b)^2 + (\sum c - \sum d)^2$$$ but i don't know how and seems LGMs' solutions all involved in vector and convex hull things.