I hope +ve delta for me

Excited for the 150th edition of Edu round.

After long time going to try this contest. hope to see improvement

Good luck to everyone participating

Best of luck on this contest everyone! Hope you gain rating this round :D

I always feel that Problem Education Round is distinguished by the simplicity of the questions. Good luck to all ^-^

Plz don't give a speed contest..

Keep learning because life never stop teaching.

From previous somedays i am giving virtual contests but it is not showing in my profile. can anyone give me some ways to check those contests.

by the way good luck to everyone whoever going to participate in upcoming contest.

orz

please, don't give me the speed contest

Hope to do better this time :( Good luck Everyone!

Excited for this Round

orz @everyone

good luck everyone hope the pretests will be strong

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?

hoping for a good edu round!

wow new writer in Educational Codeforces round 150 :)

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

!good contest

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

can anyone tell me what's wrong in this solution of problem B

Please tell if someone is kind to stream problemset discussion. Thx

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.

PROCEDURE FOR C WAS VERY CLEAR BUT COULDN'T IMPLEMENT IT

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.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.

Can any body tell me why my Solution is wrong for Problem B https://codeforces.com/contest/1841/submission/209462711

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 what is test case 9 in Problem C? I am not able to figure out where my code is giving wrong output.

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

Can hacks affect penalty time?

Can someone please review my D submission. I just want to know can we optimize it and get the correct solution using this approach https://codeforces.com/contest/1841/submission/209448066

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

The best feeling i got today was when my solution for C was accepted at 1:59:54 :)

Can someone tell me what is wrong with my solution??? https://codeforces.com/contest/1841/submission/209481347

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.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.

Can you guys tell where my code is wrong for B[submission:https://codeforces.com/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?

Please can someone review my code, like what else can I do, and is this approach correct. Please https://codeforces.com/contest/1841/submission/209448066

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.