Educational Codeforces Round 150 [Rated for Div. 2]
By awoo, history, 17 months ago, translation, In English

Hello Codeforces!

On Jun/12/2023 17:35 (Moscow time) Educational Codeforces Round 150 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Dmitry TheWayISteppedOutTheCar Piskalov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Additionally, big thanks to the testers ashmelev, shnirelman and Fanarill for their valuable advice and suggestions!

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space

Hello Codeforces,

Thinking about what to do with your one wild life? You are amazing in every way imaginable! You are young and immensely talented, so why not setting yourself up for a lifetime adventure — studying abroad with Harbour.Space University. Our experienced ICPC coaches are looking for new talent to join the Harbour.Space teams in SWERC and Asia Pacific regions.

Every year and all around the year, Harbour.Space University is offering full and partial Bachelor and Master scholarships to study in Barcelona and Bangkok for the academic year 2023/24 for all aspiring and eligible ICPC candidates. We qualified 2 times for the ICPC world finals and it is only the beginning of skills deployment for Spacers.

Sign up using this form to be invited to join our week-long summer camp in Spain, to get to know each other and meet the HS faculty and staff.

Our upcoming Welcome Camp will take place in August 1-7, nearby Barcelona.

After we spend a week together, you can be offered a place to study at our university. You don’t even have to leave Spain after the camp, if you secure an offer.

This is your real chance to experience two amazing cities with people from all over the world and get a diploma and accreditation too. Study, compete, work, travel, teach, enjoy the sun, sea, mountains, and all these while networking with the legends of competitive programming, future high-tech entrepreneurs and famous startup investors.

We are a no nonsense university that will immerse you into the international culture and spirit of adventure, improve your English and help you build unprecedented confidence and technical expertise to ace the ICPC. With us, you can do what you love everyday, as we never force you to take courses that you do not find interesting! When we say full academic freedom, we mean it. Your personal growth and everyday development are our utmost priority. We recognise your special abilities and therefore needs, everyone at Harbour.Space is unique and here for a reason.

Our caring admission officers are always there for you to answer any questions you might have about studying and working in Barcelona or Bangkok campuses.

Come and help us build the university of the future. Join the Stars.

Lana Velikanova, The Founder and CEO

(Please feel free to add me to your LinkedIn network)

UPD: Editorial is out

  • Vote: I like it
  • +209
  • Vote: I do not like it

Comments Comments (169)
| Write comment?
»
17 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I hope +ve delta for me

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Excited for the 150th edition of Edu round.

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

Good luck to everyone participating

→ Reply
»
17 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Keep learning because life never stop teaching.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    may your "sheer luck" support you :)

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

    You may try any previous educational round as virtual round or simply solve.

    → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

    I am not an expert to advice you. But, anyways these are general advices that everyone recommends.

    1- You must stay calm (even if you stuck, even if you got WA) it's ok just try your best and keep a bottle of water with you.

    2- don't rush in reading the problem take your time in reading & thinking (use paper and pencil) investing ~15 minutes reading & thinking carefully may prevents you from getting a WA with penalty 10 minutes + frustration.

    3 — Before submitting try corner cases like when input is small, big, even, odd, prime , string ends with space, what if the last number in array doesn't break some condition ..etc. Think in some cases that you didn't handle.

    4 — Have a confidence in yourself (don't go with mindset oh this hard so I can't solve it) you will the fight before you even started (don't give up without a fight).

    5 — Fight for the last minute of the contest trust me you don't how many times you can submit a solution in the last few minutes.

    6 — After the contest ends try up-solve by solving the problem that you stuck at. If you stuck after the contest too you can see it's tags maybe it's on a topic that you don't know, go study it for a little bit and come back. Stuck again then go for the editorial.

    Good luck & I hope you have a +ve delta bro <3.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

do you like yuanshen?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Wrong submissions for a problem you don't end up solving do not give you any penalty.

    But if you submit a wrong solution to some problem and don't solve it, your rating will get affected.

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

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bruh c was kinda... interesting

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

    I agree, although the main observation was easy to find, it took me too long to implement.

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

    yeah, it isn't hard but actually implementing all that is hell, I wasn't fast enough to start it and implement a solution.

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

      Yeah, it was hard to implement if you use greedy approach. but you can also solve it with DP and implementation wasn't that hard.

      #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
 
const int N2 = 1e2 + 5;
const int N3 = 1e3 + 5;
const int N5 = 1e5 + 5;
const int N6 = 1e6 + 5;
const int INF = 2e9 + 5;
 
vector<pair<int, int> > directions_8 {{-1, -1}, {1, 1}, {1, -1}, {-1, 1}, {0, 1}, {0, -1}, {-1, 0}, {1, 0}};
vector<pair<int, int> >directions_4 {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
 
 
int getMax(vector<vector<vector<int>>>& dp, string& str, int currIdx = 0, int currMax = 0, int rem = 1) {
    if(currIdx == str.length()) return 0;
 
    if(dp[currIdx][currMax][rem] != -INF) return dp[currIdx][currMax][rem];
 
    int charIdx = str[currIdx] - 'A' + 1;
 
    int possibleAnswer = - INF;
 
    if(rem == 1) {
        for(int i = 1; i <= 5; i ++) {
            int temp = pow(10, i - 1);
            if(i >= currMax) possibleAnswer = max(possibleAnswer, temp + getMax(dp, str, currIdx + 1, i, 0));
            else possibleAnswer = max(possibleAnswer, -temp + getMax(dp, str, currIdx + 1, currMax, 0));
        }
    }
    
    int temp = pow(10, charIdx - 1);
    if(charIdx >= currMax) possibleAnswer = max(possibleAnswer, temp + getMax(dp, str, currIdx + 1, charIdx, rem));
    else possibleAnswer = max(possibleAnswer, - temp + getMax(dp, str, currIdx + 1, currMax, rem));
    
    dp[currIdx][currMax][rem] =  possibleAnswer;
    return dp[currIdx][currMax][rem];
}
 
int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
    int t;
    cin >> t;
 
    while(t --) {
        string s;
        cin >> s;
 
        reverse(s.begin(), s.end());
 
        int n = s.length();
 
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(6, vector<int>(2, -INF)));
 
        int answer = getMax(dp, s);
 
        cout << answer << endl;
 
    }
      → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very good round, enjoyed it a lot

→ Reply
»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

anyone explain the code process for the c question

→ Reply
»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

What is problem C Wrong answer on test 9 ?

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

    You should consider that a certain large value in the back will affect many small values in the front, and in this case, you need to reduce the large value, such as DDDDDDDDDDDE，you should change E to D.

    → Reply
»
17 months ago, # |
  Vote: I like it +47 Vote: I do not like it

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?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    I found this on google: link

    In short, you sweep through all possible lines through the origin. Each one divides the points into two sets, and you consider each of those two sets as a possible answer.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
      ← Rev. 4   Vote: I like it +34 Vote: I do not like it

      I discovered another way which is possibly easier (only ACed 7mins after end)

      Consider 4 cases of sum(x) and sum(y). Assume sum(x) and sum(y) is positive, then you take all (+x,+y) and discard all (-x,-y). Then you take all (+x,-y) into your sum(x) and sum(y). Next, take the remaining (-x, +y) you didnt take as well as -(+x, -y) which you took (to undo taking them) and sort them increasing (abs(x)/abs(y)) ratio. Then you keep adding the (-x,+y) in sorted order to your sum(x) and sum(y) and take max everytime you do so. Repeat for all 4 cases. (Easiest way is just multiply all the x and y by 1/-1).

      The idea is like the 2 extreme points form like an arc, then the intermediate points form a convex hull of some sort. I cant prove but it feels like it works intuitively.

      Submission: https://mirror.codeforces.com/contest/1841/submission/209475017

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      How good should my search skills be to find something like this?

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

    Treat each $$$(x, y)$$$ as a vector, then the problem becomes finding a subset of vectors whose vector sum is furthest from the origin. Googling "sum of vectors furthest" then brought me to https://cs.stackexchange.com/questions/56158/given-a-set-of-2d-vectors-find-the-furthest-reachable-point which provides a fairly nice to implement solution based on one radial sweep.

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

    I believe this USACO problem is a harder version of that. Copying from the editorial:

    Let f(x,y)=x^2 + y^2 be the function we want to maximize. It turns out that for any convex function f, we can apply the same solution.`

Claim: We only need to consider evaluating f at the vertices of the convex hull of the set of all possible Minkowski sums.`
    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Can you Explain C and D.Plz.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      D: Sort the intervals by their left endpoint. Let $$$dp[i]$$$ be the maximum number of intervals in the range $$$[i, n-1]$$$ that we can keep (so the answer is $$$n - dp[0]$$$).

      We have two transitions: if we decide to skip interval $$$i$$$, then we let $$$dp[i] = dp[i+1]$$$. On the other hand, if we decided to keep interval $$$i$$$, we must find another interval $$$j > i$$$ to pair it up with. Now, we might as well pick $$$j$$$ to be the interval with the smallest right endpoint that intersects $$$i$$$, to minimize intersections with other intervals. Note that we have to skip over all other intervals that intersect $$$i$$$ and $$$j$$$, so let $$$dp[i] = 2 + dp[k]$$$, where $$$k$$$ is the leftmost interval that does not intersect intervals $$$i$$$ and $$$j$$$.

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

        I did it slightly differently but the implementation might be cleaner for some.

        Basically, realize that you can reduce the problem to

        1. make a new list of intervals that consists of pairs of intervals in the original array that have nonempty intersection, merged. You can do this in O(n^2).

        2. solve the maximum # of disjoint interval problem on this new list.

        3. your answer is n — 2 * # of disjoint intervals you found in step 2.

        → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Test case 9 or problem C ruined my contest.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Problem F almost = This Problem

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

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

    Best answer can be negative (you only allow changes if best > 0)

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

      Hmmm. I did include that. I only set best initialized to -10^15. Maybe that was the issue.

      → Reply
»
17 months ago, # |
← Rev. 6   Vote: I like it +5 Vote: I do not like 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...

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Input: 2 DDDDDDDDDDDDDDDDDDDE EEEEE

    Expected: 20000 50000

    Found: 28000 40000

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

      OK, So, we should consider decreasing the last E to D.

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

      I don't understand this comment. What does it have to do with mine?

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

      Yes, you can change at max 1, it implies either 0 or 1, so for TC 2, you change 0 times to get 50K

      For input 1, you can change E to D, so answer will be 20*1000

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

    The answer can be negative as well; I missed that at first and got WA on test 10. Maybe that's what you're missing as well.

    → Reply
»
17 months ago, # |
← Rev. 4   Vote: I like it -67 Vote: I do not like it

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?

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

    same but you should also consider decreasing. Check my submissions.

    → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

SO problem D can be solved by Monotonic stack？

→ Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

What test case for problem B was this solution failing?

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

    I used 2 variables, a prev and current pointer, but my solution failed like 50 times cuz i forgot to check if i added the element prev is at, also try checking if the current number is smaller than first element if you got to the beauty something part (i hope u understood)

    → Reply
»
17 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it
PAIN 😞
→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have +- the same, i will not write Edu in future:)(cause on last maybe 4 edu i get -100. But on normal rounds i dont get such huge drop :))

    → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What's test 10 for C?

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

    Never mind. Didn't realize the answer could be negative.

    → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your code is giving wrong answer for these type of input strings: DDDDDDDDDDDDDE . Changing last E to D is optimal.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I figured out. I wrote some absolute bullSh*t there. Finally did with Dp. I should have thought through dp way too during contest.

      → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

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.

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

    In D, how do you deal with cases where l[i]<l[j]? Thanks in advance!

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

      We only need to check the maximum index k where r[k]<min(l[i],l[j]).

      → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it +47 Vote: I do not like it

    There's a much easier to implement solution for C. If we change a character with another character having value greater than it, it's always best to change the first occurrence of the original character. And, if we change a character with another character having value less than it, it's always best to change the last occurrence of the original character. So we just have to check values of at most 31 strings, and print the maximum of those.

    UPD: at most 21*

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

      Did the same but initialised max with 0

      → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      So we just have to check values of at most 31 strings, and print the maximum of those

      According to your observation, given a pair (original -> modified), there is only one string that needs to be checked.

      There are 5 different characters, and each one can be modified to 4, so shouldn't it be at most 5*4 + 1 = 21 strings?

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

      Used the same implementation but getting wrong answer on test 10. Not able to find mistake. mysolution

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

        ans can be negative, you shouldn't initialise it with 0.

         int ans=0;
 ans=max(ans,call(s));

        change this to

         int ans=call(s);
        → Reply
    • »
      »
      »
      17 months ago, # ^ |
      ← Rev. 2   Vote: I like it +12 Vote: I do not like it

      Can't wrap my head around the observation.

      Consider this testcase: CCBCEB

      Changing B to D, wouldn't it be better to change the last occurrence in this case?

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
        ← Rev. 4   Vote: I like it +12 Vote: I do not like it

        Yeah you're right, it should be the first occurrence of the character where changing the character results in a positive value for the character. Not sure how I overlooked this during contest. The original algorithm still works though, because for such cases, it'll be better to change the first occurrence to the character having max value which appears after it in the original string, which is luckily considered.

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

        I believe that increasing the first occurrence gives you the best answer. Increasing the later occurrence will give you atmost the same answer as before but it would not be any better for sure. Like in your example changing the 2nd B to D does not give you a better solution than changing the first B to D.

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

          How about CEC. changing the 2nd C to D is absolutely better than changing the 1st one to D.

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

            Oh, didn't think about this one :(

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

            But in this example we can change 1st C to E EEC

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

    I did it slightly differently but the implementation might be cleaner for some.

    Basically, realize that you can reduce the problem to

    1. make a new list of intervals that consists of pairs of intervals in the original array that have nonempty intersection, merged. You can do this in O(n^2), and multiple versions of the same array do not matter (e.g. the new list can have duplicates).

    2. solve the "maximum # of disjoint interval problem" on this new list of intervals

    3. your answer is n — 2 * # of disjoint intervals you found in step 2.

    → Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    sum[t][i]=contribution of s[1...i] if s[i+1]==t and s[i+2....n] doesn't exist.

    lets calculate sum[t][i];

    intialise cnt['A']=0,cnt['B']=0,cnt['C']=0,cnt['D']=0,cnt['E']=0;

    sum[t][i]=sum[t][i-1] here sum[t][i-1] is the contribution of s[1....i-1] if s[i]==t.

    if(s[i]<t) sum[t][i]-=value(s[i])

    but if (t at (i+1)th position < s[i]) means that bec u added sum[t][i-1] at there but at the ith place bigger element was there hence therefore for all 'A'<=u<= 'E' and u>=t && u<s[i] which were accounted as positive in sum[t][i-1] now need to be subtracted and make cnt[all need to be subtracted for whom s[i] is the greater just next greater element]=0 now ..

    recurse

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

      also one more thing dp states are just 5*2e5 ...when ever u see such things try to make dp .in this way the problem is very standard dp otherwise greedy makes the job even simple ...

      one more approch that i think will work:

      we can construct 5 multisets ...set a ,set b,set c,set d,set e;

      we have an algorithm named as next greater element by stack ds.use it to find next greater element of each .

      → Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it +37 Vote: I do not like it

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?

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

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

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

    Consider this test case : q = 8 and array = [1 1 8 8 2 3 8 3] Your output: 11111000 Actual ans : 11110010

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can hacks affect penalty time?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    No. In EDU, Div.3 and Div.4, i.e. contests with an open hacking phase, succesful hacks don't give any extra score and unsuccesful hacks don't give any penalty.

    → Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Amazing set of problems.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anybody know what is testcase 10 for C?

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

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

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Looks like you might get wrong answer if the first element to break the increasing order is larger than the first element of the array.

    Input:

    1
1 9
3 7 7 9 4 4 6 3 4

    Correct output:

    111100010
    → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

Problem F (same solution): Link

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

→ Reply
»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

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

    You should initialize k with some value (maybe with n-1), otherwise there is undefined behavior and only compiler decide, what to do.

    → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

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

    You call the recursive function is called to calculate the dp state dp[ind][pos], but the return line is

    return dp[ind][st] = ans;

    This means that the state you're trying to calculate doesn't get stored at dp[int][pos], meaning that successive recursive calls to the same state will not utilize the already calculated dp values, which leads to TLE.

    Fixing this gave me WA9. Here is a case where your code fails:

    Input:
1
DDDDDDDDDDDDDDDDDDDDDDDDE

Expected Output:
25000

Your Output:
-3000

    Explanation: Change last E into D.

    → Reply
»
17 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

Solution
→ Reply
»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Yes, See test case 10,Many D and 2 E at last

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

      change last E to D, but i think if specifically answer = -1 is possible than my solution Submission and many other solutions can be hacked as using dp[i][j][k] != -1 is not safe here.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Finding a Test Case which gives -1 exact is hard. Let's wait till the Final system Testing.

        → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Lately in educational rounds it is taking 6-8 hours.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    i did it a bit differently without dp, using segment trees

    each time pair two intersectable segments, and it is always optimal that we should pair such intervals such that their combined range is more left wards

    like say there are k intervals [l1,r1],[l2,r2],.....,[lk,rk]

    and let the combined range of paired intervals be [l,r]

    we should pair such intervals with minimum r, then remove all the intervals with intersects with this range and repeat the process

    you can take a look at my submission : 209523466

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

    My solution: consider all pairs of segments. If they intersect than you can make a new segment by uniting these segments. Put all these "pair-segments" in a set. Then observe a new problem: you need to find the maximum disjoint subset of this set of "pair-segments". It can be done with dp with coordinate compression for example. The answer will be n — 2*(size of maximum subset)

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It can be done with greedy too:

      From the "pair-segments", sort by the end point of intervals and take from the first, if possible.

      Submission for the implementation: 209554396

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

    It's CSES Projects with 1 extra step.

    → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

I found a small bug in tourist's code!

In the code of his Problem 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

→ Reply
»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hope to release tutorial earlier.

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me how to do problem C with DP

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it -11 Vote: I do not like it

    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.

    → Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    n=4

    a={2,0,3,1}

    m=10

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      one possible arrangement could be :

      B 9 B B

      B 8 B 10

      1 2 B 7

      3 4 5 6

      i think you have misread the question that first a[i] cells are black in ith column not ith row

      → Reply
»
17 months ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

sorry

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

a similar question approach for 1841-D is in Interviewbit

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

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any counter test for this code of C

→ Reply
»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

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

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 :)

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did the rating updated before system test again?

→ Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

My opinion about problems and contest: A: I think it was a cute problem. Just some observation and you have it, but if you get stuck, its over. I got stuck btw :'( B: Average. Just some implementation and you have it. C: Its tough, I think it should be at the place of D in the contest. Logic is easy but the implementation is way tough (atleast what I did to AC was really tough and annoying to code). D: Its easier, I think it would had around 3-4k AC in the contest if it was at the place of C. Most of the people got stuck into C and didn't moved forward.

If you're Interested to know about any of my approach then do let me know. I would love to explain. Overall Nice Contest. Great Problems.

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

The problem C has weakly pretest, maybe you need play genshin

→ Reply