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

Hello Codeforces!

On Aug/31/2023 17:35 (Moscow time) Educational Codeforces Round 154 (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, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Additionally, big thanks to the tester stAngel 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
WORK & STUDY OPPORTUNITY IN BARCELONA @HARBOUR.SPACE UNIVERSITY

Harbour.Space University has partnered with Giga (UNICEF) to offer Master’s degree scholarships in the field of Data Science, as well as work experience.

We are looking for various junior to mid level candidates:

Data Scientist:

  • Strong ML knowledge
  • Experience with Data Visualization Tools like matplotlib, ggplot, d3.js., Tableau that helps to visually encode data
  • Excellent Communication Skills – it is incredibly important to describe findings to a technical and non-technical audience
  • Strong Software Engineering Background
  • Hands-on experience with data science tools
  • Problem-solving aptitude
  • Analytical mind and great business sense
  • Degree in Computer Science, Engineering or relevant field is preferred

Data Analyst:

  • Cleansing and preparing data
  • Analyzing and exploring data
  • Expertise in statistics
  • Analyzing and visualizing data
  • Reports and dashboards
  • Communication and writing
  • Expertise in the domain
  • Solution-oriented

All successful applicants will be eligible for a 100% tuition fee scholarship (29.900 €/year) provided by the partner company.

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/day

You will complete 15 modules (each three weeks long) in one year. Daily class workload is 3 hours, plus homework to complete in your own time.

Work Commitment: 4+ hours/day

Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.

REQUIREMENTS:

  • Industry experience
  • International exposure
  • Eager to learn
  • Sustainability is a key topic for you
  • You want to work for an NGO
Apply here →

UPD: Editorial is out

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

Comments Comments (167)
| Write comment?
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In blog : The problems were invented and prepared by ..., Roman Roms Glazov, ...
But in contests page Roms doesn't exist.

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

I'm always scared of educational rounds because I tend to do worse in them — but it's never too late to turn the trend around. Good luck everyone!

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

    its not just you buddy, these are just speed forces rounds lately. People solve till ABC and There is huge difficulty gap in C and D. Good luck :D

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

      Last One？

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

      but this time there is huge difficulty gap between B and C.

      Some people I saw that they solved D, but not C.

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

        That was me.. I had a stupid bug in my C sol lol. -100 delta for me, the trend continues xD

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

          same here, solved D in just 5 minutes but wasn't able to debug C

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

            Earlier educational rounds used to be educational. Now it's more like easily come up with the logic and implementation in 10-15 mins and debug the code for the corner case for next 20 mins. dsa problems have vanished entirely

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

              Nah now it's just sth like F being unsolvable for the very vast majority of people and E being some classical problem lmao

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

                Edu rounds can educate me that I can't become Master without a clear brain.

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

                  Edu rounds can educate me that I'm not at all educated...

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

    ya dalala

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

Thanks HARBOUR.SPACE UNIVERSITY

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

Hi all, it would help if you can post some insights/hints for the problems of this contest (AFTER it ends) on https://starlightps.org. Here is the collection for the problems of this contest: https://starlightps.org/problems/collection/cf-edu-154/.

This will help us get more data so users can have a platform to:

  • share/discover hints/insights on various problems
  • find similar problems given insights they struggled with.

Check it out if you're interested. Thanks!

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

Get ready for the worst implementation problems like always

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

I'm unrated. Can I participate? I've never participated in any contest before. This is my first time in codeforces. :')

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

    Of course, you will be rated after you participate in the competition

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

This is the last contest before the National Day holiday in my country.

I will do my best!

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

Wish no weak pretests again.

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

Hoping to get more educated in this educational round

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

Good luck!

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

It seems that the standings is broken unusual currently (it shows all participants in official standings, even div.1). Could you please fix redesign this bug unusual design ASAP?

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

Will be delta calculated considering contestants from div. 1 or not?

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

Can anyone help and tell for which test case my solution is failing? Problem : C Submission link

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

C>>D.

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

    rly? I solved C in 15mins but 45 on D :) but maybe its just my skill in cp being poor ...

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

adhoc forces

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

    I solved B, D and E using DP :)

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

      What was your states and transitions to solve E ?

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

        dp[i][j]: number of arrays of size i such that the last j elements are distinct

        if j = k then the last j elements form a permutation and if j>k it means the last j%k elements are distinct and there are j/k permutations not including the last j elements

        dp[0][0] = 1

        for transitions:

        dp[i][j] = (summation dp[i-1][l] where l>=j and floor(l/k)=floor(j/k), and l is not a multiple of k) + dp[i-1][j-1]*(k-j%k)

        k-j%k is the number of possible elements distinct from the last j%k, it's the number of possible ways to make the last j%k+1 elements distinct

        the number of possible ways to make only the last j%k — x numbers distinct is 1, just append the xth element from the end

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

How to solve E?

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

    I didn't solve E, but I think it maybe smth like $$$dp[i][len][count]$$$, where $$$i$$$ is a length of prefix, $$$len$$$ is the maximum suffix, where all numbers are distinct and $$$count$$$ is the number of obtained correct sequences of length $$$k$$$. The number of states is not more than $$$N * K * N / K = N^2$$$, so it maybe correct if all transition is made no longer than $$$O(1)$$$. But unfortunately I got confused in the transitions :(.

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

      Got the same idea, but had no time due to B and C...

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

      What does your suffix mean?

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

        It means the longest suffix of current prefix of length i, where all numbers are distinct

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

      My solution uses this idea, perhaps you can check it out and see if it makes sense to you. 221347739

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

      I just figured this out (very close to solving it during contest). You can check out my submission with comments 221395884

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

How to solve D? do we need to consider some increasing and decreasing slopes?

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

    You can make some prefix negative and rest all positive.

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

      Can you tell me how you came up with this intuition? A lot of people found this fairly easy but I couldn't come up with any solution.

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

        First, assume we are only dealing with positive numbers. For any adjacent a,b, if a>=b, we will have to multiply b and all numbers after it Proof assume there is a c after b. If b is already less than c, multiplying both is the surest way to preserve that. If b>=c, then (again, with positive numbers) no matter what we do we can't change that, so it's still fine to multiply both.

        Now we can extend this to negative numbers using similar logic (replace a<=b with a>=b). Since we need a strictly increasing sequence, we can do a single transition from negative to positive numbers, but it may not be necessary (all negative/all positive could be better).

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

3 contests in a row solving E but can't finish in time, fuck

smb please tell their solution to E?

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

    Same to me for problem C. Long way to go on the revenge journey.

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

    I solved by finding, "in how many arrays does some subarray contribute?"

    For this, I use a dp state where dp[i] gives number of arrays of length i, such that the subarray ending at the last index is used.

    Now for calculating dp[i], we can first see that elements from i-k+1 to i should form a permutation of k, and for the rest, we can give any element from 1 to k. So we initially set dp[i] to be k! * exp(k,i-k).

    Now we need to subtract those arrays from dp[i] which have their last used subarray ending at some index in the range [i-k+1, i), because it will intersect with our subarray ending at i. Suppose we have an array ending at j, which lies in [i-k+1, i). So number of arrays such that last used index is j, and [i-k+1,i] still forms a permutation is dp[j] * (i-j)!. We subtract this value from dp[i] for all j in [i-k+1, i).

    Now our answer is the sum of contributions of all subarrays, so we can simply sum up dp[i] * exp(k,n-i), because for all elements after i, we can place anything we want.

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

Took so much time for C, couldn't even think about D much. How to solve D?

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

    Divide the array into two halves, make first half negative ascending and second half positive ascending. Pick the best answer among all possible half partitions (you can also make all positive and all negative).

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

    If you only multiply by positive number then the answer would be number of elementsi such that a[i]>=a[i+1]. Instead what we can do is for some i turn the prefix before it to a negative increasing array. If the prefix contains k strictly decreasing segments then the number of operations needed to convert the whole prefix to an strictly increasing prefix such that all it's elements are negative is k. So we can just check it for each index i and calculate the minimum

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

I feel D<C and the implementation of C was complex. What's the easiest solution for C?

my submission: 221301419

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

    You just need to maintain 3 variables: current_number_of_element, sorted_till(default = 0) and unsorted_from(default = inf) and do casework.

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

    I created a tree and checked for validity using dfs.

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

    I used a lazy segment tree for C

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

      I don't think I've seen this level of overkill since this

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

        It's not overkill at all. I just copied the tree and then implemented it within 5 minutes. I believe it's the easiest and quickest approach to solve problem C.

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

          Hi, can you explain your solution how it works ?

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

            Maintain a pointer and a lazy segment tree where each node in the tree is assigned one of three values: 0, 1, or 2, representing "not sorted," "sorted," and "unknown" respectively.

            Consider each type of query as follows:

            • "+": Increment the pointer by 1 and set the corresponding value in the tree to 2.

            • "-": Decrement the pointer by 1.

            • "0": If the node's value at the pointer position in the tree is 1, the answer is "no". If it is 2, set it to 0.

            • "1": If the minimum value in the range [1, pointer] of the tree is 0, the answer is "no." Otherwise, set all values in the range [1, pointer] to 1.

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

      💀

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

    I kept track of L = current length of the array, A = the maximum possible number of sorted elements, B = minimum possible number of sorted elements. If B == L, then 0 is impossible. if A < L, 1 is impossible.

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

      This makes sense to me. It's short to implement and lighter casework. 221383919

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

      For a long time I could not understand the author's solution to this problem, but I understood your explanation right away, it is so simple and understandable. Thanks a lot!

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

    Let's make a stack which maintain values where 0=unsorted from here, 1=sorted until here, 2=unknown.
    When processing query=='+', if stk.top()==0 then stk.push(0) (to propagate info) because array is unsorted obviously, else stk.push(2).
    When processing query=='-', if stk.top()==1 then do{stk.pop();stk.top()=1;} (to propagate info) because array is sorted obviously, else just stk.pop().
    my submission: 221294647

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

    I used a stack: 221370839

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

    Maintain a stack of states : 1 if sorted, 0 if not, -1 if both possible. When you add an element it's either 0 if the array is already not sorted, or -1 (since the last element can be decreasing too). For the queries : if last state is -1 and array is sorted erase all the minus ones and replace them with ones.

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

    My 3 variable solution: 221315344

    (same as described by adityagamer)

    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

How to solve C?

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

    If a prefix of an array is not sorted, the arrays to which the prefix belongs is also not sorted. If array is sorted, all its prefixes are also sorted. Just simulate operations from left to right and keep track of the state of the prefix (whether it's sorted, not sorted, or no idea), if you find a contradiction, answer is no otherwise yes.

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

C is so bad

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

Huge increase in difficulty from D to E. Why is it that only GM or LGM-s can solve last problem on div 2? It's rated under 2100 but not expected to be solved someone under 2100.

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

    I fully agree, every edu looks like this for some reason.

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

C was a brilliant problem.Took me an hour to realise it could be solved by set and lower bound.

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

A: One of "13" and "31" will be a subsequence of permutation of [1, 9], and both of them are prime.

B: Note that during the operation, the occurence of substring "01" can only be removed but can't be created. Since the first and last character can't be changed, there will be occurence of "01" in both a and b after operation, and they need to occur at the same position, so there must be some position that "01" occurs at this position both in a and b initially. On the other hand, if a[i]=b[i]='0' and a[i+1]=b[i+1]='1', we can do operation (1, i) and (i+1, n) both on a and b, then a and b will be the same.

C: We need to maintain 2 values: pos1 = the leftest possible position such that a[pos1-1]>a[pos1], pos2 = the maximum possible prefix such that a[1, pos2] is sorted. When we process query '0', we need to check if pos1<=length, then let pos2=length-1, and for '1' we need to check if pos2>=length, then let pos1=inf.

D: Suppose we need to make a[1, k] negative and a[k+1, n] positive. For making a[k+1, n] positive and sorted, we need a operation for each k+1<=i<n and a[i]>=a[i+1]. For making a[1, k] negative and sorted, we need a operation for each 1<=i<k and a[i]<=a[i+1], then we need an extra operation on [1, k] multiply by -1. Therefore we can solve the problem by keeping prefix and suffix sums.

E: When solving the problem for a single array, we can solve by greedy: Iterate i from 1 to n, when a[i-k+1, i] is a permutation and doesn't intersect with any subarray we've taken, we take it as a valid subarray. Let dp[i][j] = the answer when we consider arrays of length i and the length of the maximal suffix without duplicate elements is j, cnt[i][j] = number of arrays of length i and the length of the maximal suffix without duplicate elements is j. For 0<=j<k-1, the update is dp[i][t] += dp[i-1][j] for 1<=t<=j, dp[i][j+1] += (k-j)*dp[i-1][j] (similar for cnt[i][t]). When j==k-1, adding the missing number of the suffix with length k-1 will create a new permutation as a subarray, so the answer need to be increased: ans[i][0] += ans[i-1][k-1] + cnt[i-1][k-1], and for 1<=t<k, we have ans[i][t] += ans[i-1][k-1]. Thus we can solve the problem in O(n*k) by using prefix sum for range updates.

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

Best contest of my life, Thanks. UwU

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

This guy v6ishal is streaming contest live on youtube. Is there something that can be done? Link to the video : https://www.youtube.com/live/JLoIIk9S_F0?si=MASh06PY_pKUhj22 Channel Link : https://youtube.com/@v6ishal?si=uUk4r0I3VbBfbeI_

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

Am I the only one who thinks the sample testcases are too weak? T_T

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

    +1

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

    btw, I upsolved problem D using DP. I noticed that most contestants solve it with some observations. If anyone's approach is similar to mine(not a good "observer" haha) and is stuck in WA, I hope my submission will help!

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

      hard dp to understand, maybe you can explain what is f[i][j]?

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

        $$$f_i$$$ is the answer considering $$$[1,i]$$$.

        $$$f_{i,0}$$$ is the answer when we modify $$$a_i$$$ with a negative number, and $$$f_{i,1}$$$ is the positive case.

        Then the following process is kinda natural. If $$$a_i$$$ and $$$a_{i-1}$$$ can satisfy the restriction in one operation, the answer is equal(just "extend" the operation from $$$i-1$$$ to $$$i$$$), otherwise it has to $$$+1$$$.

        • $$$a_i> a_{i-1}$$$
        • $$$f_{i,1}$$$: whether $$$a_{i-1}$$$ is modified positive / negative, $$$a_i$$$ can be greater than it without another operation("extend" the operation / just do nothing), so $$$f_{i, 1}=\min(f_{i-1,0}, f_{i-1,1})$$$.
        • $$$f_{i,0}$$$: if $$$a_{i-1}$$$ is positive, it doesn't make any sense for $$$a_i$$$ to be negative, and we don't consider that. If we extend the negative operation on $$$a_{i-1}$$$ to $$$a_i$$$, $$$a_i$$$ will become smaller. So one more operation is required. $$$f_{i, 0}=f_{i-1,0}+1$$$.
        • $$$a_i< a_{i-1}$$$
        • $$$f_{i,1}$$$: if we extend a positive operation on $$$a_{i-1}$$$ to $$$a_i$$$, $$$a_i$$$ is still smaller, so one more operation is required. if $$$a_{i-1}$$$ has become negative, we do nothing. $$$f_{i, 1}=\min(f_{i-1,0}, f_{i-1,1}+1)$$$
        • $$$f_{i,0}$$$: if we extend a negative operation on $$$a_{i-1}$$$ to $$$a_i$$$, $$$a_i$$$ will be greater than $$$a_{i-1}$$$ and we don't need to spend another operation, $$$f_{i, 0}=f_{i-1,0}$$$.
        • $$$a_i= a_{i-1}$$$ is a mix of the above.

        thus $$$\min(f_{n,0}, f_{n,1})$$$ is the final answer.

        ah, it looks the nested markdown list is broken...

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

Did anyone else solve B using dp because it seemed simpler than trying to find a greedy solution or is it just me?

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -58 Vote: I do not like it

It was the worst Educational round (in my opinion), thanks to BledDest, Neon, Roms, adedalic and awoo!

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

    Did you participate in this EDU? I couldn't find you in the standings.

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

A was very tricky

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

this isn't an educational type round imo. just tricky constructive implementations

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

Since when does CF give penalty for failing on samples?

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

    Since the beginning. It only doesn't give penalty if you fail test case 1 in order to avoid cases of "I accidentally submitted the wrong code". But if you fail test 3 and it's in the samples it's still going to give penalty.

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

      Must've confused it with some other judge... Thanks

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

Does anyone have an example where doing a prefix sum instead of suffix sum for D doesn't work?

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

    What exactly do you mean by that?

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

      When I made my dp array to count the number of operations needed to convert the array to strictly increasing, I just made a prefix sum array and assumed I could've just taken some suffix from it, instead of making a suffix sum.

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

        I did the same way. I guess your implementation is wrong in some corner case, don't know where exactly. Maybe my solution might help

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

          Hmm that's weird. I just set the first index as 0 and just iterated thru and added 1 if current element is <= prev element

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

Is Someone tell me how to i solve A & B fast in div2 contest. To give me any advice. Thanks.

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

    Practice Cs, a and b will seem easier and you could get them faster.

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

Help me explain problem C. test case: ++++0++---1. why the result is TRUE

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

    List of numbers inserted in order: 1,2,4,3,5,6.

    The first 4 elements are not sorted so the 0 and after inserting remaining 2 elements you remove the last 3 elements which leaves us with1,2,4 which is sorted so the 1.

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. arr = {1}
    2. arr = {1, 2}
    3. arr = {1, 2, 3}
    4. arr = {1, 2, 3, 2}
    5. arr = {1, 2, 3, 2} => 0
    6. arr = {1, 2, 3, 2, 3}
    7. arr = {1, 2, 3, 2, 3, 3}
    8. arr = {1, 2, 3, 2, 3}
    9. arr = {1, 2, 3, 2}
    10. arr = {1, 2, 3}
    11. arr = {1, 2, 3} => 1
    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    until the array size reach 4 you don't know weather it's sorted or not when the array size becomes 4 0 appears which means array is not sorted and it can be due to 4th element or any of the first 3 elements after that 2 elements added last 3 elements removed we are left with first elements and we don't know weather it's sorted or not so it can be sorted sorted and the sequence is correct for eg:- add 1, add 2, add 4, add 3 -> unsorted add 5, add 6, remove 6, remove 5, remove 3 array becomes 1, 2, 4 -> sorted

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

    for each + sign append the following number

    2,3,4,3

    after this it is 0 so the array formed is unsorted again for each + append following number

    2,3,4,3, 5,6

    now remove three number from last as we have — then we get 2,3,4 after this it is 1 and also the array is sorted so it is true.

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

Can anyone explain the observation of problem B as A[i] == 0 and A[i+] = 1 for some index for both A and B?

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

Video Editorial for Problem A,B,C,D.

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

Can anyone please tell error in my soln for problem C. I am getting WA on 2638th test case 3. 221366386

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

    same for me bro, I have -12 at C and I'm gonna lose my specialist :(

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

First two solution by recursion

1) Problem A

2) Problem B

Upvote If u like my solution

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

E is very cute

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

Can anyone provide a counter example for this submission for problem C — 221365170

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

    you may try this testcase: 1 ++0++0++0--1 expected: NO your solution output : YES

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

      Damn this was the case that caused the whole problem for me yesterday!! Let's smile and move on :') .

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

I always find educational rounds tricky.

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

ABCDE are all doable but I wasted too much time on C just to figure out how to implement "properly".

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

Disappointed that i could't solve problem D during contest.It was doable and bit easier than usual problme D of educational rounds.

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

Hi all, it would really help if you can post some insights/hints for the problems of this contest on https://starlightps.org ! Here's a link to the problems: https://starlightps.org/problems/collection/cf-edu-154/. This will help us get more data so users can have a platform to:

  • share/discover hints/insights on various problems
  • find similar problems given insights they struggled with.

Check it out if you're interested. Thanks!

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

Had been solving 3rd problem from the last 6 contests, Couldn't solve this time

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

Why should there be no pretesets in problem C with |s| = 2 * 10^5?

I set my N ( MAXN ) equal to 10^5 and got time limit on system testing. :(

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

In problem c can anyone tell me where my code fails this on

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

Waiting for rating change.

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

    Continuously pressing F5 in front of the computer because I am confident that I am finally going to become a master after the rating change.

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

    congrats!

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

hackational codeforces round

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

Can someone explain me why my code fails on problem C 221400131

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

When will editorial drop?

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

I am waiting for the moment to reclaim my blue.

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

    i am waiting to become specialist for the first time :( why are the rating changes taking so long

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

      Nothing can make us happy without patience

      I think the rating changes will be executed soon!

      Enjoy your day ^^

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

Is there a math solution for problem E?

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

My solution for C got accepted during the contest, but it now shows TLE. Day ruined :(

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

I couldn't be any more unlucky. Missed 2100 by 1 rating point :(

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

What is case 58 of test 3 in problem D? I've been trying to figure out what's wrong with my solution since yesterday but I can't figure it out. Can someone tell me what that test is, or help me find a counter example for my solution? Link to my solution: Your text to link here...

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

Where is the editorial?

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

Problem E...

say DP(n) = total sum of costs of arrays of size n.

DP(n) = C(k) * (DP(n-k)+1) + C(k + 1) * (DP(n-k-1)+1) + ... + C(n) * (DP(0) + 1)

But I can't get formula for C(i), number of arrays of size i, such that only the last subsegment of length k has pairwise distinct elements.

Can someone help, please? ;((

EDIT: (mistake in DP(n), I think it should be: DP(n) = C(k) * (DP(n-k)+k^(n-k)) + C(k + 1) * (DP(n-k-1)+k^(n-k-1)) + ... + C(n) * (DP(0) + 1)

→ Reply
»
16 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
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know the 682th token for tc3 for C? My soln is here: soln although it maybe be abit unreadable

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

Overall good contest C was little tougher.

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

Why Was My Submission Skipped Despite Submitting First

https://codeforces.net/blog/entry/120756

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

NO

→ Reply