Cirno_9baka's blog

By Cirno_9baka, 2 months 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

»
2 months 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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Can you explain why you do that?

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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?

        • »
          »
          »
          »
          »
          2 months 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.

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

    that's an amazing solution orz

  • »
    »
    2 months 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

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

    That's exactly how I did it.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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.

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

      simple explanation of problem c https://www.youtube.com/watch?v=YPdTqbGxPMY

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

    is there any other way to solve it?

    could you please see if i can modify my solution a bit from here to get the result?

    https://codeforces.com/contest/1546/submission/122098445

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months 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.

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

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

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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?

          • »
            »
            »
            »
            »
            »
            2 months 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.

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

  • »
    »
    2 months 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

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

      • »
        »
        »
        »
        2 months 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

»
2 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Too hard.

»
2 months 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.com/contest/1546/submission/122098007 But the idea of counting in the map is ok though

  • »
    »
    2 months 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!!

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

    It's an amazing solution!%%%

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

sro lxl orz

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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

»
2 months 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 :(

»
2 months 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

»
2 months ago, # |
  Vote: I like it +68 Vote: I do not like it

Worst editorial

»
2 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Nice pretests for Div2 C )

»
2 months 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?

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

    Yes! It's weird. That's why I'm looking for a better explanation in comments. Editorial is not much helpful.

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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]
      
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

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

          Oops. Sorry i thought u asked for div 2.

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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!!

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

        Beautiful :)

      • »
        »
        »
        »
        2 months 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?

        • »
          »
          »
          »
          »
          2 months 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.

»
2 months 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.com/contest/1546/submission/122117451

Same code in Python accepted: https://codeforces.com/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.

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

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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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!

»
2 months 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!

»
2 months 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

  • »
    »
    2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

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

    A simple approach would be to calculate the hashcode of n string and put it in the map corresponding to the string.Find the total sum of hashcode of n string and subtract the totalsum of hashcodes of n-1 strings.The resultant difference is the hashcode of the stolen string and the string can be easily retrieved from the map.Hope it helps:) Can refer to the submission link for help: https://codeforces.com/contest/1546/submission/122143475

  • »
    »
    2 months 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.com/contest/1546/submission/122215500

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

    Thanks everyone, the problem was much easier than I thought. Much appreciated!!!

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

Maaaan was I not ready for Div 1

»
2 months 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

  • »
    »
    2 months 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.

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

      why is that, can you explain more?

      • »
        »
        »
        »
        2 months 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.

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

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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

      • »
        »
        »
        »
        2 months 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.

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

    simple explanation of problem c with proper examples, u will definitely understand. https://www.youtube.com/watch?v=YPdTqbGxPMY

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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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.

    • »
      »
      »
      2 months 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.

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

    • »
      »
      »
      2 months 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

»
2 months ago, # |
  Vote: I like it +86 Vote: I do not like it

Wrong answer on test 38

»
2 months 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

  • »
    »
    2 months 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

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

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

      • »
        »
        »
        »
        2 months 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?

        • »
          »
          »
          »
          »
          2 months 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:))

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

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

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

          tried to explain above:)

          • »
            »
            »
            »
            »
            »
            2 months 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?

            • »
              »
              »
              »
              »
              »
              »
              2 months 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

»
2 months 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

  • »
    »
    2 months 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

  • »
    »
    2 months 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

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

    simple explanation of problem c, u will definitely understand https://www.youtube.com/watch?v=YPdTqbGxPMY

»
2 months 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?

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

    Lack of luck on your part

    • »
      »
      »
      2 months 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..

      • »
        »
        »
        »
        2 months 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.

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

The round was amazing!

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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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.

          • »
            »
            »
            »
            »
            »
            2 months 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.

            • »
              »
              »
              »
              »
              »
              »
              2 months 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.

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

                Thanks !! I really appreciate it

»
2 months 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?

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

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

»
2 months ago, # |
  Vote: I like it +106 Vote: I do not like it

Good problems but bad contest.

»
2 months 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!

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

Getting WA on test case 5 for Div2B — sol

My solution is to count each letter at its index for the jumbled up strings. That is, a 2D matrix, where row corresponds to letter and column are positions and the cell is the count. After that i iterated over all the original strings. For each letter in a given original string i checked if there is an entry in the 2D matrix. If yes, decrement it by 1, else this is the answer. Can someone help me figure out issue with this solution?

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

    I did the same. can someone explain why its wrong?

    public void solve(InputReader in, OutputWriter out) {
      int n = in.nextInt();
      int m = in.nextInt();
      String[] original = new String[n];
      int[][] modified = new int[m][26];
      for (int i = 0; i < n; i++) {
        original[i] = in.next();
      }
      for (int i = 0; i < n - 1; i++) {
        String s = in.next();
        for (int j = 0; j < s.length(); j++) {
          modified[j][s.charAt(j) - 'a']++;
        }
      }
    
      for (String s : original) {
        for (int i = 0; i < s.length(); i++) {
          modified[i][s.charAt(i) - 'a']--;
          if (modified[i][s.charAt(i) - 'a'] < 0) {
            out.println(s);
            return;
          }
        }
      }
    }
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also did exactly same thing and got WA on test 5. It's because we aren't checking odd number of occurrences.

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

        Ok, this comment https://codeforces.com/blog/entry/92739?#comment-815088 helped me understand

        slight modification to my code that got it to pass.

        char[] result = new char[m];
        for (String s : original) {
          for (int i = 0; i < s.length(); i++) {
            modified[i][s.charAt(i) - 'a']--;
            if (modified[i][s.charAt(i) - 'a'] < 0) {
              result[i] = s.charAt(i);
            }
          }
        }
        out.println(new String(result));
        
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    got the issue. The missing string could be the first original string and have all the letters in the 2d matrix. Instead of assigning the string for which we cannot find letter at that position as answer, build the string. That is, if the letter is not present at particular position, put that letter in the answer string at the same position.

    AC solution

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

Why was problem B interactive?

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

    Because we cannot check the legitimacy of the hack data.

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

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

  • »
    »
    2 months 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)

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

    tried to explain in this thread

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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?

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

        • »
          »
          »
          »
          »
          2 months 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?

          • »
            »
            »
            »
            »
            »
            2 months 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.

      • »
        »
        »
        »
        2 months 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

        • »
          »
          »
          »
          »
          2 months 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.

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

      Thankyou harshh3010 for an amazing explanation :)

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

      Thank you understood the logic. Great explanation.

»
2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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 ._.

»
2 months 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?

  • »
    »
    2 months 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

  • »
    »
    2 months 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

  • »
    »
    2 months 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

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

      Greatest solution ever!!

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

      Great observation

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

      Lekin saath me yeh kya khabr chhapi hai...Ab ghodo ki race me gadhe bhi dodenge!!!

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

      Can you plz. explain your approach.

      • »
        »
        »
        »
        2 months 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.

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

  • »
    »
    2 months 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)

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

      Yes, I understand it now. Thanks!

      • »
        »
        »
        »
        2 months 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 ?

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

          Ah yes. Understood it now.

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

problems were nice but I wish I could say this for editorial also Btw thank you AquaMoon ! for this wonderful round

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

Thanks for nice contest.

»
2 months 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?

  • »
    »
    2 months 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$$$.

    • »
      »
      »
      2 months 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$$$.

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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.

»
2 months 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

  • »
    »
    2 months 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.

»
2 months 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

»
2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months 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
  • »
    »
    2 months 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"

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

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

  • »
    »
    2 months 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)

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

can somebody plz tell why this code gives wa on problem div2C https://ide.codingblocks.com/s/587538

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

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

Format of editorials with hints is much better

»
2 months 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.com/contest/1546/submission/122093074

»
2 months 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?

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

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

  • »
    »
    2 months 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.

»
2 months 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

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

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it
When 'A' is a curse
»
2 months 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!

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

how many more tester u need to make a better editorial!!?. Yes I need downvote . shower them.

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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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

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

»
2 months 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

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

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

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

Weak pretests of Div2.C...

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

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

    Same!!!!!!!!!!!!!!!!!!!!!!

  • »
    »
    2 months 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"

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

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

»
2 months 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

  • »
    »
    2 months 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.

  • »
    »
    2 months 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.

»
2 months 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?

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

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

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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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.

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

Another way to think of $$$Div2D$$$$$$/$$$$$$Div1B$$$ goes as follows:

  • $$$1's$$$ stay in place

  • $$$11's$$$ can move wherever

  • $$$ans$$$ $$$=$$$ number of ways to place $$$11's$$$ onto the field

  • imagine $$$s$$$ as $$$00...$$$ $$$+$$$ $$$11$$$ $$$+$$$ $$$00...$$$ $$$+$$$ $$$11$$$ $$$+$$$ $$$00...$$$ $$$+$$$ $$$...$$$

  • $$$count$$$ $$$of$$$ $$$0's$$$ in all blocks $$$=$$$ $$$n$$$ $$$-$$$ $$$count$$$ $$$of$$$ $$$1's$$$ $$$-$$$ $$$count$$$ $$$of$$$ $$$11's$$$ $$$*$$$ $$$2$$$

  • there will be $$$count$$$ $$$of$$$ $$$11's$$$ + $$$1$$$ blocks of $$$0's$$$

  • the task is reduced to counting the number of ways to get a sum of $$$X$$$ using $$$Y$$$ nonnegative terms

  • it's a well known problem, answer to which is $$$ { {X + Y - 1} \choose {Y - 1}} $$$

  • in our case $$$X$$$ is $$$count$$$ $$$of$$$ $$$0's$$$ and $$$Y$$$ is $$$count$$$ $$$of$$$ $$$blocks$$$ $$$of$$$ $$$0's$$$

»
2 months 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

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

hey guys... please help me how XOR is working in problem B. I'm having trouble understanding that. can you please elaborate a little...is it something that characters are converting in their ASCII then in binary and the final value is again converted to the character?

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

    you can do it without xor by making an array of size m first whose values are intially 0, call it Z

    for the first n strings of size m, add values of the characters(asci values, ex:a:97, b:98) to their corresponding indices, for example, if n = 3, you are going to add the characters at index 0 of each string to index 0 at Z, then repeat for index 1, 2,...., m — 1(Z[i] += s[i])

    now, for the next n — 1 strings, subtract from Z each character's value at the same index you read that character(Z[i] -= s[i])

    now, its as you say, the final values left in Z are decimal representation of asci characters of the stolen string and all thats left is to convert and print them

    as for why xor works its because each character from the first n strings is repeated again in the next n — 1 strings, except for the stolen string where each character appears only once

    when you xor 2 equal values you get a 0 (x ^ x = 0), what we kinda did is(x ^ x ^ a = a), where a is whatever the character of the stolen string, so, it works

»
2 months 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!

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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.

  • »
    »
    2 months 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
    • »
      »
      »
      2 months 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"?

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

        A unique row will not be an eliminated row.

      • »
        »
        »
        »
        2 months 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$$$.

    • »
      »
      »
      2 months 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 :)

  • »
    »
    2 months 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$$$.

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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$$$.

»
2 months 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.com/contest/1546/submission/122161335 I would be thankful for pointing out what i am missing. Thanks

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

    it sucks

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

    U can take help from this : https://youtu.be/YPdTqbGxPMY

  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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.

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

I was struggling with Div2D but now I understand how the editorial solution works.

After getting the pair of one groups (scanning from left to right), isolated ones will always be of the form (----10...0----) or (----1) because otherwise they would be in a group (by the manner that groups are constructed).

Now we can watch operations (11)0 ---> 0(11) as if the group (11) is an invariant thing that jumped over the zero. Also, we can watch (11)1 ---> 1(11) as if the group (11) is an invariant thing that jumped over the isolated one giving an equivalent configuration. Since the configuration is equivalent, we can eliminate isolated ones at the beginning.

Notice that if there is a sequence of zeros, a group can go jumping forward and back through them.

If a group meet another group, we can consider that it can also jump through them. That means, if we are at a state (11)¹(11)², we can consider that we can go to a state (11)²(11)¹.

So we are indeed in a configuration similar to that of star and bars problems where the bars are the zeros and the stars are the groups (11) defined initially.

Everything is clear to me now, the only thing that seems a mistery is what is the intuition to initially search for these kind of groups. Maybe experience...

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

For AquaMoon and Stolen String, wouldn't the two for loops cause TLE?

»
2 months 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$$$.

»
2 months 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?

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

    If n is even, we can divide the array into pair of consecutive elements and swap inside each pair. Now everybody have left direction and the problem is equivalent to the original problem.

    If n is odd, I guess there is no solution. Proof: Construct a bipartite graph with 2*n nodes and connect vertex i to j+n if abs(i-j) is odd. The maximum match in this graph is of size n-1.

  • »
    »
    2 months 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.

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

    Problem C : Explanation

    https://youtu.be/YPdTqbGxPMY

»
2 months 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

  • »
    »
    2 months 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

  • »
    »
    2 months 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
»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

»
2 months ago, # |
  Vote: I like it -28 Vote: I do not like it

the worst round, i've ever seen.

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

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

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

Problem C — Explanation with code

https://youtu.be/YPdTqbGxPMY

»
2 months 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:)

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

Div2F/Div1D is very beautiful!

What if two elements are modified in the same array instead of only one ?

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

Div2 D, Div1 B The editorial for D problem is not the best, I got some hint though. I tried to explain D using comments check my submission (don't try to read code, ik it's messy). If you have any doubt you may ask.

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

proplem D

can someone help me understand why "0110" different that "0011" combination-wise as per problem description?

»
2 months 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

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

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

Can anyone please help why I am keep getting out of bounds and how to fix them? 123386850

»
3 weeks ago, # |
Rev. 5   Vote: I like it -8 Vote: I do not like it

Div2 C

Why the judge answer to this case is NO??

1

6

2 1 2 1 2 1

Sequence of operations to make this case valid.

111222

LRLLRL

121122

LLLRRL

121122

LLRLRL

111222

LLRLRL

111222

RRRLRL

112212

RRRLRL

112212

RRLRRL

111222

RRRRLL

111222

RRRRRR