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

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://codeforces.net/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://codeforces.net/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.

Can you guys tell where my code is wrong for B[submission:https://codeforces.net/contest/1841/submission/209450341]

Problem F (same solution): Link

where xi = b - a, yi = d - c

Can't you do D in O(nlogn) using RMQs? Should've switched C and D or make n = 2*10^5 in D. Then again it's edu so it doesn't matter as much.

for this submission, my pc and ideone.com shows right output, but in cf, a completely different output is shown. can someone pls point out the problem?

I am getting TLE in the test case 5 for this solution of the problem c. I have tried a DP solution.

I am not able to get why this solution is giving TLE. I think the time complexity of this solution is O(2e5* 10) or O(N*10). Since here the state is of order: O(N*10) and the transition is of order O(1).

Similarly I am also getting Segmentation Fault when I have run this solution on some random test consisting of string having length nearer to 1e5 on my local system.

The approach, I have used is something like this: For the dp the states were: ind , pos

The first state(ind) is for the index and the another state(pos) is finding two things at any index.

The first thing(last) is the last character occurred till now from the ind+1 to index n-1 and, The second thing(st) is to tell whether we have placed 'E' character or not in some higher index then this index earlier or not.

So over all, I can say: dp[ind][pos] => this will tell me the largest sum I am able to make from the index 0.. to till index ind when the last occurrence maximum alphabet is:'A' + a%5; This last occurrence is from the index ind+1 to index n-1.

So in the recursive function I just try to check If i am able to assign the character 'E' to my current index or not. If I can assign to current character then I will try to get the solution for both the cases when I have assigned to current index and when I have not. and taking maximum of them will be my answer.

If I can not assign then I will just find the value of current character value and try similarly for other lower indexes.

There could be a fun twist to Problem (A):

In every turn the players choose exactly 2 equal numbers and replace them with their sum. They start with $$$n$$$ $$$1(s)$$$ and Alice goes first. The player with all numbers different in their turn wins.
Figure out who will win.

In problem C, is it possible to have an answer < 0?

One of my friend, kehuydiet800cf, has copied Problem C in recent contest, these codes look the same:

209470016 from kehuydiet800cf

209468826 from chhavirana8

I think they has copied each other or from one source.

Can anyone please help me to figure out... what wrongs in my logic for Problem D... it is giving me wrong answer for 5th test case... I had almost similar approach as others stated here... Any help will be appreciated!

Code Link

How much time does it takes to update rating after finishing system testing?

for C it was easy to come up with an idea but I found implementation was lengthy and error prone. Does someone have easy implementation for C?

Can anyone please explain to me the approach for problem D. And if possible, please share a list of question to master DP.

I found a small bug in tourist's code, in the code of his E, he used int where long long should have been used

Here is a python code to make a hack data

import random as rnd
N=200000
print("1\n200000")
for i in range(N):
    if i%3:print(0,end=' ')
    else:print(N,end=' ')
print()

The correct output is 13333200000

But tourist's output is 448298112

Hope to release tutorial earlier.

can someone tell me how to do problem C with DP

Can someone please tell me why my code is failing in D [submission:209540485 Jun/13/2023]

Can someone please tell me why my code is failing in D 209540485

Finally I became master in this round! And this time I got the highest rank of all Div. 2 round.

In question E, I do not understand that the answer to the fourth example is 4

4 2 0 3 1 10

Can someone help me?

sorry

a similar question approach for 1841-D is in Interviewbit

Please help with “Your solution 209416596 for the problem 1841A significantly coincides with solutions theSSS/209391885, tanukool/209416596.”

The only code I used from the common source is for dealing with IO which is from USACO guide. Other than that the solution is my own and it is actually very simple by the nature of the problem so I guess there might be room for collision. Please reconsider this blame.

Edited: Many people got the same solution with similar coding style except it is c++ (e.g. 209387876).

Any counter test for this code of C

https://youtu.be/xImHQo2cTJU Video solution for D (shameless promotion :P)

I have made a detailed video (its in hindi language) to solve problem C using different approaches.
Video link : link
Let me know if it helps you :)

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

Why did the rating updated before system test again?