MrSavageVS's blog

By MrSavageVS, history, 8 days ago, In English

Hello, Codeforces!

NJACK — the Computer Science Club of IIT Patna is excited to invite you to Codeforces Round #956 (Div. 2) and ByteRace 2024 under Celesta — the annual Techno-Management Fest of IIT Patna.

The contest will take place on Jul/07/2024 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

Many thanks to all the people who made this round possible:

You will have 2 hours 15 minutes to solve 7 problems.

UPD: Scoring Distribution: 500 — 1000 — 1250 — 1750 — 2000 — 2500 — 3000

UPD: Editorial

UPD: Congratulations to the winners!

Top 5 (Div 2):
1. _worst_
2. Shirayuki_Noa
3. cynNYCal
4. cocae
5. _furina

Top 5 (Div 1):
1. neal
2. jiangly
3. BurnedChicken
4. turmax
5. Sugar_fan

About Celesta

Celesta is the annual Techno-Management Fest of IIT Patna. Celesta conducts a variety of events in various technical domains. Some of these are open and free for all, with exciting prizes and goodies for the winners!

You can head over to our website and check it out for yourself!

We have had the 2023 edition of ByteRace hosted on Codeforces too. Feel free to have a look: Codeforces Round 845 (Div. 2) and ByteRace 2023

Good luck!

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

»
8 days ago, # |
  Vote: I like it +132 Vote: I do not like it

Special thanks to ScarletS for coordinating the round (and not killing me)!

yet.

»
8 days ago, # |
  Vote: I like it +14 Vote: I do not like it

Auto comment: topic has been updated by MrSavageVS (previous revision, new revision, compare).

»
8 days ago, # |
  Vote: I like it +46 Vote: I do not like it

As a tester, I tested after getting to violet :)

»
8 days ago, # |
  Vote: I like it +41 Vote: I do not like it

As a tester, I was told to farm contribution here

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    He he big brain move

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

NJACK orz

»
8 days ago, # |
  Vote: I like it +44 Vote: I do not like it

As a tester, the problems are nice and you should read them all!

»
8 days ago, # |
  Vote: I like it +113 Vote: I do not like it

When you realize that you're rickrolled by the announcement

»
8 days ago, # |
  Vote: I like it +59 Vote: I do not like it

As a tester, I can confirm that writers have brainrot

»
8 days ago, # |
  Vote: I like it +29 Vote: I do not like it

As a problemsetter, all the problems are really cool and interesting. Wish all the participants a large positive delta and a fun experience.

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

finally SyndryVictory round

»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

As a tester, wait I didn't tested it well I belong to IIT Patna and NJACK so I am just happy.

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

    I am now at 1399 after this contest no one can ever imagine how much I love codeforces.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You will most likely get specialist after they remove cheaters :O

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

On behalf of all the missing newbies and negative testers, I can say that this round is going to be awesome!

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

As a participant, I can confirm that the testers are crazy!

»
8 days ago, # |
  Vote: I like it +57 Vote: I do not like it

Rick Astley is mentioned in the blog!

»
8 days ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

Will try to reach as near to CM as possible

»
7 days ago, # |
  Vote: I like it +70 Vote: I do not like it

Did I just get rickrolled?

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

FINALLYYYY!!!!

»
7 days ago, # |
  Vote: I like it +13 Vote: I do not like it

As a tester, testing this round was tasty, although I did it in hasty.

»
7 days ago, # |
  Vote: I like it +28 Vote: I do not like it

As a tester, f*ck the cheaters!!

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

As a participant, I am getting a vibe that this contest is going to be great :)

»
7 days ago, # |
  Vote: I like it +9 Vote: I do not like it

As a participant, I can confirm that MrSavageVS is indeed Savage.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Feeling excited :)

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

very excited for this contest.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I dare you to write down red highlighted character! -_^

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by MrSavageVS (previous revision, new revision, compare).

»
7 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Why no author pics, Lets continue the tradition.

»
7 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Ayo thats stealthy. Rick rolled us.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, the problems are nice and you should read them all!

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

All the events on the website are dated 2023 -_-

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

NJACK orz

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

IndianFORCES

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

Rick Astley orz

»
7 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Did you just rickroll us?

»
7 days ago, # |
  Vote: I like it -21 Vote: I do not like it

Ratings for problem prediction:

A:800 B:2500 C:2600 D:2700 E:3000 F:3200 G:3500

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

The poster in blog is very attractive and catchy!

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

IITPforces

»
7 days ago, # |
  Vote: I like it -6 Vote: I do not like it

Scoring distribution: 100 5000 6000 7000 8000 9000 10000 skul

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

AI generated banner lmao

»
7 days ago, # |
  Vote: I like it +5 Vote: I do not like it

nice rickroll.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, what should I do?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

never gonna give you up...

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks to all

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope they will take cheating seriously.

»
7 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Expecting great problems from IIT Patna

»
7 days ago, # |
  Vote: I like it +11 Vote: I do not like it

wtf epic games hosted a cf round and now celeste??!!11!1!

»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

7/7/24 .. 7 problems .. thala for a reason

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

It took me a couple of minutes to find out how I got rickrolled.

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Okay thanks :')... Ig you're the 4th person to rickroll me...

»
7 days ago, # |
  Vote: I like it -12 Vote: I do not like it

Seven questions in total? I need the score distribution to decide whether to participate in this competition

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

This is like the best rickroll I ever got tbh.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited for this!!!

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

excited for this contest!

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

As a tester, I'd say problems are crisp and interesting. All the best!!

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

Let me blue. I beg u

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

Where is the credit to Rick Astley?

»
6 days ago, # |
  Vote: I like it +19 Vote: I do not like it

Scoring distribution when?

»
6 days ago, # |
  Vote: I like it +18 Vote: I do not like it

Dear Mr Savage MrSavageVS, are you planning to update score distribution later than the contest end?

»
6 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Please update the scoring distribution.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone !

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Rick Astley lol

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i hope i reach pupil

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Auto comment: topic has been updated by MrSavageVS (previous revision, new revision, compare).

»
6 days ago, # |
  Vote: I like it +5 Vote: I do not like it

will try to reach newbie

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

red letters spell rick astley gl to every1

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

how to participate in celesta

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

Hope B be segment tree+dp

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

my target : solve one question

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited for this round! Let's solve some interesting problems together!

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

rickrolled!

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's Gooo.. Participating in a rated contest after 9 months :)

»
6 days ago, # |
  Vote: I like it +10 Vote: I do not like it

I predict this round is going to be mathforces.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

After over 7 months of inactivity, I am coming back to demote. cya in the tutorials ;D

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Cannot submit code even registered. logout/in cannot work.

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

thank you a lot for your great effort but the problems are not beautiful. I am sorry but now I just want to not become nwebie again[standings:1983]

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets Goo!! Let's GOOO

Did my best

I hope my solution for all Problems pass the system test

»
6 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Mathforces round

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

    I coded by hoping my approaches were correct.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      someone famous proved that there are unprovable facts

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

    True, But there were observations that made the maths part skip

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

    After I saw the authors, I was ready for round like that. But, since I don't really care about my rating I decided to participate anyway.

    I have to admit: this round has nothing to do with programming for problems A-E. Maybe only problem C is at least not about math. So, as was discussed in the recent post about "the fall of Codeforces", I am pleased and honored to give this contest my sincere dislike.

    • »
      »
      »
      6 days ago, # ^ |
      Rev. 2   Vote: I like it -22 Vote: I do not like it

      yeah. its just some useless observations. No programming required. Should rename the site to stupidpuzzleforces.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it -42 Vote: I do not like it

      I think you are not smart enough to judge.They all are Iitian.

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

        he is CM and was grandmaster a few years ago. most iitians are not even expert.lol. Being an iitian doesnt mean u r smart. Also no one outside india care about IITs.

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
          Rev. 2   Vote: I like it -24 Vote: I do not like it

          Why do you feel being expert is the indication of being smart and why should all IITians should do CP. I am pretty much amazed by your comment. We IITians are engineers, we do solve the technical and real-life problems which society asks us and contributes a lot in development of technology.

          I can again smell the jealousy inside you by your statement of "_No one cares about IITs outside India_" . I guess you should get some exposure to the world, kid. The value IITs have in world is remarkable, and the entrance exam JEE Advanced is meant to be one of the toughest exams in the world and people really toil hard to solve that paper.

          I can understand your frustration by the comment by system_check_account, but please do think before you text.

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

            lol, mf I am an iitian, Thats how I know most of us are not exactly smart. Spending 2 years of your life mugging up stuff and having no life doesnt make you smart. Also people like you who make their entire personality as "I am iitian" is an embarrassment to all of us. The only people who are jealous of us are a few nerds who couldnt clear jee.No one else gives a shit.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      sir i need ur advice i m passing to second year bachelor computer science

      and for now all i know in dev

      some html css and a little js

      should i focus more on dev or keep grinding cp

      or should i quit codeforces and start practing on leetcode

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

    Ohh please shut-up, i abhor comments like these. CP encompasses alot of things which includes Maths and If a contest happens to comprise of only one of those things i don't think that should be a problem, you didn't come here to write best selling novels.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      its not even math. its just pattern recognition and guessing. thats it. lol. such terrible questions.

»
6 days ago, # |
  Vote: I like it +24 Vote: I do not like it

why does D exist?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do B?

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

    Sum in every rows and columns must be equal modulo 3

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    summation for all row and col in grid A and Grid B mod 3 if equal then yes

    else No

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

      But why ?

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

        Because each conversion does not change the sum in the row and column modulo 3

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

          This only proves one direction; it doesn't prove that every matrix $$$b$$$ can be reached from $$$a$$$ if the sum in each row and column are equal $$$\mod 3$$$ though!

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I just believed it worked)

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you please explain the approach ?

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah that's the only hard part to proving the solution. Figuring out that the parities of sums and columns mod 3 can't change is pretty obvious.

            I have no idea how to prove that every matrix that meets the above conditions can be reached, but I think it's a similar question to determining whether or not a rubik's cube with a certain arrangement of colors can be solved.

            https://puzzling.stackexchange.com/questions/53846/how-to-determine-whether-a-rubiks-cube-is-solvable

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

            It's very easy to prove that every matrix b can reached from a if the sum in each row and column are equal mod 3.

            Always take a subrectangle that uses the very bottom right of the array as a bottom right corner. Use it to modify the first element of the first row as you wish. You don't care what happens on the first element of the last row and the last element of the first row. Then do the same of the second element, again you don't care about the last row and the last column. At the end you set up everyone correctly except the last row and the last column. However since the sum of row 1 is the same in a and in b and is an invariant, the last element of row 1 is necessarily set up correctly. Same for all the elements of the last column and the last row.

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you, very nice proof. I think we have different definitions of "very easy" though.

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Nice proof, thanks!

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

                Usually it's other people helping me, feels good to be on that side for once haha

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Then shouldn't it be the diffrence between each position of the two grid creates what matrix,thats row and column?

      • »
        »
        »
        »
        6 days ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        if u take a subrectangle and perform operations multiple number of times in any order than either u will get same subrectangle or the one diagonal will increase by one and other by 2 or one will increase by 2 and other by one and this can be proved very easily.... hopefully this much is sufficient to get the answer

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Then diffrence of two grid should be checked ,isn't it ?

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            no than we just compare elements of both and try to make them equal . only some values can be made fully equal rest values should be such that they should become equal ... lol i am very poor at explaining things but i'll try my best sorry

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

    Something related to invariants.
    What things don't change when you apply operation once?

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

Problems B and D were totally not cool, I just had to guess both of them and I'm not sure which one I dislike more.

Problem C was kind of obvious but felt like: "Do I really have to implement this?"

Problem A: ???, but I guess even an output of 1 2 ... n-1 n works

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i just wrote the same thing on a previous comment lol

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

    Literally me. Nice thing I trusted in my guessing skills

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

      like i am just curious, you are rated very high, do you guys still face some problems while solving B and D? (I just want to know, this is not to mock in any sense cuz i cant i am rated 1200 lol)

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes! it took me 20 minutes in B

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

        I pretty much had the idea since the moment I read the problem, but you have to kinda proof your solution before, and that's what takes time. I got the idea probably because I have been solving a lot of problems, so, you will just get better by practicing

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

    I could prove all of them. I think they were fine problems. Except C, I agree it was somewhat obvious but annoying to implement.

    B: Just do the greedy thing where you update a[i][j] to be equal to b[i][j], and update corners (i,j+1),(i+1,j),(i+1,j+1). Then notice this doesn't alter row or column sums mod 3. At the end you'll have fixed all the positions for 1 <= i < n, 1<=j <m. And if you haven't fixed the rest, you have to have that the columsn/row has different column sum

    D: First notice its not possible if they are not the same as multisets. Then notice if they are the same as multisets, but have repeated elements, it is always possible, because you can rearrange one freely and just swap the same elements in the other. If they have the same elements, with no repeats, you can do coordcompression and turn them into permutations. Then its possible iff they have the same number of cycles mod 2, because swapping two elements in an array either increases or decreases number of cycles in each array by 1, and thus maintains their difference mod 2. So if they have the same number of cycles you can sort both of them, and if they don't you'll never get them to have the same number of cycles, so they'll always be different.

    I also thought E was a very nice problem.

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

      D does not have to be that complicated... all we need to do is check the parity of inversion index of both the arrays and that the arrays are equal after sorting

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Man, looking at the comments make me realise how dumb I am. But one question,how do I learn all of these things. I mean parity, inversions and all these fancy terms?? Is there a good learning site or should I just practice questions and upsolve??

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think you should just solve problems. I had solved this problem a while ago https://codeforces.com/contest/1768/problem/D that uses this technique. I think without that maybe I would not have been able to solve it.

        • »
          »
          »
          »
          »
          5 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Half of these are just fancy terms and not some high-level stuff. Parity just means whether something is odd or even. Similarly, you can search for what the inversion count of an array means. It is not that complicated.

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

            Yeah,I looked at the editorial for D and slowly it all started to make sense,I stopped at the "Inversion count in efficient time" but now I'll go straight to learn it

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        for D I also had a different approach, where I just iterated over the arrays and greedily matched B[i] to A[i]. I kept an array pos that stores the positions of the values in array B, so I could look up the index of the value A[i] in B in constant time and swapped B[i] with whatever element is at pos[A[i]], then swapped arbitrary elements in A in the range [i+1, n) to make the swap operation in B possible. From this you get the invariant that A[j] == B[j] for all j < i. This always works up to n-2, because there is always at least one auxiliary element that can be swapped. After going through 0 to n-2, I check if the last two elements are in correct positions, because if they aren't, there is no way to make them equal, as swapping any element but the last two will break the order of another index.

        I've been thinking about this for a while and I still can't figure out why it actually works, mostly why swapping arbitrary values in A seems to have no impact on the result of the last two elements: 269285999

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm trying to derive a way to determine parity of permutation just from cycles, but some things you said need more address. The fact you said "swapping two elements in an array either increases or decreases the number of cycles in each array by 1". That's true for a permutation (crisscross apple sauce, cycle here, cycle there, yea, it changes by 1), but making cordcompression doesn't make an array a permutation, we just have all a[i] < n. So if after swap my parity didn't change, what does it tell me about an array? 

      The main problem for me is: permutation swap causes a change in parity of inversions and also changes the parity of the number of cycles. Therefore those invariants are intertwined (seems like n + cnt_cycles(p) mod 2 = inversions(p) mod 2). But I didn't try to derive exactly how they are related, because I don't understand how to get the number of inversions just by looking at a cycle decomposition. 

      So I have proven fact for permutations, but this logic crumbles for an arbitrary array since swaps now can change or not change the parity of an array. But if it does not change the parity, does the number of cycles stay the same? And also goes the other direction: if the number of cycles stayed the same, did the parity change? I already did consider some cases (like if we picked two elements to swap and positions are both on a cycle, only one on a cycle, none on a cycle, etc.), but I don't understand how to get the parity of inversions in those cases. Any help appreciated

      tldr. I deduced that for permutation p the following holds: n + cnt_cycles(p) mod 2 = inversions(p) mod 2. But does that hold true for an arbitrary array where a[i] < n?

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I explained how to deal with the non-permutation cases. In those cases, you either have different multisets, in which case you can't solve it, or repeated elements, in which case you always can.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In D, it was given that both arrays contain only distinct integers, which makes it a little easier.

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

    Totally!! Such a poorly written contest, zero quality questions.

»
6 days ago, # |
  Vote: I like it +12 Vote: I do not like it

nice guessForces :)

»
6 days ago, # |
  Vote: I like it +9 Vote: I do not like it

GuessForces

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Stuck at E again.

»
6 days ago, # |
  Vote: I like it +4 Vote: I do not like it

A to D is leetcode medium, E is pain.

»
6 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Very nice problem E! I really liked how the permutations of the balls can be rephrased as weak compositions which makes the probabilities almost trivial.

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

    Can you please elaborate on how you got to weak compositions?

    My issue with the task that I cannot grasp how to calculate how many special balls does alice take on average. I understand that every time Alice passes the turn to Bob and vice versa the amount of regular balls is decreased by 1.

    So if there are 3 regular balls we have 4 moments when one of the players can take special balls


    1) Alice turn, 3 regular balls remaining 2) Bob turn, 2 regular balls remaining 3) Alice turn, 1 regular ball remaining 4) Bob turn, 0 regular balls remaining.

    And when I compare case 1 and 3 for example, I see that Alice has a bigger chance to take a special ball, because there are less balls in total.

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

      So let's label the special balls as * and the regular ones by |. Now every permutation of the balls looks something like this:

      **|*|***||*|**
      AA B AAA  A BB
      

      where A means that Alice takes it and B means that Bob takes it. Now we can view this as representing multiple "bins", separated by |, and containing the * (this is a classic proof in combinatorics, see (https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)) on wikipedia) (this is also the weak compositions of k with n-k+1 terms). Thus we have n-k regular balls, separating n-k+1 bins. Now it is quite easy to see that any such configuration of * and | is equally likely, so any special ball is equally likely to end up in any of the n-k+1 bins. Note that the odd-indexed bins correspond to the ones containing balls taken by Alice, and the even ones by Bob. And we can easily compute the probability that a random bin is odd-indexed (1/2 if n-k+1 is even, ceil(1/2*(n-k+1)) otherwise), which is the same as the probability that some special ball is taken by Alice.

      Please let me know if anything is unclear.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wow B is really cool

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

Yeah guessForces. I couldn't guess B but guessed D lmao.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there some edge case in C? My code was failing on pretest 7

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

oh boy, I sure hope my python hashmap solution for D doesn't FST

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG I new F but no time

»
6 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Answer for $$$E$$$ is (sum of special values)*$$$\left(\frac{\lceil \frac{n-k+1}{2} \rceil}{n-k+1} \right)$$$ + (sum of non-special values)*$$$\left(\frac{\lceil \frac{n-k}{2} \rceil}{n-k} \right)$$$

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain how you get the (sum of special values) * $$$\left(\frac{\lceil \frac{n-k+1}{2}\rceil}{n-k+1}\right)$$$ part?

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

      The sequence of non-special balls picked alternate between Alice and Bob (for a total of n-k moves). We can insert the special balls in any gaps (n-k+1 in total). Half (the ceiling expression to be precise) of them precede Alice's choice of a non-special ball, which is precisely the special balls chosen by Alice. All the gaps are equally likely for a special ball to be placed.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks!

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had this idea during the contest, but I could not figure out the probability distribution of the positions the special balls are placed in. How would you justify that all of the gaps are equally likely for a special ball to be placed?

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

          I don't know if its useful, but, imagine every turn is a box, like this: Alice's turn | Bob's turn | Alice's turn | ...

          Any distribution of the special balls on the boxes corresponds to a posible game, every game is diferent, and should have the same probability out of a random game (ignoring the normal balls). So given a game, what's the probability of the i-th special ball falling onto first box? Well, it could have fall into any of the n — k + 1 boxes, and there is no any other restriction, so every box has the same probability which is 1 / n — k + 1. The you count Alice's number of turns, and Bob's number of turns and you got it.

          Let me know if there's something still missing.

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

            I see. But I don't think this

            so every box has the same probability which is 1 / n — k + 1

            is a trivial statement. For example, for the first box, the probability of ball $$$j$$$ (or any ball) falling into it is

            $$$\sum_{i=0}^{k-1} P[\text{i sb chosen before j}] P[\text{j chosen}] = \sum_{i = 0}^{k-1} \left(\frac{(k-1)(k-2)\cdots(k-i)}{n(n-1) \cdots (n-i+1)}\right) \frac{1}{n-i}$$$

            For the second box, this number would be a lot more complicated. I really don't see how you would mathematically show that all of these are 1 / (n-k+1). Maybe I'm just overthinking it.

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

              I don't really understand your formula. I think you are omitting, or maybe it's what you're asking, the fact that the probability of the distribution of a special ball is NOT affected by the distribution of other special balls or the distribution of the non-special balls. As it is nos affected, you can ignore the other special balls, and calculate the probability of choosing a random gap between n — k + 1 gaps.

              It's hard to explain why the special balls don't affect each other rather than asking why would them affect each other? Mathematically, generating the formula having all in mind, simulating the process, we may not see how we end up with the probability being just equal, but it is because we are ignoring that other balls don't matter

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

      You can find this in another way as well.

      first of all you have to understand that

      expected number of points = expected number of special values * average of special values + expected number of normal values * average of normal values

      Now how to find the expected number of special values and the expected number of normal values?

      I basically used a $$$2 \cdot N^2$$$ DP to generate the formula.

      The Dp problem was if it is my turn and there are $$$x$$$ special values and $$$y$$$ normal values, what is the expected number of special values and normal values I will get?

      You can easily solve this in $$$2 \cdot N^2$$$ .

      Note that you don't need to use large N :)

  • »
    »
    6 days ago, # ^ |
      Vote: I like it -7 Vote: I do not like it
    spoiler
»
6 days ago, # |
  Vote: I like it +13 Vote: I do not like it

I don't know why people are calling this contest GuessForces, A, C and D were easily provable. However, I guessed B, does anyone have a proof of the solution?

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

    If D is easily provable during the contest then it's time for me to lay off the competitive programming

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

      For D I "simulate" the process of swapping. I could use the operation of length $$$2$$$ on array $$$b$$$, and I will try to make $$$b$$$ equal to initial $$$a$$$ after those operations. If the number of operation I used is even, then the answer is NO, and YES otherwise. This is because when we used the operation on array $$$b$$$, we can used it in $$$2$$$ adjacent elements of array $$$a$$$. Then the array $$$a$$$ will be unchanged after even number of operations.

      For example if $$$a$$$ is [1, 2, 3, 4, 5] and $$$b$$$ is [1, 4, 2, 5, 3] then $$$b$$$ will be like this after the operations: [1, 4, 2, 5, 3] -> [1, 2, 4, 5, 3] -> [1, 2, 4, 3, 5] -> [1, 2, 3, 4, 5]. Meanwhile, $$$a$$$ will be: [1, 2, 3, 4, 5] -> [2, 1, 3, 4, 5] -> [1, 2, 3, 4, 5] -> [2, 1, 3, 4, 5] (we keep swapping the first and the second element of $$$a$$$). As we can see, the number of operation is odd, so the answer is NO.

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

        This is a solid solution, however I applied the following:

        • See a "NO" answer for cases with 1 even-length cycle
        • See a "YES" answer for a case with 2 even-length cycles
        • Do a silly case of a =1 2 3 and b =3 1 2 on paper by hand
        • Make a wild guess that odd-length cycles don't affect the answer, and in case of odd number of even-length cycles the answer is "NO"

        Never stop guessing

        To clarify, I don't think that this method of solving problems is good, but it is what it is when it comes to codeforces nowadays

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

        I have the same approach in mind , but I am having trouble implementing it, can you please shed some light on the implementation.

        For now what I think is, I will store all occurrences of every number in a vector of vector , or set<int, vector> , then I will just calculate the number of positions required to shift a number at index 'i' in array B to its concerned position in array A, however , when I am shifting an element to its left side, then all the elements to its left will be shifted to the right by 1 index. I am having trouble in optimizing this to O(nlogn) or O(n). Any help will be appreciated.

        EDIT: Counting the number of inversions for both the given permutation worked!!

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Okay so assume we move elements of $$$b$$$ to match $$$a$$$ from left to right. Supposed we want to move a $$$b_j$$$ to the position $$$i$$$ on the left. Then the operations count will be added by $$$j-i-1$$$. After that, we need to shift all the elements in range [i, j — 1] to the right. It just like adding $$$1$$$ to the value of the position in range [i, j — 1], which can be done by segment tree or fenwick tree (DM me if you have hard time understanding it).

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

        If we try to sort both 'a' and 'b' using adjacent swaps and check parity of no. of operations to sort 'a' and 'b', if their parities are the same, the answer is "YES" otherwise "NO". Will this also work? UPDATE It did work!

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

      The main point I used in proving $$$D$$$ is that every swap between elements at positions $$$i$$$ and $$$j$$$ ($$$i<j$$$), can be achieved using $$$2\cdot (j-i)-1$$$ adjacent-element swaps, i.e., by moving the $$$i^{th}$$$ element all the way right to $$$j$$$, then moving the $$$j^{th}$$$ element (which is now at $$$j-1$$$) all the way left to $$$i$$$.

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

      With some well known facts it is. Proving that two permutations must have same parity is trivial when you know that making swap always changes the parity. To prove that it is sufficient you can use the fact that every permutation can be decomposed into some swaps of adjacent elements, and the parity of the permutation is equal to the parity of the number of those swaps. So, if the parity is the same, you can decompose both permutations and eliminate those swaps one-by-one.

      But of course, you need to know something

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

    The main point I used in proving $$$B$$$ is that that any sub-rectangle can be achieved by using sub-rectangles of size $$$2\times 2$$$., i.e., applying the $$$2\times 2$$$ sub-rectangles from right to left for every row from top to bottom will achieve the same effect of using the large sub-rectangle at once.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how do you prove D ?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is easy to see that the sums modulo 3 of each row and column are preserved. We can use the following simple algorithm to convert matrix $$$A$$$ into $$$B$$$ if they have the same row and column sums:

    for i = 1 to n - 1:
        for j = 1 to m - 1:
            If A[i][j] = B[i][j] then we are good.
            Otherwise, apply the operation to A[i, i+1][j, j+1]
            (2x2 matrix with top-left corner i,j)
            increasing by (B[i][j]-A[i][j])%3 to 
            convert A[i][j] to B[i][j]
    

    It is clear that the first $$$(j-1)$$$ elements of each row become correct. But since the sum of each row is preserved, and we assumed that $$$A$$$ and $$$B$$$ had the same row sums, therefore, the last value will be correct as well. By similar reasoning, the last row will also be correct after the first $$$(i-1)$$$ rows have been fixed.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assume sum of every row/column of A equals to B modulo 3. This is a necessary condition since operation doesn't doesn't change sum of rows/cols modulo 3 (1 + 2 = 0 mod 3, nicely explained lol). Then start greedy algorithm using 2x2 rectangle. If a[i][j] != b[i][j] then apply 2x2 putting a[i][j] element in the left corner of operation until we are equal. We will get a (n — 1) * (m — 1) correct submatrix in the upper left corner (by correct I mean a[i][j] == b[i][j] for all 1 <= i <= n — 1 and 1 <= j <= m — 1) . But the remaining elements (last column and last row) would be also correct since we sum of rows/columns of A and B are equal. Therefore it is enough to just check equality of rows and columns modulo 3 since greedy will always make them equal

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A ?

»
6 days ago, # |
  Vote: I like it +216 Vote: I do not like it

How developers comment their code:

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

problem B don't seem to be the guessing type but it seems that any hard matrices problem in this rating should be guessing and that's actually what I have learnt today, next time if I see a hard matrices problem in B then it's definitely guessing thanks for the author I really learnt something new today!

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

    it's not guessing. You can use 2x2 matrices as building block for any matrix. Also twice a matrix in form [[1, 2],[2, 1]] gives you the other type of matrix

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what about [[1, 1],[1, 1]] and [[2, 2],[2, 2]] ?

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you can't make those matrices by themselves, you need to change other entries. You can make a 3x3 matrix of ones, but not a 2x2 one

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There are only two types: guessing and remembering

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How come, the solution to 2nd pretest solution NOT be — Alice:[3,4], Bob:[5,6],Charlie:[1,2]? My code was failing with 2nd pretest, for this mismatch. I believe, above blocked answers can be rearranged too! 2nd Pretest:

6 1 2 3 4 5 6 5 6 1 2 3 4 3 4 5 6 1 2

»
6 days ago, # |
  Vote: I like it +4 Vote: I do not like it

CringeForces

»
6 days ago, # |
Rev. 4   Vote: I like it +59 Vote: I do not like it

A: Obviously a[i]=i satisfies the condition.

B: Let c[i][j]=a[i][j]-b[i][j] and we need to make c[i][j]==0. Let row[i] be the sum of i-th row, col[j] be the sum of j-th column. Notice that every operations don't change row[i] and col[j], so they must be 0 initially. In fact, if row[i]==0 and col[j]==0 initially, we can make c[i][j]==0 by operations on 2x2 subrectangles.

C: There are 6 possible relative orders of l_a, l_b and l_c, we can find the answer by brute force for all possible orders.

D: Each operation will change the parity of inversion number of a[i] and b[i], so they must be the same initially. If they are same initially, we can sort a[i] first, and b[i] will be an array with even inversion number, and we can sort b[i] by swapping adjacent elements, while swapping a[1] and a[2] repeatedly.

E: Let S1 be the sum of special balls, S2 be the sum of normal balls. If we let p1 = the probability Alice can get i-th ball when i<=k, p2 = the probability Alice can get i-th ball when i>k, then ans=S1*p1+S2*p2. For n-k normal balls, Alice and Bob will take a normal ball alternately, so p2=(ceil((n-k)/2)/(n-k)). For the i-th special ball, Alice can take it if there are even normal balls be taken before it. The number of normal balls taken before a certain special ball can be any integer in [0, n-k] with equal probability, and p1 is the portion of even numbers in this range, which is (ceil((n-k+1)/2)/(n-k+1)).

F: Let's find the answer by binary search: For certain number A we need to calculate number of pairs (i, j) where i<j and a[i, j]<A. Let f(i) be the minimum j where i<j and a[i]^a[j]<A (if not exist f(i)=n+1), then the number of valid pairs will be sum(1<=i<n)(n+1-min(i<j<=n)(f(j))). We can calculate f(i) with binary trie: Let r be the highest bit where (a[i]^a[j]) is 0 and A is 1, then valid values of a[j] will be corresponding to a node of the trie.

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

    what do you mean by this because it's not clear -> Notice that every operations don't change row[i] and col[j]

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

      The change of values in one operation will be like this:

      0 0 0 ... 0 0 0

      ...

      0 1 0 ... 0 2 0

      ...

      0 2 0 ... 0 1 0

      ...

      0 0 0 ... 0 0 0

      Where the sum of each column and row is 0 or 3, which is 0 modulo 3.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For D how do you calculate inversion number

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

    When I first read your explanation of E, I thought you were wrong at something. Then I returned to the problem and saw a very important thing:

    The first k balls are special

    While I'm thinking about those k indices could be random.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did the same. Struggled to simplify the 2D recurence

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

    Would it be true to say that for problem D if there weren't the additional constraint that all elements were distinct, then we could always transform a in b if there is an element that appears twice? (since we can do dummy-bubble-sort-like-operations on two identical elements once one is sorted and the other isn't (and actually do bubble sort on the other one)).

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, assuming that a and b contain the same elements

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

    my solution for D was as follows:

    let's say that we want to fix a and convert b to it

    we can every time do two swaps on b without affecting a, by choosing the same two indices in a in both of those two swaps(for example, we can simply choose 1 and 2 in a every time we do a swap)

    now start from the beginning or the end of the array b and convert it to a by doing swaps

    if the number of required swaps is even, then answer is yes. otherwise, answer is no

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't I use lazy segment tree, to find the minimum of a range and update xor in range

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

    G: use HLD, then it turns into solving queries with parameters l, r, c of sum a[i + x] xor (x + c) for l <= i <= r.

    If you're able to solve queries with c = 0 and r — l + 1 = 2^p for some p, then you can break the query down into queries of power of 2 by doing:

    We can solve a query of r — l + 1 = 2^p when 2^p is smaller or equal to the smallest bit in c or c is 0 by solving it for that range with c = 0 then fixing the bits higher than 2^p. So do that to carry over the bits as much as possible (do query of smallest set bit length while it would be a subarray). After that, we can do binary lifting.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The number of normal balls taken before a certain special ball can be any integer in [0, n-k] with equal probability.

    Could you explain the intuition behind this? I can't prove it.

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

      Assume the order of balls are randomly shuffled before game starts, and each turn players take the first remaining ball. Then for a certain special ball, let's ignore all other special balls, we need to shuffle it with n-k normal balls randomly, it can be arranged from 1-st position to (n-k+1)-th position with equal probability, which means, the number of normal balls before it, is uniform distribution on [0, n-k].

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

    HLD isn't needed for G, solve for each bit separately. Consider the $$$k$$$-th bit, for a path $$$v_0$$$->$$$v_1$$$->$$$\ldots$$$->$$$v_n$$$. the numbers in $$$[0,2^k-1]$$$ will have the $$$k$$$-th bit off, $$$[2^k,2^{k+1}-1]$$$ will have the $$$k$$$-th bit on so on and so forth alternating in blocks of length $$$2^k$$$.

    So this leads to the idea of splitting the path into blocks of size $$$2^{k}$$$. Then $$$a(v_i) \oplus i$$$ will have the $$$k$$$-th bit on if $$$i$$$ belongs to a even block and $$$v_i$$$ has the $$$i$$$-th bit on ($$$i$$$ mod $$$2^{k+1}$$$ $$$< 2^k$$$ and $$$v_i$$$ mod $$$2^{k+1}$$$ $$$\geq 2^k$$$) or vice versa. To count how many xor in the path has the $$$k$$$-th bit on, you can precompute $$$f(k,u)$$$ = how many $$$i \oplus v_i$$$ have $$$k$$$-th bit on if $$$v_0,v_1,v_2\ldots,1$$$ is the path from $$$u$$$ to root.

    I am omitting some details, but $$$f(k,u)$$$ is enough to compute everything with some additional path queries. Eg for a path $$$a$$$ to $$$b$$$ where $$$b$$$ is an ancestor of $$$a$$$, let $$$p(i,v)$$$ be the $$$i$$$-th ancestor of $$$v$$$. To compute the number of xors on the path with the $$$k$$$-th bit on, first take $$$f(k,a) - f(k,p(c2^{k+1},a))$$$ where $$$c$$$ is the biggest integer such that $$$p(c2^{k+1},a)$$$ is still below $$$b$$$, we are left with the path $$$p(c2^{k+1},a)$$$ to $$$b$$$ that is still unaccounted for but it can be counted in by at most 2 path queries of the form: How many $$$a_{v_i}$$$ in a path $$$v_0,v_1,\ldots,v_n$$$ has the $$$k$$$-th bit on?

    edit: The sol is $$$n \log n$$$ but very unpleasant to implement, during testing I passed with a simpler and nicer $$$O(n\sqrt{max_{a_i}})$$$ but authors decided to block that :(.

»
6 days ago, # |
  Vote: I like it +22 Vote: I do not like it

I hate Cloudflare, my submission in the last 10 seconds for C doesn't considered because of it

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

couldn't solve B, still have 0 clue whatsoever.

completely loss hope in CP.

like is there any chance to improve? even slightly

solve 600+ problems in cf still fail, it must be IQ issue.

  • »
    »
    6 days ago, # ^ |
    Rev. 2   Vote: I like it -35 Vote: I do not like it

    check my solution:

    Your code here...
    #include <bits/stdc++.h>
    using namespace std;
    
    #define ll long long
    
    bool check(vector<vector<int>> &c)
    {
        int n = c.size();
        int m = c[0].size();
    
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = 0; j < m - 1; j++)
            {
                if (c[i][j] == 1)
                {
                    c[i][j] = 0;
                    c[i][j + 1] = (c[i][j + 1] + 1) % 3;
                    c[i + 1][j] = (c[i + 1][j] + 1) % 3;
                    c[i + 1][j + 1] = (c[i + 1][j + 1] + 2) % 3;
                }
                else if (c[i][j] == 2)
                {
                    c[i][j] = 0;
                    c[i][j + 1] = (c[i][j + 1] + 2) % 3;
                    c[i + 1][j] = (c[i + 1][j] + 2) % 3;
                    c[i + 1][j + 1] = (c[i + 1][j + 1] + 1) % 3;
                }
            }
        }
    
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (c[i][j] != 0)
                {
                    return false;
                }
            }
        }
        return true;
    }
    
    int main(int argc, char const *argv[])
    {
    
        int t;
        cin >> t;
        while (t--)
        {
            int n, m;
            cin >> n >> m;
            vector<string> a;
            for (int i = 0; i < n; i++)
            {
                string tmp;
                cin >> tmp;
                a.push_back(tmp);
            }
    
            vector<string> b;
            for (int i = 0; i < n; i++)
            {
                string tmp;
                cin >> tmp;
                b.push_back(tmp);
            }
    
            vector<vector<int>> diff(n, vector<int>(m, 0));
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    diff[i][j] = ((b[i][j] - '0') - (a[i][j] - '0') + 3) % 3;
                }
            }
    
            // for (int i = 0; i < n; i++)
            // {
            //     for (int j = 0; j < m; j++)
            //     {
            //         cout << diff[i][j] << " ";
            //     }
            //     cout << endl;
            // }
    
            if (check(diff))
            {
                cout << "YES" << endl;
            }
            else
            {
                cout << "NO" << endl;
            }
        }
    
        return 0;
    }
    
    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I smell ChatGPT

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        nah bro, i just tried to make every element of the difference array equal to 0 by applying the optimal operation on a 2X2 subrectangle.

        This problem ate so much time, i have code C written but was unable to submit it as contest went over.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

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

    i am with you

»
6 days ago, # |
  Vote: I like it +5 Vote: I do not like it

How are there more than 3k submission for D

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

    Cheaters.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Exactly

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

      I found this (FYI after the contest), which had a link to this. The cheating is insane.

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

        That's craziness. On leetcode, the cheating has gotten so bad recently that 2k+ people solve Q4s that are worth 7 — 8 points. Just a few months ago, <500 people would solve such problems.

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

    I also think it's because of cheaters. When authors give round where problem D require no implementation, it's a green light for cheaters.

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

    I got D... But I couldn't figure out B haha... I think I just couldn't understand how to get B... My implementation of D is quite obscure because I just count the parity with merge sort... But I didn't know what else to do... I'm sure other people implemented better solutions than mine. (And I tried afterward to use the same thinking with parity with B... But it's so complicated with the diagonals so I didn't have time...

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

todays B>>>

»
6 days ago, # |
  Vote: I like it +3 Vote: I do not like it

problem B, is not Trivial at all.

Problem C was much easier then B, don't know why they thought about putting B in the contest.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We notice that after an operation, the sum of a row doesn't change modulo 3 because one element is incremented by 1 and one element is decremented by 1. However, I do agree that this shouldn't be in the contest, because it seems more like a Math Olympiad problem rather than an actual coding problem.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem B — stupid greedy algorithm

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how?

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Just apply the operation to each 2x2 matrix so that the upper left corner coincides with the cell being processed, process all the cells except the last column and the last row, if after checking the operations the matrices are equal, then the answer is yes, otherwise no

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how is this considered greedy and not guessing ? I mean the 2x2 thing

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This problem ate so much time, i wrote C but was not able to submit on time.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

:(

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i had to ask for screenshot of Problem A in errichto server due to cloudfare stuck in a loop. M1 and M3 weren't showing latex and M2 didn't work.

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

Man, if only I hadn't wasted 1hr on that goofy ahh problem B I could've gotten more points for C and D :')

»
6 days ago, # |
Rev. 4   Vote: I like it +44 Vote: I do not like it

i ended up solving E where any k balls are special instead of the first k balls ;_; (SERIOUSLY THEY COULD HAVE JUST ADDED THE WORD FIRST RIGHT ON TOP)1.

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

    The statement doesn't mention that the first k balls should be special. What do you mean?

    Edit: Just saw it. Problem setters should apologize us for giving those crucial detail just in a very small corner of input LOL.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh my god dude same i just saw it after seeing your comment :/

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate your solution ?

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

    Some people (me included) think that the problem description section should define things like that. Others think the statement includes the other sections as input, output, sample and extra comments.

    Next time try to read everything.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I agree but you better read everything next time

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved A,B and B in 7 minutes.

»
6 days ago, # |
  Vote: I like it +28 Vote: I do not like it

Problem setters need a lesson on the difference between "guesses" and "observations."

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

    What's the difference?

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Guesses are made randomly without thinking, and observations are made with thinking and logic?

»
6 days ago, # |
  Vote: I like it +41 Vote: I do not like it

why it wasn`t stated int the statement of E that the first k elements are special and it was only stated in the input section?

I coded for any k elements and debugged it and calculated the samples manually and read the statement multiple times but at the end of the contest I read the inputs and figured out the first k elements are special.

it should have been stated in the statemen!

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, I remember thinking the problem would be much easier if the first k were special. I didn't see that part and gave up because I couldn't solve it.

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

      I might not be getting something, but if the special elements are chosen at random, the problem almost doesn't change. You just have to calculate the expected value of a sum of $$$k$$$ random elements instead of the sum of the first $$$k$$$.

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        the problem changed A LOT for me (i did eventually solved it both ways and my solutions for both are VERY different)

        • »
          »
          »
          »
          »
          5 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Whats your solution?

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

            you can check my submission for the implementation (it's really bad but who cares)

            but basically my idea is you have k special balls and n-k normal balls

            across all n! cases, you will pick up all special balls the same amt of times and all normal balls the same amount of times (but doesnt have to be the same as the special balls)

            so the solution must be some R = (special sum * special factor) + (normal sum * normal factor)

            let's call a cluster some amount of special balls followed by a normal ball

            any case could be reduced to

            [cluster 1] [cluster 2] [cluster 3] ... [cluster n-k] [special cluster (consisting of only specials)]

            you will pick up the balls in any odd clusters

            -> ceil(n-k)/2 normal balls will be picked up per case

            -> each normal ball will be picked up (n!*ceil(n-k)/2)/(n-k) times

            for special balls, solve for each u -> number of special balls in odd clusters

            the number of ways will be (oddPos+u-1)C(u-1) * (evenPos+(k-u)-1)C(k-u-1) {stars and bars} * k! {k shuffle} * normalBalls! {normal ball shuffle}

            each case will give u special balls, distributed between k balls so the final formula is $$$\binom{oddPos+u-1}{u-1} * \binom{evenPos+(k-u)-1}{k-u-1} * k! * normalBalls! * \frac{u}{k}$$$

            solve for each u from 0 to k and you should be able to calculate the special factor (tho edge case if there arent any normal balls then the output is just [sum, 0])

            the expected value for bob is just S — [alice's expected value]

            \\\\\\\\\\

            my solution for the wrong version does involve a lot of combinatorics spam

            expected values for each where alice recieves sA effective special balls (special balls that arent the last) and bob receives sB ESB

            let A,B be the balls alice and bob picked up respectively (this is easy enough to calculate)

            let S be the sum of balls

            let v = $$$\binom{A-1}{sA} * \binom{B-1}{sB}$$$

            (v is the number of combinations of special balls)

            alice: $$$\frac{v*((n-1)!*S*A)}{n! * \binom{n}{k}}$$$

            bob: $$$\frac{v*((n-1)!*S*B)}{n! * \binom{n}{k}}$$$

            (no proof since it's absurdly long)

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You are right my solution for these two versions wasn't different that much but the fact that I read the statement multiple times and checking the samples manually is very frustrating. and there is no reason that it wasn't stated in the statement when most of people just ignore the input section because it is just about the input of the problem not the statement of it.

»
6 days ago, # |
  Vote: I like it +7 Vote: I do not like it

C is obvious right from the start, just painful to implement. While B is definitely not obvious at all.

If the reason that B is placed before C is because it has shorter code to write then it's kind of a lame reason tbh...Obviously problem C is an easier problem, and is more solvable.

»
6 days ago, # |
  Vote: I like it -12 Vote: I do not like it

Won in this speedforces :)

Time to back to CM!

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

For Problem D:

  1. Check if the elements are same in both array.
  2. Minimum Swap to sort the both array should be of same parity (even or odd).

That's it done..................

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B is a weak form of 2015 USAMO Problem 4. FYI for those people asking for proofs.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Completely lost solving B. Feeling low. Still donno why my sol works

»
6 days ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

Proof of D (with some group theory):

First, we need $$$a$$$ and $$$b$$$ to have the same elements (with multiplicity).

Once we have that, each action we perform is just a transposition (i.e. a permutation of the form $$$(i,j)$$$) of the elements of $$$a$$$ and $$$b$$$. We know that

Fact. Transpositions generate the full symmetric group $$$S_n$$$.

So we can get $$$a$$$ to $$$b$$$ with transpositions if we didn't modify $$$b$$$ at all.

Lemma. We can get any transposition as the composition of transpositions that swap adjacent elements.

Proof. Let $$$(i,j)$$$, $$$i<j$$$ be a transposition. Then

$$$ (i,j) = (i,i+1)(i+1,i+2)\cdots(j-2,j-1)(j-1,j)(j-2,j-1)\cdots(i+1,i+2)(i,i+1). \blacksquare $$$

Now there are two cases.

Case 1. If $$$a$$$ and $$$b$$$ have two identical elements, we can get from $$$a$$$ to $$$b$$$.

Proof. First, perform a transposition so that the two same elements are next to each other in $$$b$$$ (it doesn't matter what the corresponding action in $$$a$$$ is). Then perform some permutation to turn $$$a$$$ into $$$b$$$. Since we can decompose it as permutations that swap adjacent elements, let the corresponding action on $$$b$$$ be swapping the two identical elements. $$$\blacksquare$$$

(otherwise the group $$$S_n$$$ acts faithfully on $$$a$$$ and $$$b$$$ by permuting the elements since the elements are distinct, so we may just view $$$a$$$ and $$$b$$$ as permutations)

Case 2. Otherwise, $$$a$$$ can be turned to $$$b$$$ if and only if the parity of the pemutation of $$$a$$$ is the parity of the permutation of $$$b$$$.

Proof. If $$$a$$$ and $$$b$$$ have the same parity, perform the permutation on $$$a$$$ to turn $$$a$$$ to $$$b$$$ (this has even parity). The corresponding action on $$$b$$$ can just be swapping $$$2$$$ adjacent elements, which after doing an even number of times leaves $$$b$$$ unchanged.

If $$$a$$$ and $$$b$$$ have different parity, then each action is a transposition, changing both of their parities to not match again. So they will never be the same. $$$\blacksquare$$$

»
6 days ago, # |
  Vote: I like it +61 Vote: I do not like it

Such a cringe TL for problem F (as far as I can see a very big proportion of the Ac submissions use more than half of it). I wonder what ratio between TL and worst source from testing they decided to use...

»
6 days ago, # |
  Vote: I like it +5 Vote: I do not like it

peak guessforces

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

Well well, todays contest clarified why some newbies might reach expert and eventually fall on their faces to newbie again

»
6 days ago, # |
  Vote: I like it +21 Vote: I do not like it

pls fix the cheating issue, do whatever is required, linking with mobile number, banning codeforces ids of people who do this, pls do something, but stop these cheaters on this platform atleast, just spoils the whole contest,MikeMirzayanov

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

IIT PATNA students ruin this contest agree -> upvote disagree ->downvote

»
6 days ago, # |
  Vote: I like it +1 Vote: I do not like it

TOday was my worst round of CF so far...........got stuck on B and couldn't take chances on C..... Need more practice ig......

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

1983B - Corner Twist is almost coincide with 1119C - Ramesses and Corner Inversion and required same technique to solve MrSavageVS!

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Damn I figured out how to solve E but I didn't have a mod_frac template QvQ

»
6 days ago, # |
  Vote: I like it +9 Vote: I do not like it

Cringeforces + Guessforces, did not enjoy this round at all (or maybe im just mad at the -150 delta t_t)