Блог пользователя MrSavageVS

Автор MrSavageVS, история, 4 месяца назад, По-английски

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!

  • Проголосовать: нравится
  • +211
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится +132 Проголосовать: не нравится

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

yet.

»
4 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

As a tester, I was told to farm contribution here

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

NJACK orz

»
4 месяца назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +112 Проголосовать: не нравится

When you realize that you're rickrolled by the announcement

»
4 месяца назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

As a tester, I can confirm that writers have brainrot

»
4 месяца назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

finally SyndryVictory round

»
4 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

Rick Astley is mentioned in the blog!

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

Will try to reach as near to CM as possible

»
4 месяца назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

Did I just get rickrolled?

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

FINALLYYYY!!!!

»
4 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

As a tester, f*ck the cheaters!!

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Feeling excited :)

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

very excited for this contest.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Why no author pics, Lets continue the tradition.

»
4 месяца назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Ayo thats stealthy. Rick rolled us.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

NJACK orz

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

IndianFORCES

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Rick Astley orz

»
4 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Did you just rickroll us?

»
4 месяца назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Ratings for problem prediction:

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

The poster in blog is very attractive and catchy!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

IITPforces

»
4 месяца назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Scoring distribution: 100 5000 6000 7000 8000 9000 10000 skul

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

AI generated banner lmao

»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

nice rickroll.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a participant, what should I do?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

never gonna give you up...

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck everyone

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Thanks to all

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I hope they will take cheating seriously.

»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Expecting great problems from IIT Patna

»
4 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

This is like the best rickroll I ever got tbh.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Excited for this!!!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

excited for this contest!

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Let me blue. I beg u

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Where is the credit to Rick Astley?

»
4 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Scoring distribution when?

»
4 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Please update the scoring distribution.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck everyone !

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Rick Astley lol

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i hope i reach pupil

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

will try to reach newbie

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

red letters spell rick astley gl to every1

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to participate in celesta

»
4 месяца назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Hope B be segment tree+dp

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my target : solve one question

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

rickrolled!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I predict this round is going to be mathforces.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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]

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Lets Goo!! Let's GOOO

Did my best

I hope my solution for all Problems pass the system test

»
4 месяца назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Mathforces round

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    I coded by hoping my approaches were correct.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      someone famous proved that there are unprovable facts

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится -22 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится -42 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
          Rev. 2   Проголосовать: нравится -24 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится +9 Проголосовать: не нравится

            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.

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

      Deleted

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится -16 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

why does D exist?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do B?

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Sum in every rows and columns must be equal modulo 3

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    else No

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      But why ?

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          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!

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I just believed it worked)

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Can you please explain the approach ?

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится

            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.

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +95 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i just wrote the same thing on a previous comment lol

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Literally me. Nice thing I trusted in my guessing skills

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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??

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

nice guessForces :)

»
4 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

GuessForces

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Stuck at E again.

»
4 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

A to D is leetcode medium, E is pain.

»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wow B is really cool

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

OMG I new F but no time

»
4 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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)$$$

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks!

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 месяца назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              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

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 :)

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится
    spoiler
»
4 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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!!

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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!

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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$$$.

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    how do you prove D ?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve A ?

»
4 месяца назад, # |
  Проголосовать: нравится +216 Проголосовать: не нравится

How developers comment their code:

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There are only two types: guessing and remembering

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

CringeForces

»
4 месяца назад, # |
Rev. 4   Проголосовать: нравится +59 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For D how do you calculate inversion number

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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].

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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 :(.

»
4 месяца назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится -35 Проголосовать: не нравится

    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;
    }
    
    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      I smell ChatGPT

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    .

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    i am with you

»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How are there more than 3k submission for D

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Cheaters.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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...

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

todays B>>>

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Problem B — stupid greedy algorithm

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      how?

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

:(

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 4   Проголосовать: нравится +44 Проголосовать: не нравится

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.

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you elaborate your solution ?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I agree but you better read everything next time

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Solved A,B and B in 7 minutes.

»
4 месяца назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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!

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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$$$.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Whats your solution?

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
            Rev. 5   Проголосовать: нравится +1 Проголосовать: не нравится

            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)

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
4 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

»
4 месяца назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

Won in this speedforces :)

Time to back to CM!

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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..................

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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$$$

»
4 месяца назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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...

»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

peak guessforces

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me which edge case I am missing for question c 269290282

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem D is very similar to this problem, my approach is: if the number of inversions of a has the same parity as the number of inversions of b, and they both have the same elements (sort(a) == sort(b)), then the answer is yes

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can u prove ur fact ?

    • »
      »
      »
      4 месяца назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Kind of proof: (very unclear, sorry) Only do flips of length 1 for convenience since it doesn't change the answer. Fact: all operations are reversable, so you can't do an operation that changes the answer since you can just reverse it. That means, if with some operations we bring the arrays to an obviously impossible place, we know the answer is NO. Let inva and invb be the necessary nb of inversions to sort a and b respectively, then you can start sorting both. Assume you will finish sorting a first (if not just change the variables in the proof). Then b will need invb-inva more operations to finish sorting. If invb-inva is even, you can keep sorting b while flipping the same two elements in a to keep it sorted, if it's odd then a will no longer be sorted by the time b is sorted and it's impossible

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Instead of considering the fact blindfolded that you can swap 2 elements present at the same distance, let us approach it in this way.

      Initial Observation

      It means that essentially you can swap any two elements in both the arrays. (quite intuitive, if not then try doing a dry run on pen and paper. Also can refer to the swapping in Bubble sort.)

      So let us think to bring both the arrays at a particular centralised state. Now this centralised state could be anything. For better understanding, let us take it as sorted.

      Now let's say you are taking X adjacent swaps to sort the first array and Y adjacent swaps to sort the second array.

      Claim
      Proof

      So now, this problem simply boils down to count the number of swaps to bring both the arrays in a centralized state.

      In my code, I considered the centralized state to be array A itself and hence changed array B into array A and calculated the number of swaps.

      Extras

      269287338

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

2nd Question....

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am new to cf(and cc in general as well), this was the first contest here, where I could solve a problem, how many more do I have to give to be rated here.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You will be given a rating in this contest itself, it usually takes a day or two for the rating to be updated.

»
4 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Nice title of E .

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
»
4 месяца назад, # |
  Проголосовать: нравится -78 Проголосовать: не нравится

Poor problems.
A — guess simplest answer, redundant long statement
B — guess to reduce bigger than 2x2 rectangles as obsolete
C — didn't read (statement too long)
D — guess to reduce to simplest greedy

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

»
4 месяца назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Not even in my worst nightmares i could think of solving C as pupil and getting -ve delta.People really ruined this platform.Cheaters better do development,there cheating is valid and allowed(untill and unless you steal).

»
4 месяца назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

looks like problem setters were having constipation and they successfully pooped on today's pset.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For C , first fix the ordering of arrays , then its a dp . For each index j find k ( k <= j ) such that sum[j] — sum[k] >= target ( can be done using sliding window or binary search ) . Now use prefix dp to find if dp[i][j] is valid or not . General solution for any number of arrays

»
4 месяца назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I used chatGPT after the contest.Proof: I didn't submit the solution of D during the contest

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Wow. That is quite surprising actually, and a little concerning too. (although to be fair it didn't know how to find inversions in $$$O(n \log{n})$$$ using segment trees)

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can also find the number of inversions using handwritten mergesort (but I'm not quite sure that this is easier than solution with segment tree)

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I solved it using mergesort. Only need to add 1 code, which is calculate the swap when the element in the left side is bigger than the right side. The rest is the same.

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        number of inversions can also be found using ordered set

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    The setters should really check if the problems are solvable by Chat gpt and gemini before using them in contests

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello Can you give me hint for B

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Try to think of invariants, ie, some property that does not change about the matrix after you apply an operation. For example, one invariant is that the (sum of all elements)mod3 of a matrix does not change if you apply an operation.

    This is not sufficient, but there is another similar invariant that will solve this.

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      is it that

      Spoiler
      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yes! That's absolutely correct :)

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          thanks for your help mate, is this a general strategy for applying operations type of problems? I seem to struggle with those a lot, especially when its a 2D array and you have to pick sub rectangles from it

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            No problem. This strategy is not very common in problems that I have seen. I dislike 2D array problems too as they are not very intuitive. What I find helpful is trying to solve some testcases manually, hoping to see some pattern or hint.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why did this not work:

269283769

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where is the tutorial?

»
4 месяца назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

It would be 10x funnier if the first sentence in E was "Alice and Bob are playing with balls." instead of "Alice and Bob are playing a game."

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can any one give me a hint in problem c?

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I solved it by breaking the problem into 6 cases. A's first B's second, C's last A's first C's second, B's last B's first A's second, C's last B's first C's second, A's last C's first A's second, B's last C's first B's second, A's last Basically you try all of these at the same time and whichever works you can just return immediately. It's quite a boring solution :( and just implementation heavy...

    This was my solution (I didn't use an array because didn't get good sleep last night and was just going to pay close attention to my variables... It probably would have taken a lot less code if I could have thought about the array solution).

    https://codeforces.net/contest/1983/submission/269274852

    Edit

    just a quick note that the comments aren't correct on which things we are modifying because I was too lazy to change the label when I'd copy the block and do a find/replace in my editor to get all 6 cases...

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As a IIITian who couldnt crack IIT, the contest was great :)

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you for this really splendid round! I'm especially grateful for the amount of sample tests and engaging problems. :))) The only complaint I have, is that B was maybe a little bit too rough, aside from that, all things were good.

»
4 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

It would be better if you write important information on the problem state but not the input.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You are right but rickroll in the announcement.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Already their are many cheaters who cheat through telegram or youtube and my making these type of rounds where questions are totally of guessing type and even D question can also be solved by chatgpt just increases the amount of cheating.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please tell that in this contest second question I coded is running on vs code with correct output but when submitting on platform it is telling wrong answer on 1st testcase but it is running on vs code

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    because there might be few logical errors which got caught in the pretests

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ok so is it that vs code not detected but it did?

      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        No it's not like that, here we have online Judges which has more test cases which aren't given to you and you've to pass those all to get Accepted. At VS Code you just passed the given Test cases from the questions

        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I know that but on the the testcases shown to us code is giving same ans on vs code but here not

          • »
            »
            »
            »
            »
            »
            4 месяца назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Why don't you actually copy & paste examples when you test it? The way your code gets inputs is wrong, because each row of the grid is given without spaces between the elements, so `cin >> a[i][j];' will try to read the whole line as a single integer and not digit by digit.

            It must've been a tough work of manually typing the whole example even with adding spaces...

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem C, has anyone solved it using concept of sliding window? My approach was finding all the windows of sum k for alice, bob and charlie. After that, finding the non-overlapping ranges bw them.

Code

But I was not able to implement it fully. Kindly help me out with my query or tell if I am thinking in wrong direction.

Thanks.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You don't need sliding windows. You just need to iterate from 0 to N, assign the cakes to Alice until the $$$sum \geq \frac{tot}{3}$$$. Once the condition is satisfied, there is no point to give more cakes to Alice. So you can move to assigning the cakes to Bob, until Bob's $$$sum \geq \frac{tot}{3}$$$, then go to Charlie.

    The order of who you assign is important. Maybe assigning (Alice -> Bob -> Charlie) doesn't work, but (Charlie -> Bob -> Alice) works. Therefore, you just need to check every possible order. If none of them works, then you cannot assign the cakes to satisfy the constraint.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In my submission 269266307 I used a sliding window in combination with dp. I used a dp array for each person, that contained from where to where should a peace of cake be cut (dp[i] = j, where i is the start of the peace and j is where it should end). To then actually generate the dp array i used a sliding window (but I think it can all be bruteforced). After the dp array is generated try all 6 possible orders of people (ABC, ACB, BAC...).

    Hope this helps (even though my implementation isn't that clean)

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

for problem number D: I find that simply swapping the numbers with their correct position in sorted array and counting those for both arrays give the result without using any segment tree or merge logic: submission

#include <bits/stdc++.h>
#define ll long long
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int>a(n) , b(n);
    unordered_map<int,int>mp1 , mp2;
    for(int i = 0 ;  i < n ; i++){
        cin >> a[i];
        mp1[a[i]] = i;
    }
    for(int i = 0 ;  i < n ; i++){
        cin >> b[i];
        mp2[b[i]] = i;
    }

    for(auto it : mp1){
        if(mp2.find(it.first) == mp2.end()) {
            cout << "NO" << endl;
            return;
        }
    }

    vector<int>sa,sb;
    sa = a , sb = b;
    sort(sa.begin(), sa.end());
    sort(sb.begin(), sb.end());
    int c1 = 0 , c2 = 0;
    for(int i = 0; i < n ; i++){
        if(sa[i] == a[i]) continue;
        mp1[a[i]] = mp1[sa[i]];
        swap(a[i] , a[mp1[sa[i]]]);
        c1++;
    }
    for(int i = 0; i < n ; i++){
        if(sb[i] == b[i]) continue;
        mp2[b[i]] = mp2[sb[i]];
        swap(b[i] , b[mp2[sb[i]]]);
        c2++;
    }

    if((c1 % 2) == (c2 % 2)){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }
 
}


int main() {
    
    int T;
    cin>>T;
    while(T--){
        solve();

    }

}
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good luck next time in div 3!

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How you solve 4 problems within 1 min in last contest ShivanshJ? Any tips

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

B and 1119C - Ramesses and Corner Inversion are basically same problem. Difference is mod 2 and mod 3.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I recently received a plagiarism flag on my solution for problem D in this contest. I believe this is a misunderstanding, as the solution is straightforward and widely known. The problem and its solution closely resemble problem 1591D, which is why many solutions might appear similar.

Given the simplicity and commonality of the approach, I kindly request a review of my submission to consider the context and remove the plagiarism flag. Thank you for your understanding.

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

This in regard for the my solution to problem 1983D of this round.

I got a notification regarding my the coincidence of my solution 269270131 with 269259042. This was due the coincidence of the algorithm used in the problem, both were taken from this source link. I had even mentioned the source in my submission. I wrote rest of the code myself. Also the style of writing the code matches with my previous submissions.

I request the Codeforces Team to review my submission.

»
4 месяца назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

MikeMirzayanov CHEATERS: There are several youtube channels that are streaming all the code solutions live, telegram channels that share the code before and during the contest. Due to these activities, users like me who do fairly in the contest get improper allegations of plagiarism. If talk about my case, my code and syntax are all of my own, I can also share the source of my code. I do not know why I have been accused of plagiarism. I hereby request the admin to please check into these cases.

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

MikeMirzayanov, I believe I have been falsely accused of plagiarism in the recent contest. My solution matches a publicly available code from GeeksforGeeks that was published before the contest. Could you please review my case? Here are the details:

-Description: In last div2, My solution https://codeforces.net/contest/1983/submission/269278403 got skipped telling in has significant match with https://codeforces.net/contest/1983/submission/269258951 this solution. But the two functions minSwapsToSort() and minSwapToMakeArraySame() was copied from geekforgeeks https://www.geeksforgeeks.org/minimum-swaps-to-make-two-array-identical/ . Our main functions are even different. Hope codeforces will take steps as soon as possible.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

My solution https://codeforces.net/contest/1983/submission/269263444 got skipped telling in has significant match with (1) https://codeforces.net/contest/1983/submission/269253412 and (2) https://codeforces.net/contest/1983/submission/269251305 this solution. I see that the logics that we have used are same for the problem, but I think for (1) solution, it matched because of similar prompts/ responses from chatGPT, and (2) might have written it by his own, I have no connection with the people with whom my solution matched, also my solution was submitted after a huge time gap from both the people and also please take into consideration the limitation of python solutions that tends to be very similar if they have a same logic, also I thinks using chatGPT solution should not be considered as plagiarism as ChatGPT is an open-for-all software which can be used by anybody and if we give it same logic to solve a problem, it might generate similar solutions, I hope that my solution will be considered after this clarification

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I just received an email stating that my code for B 269246318 has coincided with 2 other people's solutions and has been disqualified. Now, before you guys start to question the authenticity of my previous contests, the skips were due to me accidently using public mode on IDEone. I went through the rules and did not complain.

However, for yesterday's contest, I was using GPT to help me implement my idea, as I was blanking out a bit there. After going through the rules, any tools published before the contest are not prohibited. I understand this is not the right way to go about giving the contests, and I acknowledge this was a lack of judgement on my behalf. However, I would like to appeal regarding this solution as this is not a violation of the rules per se. Using AI tools which are not prohibited and copying other's codes should not be treated as same in my opinion.

Thank You. PS: It is a conversation with an attachment in it, which is apparently not supported yet, thereby I cannot provide the conversation as proof; but anyone can try to run the problem and get the desired result.

Edit: The coincidence occurred with 269249083 and 269251658.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Bro its so easy to recognize that you cheated it took you 13 to 14 mins to solve A and you did B in 11 mins which even expert rated coders had tough time dealing with stop cheating and do CP for your own skill improvement not for ratings as you grow rating will come with it as a perk

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ah! Got a mail regarding the solution matching with other candidates idk what went wrong I totally accept that there was something that went wrong and i am an absolute beginner and i don't know much about rules and regulations but one thing i can make sure is that it was not intentional or you can say i was not aware of consequences of these things. I am sorry i will take care of it in future and about my profile it does not have anything, if it get suspended on my first mistake then i will start again with another profile make sure to keep that clear. Sorry if i did any cheating or be the source of cheating ,unintentionally.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is there some issue with cf my solutions are in queue for 2 hours now??

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Bro, don't you know, you can't delete account on codeforces

    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But you can write to MikeMirzayanov who is developing this feature for now he said "Just erase all personal data from your user account and don't use it anymore. We don't store personal data long-term." so I will do the same.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I just received an email stating that my code for B 269266228 has coincided with 269287776. and has been disqualified. I see that the logics that we have used are same for the problem, but I think for solution, may be it matched because of similar prompts/ responses from chatGPT, or might have written it by his own.There is almost an hour gap between our submission.I hope that my solution will be considered after this clarification

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

CF system had sent me mail about vioaltion for my solved problems.I solved the problems using chatgpt Prompt(as far i know this is legal). I do not know my code got same with others.Please help me on this

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Dear Codeforces Team,

CF system had sent me mail about vioaltion for my solution 269286787 for the problem 1983B.I solved the problems myself and used chatgpt for error handle I do not know how my code got same with others.Please help me on this i have been regular and faithful in codeforces since 3 year . please help me don't give penalty.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help me someone.why didt i get this violation mail.I just use chatgpt

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have attempted the test and my solution 269278694 for the problem 1983B is said to be identical to others solution. I just want to this is so because this problems solution can easily be found on GFG and Leetcode with identical or near to solution and also could be generated through chatGPT thus wanted you to kindly remove plagiarism from my solution

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    lol. dont come here and cry now. Thats what happens when you take expernal help instead of using your own brain.

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

oh no indian round

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

He rickrolled us through the red letters :)).

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

B is waste of time ..