Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

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

Hello Codeforces!

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

Good luck to all the participants!

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

Harbour.Space

Hey Codeforces!

Are you curious about the latest AI advancements and how they impact our world? Do you want to know more about how AI-based methods, especially in Natural Language Processing, are revolutionizing the way we work and interact with technology?

Space.Talks Present: Radoslav Neychev, AI Enthusiast, Researcher, and Machine & Deep Learning Professor.

Radoslav, a top-tier data scientist with extensive experience in Deep Learning and Reinforcement learning techniques, is coming to our Harbour.Space Barcelona Campus to give a talk on this topic. If you can't make it there, you can join the conversation, as we will stream it live on our YouTube channel here.

In this Space.Talk, Radoslav will share his expertise on how AI is changing our everyday lives and why it's important for both technical and non-technical specialists to understand the basics of how AI works. Plus, he'll also answer important questions about AI research and its future implications.

Mark your calendar for Thursday, April 20th, at 12hrs CET, and join us for an engaging conversation. Whether you're an experienced tech expert or just starting to explore the world of coding, this talk is for you!

And remember that we are always looking for the best and brightest! If you want to learn from industry experts like Radoslav, check out the scholarships we are offering and build a brighter future with us!

Learn more here →

UPD: Editorial is out

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

Comments Comments (153)
| Write comment?
»
19 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Great. Contest are rare lately. Is it because of ICPC on the platform?

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

    Because during summer in Europe it's GMT+2 instead of GMT+1 (winter)

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

As a participant, I will appreciate the work of authors and testers. Thank you for the contest!

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

Thanks for the contest!!. That's my 2nd educational round. Let Go!!

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

Hope for stable servers.

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

    And hope for correct author solutions.

    And for rated contest.

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

Feeling like after 1 year I will participate in a CF Contest. These days contests are rare.

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

My first educational round since 3 months ago. Will I be able to solve 4 problems?

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

glhf!

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

You better not leave the rating like last time.

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

Hoping to learn new techniques and methods regardless of rating changes.

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

MUDA MUDA MUDA MUDA

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

I have 192 points to candidate master, hope to get more rating points tonight.

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

I hope that I can get more ratings this round.

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

If you hack someone you will get points?

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

    Not in educational rounds.

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

      i didn't understand , so hack unrated?

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

        In educational rounds if you hack someone's solution, it doesn't contribute anything to your "score" per se, although it could increase your ranking due to the submission no longer being "accepted".

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

Is the site getting hanged due to DDoS?

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

Solved A-E. Problem F has simple O(n*m) solution but I don't know how to optimize it.

A: Each '?' provides 10 options except the '?' at the beginning of the string, which provides 9 options. Also the first char of string cannot be '0'.

B: Because a!=a', we can find the minimum index L and maximum index R that a and a' differ at that position. Then the answer must contains [L, R]. To find the longest possible subarray, we need to extend [L, R] to left and right while a' is non-decreasing on this range.

C: Consider for all possible selection of remained character. Let c be the remained char, we can find all maximal blocks without c, and consider them seperately. For each block, let it's size be L, then we need 1+floor(log(L)) to remove it, and the answer depends on the maximum size of blocks.

D: Let r be the furthest cell we move to, and t be the number of segments we used, then the cost is r+2t. If we ignore a segment [l, r](and possibly make t decreased by 1), we will make r be increased by at least r-l+1, so we can assume that only segment with size 1 is ignored. Then for each possible segment which could contain the furthest cell, we calculate the number of 1-size segments before it, and the number of cells we can ignore (which is (sum of size of segments) — k), then we know there are how many segments we can ignore if we stop in this segment.

E: If we always remove the most right valid pair of brackets, we can see that the cost is the sum of depth of each pair of brackets, which means if we let '(' be 1 and ')' be -1, and s[i] be the array of prefix-sum, the cost is sum(str[i]==')')(s[i]) (the sum of prefix-sums at positions of right brackets). Therefore, we can see how to reduce the cost: If we move a right bracket from i to the right of j (j<i), we make s[i] on range [j+1, i-1] be reduced by 1, and changed s[i] to s[j]-1. If we move a left bracket from i to the right of j (j>i), we make s[i] on range [i+1, j] be reduced by 1. Also these moves must remain s[i]>=0 for all i. Therefore, we can consider for every possible i and find the optimal j by range minimum query and binary search, then we solved the problem for k=1. For k>1, I used greedy approach (which means simply solve the k=1 version for k times) and it passed the pretest (however I can't prove it).

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

    Can this fact be used to optimize F ?

    m * (k + 1) < n

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

    I failed test 2 on B. Why is it that simply getting the longest non-descending subarray is wrong? Since isnt any non-descending subarray from a can be obtained by sorting a'?

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

    is there any better explanation of problem c? like with some example cases?

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

      for example the string "codeforces" and we chose the letter 'c' to be the last letter remain in the string. We need to remove two substring "odefor" and "es", since these too substrings are apart from the letter 'c', so the required number of operation will be depend on the longest substrings need to be removed.

      for a string with the length of L, we need floor(log2(L)) + 1 operation to remove the whole string, since each operation we can remove at most L/2 letter if L is even, (L+1)/2 if L is odd,

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

        Great explanation. And for the less mathematically inclined (like myself), it's perfectly reasonable to calculate the number of steps needed as:

        int steps = 0;
while (max_len > 0) {
  max_len /= 2;
  ++steps;
}

        Which should be easy to understand: at every step, we can delete half the characters (rounding up, so the number of remaining characters is rounded down).

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

    In E, in one move we should always move '(' next to its corresponding ')', now for all the brackets in middles of this pair depth decrease by one. So answer is just pick k pairs with maximum number of ')' in between them. The constraint k<=5 doesn't matter. Code : 202899903

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

      Hi I dont understand for some test cases for example You are given a regular bracket sequence. In one move, you can remove a pair of adjacent brackets such that the left one is an opening bracket and the right one is a closing bracket. Then concatenate the resulting parts without changing the order. The cost of this move is the number of brackets to the right of the right bracket of this pair. I think for k = 0 squence = (()) we could remove the first outside () and leave inside () at cost 0 because there is no brackets for outside () , and remove the inside (). the total cost is 0 , but why it's 1 ? thanks

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

What was D ? fully ruin my contest -_-

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

    The problem required the perfect code so that corner cases get handled coorectly, apart from that it was simple multiset implementation.

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

      can you explain a little bit more

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

        Maybe my submission here helps?

        I tried to explain how it works in the comments. The crucial insight is that although it's mostly optimal to fill ranges from left to right, it may be better to skip ranges of size 1, and add the black cells to a later, larger range instead, to save the cost of pressing and releasing the shift keys.

        Let me know if something is unclear!

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

      It was definitely tricky, but it didn't require any complex data structure at all: just a few counters.

      I failed to solve it during the contest myself (while I had no trouble with Problem E), but if you know what you're doing, it's quite simple. See: https://mirror.codeforces.com/contest/1821/submission/202905798

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

        I solved it just after contest.....just some manipulation in my previous code which was giving wa.....i used multiset datastructure.

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

Very good string problem for C. I like it.

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

    I agree, that was a fun one!

    Problem E was also fun, though maybe more of a tree-problem disguised as a string-problem.

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

F was cool, thanks!

Maybe my solution for problem E is incorrect, but I don't understand why $$$k\leq 5$$$

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

Misread E for about 20mins(because of my poor English carelessness,I thought I could choose "some brackets"),and tried to solve F by dp with data structures but failed.So I missed a great chance to enter the top 10 in rated contestants.Sad :(

So could someone teach me how to solve F? thx >-<

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

    I ran into the same pitfall of some bracket. As a result, I didn't solve E in the contest XD.

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

For F, I manage to solve it except for this one part:

How to find the number of m-tuples that add up to n such that at least j numbers is greater than k? Find this for all j from 0 to m.

With this, you can change the question to how many different ways to place the empty space, then depending on the number of regions of empty space > k, you multiply some power of 2. (Fix the tree to always fall left if possible).

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

    My solution for problem F:

    We can say that, given $$$n$$$ positions, a subset of $$$m$$$ positions is good if it is possible to assign to each position a subsegment of length $$$k+1$$$ that either starts or ends at this position, and these segments cannot intersect.

    Let $$$l_i$$$ be the number of positions between the $$$i$$$-th and $$$(i+1)$$$-th picked ones; $$$l_0$$$ being the number of positions before the first picked, and $$$l_m$$$ -- the number of positions after the $$$m$$$-th one. Each of the positions may be coded by a number from 012 by the following principle:

    • 0 means that $$$l_i < k$$$; it also means that the trees around this segment can only fall in the directions LR.
    • 1 means that $$$k\leq l_i < 2k$$$; it also means that the trees around this segment can fall however they will, except RL.
    • 2 means that $$$2k\leq l_i$$$; the two trees can fall wherever.

    Assume that we have the coded sequence $$$c_0\ldots c_m$$$. Then the generating function of the number of total positions occupied can be represented as

    $$$\prod_{i=0}^m P_{c_i}(x),$$$

    where

    $$$P_0(x) = 1 + x + \ldots + x^{k-1} = \frac{1 - x^k}{1 - x},$$$
    $$$P_1(x) = x^k + \ldots + x^{2k-1} = \frac{x^k - x^{2k}}{1 - x},$$$
    $$$P_2(x) = x^{2k} + \ldots = \frac{x^{2k}}{1 - x}.$$$

    Let $y = x^k$. Then for each sequence of codes for the segments we have some polynomial which looks like the product of different $$$(1-y)$$$, $$$(y-y^2)$$$ and $$$y^2$$$'s, divided by $$$(1-x)^m$$$. Let's calculate the sum of these products over all valid codes.

    But what is a valid code? One can see that a code is valid iff between every two 0-s there is at least one 2. Indeed, otherwise, for a sequence, say, 01110, the trees fall like L (0) R (1) ? (1) ? (1) L (0) R. One can see that if we want to define the direction of falling for all trees from left to right, we inevitably end up replacing each ? with R and contradict the last (1).

    Now we can do some dp. We can say that each time we are in one of two states; call them safe and unsafe. A state if safe if we can insert 0 right now and not lose immediately; therefore we start from the safe state.

    We have some transitions:

    • if we append 1 when we are in an unsafe state, we proceed to an unsafe state.
    • if we append 2 when we are in an unsafe state, we proceed to a safe state.
    • if we append 0 when we are in an safe state, we proceed to a unsafe state.
    • if we append 1 or 2 when we are in an safe state, we proceed to a safe state.

    So we can express the transitions by a matrix, and in the end the polynomial is

    $$$[x^{n-m}]\frac{\begin{pmatrix}1 & 0\end{pmatrix}\begin{pmatrix}y - y^2 & y^2 \\ 1 - y & y\end{pmatrix}^{m}\begin{pmatrix}1 \\ y\end{pmatrix}}{(1 - x)^{m+1}}.$$$

    The matrix exponent can be calculated in

    $1$
    $$$O\left(\frac{n}{k}\log\frac{n}{k}\log{m}\right)$$$ as we are only intersted in the first about $$$n/k+1$$$ coefficients, and
    $$$[x^k](1-x)^{-m-1} = (-1)^k\binom{-m-1}{k} = \binom{m+k}{k}.$$$

    It may be not very optimal, did anyone do anything easier?

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

      Assume trees always fall to the left if possible. We look at the spaces the trees can take up after they fall, and then multiply by the number of ways they could have fallen. If a tree has $$$k$$$ spaces before where it falls, then it can only have been at the right endpoint. Therefore, if there are $$$x$$$ trees without $$$k$$$ spaces to the left, and $$$m-k$$$ trees with $$$k$$$ spaces to the left, then there were $$$2^x$$$ ways for the trees to fall. If we let $$$a[x]$$$ be the number of ways that at most $$$x$$$ trees have $$$k$$$ spaces to the left, $$$a[x] = \binom{n-2km+kx}{x,m-x}$$$. Let $$$b[x]$$$ be exactly how many ways the trees fall. We can count $$$b[x]$$$ using PIE with $$$a[x]$$$. $$$b[x] = a[x] - a[x-1]*\binom{m-x+1}{m-x} + a[x-2]*\binom{m-x+2}{m-x} - \ldots$$$. To find $$$\sum b[x]\cdot 2^x$$$, we do some math, and it nicely evaluates to $$$\sum a[x]\cdot 2^x \cdot (-1)^{m-x}$$$, which can be done in $$$O(m)$$$ time. A nicer way of finding the sum with PIE can be done by starting with all cases with $$$x=m$$$, and then subtracting and adding the inside cases until we reach $$$x=0$$$, but the expression is the same.

      Because smax told me to, here's a link to the submission 202891483.

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

        Done the same. Having struggled for a long time to solve the problem

        Find the number of m-tuples that add up to n such that at least j numbers is greater than k

        But later on, found that it is unnecessary to solve this problem directly.

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

        What does $$$x, m-x$$$ mean in the formula for $$$a[x]$$$?

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

      Actually the polynomial matrix multiplication result is just simply $$$(2y - y^2)^m$$$ (according to WolframAlpha)，thus the complexity would be $$$O(n)$$$.

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

problem E completely ruins the problemset. 400ish solves wtf.. I have never seen that much solves for E, especially in educational rounds.

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

    Why would that be bad?

    I always think it's good when the solve rate for each problem is somewhere between 1/2 and 1/3 of the previous problem. That allows sequences like 10000, 5000, 2500, 1250, 625, 312, 156, or 10000, 3333, 1111, 370, 123, 41, 13. I hate it when there is a hard cliff where for example “everyone” solves the first three problems and “nobody” solves the last three problems.

    This contest was fairly well balanced. Solve ratios between adjacent problems were: 1.5, 1.4, 4.6, 2.4, 14.4. That means that problem F was arguably too hard, but problem E was pretty good.

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

If I pass the system tests, I will become expert today for the first time

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

Weak pretests in D

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

Could someone help with my submission for D?

202882450

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

Screencast with commentary

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

Who is author of problem C and who specifically prepared the samples?

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

E is a nice problem: cost of the brackets can be interpreted as the area under the graph of prefix sum of the sequence :) (1/2 (Area - n/2) to be precise)

→ Reply
»
19 months ago, # |
  Vote: I like it +34 Vote: I do not like it
Hey CF, I am not chaGPT -_-
→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D:
Getting WA on TestCase 2
Suggest some counter Case. Unable to figure out the mistake.

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

    the edge cases in D are when you are considering intervals of size 1

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

is D just greedily skipping and picking segments T-T

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

    Yes

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

      bruh I thought it was some variation of knapsack or bitmask dp. i came up with the greedy solution in the last 2 mins rip

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

        Imagine performing bad twice in row just because you mistyped variable name

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

          Imagine performing bad because you are doing j = i instead of i = j

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

https://mirror.codeforces.com/contest/1821/submission/202880565
can any help to find my mistakes or find any anti test. (: its differ on 1215th on test-2.. -_-

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

Can anyone please give me a counter example for my submission for problem D.

UPD: Aced with Greedy. Thank you everyone for the help. (adityagamer thanks for test case).

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

      Isn't it correct? like I would color $$$21-36$$$ then $$$59-65$$$ so total = $$${65 + 2 * 2 = 69}$$$ I would hold and release shift twice?

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

        The ranges are inclusive — 21->36 is 16 squares so you only need to colour 59->63

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

        You can just go to 63, and that's enough 21 colored cells. So 63 + 2 * 2 = 67.

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

        Since k is 21, you only need to go till 63. So total = 63+2*2 = 67

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

What's the issue with this more general solution for D that doesn't explicitly use the special len=1 case but should still take it into account?

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

I liked D, nice problem

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

    oh bro really?? very nice to know that tbh

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

Am I the only one who solved D with sqrt decomposition+ greedy :d I figured there would be an easier solution but sqrt seemed fun :d

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

    Share your sqrt solution, I'm curious :)

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

Can someone give me a counter test to this submission for problem D? Thanks in advance.

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

Can anyone share a dp solution for D?

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

Can anyone tell me what is wrong with my C https://mirror.codeforces.com/contest/1821/submission/202883081 am using same approach as in editorial and is running fine for every case i can think of

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

    You checked only for characters whose count is maximum in the string while it may be possible that for some other character you get the smallest number of steps so instead of checking for those characters only check for all characters from a to z since there are only 26 of them so u shouldn't be worry about time complexity.

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

how to solve C?

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

    For every letter you see the minimum operations to remain with only that letter

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

In problem D, can anyone please explain why the correct output of this case is 22 but not 23?

1
4 10
1 4 9 15
1 6 13 19
→ Reply
»
19 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Can someone explain why this approach fails for problem D. I am just trying to minimse the number of segments that needs to be taken by removing the segments with lowest differences. Link to submission Thank you in advance.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
void solve()
{
    ll n , k , available = 0;
    cin >> n >> k;
    vector<vector<ll>> vt(n+1 , vector<ll>(2));
    for(ll i = 1; i <= n; i++) cin >> vt[i][0];
    for(ll i = 1; i <= n; i++) 
    {
        cin >> vt[i][1];
        available+=(vt[i][1]-vt[i][0]+1);
    }
    sort(vt.begin(), vt.end());

    if(available < k)
    {
        cout << -1 << endl;
        return;
    }

    ll previous = 0 , ans = mx , curr;
    vector<ll> aux(n+1 , 0);
    for(ll i = 1;i<=n;i++) aux[i] = aux[i-1]+(vt[i][1]-vt[i][0]+1);
    for(ll i = 1;i<=n;i++)
    {
        ll idx = upper_bound(aux.begin() , aux.end() , k+previous) - aux.begin();
        if(aux[idx-1] >= k+previous)
        {
            curr = vt[idx-1][1];
            curr += 2*(idx-i);
            ans = min(ans , curr);
        }
        
        if(idx <= n)
        {
            curr = 2*(idx-i+1);
            curr += vt[idx][0] + (k+previous-aux[idx-1]-1);
            ans = min(ans , curr);
        }
        previous = aux[i];
    }

    cout << ans << endl;
}

this is my solution for problem D. Plz somebody explain what is wrong with this approach.

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

    Does it work for touching segments where you don’t need to click shift on the border?

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

      by definition there are no touching segments. as they have stated that r(i) <l(i+1)-1

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

        Damn, I was solving with assumption that there are:)

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

      In constraints section it is specify that touching section is not allowed Given that r[i] < l[i+1]-1 for all 1 <= i <= n

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

        Then the second question, why the upper bound from begin?

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

          My basic approach is that:- 1. I skip coloring initial i-1 segment and start coloring from i-th segment then prefix count all colorable cells upto i-1 segment is stored in previous variable. When i was finding upto which segment i have to travel to get at least k colorable cells. I take upper bound , and i m taking it from beginning because i added previous in it. ll idx = upper_bound(aux.begin() , aux.end() , k+previous) - aux.begin(); During contest i was thinking it will reduce some complexity.

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

            Then you should consider previous+=aux[i]; However, what if you need to skip nonconsecutive blocks?

            in addition, you have no need to skip blocks of length >= 2 since you will need at least 2extra moves that is not better than 2 clicks

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

Nice contest! You can find the video editorial for Problem A, Problem B, Problem C and Problem D here- here

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

Maybe this sounds like a stupid question, but why are div 1 users included in the official standings?

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

    Both div 1 and div 2 participants are included in the official standings till the final system testing. Afterwards, you get the option to see only div1 participants, only div2 participants or everyone, in the standings.

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

Can anyone please explain why this code gives RE in GNU C++20 202863602, but AC in Clang++20 202892668.

Later I changed vector<pair<int, int>> v to vector v which stores only differences and it gave AC on GNU too, but I don't see a reason why this would give RE.

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

Can someone pls explain how the expected output for this input is 11?

1
3 4
1 4 6
2 4 7
→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please prove or hack my solution to problem E which I did in O(n)?

Approach: Find pairing between individual brackets. For example in (()) first bracket is paired with fourth and the second with third. Find this using stack. Simply eliminate the top-k pairs of brackets where pairs are farthest apart. The answer is the cost of the resultant string.

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

    can you explain problem E statement ?

    TestCase : ((())()(()())((()))) Answer : 4

    WHY ?

    Honestly, authors should give at least good test case with proper explanation.

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

      The cost for any rbs is the minimum cost to make it empty. So, the optimal way is to repeatedly remove the rightmost adjacent parentheses pair until we remove all pairs greedily since this gives the minimum cost. Now, before calculating the cost for the given string, we are allowed to perform k operations as mentioned in the problem statement. After a single operation, you can place a bracket adjacent to it's respective partner such that it can be removed easily. This is how I interpreted it

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

What's up with the server?

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

Can someone explain to me why greedy with min-priority-queue works for problem D? Having a hard time grasping it.

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

Can anybody tell what's wrong with my code and on which testcase it is failing. https://mirror.codeforces.com/contest/1821/submission/202836388

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

    Try this, answer should be (1, 2) whereas yours gives (1, 3)

    1
5
5 2 1 4 5 
2 5 1 4 5
    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bro, i just forgot to break the loop in else condition : /

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

for problem b

14

3 4 2 1 4 5 2 1 8 7 6 5 4 3

1 2 3 4 4 5 2 1 3 4 5 6 7 8

the output is 1 14 it should be 8 14 right I am unable to understand the question can someone please help

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

    Note the constrain:it is possible to obtain the array a′ by sorting one subarray of a.

    While for this input it should sort at least 2 subarrays.

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

Registed 6 years ago， and become master finally. And still huge gap to grandmaster. Cheer for myself.

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

Can someone help me with C, I am getting TLE in test case 8. My submission

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

During the contest I got AC for this code: https://mirror.codeforces.com/contest/1821/submission/202855933

While not optimised, I believed that it was sufficient to pass the time limits (I had ~700ms runtime), so I did not optimise it further.

After the contest it got TLE due to high constant factor of using set()

I changed the code and now it works: https://mirror.codeforces.com/contest/1821/submission/202930258

It is pretty unfortunate as I really thought that my original solution was optimised enough for the testcases, how could I tell if I should always optimise my code beforehand? Should I always optimise my code even if it passes the pre-tests?

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

thank you

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

Does E problem's "extract" mean for one time I can take a pair of matching braclets "(......)" ? If take ONE braclet each time how can I pass the example?

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

    I definitely comprehend the problem as "extract a pair of bracket each time", and it got Accepted...

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

can we use DP to solve D.

code
→ Reply
»
19 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
»
19 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Why hasn't the tutorial been released yet?

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

Wondering solution of D by using binary search

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

hey in E why k is only till 5 is it too confuse us? or make implementation easier?

→ Reply