Educational Codeforces Round 128 [Rated for Div. 2]
By awoo, history, 3 years ago, translation, In English

Hello Codeforces!

On May/13/2022 17:35 (Moscow time) Educational Codeforces Round 128 (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, Vladimir vovuh Petrov, 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

Harbour.Space takes over SWERC by winning gold and silver for the first time in its history and will go to the ICPC World Finals. Congratulations to all of our participants and coaches that made this a reality!

This is a very important moment in Harbour.Space and Codeforces long partnership, with 127 educational rounds being organized and a big Harbour.Space Scholarship Contest held on July 22th. We have selected contest winners (early-morning-dreams, Meijer and amanbol) to form our current teams.

Since its creation, one of Harbour.Spaces’s goals has been to win SWERC and compete at a high level in the ICPC globally. On April 24th, that objective was accomplished when Harbour.Space’s team RAW POTS (read it backwards!) won the gold medal and the overall contest against Southwestern Europe’s top contenders.

Harbour.Space

Team Raw Pots — gold medal:

Maksym Oboznyi (MaksymOboznyi), Marco Meijer (Meijer), and Danil Zashikhin (early-morning-dreams)

Team Kempirqosaq — silver medal:

Temirlan Baibolov (bthero), Dinmukhamed Tursynbay (DimmyT), and Amanbol Kanatuly (amanbol), ranked 4th and won a silver medal.

Team Harbour.Backspace — ranked 27th:

Anier Velasco (aniervs), Fadi Younes, and Ekaterina Podruzhko, ranked 27th.

The faculty, current students, alumni, and everyone involved with Harbour.Space would like to congratulate the winners and participants at SWERC 2021-2022 for their wonderful performance and hard work.

As usual, we are always excited to see Codeforces participants as our students here at Harbour.Space. That’s why we encourage you to apply to our latest apprenticeship program in partnership with Hansgrohe, as a Kotlin Developer until May 31st, 2022.

Apply | Scholarship

Harbour.Space University Team

UPD: Editorial is out

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

Comments Comments (151)
| Write comment?
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Wish i will solve problem ABCDE and go orange this time!!!

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +47 Vote: I do not like it

nvm

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

good luck to every one :)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't wait to get back the rate I lost in #789!!!ψ(｀∇´)ψ

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

rotavirus face reveal?

→ Reply
»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

All the best everyone!!! Hoping that everyone will get a positive delta

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

Do your best guys and never give up

GOOD LUCK!

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

Wishing everyone luck to overcome the curse of Friday the 13th.

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

I Hope to solve A B C D and become specialist.

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

I didn't participate contest for a long time, very happy to be back and good luck to everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can u provide the score distribution?

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

    Ig there is no score distribution in educational rounds.

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

    Problems are not weighted in educational rounds.

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

Wish I will go outside the infinite loop between Newbie and Pupil :)
Who is like me !!

→ Reply
»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

How many questions I need to solve to be a specialist if my current rating is 1207 ? Can Somebody tell me ?

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

Congrats to the gold and silver medalists!

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

Is it allowed to browse the internet during the contest?

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

    Yes

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

    Yea, you can even copy the exact code from some public websites and it won't be counted for plagiarism. Copying from private websites or from friends is counted for plagiarism

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

Happy to see Kazakh names on the leaderboard! Good luck everyone!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

Sorry if this is harsh, but this was a very poorly prepared round. If you need to make three contest announcements on problem C, change the output format of problem F after half the contest, massively misjudge the difficulty of E, and have major wording issues on problem D, then there hasn't been enough proofreading. That's 4/6 problems in a 6 problem contest having serious issues.

Clarity issues with C:

Clearly this wasn't explained well enough in the statement, because we needed (or at least we got) 3 contest announcement to clear it up. It's a bit annoying to have to click through a bunch of dialogs during contest about announcements.

Wording issue with D:

The statement says "what is the maximum possible number of different integer points of the line your dog could have visited". This is equivalent to asking "how many points X exist such that there is some way of replacing 0s with integers -K to K such that your dog would be at point X at some time and eventually return to point 0?". That's not what the problem writers mean though, they should say "You know your dog chooses her path in such a way to visit the most number of spaces. How many spaces did she visit?"

Difficulty estimation issue with E:

E has way more solves than D; I believe rightly so. I won't spoil anything here since the round is ongoing, but I have no idea what the authors were thinking with this relative difficulty estimate. Either unnecessarily complex solution ideas, or perhaps didn't have nearly enough testers, I guess.

Output format flipped with problem F:

For the first half of contest, problem F told you to print 1 if it was not in the set, or 0 if it was in the set.

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

    agreed. I thought E was quite complex until I see the huge number of people who solved it.

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

    I don't agree about C.I felt all the three announcements made are redundant

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

      But if they were completely redundant (I agree that they were), they shouldn't have been announcements (just clar request answers) because they are mildly annoying to click through for people who can read the statements.

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

        I Agree.

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

          As I already said, these announcements were made to decrease the number of questions.

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

    I do agree on some of these things, like bad output format in F (that's clearly our fault) and difficulty issues with D and E (they should be in reverse order, we overestimated E and underestimated D). However, I don't agree with what you said about C/D.

    Regarding C, I believe the problem statement was absolutely fine. All of the announcements I have sent during the contest either repeat what was said in the statement, or tell something completely obvious. The only reason why I had to send these three announcements is just to cut down on the number of questions on this problem — we were getting too much of them, and a lot from people who clearly haven't read some part of the problem. I actually wanted to send the fourth announcement describing that the cost is the maximum of two values, not the sum of them (even though it is written in bold in the statement, there were lots of people sending their questions where they calculated the cost as the sum of the two values).

    Now, considering D and its statement. I don't think I can argue about the English grammar (where we can use the phrase "could have" and where we cannot, for example) with someone whose native language is English, but I want to ask you a question. If you think that the statement is equivalent to "how many points X exist such that there is some way of replacing 0s with integers 0 to K such that your dog would be at point X at some time and eventually return to point 0?", then what is the meaning of the words "*maximum possible* number of different integer points"? We clearly don't maximize anything in this understanding of the problem, so it makes no sense.

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

      I think you're right under my incorrect interpretation it'd make more sense to say "total possible" than "maximum possible", but also I think that's relatively normal for people to say incorrectly. I think the real issue with the wording is that you're asking for the number of reachable spaces, not the number of spaces reached by the optimal path.

      Unrelatedly, thank you for the "additional constraints" on input rather than saying "It is guaranteed". :)

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

      I would argue that 'cost of removal' is pretty ambiguous in C.

      I myself understood it as a cost of single move — mainly because plural form 'removals' was used in previous sentence.

      But I think that task descriptions were fine.

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

    oh wow, I had completely misinterpreted D just as you said. I was wondering why the problem was so easy and yet had so few solves.

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

Before ending the contest, it's the first time to close it before thinking about problem C. It's a big gap between B and C.

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

    suppose you trim the string to $$$s[i + 1, ..., j]$$$. write out how to describe the two costs with index $$$i, j$$$ and the prefix sum of number of '1' $$$pre[i], pre[j]$$$, then you can find some relationship.

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

    learn how to use binary search. (*)

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

104 minutes by just staring at screen : ( and trying

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't understand D at all!

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

    Let $$$p_i = a_1 + a_2 + \ldots + a_i$$$. Choose some numbers in $$$[-k, k]$$$ for positions with zeros so that $$$p_n = 0$$$ and you need to maximize $$$max(p_i) - min(p_i) + 1$$$.

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

    me too...

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

What was the main idea behind problem C? Was it dp, binary search or some other algorithm?

I kind of got there with dp-greedy approach, but unfortuntely I couldn't figure out which edge cases I was missing.

Will highly appreciate to see some dp approaches, however will not mind to hear other algorithms. Thanks in advance!

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

    I used dp.

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

      Would you mind to run me through your idea briefly?

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

        Define $$$pre[i]$$$ as the number of $$$1$$$ in $$$s[1,...i]$$$. Suppose you trim the string to $$$s[i+1,...,j]$$$. The number of remained $$$0$$$ is $$$(j - i) - (pre[j] - pre[i])$$$. The number of removed $$$1$$$ is $$$pre[N] - (pre[j] - pre[i])$$$. So, if $$$j <= pre[N]$$$, the maximal will always be $$$pre[N] - (pre[j] - pre[0]) = pre[N] - pre[j]$$$. if $$$j > pre[N]$$$, you may choose the minimal of $$$pre[N] - (pre[j] - pre[j - pre[N]])$$$ and $$$min_{i=1, j - pre[N]}{(j - i) - (pre[j] - pre[i])}$$$. Note that $$$min_{1, j - pre[N]}{(j - i) - (pre[j] - pre[i])}$$$ could be calculated by a prefix maximum of $$$i - pre[i]$$$. Iterate all possible $$$j$$$ and get answer.

        Update: as $$$i - pre[i]$$$ is a non-decreasing sequence, the minimal of $$$min_{1, j - pre[N]}{(j - i) - (pre[j] - pre[i])}$$$ happens at $$$j - tot$$$. So the minimum cost for each $$$j$$$ should be $$$pre[N] - pre[j], if j <= pre[N]$$$, or $$$j - pre[j] - (j - pre[N] - pre[j - pre[N]]) if j > pre[N]$$$.

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

          Yeah, thats pretty nice solution. Thank you!

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

          Not sure my idea was same as that of yours but My idea was there exist an optimal solution in which number of zeroes in resulting sub-string equals total number of ones removed (otherwise, we can increase minimum value without altering the result). Now, zero_count in resulting sub-string = total one_count removed => zero_count in resulting sub-string + one_count in resulting sub-string = total one_count removed + one_count in resulting sub-string => length of resulting sub-string = total one_count of initial string. Now I know length of resulting sub-string (i.e, one_count of whole string) and cost (i.e, zero_count in that sub-string), I can just use prefix sum to minimize the cost in one iteration.

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

            What an elegant solution! I would say it's more easy to understand and implement than any other methods. btw, writing equation using latex maybe more easy to read.

            $$$ N_{0\ in\ result\ substring}\ =\ N_{1\ in\ removed\ string}\ \ => \\ N_{0\ in\ result\ substring}\ +N_{1\ in\ result\ substring}\ =\ N_{1\ in\ removed\ string}\ +N_{1\ in\ result\ substring}\ \ => \\ length\ of\ result\ substring\ =\ N_{1\ total} $$$
            → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          in the case of j<=pre[N], why you didn't consider i like pre[N] — (pre[j] — pre[i]) for all values of i and j?

          you took i = 0 and the maximal became pre[N] — (pre[j] — pre[0])

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

            Because $$$pre[i]$$$ is non decreasing.

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

              Can you also tell why you took i = j — pre[N] in second case, I am not getting it?

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

                That’s also because $$$i-pre[i]$$$ is non decreasing.

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

      what was the idea for DP ? I have solved with binary and greedy

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

    I did it using Binary search

    To check if it is possible to achieve this cost
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    A sliding window approach also seems to work. If the cost comes from the undeleted part of the string you delete more characters from the left, otherwise, you choose to delete fewer characters from the right.

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

      Could you explain it a bit more, please?

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

        Sure, I can try at least although I think it sounds way more complicated when I try to explain it than it sounded in my head.

        First of all, I find it easier to think about choosing some substring than choosing how many characters to delete from each side.

        Let's now say we have chosen where the substring should begin and try increasing the length of the substring one character at a time. At first, the cost will come solely from the ones but that number will decrease until the number of zeros will start to matter. Then the cost will start increasing again. This means the optimal cost will be when the amount of zeros and ones is the same.

        Now in the program, we want to find the optimal substring that begins at each character and then chose the optimal cost therefrom. First, we find the optimal substring that begins at the beginning. It is not hard to convince oneself that the optimal substring that begins with the second character will not end earlier that the optimal substring that begins in the beginning. Therefore we don't need to try substrings that begin earlier than the previous substrings.

        To implement this efficiently we can use a classic two-pointer/sliding window strategy. We keep track of where the substring we are currently interested in starts and ends and move the end or the start of the substring by one. All while keeping track of how many zeros and ones there are for the current substring. Each pointer only needs to move the length of the string so the algorithm runs in O(n).

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

          I see the idea, thats a great one!

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

    It can be done with binary search + sliding window(btw isn't sliding window a subset of two pointers?)

    Submission

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

    I used ternary search.157084549 Edit: and then got hacked! Can anyone give me proper implementation of ternary search to find minimum

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

    I solved C by greedy.

    Let $$$Z$$$ be the number of $$$0$$$ in the initial string.

    If we want to remove $$$L$$$ characters, and $$$C$$$ of which are $$$0$$$, then the cost is $$$max(Z - C, L - C)$$$.

    If $$$L < Z$$$ , then $$$max(Z - C, L - C) = Z - C$$$, which means we can delete up to $$$Z$$$ characters and the cost won't get higher during the deletion.

    If $$$L = Z$$$ and we want to delete another character $$$x$$$:

    • $$$x = 0$$$

      The cost will become $$$max(Z - (C + 1), (L + 1) - (C + 1)) = max(Z - C - 1, L - C) = L - C$$$. We get the same cost as that of $$$L = Z$$$.

    • $$$x = 1$$$

      The cost will become $$$max(Z - C, L + 1 - C) = L + 1 - C$$$, which is higher than that of $$$L = Z$$$.

    So the solution is to enumerate all possible deletion that delete exactly $$$Z$$$ characters and the minimum cost should be the answer.

    157091140

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

      Nice idea. I've tested it without storing arrays of prefix/suffix sums: 157096927

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

        I didn't notice that the two arrays were not necessary, thanks!

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

      excellent idea.... Thanx for sharing

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

    I used two pointers and bp. If you have an answer X, then the segment that we don't change can't have more than X zeros. Just do two pointers stuff on that. Total time is $$$O(nlogn)$$$ 157048159

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

    I used binary search the answer

    Assume we want to check whether we can get score of $$$X$$$, then I will try to remove $$$i$$$ number of $$$1$$$s from the front and $$$X-i$$$ number of ones from the back ($$$0 \le i \le cnt_1$$$)

    If there is such $$$i$$$ so that the remaining substring consists with at most $$$X$$$ number of $$$0$$$s, then we can obtain score of $$$X$$$ and try lowering the answer (or increasing it if there's none such substring)

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

      can you please tell me how you concluded that it is a monotonic and continuous function? Like if the answer is valid for x then it is also valid for x+1

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

        Hey, at start you can observe that the actual answer is <= number of 1s in the string (as that's the cost if you decide to remove all characters and make the string empty).

        Now, you set the binary search range [low, hi] to [0, number of 1s]. Now you guaranteed that the hi value corresponds to a valid cost that can be generated.

        Now, let's say there is some cost X between [low, hi] that can be generated by removing some prefix and suffix, reducing the original string to string S'.

        To observe why all values between X and hi are also achievable, you can see that removing first letter from S' will change the cost either to X+1, or X-1 (depending on if it was zero, or one).

        If you repeat that operation again and again, S' will eventually turn into empty string with cost hi. All values between X -> hi will be generated on the way, as each single letter removal increases or decreases the cost by one — no value in between can can be skipped.

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

    greedy O(n) — https://mirror.codeforces.com/contest/1680/submission/157062229 We check every deletion of 1's from left side, while trying to add 1's from right side as much as possible.

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

    I used ternary search.
    Idea is "what is the optimal ans if i keep X 1's in my answer".

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

How To solve C?

I tried greedy + binary search , to find the nearest 0 from left side(using binary search) and the nearest 0 from right side ,whichever is remove in that direction and update the answer, update the corr left most point & right most point values, till first < last.

Can someone tell me where I am wrong with this approach? Thank you.

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

    Code 157056549

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

    I solved with binary search on the score (and a 2 pointer solution where I removed as many 1's as possible from the front, then added them back in 1 by 1 while removing them from the back to verify if a score was possible).

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

    what if both zeros are equally far from both sides :(

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

Who tested C.. the pretests are very strong lmao.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the main observation about C problem is that you need to remove 1's >= 0's

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

    Thats not necessary in my opinion. For example take the string 100110011. Here, for optimum answer(i.e. 2) you remove just one 1 and two 0's (from starting).

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

      it's important for greedy+binary search solution: in your example you can also get acceptable results such as (1001)10011 and (100)11001(1), the answer is the same — 2

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

        Well, I was trying to convey that your observation seems wrong to me through a silly example. Just take the string 100000110011. Here for optimum answer(i.e. 2) we remove one 1 and five 0.

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

          I understand what are you trying to say, but 0's in my statement are the ones which left not removed.

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

    Hello, MrOtter , how this observation is true , can you please explain ? i.e. (no of 1s removed >= no of zeroes left). And why its vice-versa is not true? What's exactly makes the difference ?

    actually, wracking my brain for hours and could not get the observation by seeing others implementation. It will be very helpful if you can explain it clearly.

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

      because to minimize answer you need to remove 0s as most as possible and leave 1s as most as possible. in other words you need to find balance between 1s removed and 0s left to minimize difference between them. how you can do it?
      you can observe that you can remove 0s from left and right for free while there are none of 1s. but when you get to 1s you can consider them as price to get to next 0s. so you need to construct threshold condition where you allow to remove 1s and it can improve answer. that's how can come up with condition "no of 1s removed >= no of zeroes left" because you can always remove 1s while no of 1s removed < no of 0s left (maxOf(1s, 0s) = 0s) and it will not get answer worse so it is worth to try.
      based on this observation you can come up to binary search solution

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

I spent all the last hour working on F,while failing to solve it in time(If only i have ten more minutes).Maybe i need another contest to get orange...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can D be solved in O(n)?

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

Problem F is similar to "Voltage" from JOI Spring Camp 2014: AtCoder oj.uz

→ Reply
»
3 years ago, # |
  Vote: I like it -48 Vote: I do not like it

Before I start the contest and for NO reason I decided to take look at problem C first and I found It Crazy a little bit so I decided to not participate in this contest. I am happy to keep my color and not join this stupid contest.

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

    Coward

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -42 Vote: I do not like it

      If you faced a Lion in your way you will fight against him instead of taking your car and escape not to be a "Coward". Right?

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

        Waiting for right contest, only to get positive delta is being coward.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -24 Vote: I do not like it

          I will have only + delta in my account by this way

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

            Yes, you will, if you keep being coward

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

            Negative delta for a single contest is meaningless.

            Skipping a contest is failing to take advantage of a learning opportunity.

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

        Why would you compare a CF problem to a lion?

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it -9 Vote: I do not like it

      Xinotpyrk And stop making Fake account to participate in the contests I think you are the real Coward here!

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

        Ok

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

        let us see who will get better rank in next contest @Omar_Hafez vs @Xinotpyrk.

        I hope C will not be that difficult so that competition can happen.

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

          Hopeforces

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

          I will WIN. (If problem C was easy for sure :) )

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

            Inshallah

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

              Results of this match: Both players managed to solve problems A and B, but Arun_bro1 beat Omar_Hafez by placing 647 ranks higher and solving problem C, which Omar_Hafez failed to solve. Although Arun_bro1 received quite a few Wrong answers on problem A and B at the beginning, he made a comeback by solving problems B, C, and then finally problem A about 70 minutes after the contest. This definitely gave Omar_Hafez some room to make his own comeback by solving problem C, which may have given him the lead due to his lower penalties.

              Winner of this match: Arun_bro1

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

    can you define coward for me @Omar_Hafez?

    → Reply
»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

This round is really strange. When I was solving B, I literally don't know why I got WA on first two attempts and AC on the third attempt. This is the first time I have this kind of feeling. It took me much longer than expected to solve B, which really brought down my morale. Normally I should be able to solve at least 4 problems and enter top 1000, but this time I only got 2400+ standing with 3 problems solved. This sucks.

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

Can I use the minimum spanning tree to solve E? Just like this question.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How to do E? My idea was to consider every chip as the last remaining chip, then to calculate answer by considering that the chips in the same row will just move towards the selected chip, and chips in the other row would first go towards the cell directly above the selected chip and then in 1 move, move downwards to finally become 1 chip. Am I missing something?

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

    I used 4 status to mark the position of chips in current column. then you can do dp transition.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

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

    Here is my approach: Let's say finally we have the remaining string from s[i...j]. Then answer for this string will be res = max(zero-pref[i-1][0]-suf[j+1][0],pref[i-1][1]+suf[j+1][1]), here I used ternary search as for every i, I need to find optimal j such that this function is minimum and we can see if we traverse j from end towards i value of function will first decrease then increase. So that's how for every i, I found optimal j using ternary search.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way to solve problem C using recursive dynamic programming?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -20 Vote: I do not like it

A < B< c ~ E < D

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C using DP ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It hurts bad when your code gets accepted by just changing l = 1 to l = 0.

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

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

Could anybody tell me why 157030318 got AC,but 157022306 got WA?

I'm totally confused.

╥﹏╥

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

    This test case will fail in your code: 1 5 5 LLLLL LLLLL LLLLL LLLLL LLLLR

    It should be YES but it gives NO. I tested it locally on my pc and it work but on codefoces custom invocation it will fail

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

    When things pass locally but fail online (see comment from Omar_Hafez), the reason is almost always that you are accessing out of bounds memory by mistake. In this case you were accessing elements s[6][6] but your array's dimensions only allowed for indices from 0 to 5. The changing behaviour depends on what is currently held in the memory accessed inadvertently by s[6][6]. Offline its value was 'ok' so you passed; online its value was 'not ok' so you failed.

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

      jimm89 But this code never reaches s[6][6] it will always be lower than 6 because the flag he made will stop reaching this point

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

        Picture link

        It does in custom invocation (see picture). This is something to do with you attempting to read into 's[i] + 1' — it is not behaving as you expect it to.

        If you re-index i and j to 0-based, you will pass. Submission with re-indexing — note that I've even reduced to s[5][5] and it's fine.

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

          C style strings need a terminating null character \0 at the end. By not reserving the buffer for it, you're going against the rules, hence I'd guess that is what causes this unexpected behavior.

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

          In the picture you mention the code will never reach s[6][6] because the flag is 0

          if(flag && s[x][y])

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

            That’s true. But the fact that it is 6 6 is still the reason the answer returns NO.

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Come on, problem E is really so easy that a simple dp can work it out!!! However, I forgot to give my dp a special judge because I combined the dp in three situations into one--Just the simple code "-(maze[1][j]=='*'&&maze[2][j]=='*')". O.M.G. then I've got wa in the contest and luckily got Accepted 5 minutes after the contest was over... Poor I!

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

Hi guys, can any one help me what the second loop is doing, a valid solution for C problem.

void run_case() {
    string S;
    cin >> S;
    int N = int(S.size());
    int zeros = int(count(S.begin(), S.end(), '0'));
    int ones = int(count(S.begin(), S.end(), '1'));
    assert(zeros + ones == N);
    vector<int> prefix(N + 1, 0);
 
    for (int i = 0; i < N; i++)
        prefix[i + 1] = prefix[i] + (S[i] - '0');
 
    int best = min(zeros, ones);
 
    for (int i = 0, j = 0; i < N; i++) {
        while (j < N && j - i - (prefix[j] - prefix[i]) < ones - (prefix[j] - prefix[i]))
            j++;
 
        best = min(best, max(j - i - (prefix[j] - prefix[i]), ones - (prefix[j] - prefix[i])));
    }
 
    cout << best << '\n';
}
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It finds j such that it is optimal to end up with the segment [i, j] for the given i. As you increase j the number of zeros inside the segment doesn't decrease, while the number of ones outside doesn't increase. You can prove that for larger i's, larger j's will be optimal.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Although the problem was a bit difficult, just because you missed some observations does not mean that problem was terrible. Every Problem has unique observation and implementation... Today i completely misunderstood D('_')

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Idea for C: If you select the segment l,r you could find the score on that segment. Now you can search for each i, pretend that is r. Now you answer two questions for the segment ending at ith. 1. What's the best case such that at least as many deleted 1s as 0 on that segment? 2. What's the best case such that at least as many 0s as the 1s deleted?

For both cases, we could find out the number of 1s deleted from the end until ith easily. Now whats the best l for each case? First case favors l being as close to 0th index as much as possible, second case favor l as close to ith as possible. You can binary search this, if you had a prefix sum count for 1s and 0s.

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

How the answer of this testcase is 9 (Problem E):
1
6
* * * . * *
* . * * * *
I don't know why testcase is not being printed properly, maybe asterisk sign is doing something. If the test case is still not clear please go this ideone link : https://ideone.com/eJEMfj

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

Congrats early-morning-dreams!

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

Congrats antOntrygubX_y

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, does anyone have some ideas for the problem D?

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

    Let the original sum of array values be $$$sum$$$. If $$$\lceil \dfrac{abs(sum)}{k}\rceil$$$ is greater than the count of $$$i$$$ where $$$arr[i]=0$$$, $$$ans=-1$$$.

    Otherwise, the maximum visited points will be the distance moved from the smallest point to the largest point, which is range sum in the final array.

    We can iterate on all the $$$N^2$$$ ranges. At each range let's see the largest and smallest sums $$$sum_1$$$ and $$$sum_2$$$ we can have by considering the count of $$$i$$$ where $$$arr[i]=0$$$ at that range, then update $$$ans$$$ by $$$max(ans, abs(sum_1)+1)$$$ and $$$max(ans, abs(sum_2)+1)$$$ (the $$$+1$$$ is to account for the point at the range start).

    Submission

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why but I got different answers for same code 1680C in my compiler and in codeforces. Is this a glitch or what?

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

    It is called undefined behavior (sometimes because you want to access something you can't access like outside the array).

    In your code lines 220 and 244 you have to flip the conditions because what you write first got executed first.

    The second thing is that you don't give the variable n a value. I think you forgot to write "n = s.size();" (I think two times needed).

    you can check my last submission on the problem, I got WA on test 2 after fixing these issues in your code.

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

    It happens some time.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used ternary search in prob C but I didn't know that it doesn't work if the function is not "strictly" increasing + decreasing. But my solution got accepted due to weak pretests.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

I was running my code on ideone in default setting and someone copied my code and I was not aware about that.I don't have idea that someone can see my solution on ide during contest, that's why i recieved a msg that your solution is collided with others. I will take care from next time. I have not used any unfair means while giving the contest.I have solved all the problems by myself. Please restore my submissions and give me ratings for the contest. I will stop using ideone from now. I promise it won't happen again.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial late op

→ Reply
»
3 years 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