Cirno_9baka's blog

Codeforces Round #732 Editorial
By Cirno_9baka, 3 years ago, In English
Tutorial is loading...
solution

Idea: Cirno_9baka

Tutorial is loading...
solution

Idea: AquaMoon

Tutorial is loading...
solution

Idea: Cirno_9baka

Tutorial is loading...
solution

Idea: Cirno_9baka

Tutorial is loading...
solution

Idea: AquaMoon

Tutorial is loading...
solution

Idea: AquaMoon

Tutorial is loading...
solution

Idea: AquaMoon and mejiamejia

Tutorial is loading...
solution

Idea: ODT and box

UPD: Chinese editorial can be found here.

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

Comments Comments (228)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +141 Vote: I do not like it

A concise solution for Div1A/Div2C (in D):

code

Explanation:

  • sort among even positions in the array
  • sort among odd positions in the array
  • check whether the array became sorted
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Can you explain why you do that?

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

      When a person is at position $$$i$$$ and looks right, they will look right at positions $$$\ldots$$$, $$$i - 4$$$, $$$i - 2$$$, $$$i$$$, $$$i + 2$$$, $$$i + 4$$$, $$$\ldots$$$, and will look left at positions of the other parity. It's easy to see when you consider the possibilities: the first swap involving that person will leave them on position $$$i - 1$$$ or $$$i + 1$$$ looking left, and the second swap will take them to position $$$i - 2$$$, $$$i$$$, or $$$i + 2$$$ looking right again.

      As the persons at even positions have to look right at the end, they actually have to permute only among themselves.

      On the other hand, every permutation of the persons at even positions is possible: it takes three swaps to exchange the persons at two adjacent even positions, without changing anything else.

      So, let us place the persons at even positions in the best possible order: the sorted order.

      All the same goes for the persons at odd positions.

      What remains is to check that the whole array is then sorted.

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

        in test 38

        6

        2 1 2 1 2 1

        why answer is "NO"? if we imagine that +x is watching right side, -x left and at start we have

        +2 +1 +2 +1 +2 +1

        then

        -1 -2 -1 -2 -1 -2

        -1 +1 +2 +1 +2 -2

        -1 +1 -1 -2 +2 -2 and now we have sorted array, but we have problem with direction and now we can do more operations

        +1 -1 -1 +2 -2 -2

        +1 +1 +1 +2 +2 +2 and we found answer please can you explain me this or maybe I'm not right about it?

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

          The
          -1 +1 -1 -2 +2 -2
          to
          +1 -1 -1 +2 -2 -2
          step is wrong: -1 +1 transforms to -1 +1, not to +1 -1.

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

      Video Editorials of this contest - Div.2A AquaMoon and Two Arrays
      - Div.2B AquaMoon and Stolen String - Div.2C AquaMoon and Strange Sort

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

    that's an amazing solution orz

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

    Thank you for a very nice and simple explanation. I also stuck in test case no 38

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

    That's exactly how I did it.

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

    Better than Editorials solution! Can you explain why this condition is sufficient? Like why swapping an element with opposite parity element can never result in all elements looking right at the end?

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

      What you're asking for is necessity.
      If you have to exchange two elements with positions of opposite parities, then those two elements need to be swapped an odd number of times in total as you can only swap consecutive ones. Swapping an odd number of times means their direction changes to left.

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

    Sir, can you please explain, what would be the solution to the problem, if in the end, we want everyone to face left?

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

      Swap all pairs of consecutive positions and apply the same logic. Of course, this is not possible when the size of the list is odd.

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

    It can also be done in C++ using valarray slices: 122360101

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

      Nice to see that C++ is catching up!

      Seems like the solution is almost able to sort a stride-2 slice in-place: the valarray class is said to be able (sorry, cplusplus.com link with special characters) to do reference semantics. Is it possible to actually use the library for that, with a bit more knowledge or effort? If not, what is preventing a slice sort, conceptually?

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

        This has been in C++ for 23 years, its the programmers who should catch up, not the language.

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

          Yeah, so actually, that's the feat.
          Anyway... what about these two slices sorted in place, without a copy?

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

            For some reason, slice_array doesn't have begin/end iterators, so it can't be used in sort. I'm not aware of a good reason why this is the case. Anyway it's possible to implement generic strided random access iterators.

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

Consider each position individually. There is always exactly one letter that occurs an odd number of times. So just take them out they are the letters of the stolen string.

If this is how you provide editorials? People referring to the editorial are those who couldn't solve the problem or those who have a lot of questions in their minds. You must elaborate your solutions as much as possible.

If you say, that I must be that smart to figure out what you want to say, thank you very much!
It's not just B, the editorial of problem D gets the same remarks from me.

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

    to be fair this problem is very simple and after getting the main idea it's not hard (the tricky part about the problem is just having the idea to store based on the position)

    The editorial is bad though, it's just that it makes sense to be concise on B specifically

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

      I can understand that you found this problem to be very easy. But it wasn't for me(and I know I am at fault here). But after all, I can expect a clean explanation so that I may know my mistakes(no matter how bad/silly they are I don't care).

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

        I don't think the problem is "very easy" (in fact i skipped that problem when i read it the first time), i just think the hard part was having the initial idea and from that point forward you can figure out what to do without much trouble. I do agree that this editorial is bad (i edited my comment shortly after), im just playing devil's advocate

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

Too hard.

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

The solution for B can be found with XOR since every element except for only one is appeared in even number of time => their XOR will be 0 and the odd one out will be revealed https://codeforces.me/contest/1546/submission/122098007 But the idea of counting in the map is ok though

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

    Thanks for this, I thought about this but didn't know I could have this easy of an implementation if I had gone this way. Personally learned a lot!!

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

    It's an amazing solution!%%%

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

sro lxl orz

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

Atleast provide solutions also with explanation beginners find it difficult to understand

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

In my opinion the problems are too hard for a 2.5h-contest :(

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

For B you can solve for each position the typical problem of finding the missing number, i.e. sum(all) — sum(present) = missing. 122094011

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

Worst editorial

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

Nice pretests for Div2 C )

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

Editorial to B is super weird xddd. "We can find that several operations mean we take out any group and insert it to any position to the chessboard." — what does that even mean xd?

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

    Hey , could you please explain the idea for B in your words. I knew even groups of ones and zeros can always be arranged in all ways possible . I had a hard time convincing myself during the contest that single ones won't affect the solution OR that they are fully determined by the rest of the ordering . Couldn't yet find anything convincing yet.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it 
      Observation 1 :- Length of our answer string will be equal to m.

      Observation 2 :- Think about the Character present at each index of answer string.


          Considering 1 based indexing for simplicity :-

               At index 1 , the character present will be equal to ( all character present at 
         index 1 of given original n strings - all character present at index 1 of given 
         (n-1) strings that chirmo exchanged and reordered).

              At index 2 , the character present will be equal to ( all character present at 
        index 2 of given original n strings - all character present at index 2 of given 
        (n-1) strings that chirmo exchanged and reordered).

      .........
        Continue till index m.

      Here is my submission using the above approach :- [submission:122123590]
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        hey man thanks , but I was actually asking about Div1 B

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

      Transform the original array by scanning the elements from left to right. 0->a 10->b 11->c

      e.g. 00111110011->aaccbac Then we could swap c with any adjacent element. ac=011=110=ca bc=1011=1110=cb So the order of a and b is fixed, and we could insert c into any position.

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

        It's actually the best thing I saw about this problem. Thanks a ton!!

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

        Beautiful :)

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

        How would we transform something like: 11001? 11 becomes c, 0 becomes a, 0 becomes a, and now what about the last 1?

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

          The last single 1 can't be moved, so we could just ignore it.

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

        But why in the solution of authors we need just cntA and cntC, so

        answer is choosing cntC positions from cntA + cntC.

        Why cntB is ignored? Also if i use cntB to calculate the answer, answer becomes bigger than it should.

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

          It didn't ignore cntB. In the original solution, cg is '11', c0 is '0' plus '10', c1 is '10'. So answer is C(cg + c0, c0) = C('11' + '0' + '10', '11')

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

My submission for div2 B got TLE on PyPy and got accepted with exact same code in Python, wtf? I used flush in both as stated in the problem.

TLE solution: https://codeforces.me/contest/1546/submission/122117451

Same code in Python accepted: https://codeforces.me/contest/1546/submission/122117803

I wasted around 1 hour because of this first I implemented the logic with normal arithmetic operations got TLE, then reduced number of loops got TLE, then changed arithmetic operations to bitwise operations as they are faster, using xor to get that odd one out, then too TLE, then I thought of switching from PyPy -> Python and it worked.

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

Great round but the pretests for div 2 C/div 1 A were not so strong.

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

Well... I tried Div1C and Div1D intensely for 2 hours. No programming — just writing on paper. In Div1D I could find the manipulated row, as described in the editorial and then I started choosing 3 consecutive unmanipulated arrays (such arrays always exist since $$$k \ge 7$$$ ) and search for arithmetic progressions/do some bipartite matching or stuff. In Div1C i tried connecting the arrays in a graph (two arrays are connected if they share an equal value) and then looking for subsets of $$$n$$$ arrays with no edge between them. But for both I couldn't find a real solution.

Now I read the editorial and the solutions are so beautiful! Really wonderful Problems.

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

    I hope you enjoy Div1C, because it's quite hard for me to generate the test data of it. Meanwhile, as a tester of Div1D, it cost me 5 hours to think, finally get ispiration to AC. In fact, I suppose it's the best problem of the contest.

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

      Using the ideas from the Editorial (Chosing rows greedy for Div1C and multiplying solutions by 2 if there is no unique greedy choice and sum of squares for Div1D) I was able to solve them both yesterday. Though I'm still thinking about the proof for C and my implementation for D is quite ugly still.

      Oh yes, I guess it's difficult to find meaningful testcases for Div1C. I had problems writing small meaningful testcases on paper to understand the problem.

      I really like both of them!

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

Div2 E and F were too hard, but I have to admit the solution is beautiful. Very clever problemseters!

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

Could someone explain B? I did not understand the editorial that much :c

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

    Add all the occurencies of each letter in each index (both before and after they get jumbled). Let's say we're trying to find which letter is in the stolen string on index i. Because every letter on the non-stolen strings appear twice, the letter on the original stolen string is the only one that appears an odd number of times in that particular index. If you do that to every index you'll get the answer

    My solution is a bit different but i imagine that's what the editorial was trying to say

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

    If the characters 'a','b','c' are at the first position of 3 strings and the given 2 flipped strings have characters b,c at the first position then we know that the string which had character the 'a' in the first place is missing. We can do this for each index.

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

    I took the sum of ASCII values of i'th(1<=i<=m) character of all the original strings and subtracted from it the sum of ASCII values of i'th(1<=i<=m) character of all the new strings.Then just accumulated the character for that value in a string.that's your output.Check my submission for clarity.

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

    A simpler implementation that I used was to just XOR all the ((2*n)-1) strings' characters for each index separately. The final XOR would be the stolen string.

    Since, every character except the ones in the stolen string occur a multiple of two times at their respective indices, the stolen string remains after XOR.

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

    We have to work this out character by character, as given n*m does not exceed 10^5, so we can loop through every character. loop thorough each character [j] in each string [i], Now for all the characters find that character which is not present at the jth index of the scrambled (n-1) lines. do this for every j 0-m, and you'll have a list of characters which are missing.

    Here's how I did it.
Create a m sized vector<int> -- call it vans of size m, initialized with zeroes.
Now for every line in the first n strings [i], loop through each character [j], find it's ascii value and add to vans[j].
Now read the next n-1 strings, loop through each character [j], find it's ascii value and substract that value from vans[j].
vans is now a vector of int storing the ascii values of missing characters.

    Print them out. https://codeforces.me/contest/1546/submission/122215500

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

Maaaan was I not ready for Div 1

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

How to solve problem div2 C, I don't understand the idea in the tutorial

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

    The number of times a number is at an odd position(0 — indexed) in the original array should be equal to the number of times the number is at an odd position in the sorted array.

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

      why is that, can you explain more?

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

        Because we know that if something ends up as right, it has to swap between left and right an even amount of times. So even indicies must end up even and odd must end up odd.

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

          waooo, this is probably the best explanation, thank you so much

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

    Take three consecutive numbers. Suppose it's abc (RRR). Let's apply some operations. abc (RRR) -> bac (LLR) -> bca (LLR) -> cba (RRR). We reversed these three numbers and they're all to the right again. And reversing them just swapped a and c, and their new positions have the same parity as before, it won't change.

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

      is this interpretation your way of reasoning to solve this problem, how do you prove that for n > 3 the same parity is still true

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

        This was indeed my reasoning during the contest. I'm far from giving you a formal proof, I don't know how to show there's no way to change the parity doing other operations, but I just decided to try to code this and it worked. Maybe someone may prove it.

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

A quick question — what’s the point of tests, if they don’t tell you your solution is wrong? I could probably have submitted code from 3 rounds ago and gotten AC.

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

    It's just a basic check if you're submitting to the right problem and if your complexity is more or less ok. If they tested everything on the pretests it would take longer to get the result than it already takes

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

      He knows that, what he is basically trying to say is, they had > 10 pretests each with multitests. Still its just basically equivalent to having no tests at all.

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

      I’m well aware of it, my comment was more of an attempt to sarcastically imply the tests were shit.

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

        I know that, and i mean what my comment said. Pretests are not meant to give you 100% certainty that your solution is correct. You can make a mistake in many different ways and the way they try to account for that is with the system tests, not the pretests. My pc wasn't turning on at the start of the contest but aparently there was a 4 minute queue at that time, they won't try every single way (or even many ways) to disprove your solution, especially in the first problems (especially a solution like yours to B that is correct in a lot of cases but not all of them).

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

      It's just a basic check if you're submitting to the right problem and if your complexity is more or less ok.

      Lol, this sounds like saying that Pretests are just scam

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

Wrong answer on test 38

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

but how to calculate the number of good subsets in div2E? how to construct one is an obvious thing lol

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

    Can you explain your Solution of D ,I observed that 1 one from a pair of ones can be replaced with any zero , and then I tried out some random factorial formula which gave an AC , can you tell me how does the formula n+m C m come from ? where m is no. Of 1's duo and n is no. of zeroes

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

      it's a well-known combinatoric formula for combinations with repetitions: check

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

        How did you break this problem, so that it can be solved this technique? Can you explain please?

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

          I observed that it's possible to consider that we can move any pair of ones to every zero(011->110) because there's a state from which we can do this move, so the problem can be simplified to "calculate a number of ways in which ones can be placed into zeroes(or swapped idk how clearer) using moves described above" or something like that which is solved by summation of C_with_repetitions(number_of_onepairs, number_of_used_zeros) over the number of used zeroes. Generally, we can see at placing of several onepairs at one zero as 01111->11110, so we need repetitions. I hope my explanation at least a little bit clear:))

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

        I know this but how would you formulate it after the observation ?

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

          tried to explain above:)

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

            hey , that part is pretty clear i guess. That even pair of ones and zeros can be arranged in all possible ways. How do you deal with odd number of ones?

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

              We can just skip them, they don't matter. They will be on different positions in different states, but for each state that position is only one

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

Does anyone have the the proof or intuition about the problem Div2 C . Please explain it

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

    Lets say facing the right is position 0 and facing left is position 1, and say the person on index i gets to index j after sorting the array, which position would they be facing?

    Well, for that to happen we need at least abs(j-i) swaps and therefore just by doing that movement from i to j we would be in position abs(j-1)%2. The question is, can we still do swaps in a manner that will put us back at position j but will do a 1 (mod 2) number of swaps? The answer is no, because if we do x swaps to one side, we will still need x swaps to get back, and therefore it will be 2*x = 0(mod 2) swaps.

    Therefore if we store the indexes that a person of number x (in particular, the ammount of indexes with certain parity), we solve the problem because we just need to check if there are enough of those positions to acomodate all the people

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

    Subtask : lets assume all elements are distinct
    lets take one single element
    its position in array is y(eg:7)
    its position in sorted array is x(eg:4)
    now to move its position from 7 to 4 it will have to make min 3 swaps.

    NOTICE : if you would try to use one extra positon like 3 to reach 4 then it would have 5 swaps ( 7 to 4 , 4 to 3 and 3 to 4 ) . Thus we can confirm the parity of swaps dont change.

    Odd swaps : don't maintain the direction So we need even swaps.

    FINAL Task : Now elements are not distinct
    // now we have an opportunity to select a final position ( of duplicates)
    To make an even swap we can move from:
    1) odd pos in original array to odd pos in sorted array OR
    2) even pos in original array to even pos in sorted array

    Thus we are counting the no of odd and even pos of each element in original and sorted array

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

How was there not even a single pretest for C where a[i] was greater than n?

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

    Lack of luck on your part

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

      it sucks even more when I had the chance to touch blue :Sadge:

      well whatever..

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

        But your performance was definitely worth a blue. Within few contests you'll easily reach blue.

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

The round was amazing!

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

Is it even realistic to solve problem F in the duration of 2 hours 30 mins? Just looking at the editorial make me feels sick...

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

    I think there's a much simpler solution to F which is probably only a bit slower:

    Like the editorial, let's process a block of $$$b$$$ queries at a time. Then, instead of grouping by static/dynamic index, let's group by static/dynamic value. There are only at most $$$6b$$$ different values which change, namely the 3 old values of $$$b_{a_i}$$$, $$$a_i$$$, and $$$c_{a_i}$$$, and the 3 new ones for each changed index. For a single value, we can think solve this using a simple 4-state DP. Then, we can find the contribution of all static values for each prefix in $$$O(n)$$$ time, and we can maintain a segment tree of 4x4 transition matrices for each dynamic value to answer those queries. Overall, this will take $$$O((m/b)(n + b^2 \log n))$$$ time, and the optimal choice of $$$b$$$ gives $$$O(m \sqrt{n \log n})$$$. The constant factor seems a little high, but it seems like the editorial probably has high constant factor too.

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

      Actually, this solution can attain $$$O(m \sqrt{n})$$$ as well: just use a $$$\sqrt{n}$$$-time data structure instead of a $$$\log(n)$$$ time data structure, and make sure to compute do as much offline as possible.

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

        Hey , could you please explain your idea about Div1 B. I can't convince myself that odd ones would not affect the solution.

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

          Odd ones do affect the solution; you just need odd ones to end up in odd positions and even ones to end up in even positions, so you should just sort all the odds and sort all the evens.

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

            Hey , thanks a lot for replying. But i was asking about the other problem in which we had a chess board and the possible arrangements were asked.

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

              Oh whoops.

              The best "proof" is to view it as 0's with 1's between them. Then 110 <-> 011 means that you can do $$$a_i -= 2$$$ and $$$a_{i+1} += 2$$$ or vice versa. That means the parity of the $$$a_i$$$ is fixed, and the extra odd one doesn't matter.

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

                Thanks !! I really appreciate it

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

So if the problems are written by only two writers, why do you give such a long writers' list?

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

    They are my friends and they helped me prepare these problems.

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

Good problems but bad contest.

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

Editorials for problem div2B and div2C could've been much better!

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

Why was problem B interactive?

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

    Because we cannot check the legitimacy of the hack data.

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

Can anyone explain Div2/D? Didn't understand the editorial.

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

    Same. I assume it's a known problem, so I'll ask someone i know afterwards (unless some kind soul explains it here)

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

    tried to explain in this thread

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

    In a single move, a pair of ones '11' will be moving towards left or right (try making some random test cases, you'll figure it out soon)

    Now, start grouping 1s to find out such pairs, after doing so you will be left with some 0s, some 1s, and some 11s in the array.

    Now the problem simply reduces to finding out different ways of arranging these elements in the array. Do note that the positions of 0s and 1s would remain fixed as only 11s can move left or right. So we need to find different ways of arranging these 11s around these fixed 1s and 0s.

    One imp observation is that arranging 11s around 1s will lead to same results. Here's an example :- (11)(11)1(11) is the same as (11)1(11)(11)

    So ultimately, we need to find different arrangements of 11s around 0s, the problem now reduces to famous STARS AND BARS problem, and can be solved using combinatorics.

    If the number of 0s is k, and number of 11s is n, then we have k+1 positions where we can put these 11s, and number of ways to do so is given as,

    (n + (k + 1) — 1) Combination n => (n + k) C n

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

      "Do note that the positions of 0s and 1s would remain fixed as only 11s can move left or right".

      I think there is an issue with this assumption. Suppose I have (11)10, another configuration I can get from this is 1011, which can be grouped like 10(11), but can I say that the 1 (with no group) stayed fixed?

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

        When you have an odd number of 1s, pair the last 1 with 0. For 1110, think it as 2 pairs (11)(10).

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

          What about 110010 and 100110? both of them have 2 groups but they cannot be transformed to each other?

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

            The first one is (11)(0)(0)(10). The second one is (10)(0)(11)(0).

            You can only move (11). (0) and (10) are fixed.

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

        Yes, 1 which doesn't form a group will always stay at its position, as you can see in your example, the relative position of 1 and 0 isn't affected by movement of 11

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

          yeah, so 1's and 0's stay fixed relative to each other and our created groups of 11's move around them. Now everything make sense. Thanks a lot guys.

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

      Thankyou harshh3010 for an amazing explanation :)

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

      Thank you understood the logic. Great explanation.

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

Can someone tell me that , have I done some mistake in understanding Div2 C's statement , because I think this can be a valid steps of solution for test case 38 of Div2 C https://ideone.com/JhSefY

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

    I made the same mistake. The problem is that if you have three people: L R L.

    Then you cannot swap the first two to make R L L, because after swapping the pair the sequence is R L L, and then the two people change direction, making the sequence L R L again. So you can only turn a pair L L in to R R.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it 
    A={1,1,1,2,2,2}
   L R L L R L
 
Swapping {1,2} {3,4} 
A={1,1,1,2,2,2} 
   L L R R L L

    Notice that when you're swapping 1 and 2, you're swapping their positions, but this is wrong. The one on 2 would go to 1 and their position would go from L to R, and the opposite would occur with the 1 going to 2. The positions would remain unchanged

    EDIT: one minute too late ._.

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

Can someone help why this solution to Div2.B failed FST?

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

    say the stolen string is the first one all of it's letters appears at least once in the other original strings, your program will fail

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

    wrote similar solution and failed on same test case — comment. not sure what is wrong

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

    Consider this test case:

    1

    3 5

    abcde

    fgche

    abbdd

    abche

    fgbdd

    Correct answer is: abcde

    Your code gives: fgche

    Changes in your code would be: interchange the i and j loop while finding the answer and build the required string.

    This would help: 122135347

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

      Greatest solution ever!!

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

      Great observation

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

      Can you plz. explain your approach.

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

        Sure!!!

        Just look column-wise.

        Each character of jth col in original strings will be present in the swapped strings except the one character of which the string is absent.

        Also, since the input given is valid the output produced will also be valid.

        So first build the map of n-strings col-wise and then for each col check for n-1 swapped/changed strings and look for the extra character and build the answer string.

        I hope you would have understood.

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

Regarding Problem Div2 C and test case 38, I am unable to understand why it's answer will to be "NO".

Rather than considering the positions, let's consider the number of adjacent swaps it takes to make the array non decreasing.

[I have made the elements I am swapping bold]

2 1 2 1 2 1

1 2 2 1 2 1

1 2 1 2 2 1

1 1 2 2 2 1

1 1 2 2 1 2

1 1 2 1 2 2

1 1 1 2 2 2

So the swaps each element had to undergo to reach the final array are: 1 2 3 3 2 1

So in terms of direction L and R it will be transformed to: L R L L R L

It can be further transformed by swapping adjacent equal elements once, as follows:

L R L L R L

R L L L R L

R R R L R L

R R R R L L

Finally, we will get: R R R R R R

So, I can achieve all R's in the end and it's still non-decreasing.

Please correct me if there is a mistake here.

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

    You can't change L R L L R L to R L L L R L

    Note that swapping L R leads to L R (no change)

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

      Yes, I understand it now. Thanks!

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

        I still dont see it. how does swapping LR leads to no change ?

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

Thanks for nice contest.

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

For Div1D, changing every number so that $$$sum[y]$$$ is correct is not enough. Why is it enough to make $$$sum[y]$$$ and $$$sum2[y]$$$ have correct values?

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

    Because you can change any values to make $$$sum[y]$$$ correct but there is exactly one value that makes both $$$sum[y]$$$ and $$$sum2[y]$$$ correct. It's not the same but it's quite similar to how there is exactly one solution for $$$x$$$ and $$$y$$$ when we know $$$x + y$$$ and $$$x^2 + y^2$$$.

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

      I'm not sure why you introduced the irrelevant example of $$$x+y$$$ and $$$x^2+y^2$$$ when you can just use exactly what the problem itself uses: in this problem you know $$$x-y$$$ and $$$x^2-y^2$$$.

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

        Think about the simplified version where $$$m = 2$$$. That's what my example refers to.

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

    Look at an alternative problem. You have an array. And you have to choose a single number to increment by D, such that the target sum of squares is S.

    This chosen number is unique. Why? Say we have two such numbers which when incremented give the same sum of squares x,y.

    $$$x+(y+D)^2 = (x+D)^2+y^2\implies 2Dx = 2Dy \implies x=y$$$ because D isn't 0.

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

My solution for Div2. C (although it feels like an overkill now, I hope it will help those who are looking for some sort of "intuition" here).

First of all, we can calculate the minimum number of swaps all elements must undergo in order to make the array non-decreasing. This can be done easily with the help of inversion counting (more specifically, for some index $$$i$$$, counting the number of elements smaller than $$$A_i$$$ to the right of $$$i$$$, and the number of elements greater than $$$A_i$$$ to the left of $$$i$$$.

If some element $$$i$$$ undergoes an even number of swaps, it stays correctly oriented, otherwise it gets flipped (incorrectly oriented).

After arranging the array in non-decreasing order, it is clear that all elements which have the same value, are together.

Let us assume a segment {$$$a, a, a, a, a, a, a, a$$$}, which is oriented {$$$L, R, L, R, R, L, R, L$$$}.

Let us pick $$$2$$$ $$$L$$$s such that there is no $$$L$$$ between them. We can correctly orient them with swapping among themselves, if the number of $$$R$$$s between them is even. So, we notice that we cannot correctly orient $$$1$$$ and $$$3$$$, but we can correctly orient $$$3$$$ and $$$6$$$, and after doing that, we again have an even number of $$$R$$$s between $$$1$$$ and $$$8$$$, so we can correctly orient them as well, thus orienting the entire segment.

To implement this part, I used a stack, in which, whenever I encountered an $$$L$$$, if it was possible to "cancel" this $$$L$$$ with the previous $$$L$$$, I greedily did it, otherwise I simply pushed this $$$L$$$ to the stack. After iterating over a segment of equal values, if the stack is finally empty, then we can be sure that the segment can be correctly oriented, otherwise we can be sure that the segment cannot be correctly oriented.

Although some might find it messy, here is my code for the same : 122139852

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

    Thanks for explaining I came up with pdbs part but second part of how to handle the change in equal numbers it was tough. Thanks to explain the later important part.

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

the pretest for C was so weak it made the contest not fair for some contestant

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

Can someone please tell me why my solution of A does not work?
122139278
Thank you

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

    I was doing the same mistake, this technique doesn't guarantee that you have done atmost 100 operations.

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

    The reason your solution is giving the wrong answer is, consider a case,
    1
    5
    1 6 5 3 1
    1 4 2 4 5.
    So, the test case is valid, and when your outer loop will come at i=3, your inner loop will increase a[i] by one at j=1, so now the array will look like this,
    a[]= 1 5 5 4 1,
    and inner loop further goes on and increase a[i] by one at j=2, and array will look like,
    a[]= 1 5 4 5 1,
    Which is a completely unnecessary operation. Though we are not required to minimize the moves, we are supposed to complete it in 100 operations. That's why it is giving the wrong answer.
    Solution: You can break the inner loop when a[i] becomes equal to b[i], Hope this solution would help, 122159718.

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

Why this solution for problem B (Div2) gets tle for large m (tc4)

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

    im gonna copy a comment i did to another person with the same problem

    "I think the problem is that intead of ans=ans+z.first; you should do ans+=z.first or ans.append(z.first), because in your code you are first making a copy of ans, then summing it with z.first, and only then atributing that value to ans. This is O(n^2) because for each iteration making the copy takes O(n).

    I think depending on the compiler your code could work though"

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

How to break D into a "Stars and Bar" technique problem?

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

    let the number of 0 be x and let the no of consecutive 2 ones be y (eg-> 1110 -> 11 1 0-> y=1,x=1) now consider x: as bars and y :as stars.(i hope u get it)

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

AquaMoon wants to count the number of states reachable from the initial state with some sequence of operations. But she is not good at programming

has 2413 peak rating

I guess I should switch for programming microwaves.

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

Format of editorials with hints is much better

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

Alternate approach for Div2 B. Just keep a count of characters appearing at indexes before and after the operation. The missing character would be a part of the answer for that index,
link- https://codeforces.me/contest/1546/submission/122093074

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

Any better explanation or intuition behind div2 D? Maybe some kind of strict proof.

Edit: I understand the part that the number of groups (if you calculate every time the way it is shown in the editorial solution) remains the same no matter what you do. But I wonder why would someone come up with such an idea? Was it a result of some observations?

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

Kept getting WA on 38th test case,Question C.Anyone else?

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

    just check out this test case (38th case)

    1

    6

    2 1 2 1 2 1

    expected output: NO

    I had also got the WA on the 38th case.

    Think of if 3 equal no. are there with directions L R L, we cannot convert it to R R R.

    And then change your logic according to the problem.

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

Here is a different way of approaching Div2D-

Lets call the ones between a 0 and the next 0 as 'gaps'. For example 110011101 has 4 gaps containing 2, 0, 3 and 1 ones respectively (assume that there are dummy zeroes in the beginning and at the end). Now notice how the one move in pairs and whenever an operation is applied, the number of ones in a gap decreases by 2 and number of ones in another gap increases by 2. This means that the parity of the number of ones in all gaps will remain consistent regardless of the state.

Count how many gaps have even parity and how many gaps have odd parity. Now we just need to count the number of ways to distribute the ones in the gaps such that the parities are maintained.

Lets assume that we have decided to distribute $$$x$$$ ones among the even gaps and $$$c$$$-$$$x$$$ ones among the odd gaps where c is the total number of ones.

If there are $$$e$$$ gaps with even parity, the number of ways to distribute the ones would be the same as finding the number of non negative integral solutions of the equation $$$a_1 + a_2 + ... + a_e = x$$$ such that all $$$a_i$$$ are even. This is the same thing as the stars and bars method.

Similarly if there are $$$o$$$ odd parity gaps, you need to find the number of solutions of $$$a_1 + a_2 + ... + a_o = c-x$$$ such that all $$$a_i$$$ are odd. The product of these two answers will be the number of distributions for a single value of $$$x$$$.

Iterate over all $$$x$$$ from 0 to $$$c$$$ and sum up the product of the two answers for each $$$x$$$.

Link to my submission

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

Is there are no prefix optimum solution in D (chess) ? I tried to use DP here but its incorrect.

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it
When 'A' is a curse
→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Woah, i didn't expected that Div1C and Div1D are so beautiful before reading editorial. Thanks!

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

Oh wow, it was rather easy to mess up m and k in Div1D and because of that I wrote a solution that works for at least 5 consecutive times instead of at least 7 (in which case it gets a lil bit easier cause I can take 3 consecutive valid measurements). I interpolated quadratic polynomial in my code and used doubles along the way ;p.

My solution is a bit different as well. As a "hash" of a multiset of integers $$${x_1, \ldots, x_n }$$$ I take $$$(\sum x_i, \sum (x_i-x_j)^2)$$$. You can see easily see that second value is a quadratic function of $$$t$$$ if we make variables $$$x_i$$$ linearly dependent on $$$t$$$, so by interpolating quadratic polynomial I can retrieve changed variable. Tbh I think my solution is just strictly worse than one from editorial ;p. But not by much.

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

    Here's another pretty simple solution that works for $$$4 \leq k$$$ just like the one above.

    Let $$$p_t$$$ be the array of captured coordinates at time $$$t$$$.

    Then, let's define $$$two_t=\sum p_{t,i}^2$$$. We can see that

    $$$ \begin{align*} two_t &= \sum (x_i+tv_i)^2 \\ &= \sum x_i^2 + 2t \sum x_iv_i + t^2\sum v_i^2 \end{align*} $$$

    We already know $$$\sum x_i^2=two_0$$$, so we only need to find $$$\sum x_iv_i$$$ and $$$\sum v_i^2$$$.

    Now find any two different times $$$t_1,t_2 \not\in \{ 0,y\} $$$ (this is where $$$4 \leq k$$$ comes from).

    Then using the expansion of $$$two_t$$$ from earlier, we just get a system of two linear equations with two unknowns:

    $$$ \begin{align*} two_{t_1} &= \sum x_i^2 + 2t_1 \sum x_iv_i + t_1^2\sum v_i^2 \\ two_{t_2} &= \sum x_i^2 + 2t_2 \sum x_iv_i + t_2^2\sum v_i^2 \end{align*} $$$

    Solving, we get

    $$$ \sum v_i^2 = \dfrac{t_2two_{t_1}-t_1two_{t_2}+(t_1-t_2)\sum x_i^2}{t_1t_2(t_1-t_2)} $$$

    and then just get $$$\sum x_iv_i$$$ from one of the equations.

    Now, we can just get the unmodified $$$two_y$$$ from the earlier expansion $$$\sum x_i^2 + 2y \sum x_iv_i + y^2\sum v_i^2$$$ , and solve the problem (the rest of the solution is the same as the one in the editorial): 122165319.

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

      Actually mine works for k=4 too, but I said k>=5, because during the contest I was thinking this is the actual constraint :D

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

        Oh, yeah it does, sorry:(, fixed the wording to make it obvious yours works for $$$k=4$$$ as well (it was super late when I was posting the comment, so I didn't check). I was actually about to post my solution as a separate comment, but then saw your comment, and decided to just reply to yours instead, so that the solutions would be grouped together (since our comments seem to be the only ones talking about Div1D's solution).

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

I think Div.1 A & B are interesting problems, because I have been gained -87 rating changes because of them. TwT

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

The problem are great!But they are too hard :(

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

Weak pretests of Div2.C...

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

In Problem B, why does running n*m where n >= 1e5 and m >= 1e5 doesn't get TLE? I was stuck because of this.

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

    if you read the problem carefully, it says "the sum of n⋅m over all test cases does not exceed 1e5"

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

      Oh, I didn't see that, thanks for your clarification.

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

Please , someone make me understand Div2 A What is wrong in my submission 122158130

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

    I think it's because you made operations so many times. Please makesure that the operation time is not more than 100.

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

    You are checking a[i]>b[i] outside the inner for loop. Let's say a[i] was bigger than b[i] by 1 but there were >1 j's where a[j] was less than b[j] then you will end up decreasing one extra element from a[i]. Better to check both conditions inside inner for loop.

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

For problem E, it seems that the tutorial just gives the solution but I'm having a hard time understanding why it is correct. Can someone explain?

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

Proof for div1b-
First we will add 2 zeroes one at the beginning and one at the end.let x be the number of zeroes.let ai be the number of ones between the ith and (i+1)th zero for all 1<=i<=x-1 .Notice that the operation is same as subtracting 2 from one index(which has value atleast 2) and adding it to 2 to one of its neighboring index so the invariant is parity of ai.

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

I love the problems. Very nice ideas, and the solution is clear and easy to understand.

Thank you very much <3

(Actually I'm quite sad right now because I've just demoted to Specialist)

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

Can I get 46th test for Div 2 problem C?

It starts with: 1 100000 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...

But when I locally run test with "1 2" repeated 50.000 times I don't observe any performance problems. It seems the test is different from "1 2" repeated 50.000 times.

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

    simple explanation of problem c with proper examples, u will definitely understand. and test case 46 will also become clear. https://www.youtube.com/watch?v=YPdTqbGxPMY

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

      Thanks but I do understand editorial solution. I don't understand why my original solution doesn't pass test 46. That's why I want to get input data for this test.

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

This may be an easy-to-understand Chinese editorial to C problem https://blog.csdn.net/qq_45863710/article/details/118674749?spm=1001.2014.3001.5502

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

Can someone help me to prove the author's solution for div2E div2.E problem E div2 div.2

Why the algorithm described above works?

And why is this? "If there not exists such an array discribed above, according to the Pigeonhole Principle, all numbers of the unchosen arrays must appear exactly twice on their columns" (typo btw :()

Any help will be highly appreciated. Thank you very much!

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

    We have the Chinese version of the prove, but we do not have the ability to translate it into English.

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

      Thank you! I will look at the math symbols to guess (I don't know Chinese). Nice problems btw.

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

        By the way, you can click the link to the Chinese editorial in the original post, and then if you open it in Chrome, Google has a "Translate to english" option. I'm still trying to understand the proof myself but that version of the proof has more detail than the English editorial here.

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

    Here is a proof on "If there not exists such an array discribed above, according to the Pigeonhole Principle, all numbers of the unchosen arrays must appear exactly twice on their columns".

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

      Could you explain more details about "Each integer in $$$c_i$$$ appears at most twice, by the Pigeonhole Principle"?

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

        A unique row will not be an eliminated row.

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

        Suppose there are $$$a$$$ unique rows in the original matrix. For any column $$$c_i$$$ in $$$A$$$, there are at least $$$n-a$$$ different integers in it (otherwise the original rows cannot form a Latin square). Also, we know that each integer in $$$c_i$$$ appears at least twice. Then if some integer appears three times in $$$c_i$$$, there will be at least $$$2(n-a) + 1$$$ integers in $$$c_i$$$, which is contradicted with the fact that there are no more than $$$2(n-a)$$$ rows in $$$A$$$.

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

      Just put them all in a spoiler so that it doesn't occupy much room :)

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

    Div1 C:

    Situation 1: If an array have a number which appears exactly once at its column, then the array must choose, we can delete least two arrays(The array and arrays which with the array have common elements).

    Situation 2: All numbers of the unchosen arrays appear exactly twice on their columns. If not have situation 1. Then must is situation 2. In situation 2, we can choose any an array and delete the array and arrays which with the array have elements, meanwhile multiply the answer by $$$2$$$.

    Proof:

    Let the remained arrays set are $$$Q={array_1,array_2,...,array_{2*k}}$$$。 First we redefine Latin square：A $$$n*m$$$ matrix so that not any row or any column have common elements($$$n$$$ can not equal $$$m$$$).

    Then we define Two Latin square: A arrays set $$$Q$$$ of size $$$2*k$$$ so that we can divide it to two $$$k*m$$$ Latin square.

    Proof $$$Q$$$ is a Two Latin square: The conditions of the problem make we must can choose $$$k$$$ arrays from $$$Q$$$ so that the $$$k$$$ arrays is a Latin square. We consider the remained $$$k$$$ arrays, all number in a column appears exactly once, all row are a permutation of $$$1$$$ to $$$n$$$, the the remained $$$k$$$ arrays also is a Latin square.

    Define Minimal Two Latin square: Give a arrays set $$$Q$$$ of size $$$2*k$$$ which is a Two Latin square，we have an arrays set $$$A\subseteq Q$$$, let $$$B$$$ is the minimal arrays set so that $$$A\subseteq B\subseteq Q$$$ and $$$B$$$ is a Two Latin square. We call $$$B$$$ is the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$.

    We set $$$A={array_x,array_y}$$$($$$array_x$$$ and $$$array_y$$$ have common elements), obviously $$$array_x$$$ and $$$array_y$$$ can't choose same time. Let $$$B$$$ be the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$. Then $$$B$$$ can be divide to two Latin square unique. We choose $$$array_x$$$ or $$$array_y$$$ can uniquely determine the set reserved in $$$B$$$. And our choice will not affect how $$$Q-B$$$ chooses. We just need know set $$$B$$$ multiple the answer by $$$2$$$, and continue to choose from set $$$Q-B$$$.

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

      In your last paragraph above, can you describe what is set A? Does A have just two rows, or can it have more than two rows?

      If A is a set which has two rows, isn't B just equal to A?

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

        General speaking, we can divide $$$Q$$$ to some Minimal Two Latin square $$$B_1,B_2,...,B_t(B_i\cup B_j =\varnothing$$$ for $$$i\neq j)$$$, so that the answer is $$$2^t$$$.

        In each $$$B_i(1\le i\le t)$$$, we can find a $$$A_i={array_{x_i},array_{y_i}}$$$ so that $$$A_i\subseteq B_i$$$ and $$$array_x,array_y$$$ can't be choose same time. Use $$$array_x$$$ or $$$array_y$$$, we can uniquely make sure a choose way in $$$B_i$$$.

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

Can anyone please help to point out the mistake in my submission Div2C https://codeforces.me/contest/1546/submission/122161335 I would be thankful for pointing out what i am missing. Thanks

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

    There seems to be an out of bounds array access bug in your code, because you do a[i + 1] indexing without ensuring that i + 1 < n. However this is not the real reason for getting a WA verdict.

    Please consider 7L 7R 7R 7L pattern as a part of your sorted array. Your code will report that the answer is NO after checking the first two elements. But the real answer is YES, because we can swap the middle two elements to get 7L 7L 7L 7L and then swap the first two elements to get 7R 7R 7L 7L. After that, the last two elements can be swapped too: 7R 7R 7R 7R

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

      Yes, Thanks a lot. Now I get that I was not considering this case. Thanks once again.

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

Div1 C:

Situation 1: If an array have a number which appears exactly once at its column, then the array must choose, we can delete least two arrays(The array and arrays which with the array have common elements).

Situation 2: All numbers of the unchosen arrays appear exactly twice on their columns. If not have situation 1. Then must is situation 2. In situation 2, we can choose any an array and delete the array and arrays which with the array have elements, meanwhile multiply the answer by $$$2$$$.

Proof:

Let the remained arrays set are $$$Q={array_1,array_2,...,array_{2*k}}$$$。 First we redefine Latin square：A $$$n*m$$$ matrix so that not any row or any column have common elements($$$n$$$ can not equal $$$m$$$).

Then we define Two Latin square: A arrays set $$$Q$$$ of size $$$2*k$$$ so that we can divide it to two $$$k*m$$$ Latin square.

Proof $$$Q$$$ is a Two Latin square: The conditions of the problem make we must can choose $$$k$$$ arrays from $$$Q$$$ so that the $$$k$$$ arrays is a Latin square. We consider the remained $$$k$$$ arrays, all number in a column appears exactly once, all row are a permutation of $$$1$$$ to $$$n$$$, the the remained $$$k$$$ arrays also is a Latin square.

Define Minimal Two Latin square: Give a arrays set $$$Q$$$ of size $$$2*k$$$ which is a Two Latin square，we have an arrays set $$$A\subseteq Q$$$, let $$$B$$$ is the minimal arrays set so that $$$A\subseteq B\subseteq Q$$$ and $$$B$$$ is a Two Latin square. We call $$$B$$$ is the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$.

We set $$$A={array_x,array_y}$$$($$$array_x$$$ and $$$array_y$$$ have common elements), obviously $$$array_x$$$ and $$$array_y$$$ can't choose same time. Let $$$B$$$ be the Minimal Two Latin square general by set $$$A$$$ and $$$Q$$$. Then $$$B$$$ can be divide to two Latin square unique. We choose $$$array_x$$$ or $$$array_y$$$ can uniquely determine the set reserved in $$$B$$$. And our choice will not affect how $$$Q-B$$$ chooses. We just need know set $$$B$$$ multiple the answer by $$$2$$$, and continue to choose from set $$$Q-B$$$.

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

How would we solve problem B of div2 if it was asked that every person in the end will look towards left?

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

    I think you mean Div 2 C, "AquaMoon and Strange Sort".

    We can do the same odd/even counting technique, but flip the parity for the sorted array.

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

can anyone could give me intution for div2D i can understand why are we not including no of groups also ? why only '0' and '11' are considered why not '1' also

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

    because it cannot propagate imagine a string "001010" the no of combinations of it is 1 (itself) but now add just one pair of 11 in the string lets just add it in the beginning "11001010"

    and now see its transformation

    01101010 00111010 00101110 00101011

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

    Looking at a simple example would be the simplest i guess. E.g. ..11...1.. has these possible states:

    11.....1..
.11....1..
..11...1..
...11..1..
....11.1..
.....111..
.....1.11.
.....1..11

    We can see, this looks likes this: we have one state with all 3 ones touching. Every other state has a single 1 and a double 11. Let's mark the first 1 of a 11 group with X

    X1.....1..
.X1....1..
..X1...1..
...X1..1..
....X1.1..
.....X11..
.....1.X1.
.....1..X1

    Now let's delete every 1 in this diagram.

    X.......
.X......
..X.....
...X....
....X...
.....X..
......X.
.......X

    We only have left the X and it occupies all possible states. You can make the same with some more complicated example, which I will put in a spoiler. Hope this gives you the Intuition about how the pairs behave!

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

Problem D(div 2) solution, what's mean "—" ?

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

Can anyone translate the Chinese editorial for E into english? https://www.cnblogs.com/invisible-eyes/p/15003033.html

It seems like the Chinese editorial has much more detail than the English editorial for that problem. I am still struggling to understand how to solve E. Thanks in advance.

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

the worst round, i've ever seen.

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

can anyone explain div.2 D in a better way pleasE?

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

Ah, it's very friendly for me to write a Chinese editorial:)

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

Why "NO" in 6 2 1 2 1 2 1

Consider it +2 +1 +2 +1 +2 +1

now swap (1,2) -1 -2 +2 +1 +2 +1

now swap(3,4) -1 -2 -1 -2 +2 +1

now swap(2,3) -1 +1 +2 -2 +2 +1

now swap(5,6) -1 +1 +2 -2 -1 -2

now swap(4,5) -1 +1 +2 +1 +2 -2

now swap(3,4) -1 +1 -1 -2 +2 -2

now swap(2,3) -1 -1 +1 -2 +2 -2

now swap(1,2) +1 +1 +1 -2 +2 -2

now swap(4,5) +1 +1 +1 +2 -2 -2

now swap(5,6) +1 +1 +1 +2 +2 +2

and its sorted with all right

can anyone tell

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

    After the 7-th swapping operation, the sequence should be -1 +1 -1 -2 +2 -2.

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

I will write down the intuition I got from Div2E/Div1C so that I can get it fixed in my brain.

Consider that the latin square we will choose is something like this (have numbers 1,...,n as the first column):

1----------

2----------

3----------

...

n----------

And the corresponding dirty square is something like this (have numbers a1,...,an between 1 and n as the first column):

a1----------

a2----------

a3----------

...

an----------

If i appear only once in the first column of the the 2n x n matrix, then we know that the row

i----------

belongs to a latin square. Indeed, if it was in a dirty square, then there would also exist a row

i++++++

in the latin square (because the latin square must have all elements 1,..n in its first column), what is a contradiction.

If no element appear only once in the first column of the 2n x n matrix, then each element must appear twice. Indeed, suppose an element appear k > 2 times in this column. One of these times must be inside of a latin square and the other k-1 times must be in the corresponding dirty square. But now it rest only n-(k-1) places in the first column of the dirty square. So we can only put at most n-(k-1) different elements from 1,..n at these places. So at least one number i from 1,..,n have no place to go inside the first column of the dirty square, which means that it only appears in the latin square (necessarily once), what is a contradiction to our initial hypotheses that no element appear only once in the first column of the 2n x n matrix.

This can be extended to any column.

What the algorithm proposed in the editorial do is construct a solution greedily. It keeps a set A with the choosen rows and a set B with the trash rows. If there is a row that is necessarily in a latin square, it picks it, put it in A and put in B all rows that can't be in a latin square with it.

If all elements appear twice in its column at some point (when we have 2*k elements), it means we have at least two latin squares. Suppose two of them are of the form

1----------

2----------

...

k----------

Then we know that all other latin squares generated by this configuration is an exchange of blocks

i----------

...

j----------

between these two initial latin squares. So we know the total number is something of the form $$$2^x$$$, but we just pick one factor two and continue breaking because we will have the other factor twos when we arrive to this situation again later.

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

I solved D without proving

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

1546B — AquaMoon and Stolen String EASILY SOLVED USING XOR PROPERTY. SINCE CHARACTERS ONLY SWAP FROM ONE STRING TO OTHER STRING SO,AT PARTICULATE INDEX I [1 <= I <= M] CHARACTERS WILL BE DOUBLE + 1 [1 FOR UNPAIR STRING]SO, IF WE APPLY XOR ON EACH CHARACTERS FOR EVERY INDEX I [1 <= I <= M] FOR ALL N & N-1 STRING THEN XOR RESULT GIVE ANS[I] CHARACTER.

→ Reply