By awoo, history, 2 years ago, translation, In English

Hello Codeforces!

On Oct/17/2022 17:35 (Moscow time) Educational Codeforces Round 137 (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 Ivan BledDest Androsov, Alex fcspartakm Frolov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

The round is based on the Qualification stage of the Southern and Volga Russian Regional Contest. Thus, we kindly ask its participants to avoid participating in the round.

Good luck to all the participants!

UPD: Editorial is out

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

| Write comment?
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

New Edu Contest writer! Wow.

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

3 consecutive days of contests!

»
2 years ago, # |
  Vote: I like it +72 Vote: I do not like it

3 days in a row of contests! The professor will miss me at university (^-^)

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

    u shold pay attention in learn learn rather than code code

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -39 Vote: I do not like it

      That's why you're blue.

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

        As if you are in different color.

        (Btw you forgot to tag your “wonderful” name)

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

        Marinush I think you should stop learning to code at all and focus on learning how not to be a rude kid !

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

          I think you should stop and focus on learning how not to be.

          In taraclia we say: sa mor io frate

          Marian Stefan, IOI2023

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

      I try to learn more and code what I understand but still can't think with which I learned to solve problems. I don't know if I learn in wrong way or what?

»
2 years ago, # |
  Vote: I like it -124 Vote: I do not like it

Could you please give me some upvotes to make up for my poor contributions?

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Does it mean this problem set has been used in the regional contest offline already? How to avoid the problem leaking?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    Someone Plz explain, does it mean that Southern and Volga Regional contestants will be in Top of Standings (As they have Seen and Know all of the problems) ? How are problem setters sure that there is no Editorial of the problems in Internet already ?

    These 2 things are pretty enough to Ruin the competition for everyone.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it -7 Vote: I do not like it

      Last round (the Div.3), a cheater (seemingly teaming with multiple people) solved 3 problems in 5 minutes, and then immediately got eradicated out of standings. Likewise, I believe a large amount of the concerned situation could be prevented too.

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

        He submitted last 3 problems in 5 minutes, because he had no time to change them properly enough. I bet if he had 10 more minutes, he wouldn’t get caught. This does not explain why people can’t cheat and spread the solutions in this “contest”.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          I guess its's a bit late to answer, but I meant 5 minutes in the beginning rather than at the end. And this should seem closer to a case of an early leak, so I said it's preventable.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Why it is said to avoid the contest, do they mean it seriously or it's a joke. Or the participants of Volga Russian Regional Contest are said to avoid the contest. Please clear anybody if you understand.

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

    The participants of Volga Russian Regional Contest are said to avoid the contest.

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Everytime while participating in Educational rounds !

»
2 years ago, # |
Rev. 2   Vote: I like it +87 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it -89 Vote: I do not like it

Please ban my account and delete this comment, kthxbye :)

don't click the link!! https://noodlemagazine.com/watch/-203295556_456239121

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

Another edu!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If i hack another solution is there a penalty for that?

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

    All solutions are going to be retested with test data from successful hacks. So a successful hack influences the final standings by kicking off some solutions.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Codeforces at It's best mood. Three back to back contest.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

M let's go

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I will solve 2-3 problems really quickly to become PUPIL

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

No testers, No free upvotes!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to reach expert.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Speedforces

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why there is no impact in the standings even after unchecking the show unofficial box??

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

Huge gap between D and E, but nice round with classical C and good D. Thanks!

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I'm surprised that suddenly a lot of people started to solve D as if it was a count down for them to go

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

    Why there is no impact in the standings even after unchecking the show unofficial box?? Is this with me only or with you also??

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

      It may be useful after system test. Useless now.

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

      I don't know why they do this in Educational Rounds. You can choose to see only div2 contestants after the round or system testing I don't remember

»
2 years ago, # |
  Vote: I like it -20 Vote: I do not like it

For C, no lid can be moved more than once. But the sample doesn't show that.

F seems easier than it's supposed to be.

Interesting E.

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

    It's written in the problem statement that you can't move the lid more than once

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      Yes. But I tried to solve quickly(to get back to Master)and missed it.

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

      You Solved D! Nice.

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

        yeah.. hint: you just need to claim that there won't be a lot of strings to check (maybe at most 100) since there is an equal probability of 0 and 1 at an index (what is the probability of getting a continuous substring of 1's?). If you prove (or claim) this and make some other simpler observations, you will solve it.

        btw don't worry, I am not really a newbie

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

          actually, checking only for 10 strings does the job

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

    if it was possible to move more than once, the task turns into output the sum of the top k elements, this should have alerted you

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

      Well you can only move it in one direction

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

        Yes, you're right, I'm sorry. It's just that I read the condition wrong at first (I thought it was possible to move in both directions) and spent an extra half hour

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

    It would have been nice If they mentioned in bold For C, no lid can be moved more than once.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve d?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    First, identify the leftmost 1. The suffix from here has the longest bit length (excluding leading 0s) you can get, so this suffix should be your first substring (impossible to reach this bit length with any shorter substring).

    Now, identify the first non-leading 0. Making this 0 into a 1 will always be better than any alternative where this 0 remains as a 0. But to make this into a 1, we need the second substring to start sometime before this 0 (otherwise, it would be too short to reach this 0). Therefore, the second substring must begin sometime between the first 1 and the first non-leading 0, and its length should be exactly enough that the first 1 in the second substring covers the first 0 of the first substring.

    We can try every possible choice for the second substring, and pick the one with the largest result. The worst-case runtime is $$$O(n^2)$$$, BUT the problem states that the strings are generated randomly, so the expected number of 1s before the first non-leading 0 is in $$$O(1)$$$, so we're not likely to get a huge number of 1s before the first non-leading 0, leading to $$$O(n)$$$ expected runtime overall.

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

    Video Solution for Problem D and Problem C.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round!!!

Can you tell me how to solve D?

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

    Brute force solution works because of the given probability condition.

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

      Can you show me some hint?

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

        Your main concern would be, what if there are O(n) consecutive elements, which is not plausible since it is randomly generated datas.

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

        There is fixed a $$$s_1$$$ which maximize the value and if you know then, there is only few choices for $$$s_2$$$ to maximize the value and you can brute force over all $$$s_2$$$ and see the best answer.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does E requires some data structure or topic or is it ad-hoc?

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

    I used a lazy propagation in segment tree

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

    Sorry I thought you are saying F as it mentioned about segment tree with lazy propagation. For F, You could do it with some observations, by considering the operations done on last set to the first set.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +27 Vote: I do not like it

    Dynamic programming of the form $$$dp_x$$$ — the minimum amount of time required to deal exactly $$$x$$$ damage to the enemy so that the last shot was a double one (i. e. both lasers have just fired).

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Did anyone else also thought that the lid can be moved more than once in Problem C :")

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

    I did. And this mistake will cost me a massive loss of rating points.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

i do not know what is the wrong with me i spend around 3 months studying and practicing and still newpi .can you tell me what should i do

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

    i guess the problem is u have solved very less problems of higher rating (>=1200).

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

      What about me Plz suggest something for me too.

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

        u have done some problems of higher rating but still less.

        Try this

        If u have any doubts then do let me know.:)

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

          Which red coder u suggest have best implementation

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

            I follow jinagly and utkarsh gupta,but others are good as well.

            It completely depends on you,like if u can understand their code then it is goood for u.

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

              Utkarsh Gupta is not active these days .And Jiangly some times give and some times not when Jiangly does not give the contest then whom I have to follow. And also a one more query is that While Problem C is of some times 1600 /1700/1800 they are now out of my reach still I have to try them or not

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

                see until u reach 1900 most of the problems just need basic dsa like stacks,queue,dfs and etc.somtimes segment tree.(if u r not good in theese then read it from usaco guide)

                So if u r feeeling that problem c is out of reach just solve it by reading editorial or watching video editorials.(but u should solve it after every contest).

                It is not that u only need to follow jiangly or ug u just need to see one or two good implementations of the problem it may be anyone.:)

                For ug implementations
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    just keep trying, somedays you will be pupil, maybe expert, cm, master,.. just keep trying.

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

    Don't take it serious man. Just practice as much as you can and try to solve harder problems. Like if you want to reach pupil, solve problems with difficulty from 1300-1600. I have been newbie for 11 months but never left hope. Be courageous. Select some handles and while the contest, try to beat them. You will improve :) .

    Best of luck,

    Daniyal.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas for D?

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

    One of subarrays is of course all array without leading zeroes. So check as second subarray only subarrays that have length of nfirst 0 index after first 1. This don't give tle because that length can't be < n — 60 (chance is too small).

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

    1) One of strings (s1) should be longest started with 1. It is unique and starting with the first 1 in the string

    2) You want to cover zeroes in s1 from left to right with 1 in s2. It doesn't make sense to have leading zeros in s2. So we even know its length — it should start with 1 and this 1 should cover the first 0 in s1. Random guarantees a rapid decrease in the number of best candidates when processing more and more zeros. If some of them can cover another 0 — we leave only these as candidates and move on

»
2 years ago, # |
  Vote: I like it +22 Vote: I do not like it

How to solve problem F?

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

    Solution for F:

    First,use sweep line.Enumerate $$$x=0,1,...,3*10^5$$$,and record current segment set containing $$$x$$$.

    Now let's calculate the number of operation schemes so that after operations,the segment set contain $$$x$$$.

    ($$$i.e.$$$ contribution of $$$x$$$)

    Define clear operation $$$op_i S_{i+1}$$$ as:

    • $$$op_i==∪$$$ and $$$S_{i+1}$$$ contain $$$x$$$,or

    • $$$op_i==∩$$$ and $$$S_{i+1}$$$ not contain $$$x$$$.

    Consider the last clear operation $$$op_i$$$,

    for $$$op_1,...,op_{i-1}$$$,which do not affect the results,there're $$$3^{i-1}$$$ schemes.

    for $$$op_{i+1},...,op_{n-1}$$$(contain $$$k=(n-1)-(i+1)+1$$$ number of operations),

    • if there is $$$S_j(i+2 \leq j \leq n)$$$ which contains $$$x$$$,there're valid $$$2^{k-1}$$$ schemes in total.

    • if there is not $$$S_j(i+2 \leq j \leq n)$$$ which contains $$$x$$$,there're valid $$$2^k$$$ schemes in total.

    The total number is $$$3^{i-1}*2^{k-1}$$$ or $$$3^{i-1}*2^k$$$.

    Enumerating the last clear operation $$$op_i$$$ costs $$$O(n^2)$$$.But we can optimize it using prefix sum trick,which costs $$$O(n)$$$.

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

    There are two subproblems to solve here.

    First, for each coordinate x determine which segments it belongs to. This is classic sweepline: loop over x, at x=l[i] turn on S[i], and x=r[i]+1 turn off S[i], then process x. Sort l[i], r[i]'s together with bits of information what to do as you encounter them, and iterate over this sorted list together with x.

    The second problem then is: given a fixed coordinate x and bitmask S from previous step (indicating which segments contain x), calculate number of ways to put binary operators between S[0], S[1], ... S[n-1] so that the whole expression evaluates to 1. The final answer is the sum of this count for all x.

    One obvious way to calculate that is with dp, maintain dp[pos][result] = number of ways to get 'result' after choosing operators and evaluating the expression up to S[pos]. It's a bit too slow due to constraints on n, but observe that dp[pos] (as a vector of 2 elements) depends only linearly on dp[pos-1] and S[pos], so you can actually express it as a matrix multiplication: dp[pos] = dp[pos-1] * <some matrix>, where there's one matrix M0 for S[i]=0 and another M1 for S[i]=1. You can calculate these transition matrices by hand or with a bit of code. The whole dp then is a product of matrices: initial state [0,1] or [1,0] depending on S[0], multiplied by M[S[1]] * ... * M[S[n-1]]. You can use segment tree to efficiently evaluate it and support updating matrixes in the middle of it, as S[i]'s are turned on and off during your sweepline.

    Actually, you probably don't even need matrices as this comment suggests, just focus on dp[pos][1] counts I guess. But it's a neat trick in general to know that if your dp transitions are linear, then you can speed it up by thinking of it as a matrix multiplication. For example, closed form derivation for fibonacci numbers starts from such matrix multiplication reformulation.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

C: misread (I thought move can be arbitrary no of times and solved the hard version)
D: Also misread XOR instead of OR. In the last 5 min, were understood the mistake and then WA on 40 while 40 was the last case mentioned.

A worst contest -_-

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

    Actually the version where you can move the lid multiple number of times is at least more classic than the current version (I also think it is easier but that's subjective)

    In that other version you just insert elements from left to right in a priority queue and for each $$$1$$$ you extract the current maximum and add it.

    However in the current version, you need to look for every substring of the form $$$011 \ldots 110$$$ and then take everything except the last element and the minimum of the other ones.

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

    Agree ._.

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

For question D I keep failing test 40.

Idea is divide string into blocks of consecutive 1s and 0s. We know that one of the answer string would be the entire input string, and the other is the entire input string, and remove some of the number in the back to shift the 1s rightward.

Now we just calculate how many shift we should do. We will prioritize blocks of 10s that come first. at each block we can see the max remove we can do left and finally construct how many shift we did.

Dunno why i got test 40 wrong.

https://codeforces.net/contest/1743/submission/176780050

EDIT: nvm found the issue

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really A and B are suitable for edu round ? why are they wasting peoples time ? They can be kept in div4

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    It's important to always have some problems that are very easy to solve. It's not a div1 contest with limitations on user's lowest rating, everyone should be able to solve at least 1 problem. And also, for me, C was easier than A or B and took less time because I'm an idiot and tried using combinatorics in A instead of bruteforce ^D

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

      What are you talking about, A was way way easier when solved through combinatorics. Look at my O(1) solution: https://codeforces.net/contest/1743/submission/176712399

      Only basic high-school level pnc is used here.

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 4   Vote: I like it -10 Vote: I do not like it

        I mean, idea of A is obvious, just wasted some time to remember something from combinatorics(Eben though was faster to write bruteforce without thinking), While C was straightforward for me and took 5 min^D.

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

          I saw your submission for C, and I just want to say, please don't look at my submission for C (took me an hour xD)

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

    A is supposed to be easy, even in Div2. If it's not too easy, many participants might quit if they don't solve it quickly, which can really skew over the ratings of those who participated, as well as the problem ratings. Please do not encourage problemsetters to make Div2A too hard.

    I do agree that B is a bit easy for its position though.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?
Tried brute-forcing (for all [i,j], where i is the number of shots taken by the gun with the greater reload time and j being the number of times the other laser was fired at the same time (in coordination to save s points), plus any extra shots, if required).
Also considered the bonus free shots I could possibly get in the waiting time between coordinated shots.
I am assuming the coordinated shots could have a more optimal arrangement than the one I was going with.
My WA 5 Solution.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/contest/1743/submission/176779463 Can anyone show me a test case where my code not works ``_?

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

[Deleted]

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

    Hint : How to compute answer if string is 011111110?

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

FTL is a very nice game that exists in the real world

PLAY IT

upd:it's not expensive

»
2 years ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

I tried to solve Problem C by BFS, ending with memory limit exceeded, which confused me a lot. Is it because there are too many staus to store in queue and set ?

I think I have solved the Problem D, however, it's always WA at the test 11 and I can't find any bugs of my code.

In all, I think I can do better in this edu. :(

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

    Use spoilers for code.
    Your comment is literally taking up 30% of the blog's scroll-space.

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

    For Problem D, your mistake was in considering the left shift. A left shift does not form a valid substring. For example, consider the following test-case:

    10
    1000011111
    

    The answer should simply be 1100011111, where the second substring is the prefix without the last character (so it's equivalent to a right shift). But your code answers 1111111111, because it assumes the 1s on the right can be left-shifted to cover the 0s on the left, but there's no way to actually pick a valid substring that would cover all the 0s.

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Is it intended in problem D, that you get penalty for wrong answer on test 2 and 3, but no penalty for wrong answer on test 1, even though they are all examples?

For example Vercingetorix had "wrong answer on test 1" twice, but got no penalty. I had "wrong answer on test 3" and got a penalty.

»
2 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Meaningless problem D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please share their thought process for easy permutation problems like A? I never bothered to learn because a pattern is usually observable but I was wondering the correct 'math' way to figure it out.

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

    Each password is of the form XXYY. The number of ways to generate permutations of this is: 4! / (2! * 2!) = 6. Now, there are 10 numbers in your hand [0 — 9] and some are excluded. So the remaining numbers left are 10 — n. Let's call that size K. You need to pick 2 numbers from these remaining K numbers. The number of ways to do that is KC2 = K*(K-1)/2.

    Therefore, your answer will be KC2 * 6 [Choosing 2 numbers from the available set, and generating permutations of them]

»
2 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Nice contest! D was the best problem ever! So original!

»
2 years ago, # |
  Vote: I like it +39 Vote: I do not like it

f**k Problem D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how tf there are so many AC on D? It's not that easy imo.

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

I just looked at D after not being able to participate due to other schedules.

now what the fuck is this

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

    All the non-example tests are generated randomly,so it is nearly impossible to let your code get wrong answer in 40 test cases.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -33 Vote: I do not like it

      Well, I thought "weak pretests" was a funny joke. Turns out it could be even funnier

      It is time for weak systests with hacks prohibited.

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

        Tests are not weak, they are just random. These are different things

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

    Could you please explain why checking only first 100 shifts work? Is it because getting the first 100 characters as 0's is not probable so we always get the best answer in the first 100 shifts?

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

      probably because it is so unlikely to get a very long substring of zeroes.

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

My approach for C:

Let the given binary string be $$$s$$$.

If for current $$$i ( i \neq 0 )$$$ . If $$$s[i] = 0$$$ just continue.

Now if $$$s[i] = 1$$$ If $$$a[i-1] \ge a[i]$$$ then we swap ( $$$s[i-1] , s[i]$$$ )

But if $$$a[i-1] < a[i]$$$ and $$$s[i+1] = 1$$$ (if $$$i < n-1$$$) then check if $$$a[i-1] \ge a[i+1]$$$

Because it will result in an overall positive gain which is equal to $$$a[i-1]-a[i+1]$$$.

If it is then swap ( $$$s[i-1] , s[i+1]$$$ ) (what's happening first lid goes from $$$i \rightarrow i-1$$$ then from $$$ i+1 \rightarrow i$$$ ) else don't swap.

I am not getting where I am actually going wrong.

Submission Link: 176741104

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

    You are only half right. Notice in your third condition, you explore a a different option.

    Take example the string 0111. Your code considers, 011, 101, and you notice that 110, is also possible (swapping the first and third element). However, take a look at this string: 0111111. Your code will only consider, 1011111 and 1101111. However, these are also possible: 1110111, 1111011, 1111101, and 1111110. Basically, when you have one zero followed by n 1s, you can swap any of the 1s with the 0. But you only consider the first 2 1s.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

c was a dp problem still 7000+ submission . cheating is ruining codeforces.it seems like all the cheaters came here from codechef

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

    It could be done by greedy tho. Just by considering continuous segments of 1's. But dp solution shouldn't be really complicated in this case.

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

    The problem has a greedy solution too. It seems that dp solutions are getting hacked now (Or Only Memoization one) ;)

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

    I did C purely through greedy

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think if problem D was xor instead of or it will be more "Educational". Cause it will be a really nice application of using KMP.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? My idea is: Divide string into blocks of consecutive 1s and 0s. We know that one of the answer string would be the entire input string, and the other is the entire input string, and remove some of the number in the back to shift the 1s rightward.

But my sub failed test 40 so it's wrong. Why is this problem tagged probabilties?

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

    The solution highly relies on randomness.

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem C.Why my submission got TLE on test 4.my submission —->176765114.Thx for your help .I think my solution is O(n),but when n is equal to 200000,I got TLE.

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

So many people have used the same code surprisingly for problem C. Agreed it was pretty easy, but so many submissions is surprising to see. Most of them have similar logics, some of them changed their entire code from the previous incorrect attempts in a matter of minutes.

Submissions: 176764109, 176765007, 176759508, 176765416, 176764960 and so many more. MikeMirzayanov please look into this excessive plagiarism on problem C, and do the needful.

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

    Do look into this and conduct a plag test, as there are hundreds of submissions with the exact same code, just with the variables changed. Removing 100s of such users from the leaderboard will be very good, especially for those with ranks>5000. Kindly look into this MikeMirzayanov

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Wow problem D trolled me good this time. Bc test is randomly generated you won't get more some constant consecutive 1s or 0s.

This is totally BS, this problem should be in a trolling contest.

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

    I want to cry. I would have never thought to extract that conclusion out of that detail. Everything bold is bold for a reason.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

there is a huge gap between c and d that you know your contest ended after reading it and it was a matter of speed :(

»
2 years ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

Did not liked that problem set since it is observation based like other div2/div3. Edu round where and should be mostly implementation problems. Why else Edu rounds exist?

»
2 years ago, # |
  Vote: I like it -26 Vote: I do not like it

PLEASE ANYBODY SHOW ME MY ERROR

#include<iostream>
#include<vector>
#include<numeric>
#include<bits/stdc++.h>

#define ll long long
#define l long

using namespace std;

void findmax(set<string> &res, ll arr[], ll n, ll &ans){
    for (auto it: res)
    {
        ll res = 0;
        for (ll i = 0; i < it.length(); i++)
        {
            if(it[i] == '1'){
                res += arr[i];
            }
        }
        ans = max(res, ans);
    }
    
}

void findall(string s, ll n, ll ind, set<string> &res, bool &t){
    if(ind == n){
        res.insert(s);
        return;
    }

    for (ll i = ind; i < n-1; i++)
    {
        if(s[i] == '0' && s[i+1] == '1'){
            t = true;
            findall(s, n, i+2, res, t);
            swap(s[i], s[i+1]);
            findall(s, n, i+1, res, t);
        }
    }
    res.insert(s);
}

void getSolution(){
    ll n;
    cin>>n;
    string s;
    cin>>s;
    ll arr[n];
    for (ll i = 0; i < n; i++)
    {
        cin>>arr[i];
    }
    set<string> res;
    bool t = false;
    findall(s, n, 0, res, t);
    ll ans = INT_MIN;
    findmax(res, arr, n, ans);
    if(t == false){
        cout<<"0"<<endl;
    }else{
        cout<<ans<<endl;

    }
}

int main() {
	// your code goes here
	int t;

	cin>>t;
	while(t--){
	        getSolution();
	}
	return 0;
}
  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Try eliminating all ones that are not last in the sequence of ones after zeros. Then you shall see how to solve this in O(n). For example

    10001111110110 = 10001010 (lits) 12221234342322 = 12224222 (mags)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A?

Why does this work: std::cout << (10 - n) * (9 - n) * 3 << "\n";

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

    There are 10 numbers b/w 0-9, you are given n numbers, remaining 10-n numbers you have to pair.
    So, (10-n)*(10-n-1)/2 are the number of pairs. Then, multiply by 6 because 6 permutations.
    The above is just the simplified version of this

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

    Basically, it's just the same as kC2*6, 6 is the number of permutations when all the conditions are satisfied according to the question. Where k is (10-n), so, k*(k-1) is eventually (10-n)*(9-n) which explains the statement.

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

    Same as my submission

»
2 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Where can I report cheaters at codeforces?
For now I will leave it here, but if there is better place please let me know.
OrazB and OrazBeg Signed almost the same code for A — Password Problem.
Except that OrazBeg's answer had one difference.
If amount of testcases was 2 or 200 then it will print out trash. So it was certainly just something to pass system tests and not pass hacking tests.
OrazBeg's Answer
OrazB's Answer

Accusation relies on
- similar name
- Code is the same if we delete fragment with amount of testcases
- OrazBeg signed up 10 codes that differ only in newline characters just for other people to hack it.
- OrazB of course hacked OrazBeg 6 times.

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

    Apologies Huehuehue277353

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

      Actually, alter account is also a violation of the rule. But I don’t think you have a bad motive. Anyway, please keep this in mind.

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

    Hacks are unrated in edu rounds

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

      Bro, he is gaining 0 WA. Testing solution with alt account then submitting with main and hack alt in hacking phase to avoid plag.

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

        These all seem to be hacked practice submissions after the contest. Is anyone actually using such main/alt trick in the real contest to dodge WA?

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        not really because he first submitted on normal account and 5 minutes later on his alt

        edit. i was referring to techiehere but ssvb is right. i guess it was not even during the contest

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

          I see, I am dumb. But creating alt is violating the rules too.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D I am unable to understand how we can have output 11111 if we have 10110 as input, I am unable to find a substring which could give this or maybe I am to dumb to understand this :(

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

    10110 1011 11111

    We are doing the OR of the binary substrings so we start from right to left

»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Great D

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to D?

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Is there an $$$O(n)$$$ solution for D? One that doesn't utilise the randomness of the test cases

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

    i feel like using bitsets can pass the $$$O(n^2/w)$$$ (cuz TL is 4 secs). But u'll need to implement ur own comparison that is also avx fast.

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

    Actually solution that uses randomness is also expected O(n), because expectation value of number of process is constant complexity.

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

      Why is it that when I always comment and scroll down, what I write is already written?

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain to me the complexity analysis of D? I think the worst case will be when the first "10" we encounter is at n/2 (n is 1e6 for 20 cases). Now in this case we will have our loop running for n/2 * n/2 which will be 20*(1e12)/4. I thought C++ could only work up till 1e10 in overall complexity. So how is this working?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    The worst case will never happen.

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

      what does that mean?

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

        It has extremely low chances to happen. Most likely, it will never happen.

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

          Oh...this was the first question for me where the test cases were random. 1/(2^1e6) chances that someone got the case that I mentioned xD

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

    This approach does have $$$O(n^2)$$$ worst-case runtime. However, the problem explicitly states (in bold, too) that the tests are generated randomly. Therefore, it is extremely unlikely that the first "10" will be so late. The expected runtime is in $$$O(n)$$$, and the chances of being unlucky enough to get a bad input that TLEs is extremely low and likely has not happened to anyone.

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

Problem C wasted my 1 hour as i was shifting 1 left any number of times but we are allowed to shift it left only once.

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

    Similar case here; I thought going to (i+1) was also possible :p

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be any system test for problem D? It says that there is only 40 test for this problem but I am not sure that's why I am asking right now.

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

So cool E and F!

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

    Any ideas for these? Would like to hear some hints

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      For F you can do it by calculating the probability that ith point is in the final set.

      XOR sets x -> (1-x)
      OR sets x -> 1
      AND sets x -> x in the range and x -> 0 out of the range

      So each operation does x -> 1/3(1-x + x + 1) = 2/3 in the range and x -> 2x/3 out of the range. This can be managed by segment tree. Final answer = sum of probabilities multipltied by 3^(n-1)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does 176804514 this solution pass and 176772722 this solution TLE. Time complexities seem to be same to me. Please help :(

»
2 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Are there anyone think the problem B might be too easy for the contest div 2?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve D if the randomness condition is removed?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Perhaps with hashing/KMP, or maybe with a bitset ($$$O(n^2)$$$, but a small constant)

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

    Of course you can with some suffix structure.

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

    Any code that proves idea?

»
2 years ago, # |
  Vote: I like it -10 Vote: I do not like it

In problem B Statement, it is given that "For example, the value of [2,1,4,3] is 3 since the subsegments [2,1], [1] and [2,1,4,3] are permutations."

But this is incorrect as for N = 4, the permutatation [3,1,4,2] gives minimum possible value as 2 instead of 3.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It said nowhere that $$$[2,1,4,3]$$$ is the answer :|

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

Will the DP solution of C fail(FT) as many of the DP solutions got (Hacked)TLE?

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

    No it won't. Prolly all the solutions that got hacked were recursive-memoized and not iterative.

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

      I think I saw a few iterative solutions also that got hacked, still was unable to understand why it got TLE.

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

      I think many of them were doing memset(dp,-1,sizeof(dp) in the solve function which was causing TLE.

»
2 years ago, # |
  Vote: I like it -12 Vote: I do not like it

MY CODE IS GIVING THE CORRECT ANSWER IN MY IDE. BUT THE SAME TEST CASE IS GIVING WRONG ANSWER WHILE SUBMITTING. PLEASE HELP ME OUT.

https://codeforces.net/contest/1743/submission/176773214

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D...... I am getting stuck in it

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

    Just note that all the data is random, so you can just search for the s2 and find the max answer as this process is thought to be around O(logN)

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

      Can you please elaborate the steps for finding string S2

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        Given string $$$S$$$ of length $$$n$$$. First trim all the left zeros from $$$S$$$ and call this $$$S1$$$. We are trimming the left zeros because they can never be flipped to 1.

        Example: $$$S = 00110010110$$$
        Then $$$\hspace{0.5cm} S1 = 110010110$$$

        Next we will try to flip the remaining 0s in $$$S1$$$ from left most zero to right most zero and we will do this greedily since we need to maximize the binary value of $$$S1$$$.

        Let $$$S2 = 0010110$$$, that is we trim all the $$$1's$$$ before the first $$$0$$$ in $$$S1$$$. If we maximize $$$S2$$$, it would the same as maximizing $$$S1$$$.

        We use 2 pointer approach. Let $$$itr1$$$ be the iterator for $$$S1$$$ and $$$itr2$$$ be the iterator for $$$S2$$$.

        $$$if(S2[itr2] == 1)$$$ then we can't make it $$$0$$$ as we are performing BITWISE OR operator. And this works to our advantage as we want to maximize $$$S2$$$.

        $$$if(S2[itr2] == 0)$$$, then $$$S2[itr2] \hspace{1mm} | \hspace{1mm} (Bitwise OR) \hspace{1mm} S1[itr1] = 0 \hspace{1mm} | \hspace{1mm} S1[itr1] = S1[itr1]$$$. So we set $$$S2[itr2] = S1[itr1]$$$.

        Question: What will be the starting index of $$$itr1?$$$

        Answer: Let $$$idx_0$$$ be the first occurrence of $$$0$$$ in S1. If we take $$$itr1 >= idx_0$$$, then $$$S1[idx_0]$$$ will never become $$$1$$$. So $$$itr1 \hspace{1mm} \epsilon \hspace{1mm} [0, idx_0 - 1]$$$.

        Pseudocode

        Code: 176851036

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

          Using a language with BigInteger support will be very helpful in the process. See my submission (176783281) for a solution using BigInteger on python.

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

            True, the code will become much simpler.

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

          Shimt! Yesterday in contest I taught that this approach will give tle That's why i didn't implemented this

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What does it mean when it says jury has a better answer in the 2nd problem. I faced this problem in past also but solved after manipulating a few steps. I don’t understand what does it mean and how to avoid it in the first place? Thanks in advance!

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

    That simply means that your output is not the optimal solution for the given testcase.

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

Have this contest turned unrated? I was hoping to become master after this contest. :(

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

Waiting for the editorial.

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

Will there be system testing?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

System testing is done now. When the ratings will be updated?

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

    Looks like that's the most frequent comment of yours. I wonder if anyone ever has answered that. I wish anyone could. Soon, I guess.

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

    I too waiting for the same. I guess plagiarism check would be going on.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any one who can tell me the solution of problem D please?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me why test case generated randomly is relatively important? in the problem D

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

    Because the solution is based on the fact that the first group of ones in the string has <= relatively small number. The probability of having, let's say 1000 consecutive ones , is $$$\frac{1}{2^{1000}}$$$, which is extremely small number.

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

    The algorithm is O(x*(n-x)) where x is the length of the suffix such that if we remove that suffix all the element that remains is 1. So having a 100 1's at the end have a very less probability so the algorithm works in 100*n that is acceptable.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I think codeforces have forgot that this round is rated.

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

Thank this round for making me Blue

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

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks for this contest make me green,Can i have an upvote:)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

yeah