Alexdat2000's blog

Codeforces Round #770 (Div. 2)
By Alexdat2000, 3 years ago, translation, In English

Greetings to all humans and robots on this site!

sevlll777, crazyilian, Mangooste, purplesyringa and me (Alexdat2000) invite everyone to participate in the Codeforces Round #770 (Div. 2), which will take place this Feb/06/2022 17:35 (Moscow time). This round will be rated for all participants with a rating of strictly less than 2100. You will have 2 hours and 30 minutes to solve 6 problems. There will be an interactive problem in the round, so we recommend all new participants to read Interactive Problems Guide.

The traditional thank-you list:

Scoring distribution: 500 — 1250 — 1500 — 2000 — 2500 — 3000.


Codeforces Round #770 (Div. 2) is ready to resist the rise of machines
Do you think you are stronger than a robot or not?

We wish all participants high rating! Show that people are still worthy!

UPD: Editorial

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

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

As a tester I don't lose to AI in this round xD

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

it would be funny if AI won't be able to solve a single problem

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

Super excited (and kinda scared) to see an AI competing in a CF contest! Congratulations to the responsibles for such an amazing advance in the field of Artificial Intelligence (and my future nightmares)

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

‎Sorry AI, not today!

→ Reply
»
3 years ago, # |
  Vote: I like it +244 Vote: I do not like it
Well this meme just became reality XD
→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +174 Vote: I do not like it
    Another Meme :)
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it -26 Vote: I do not like it

      They still don't think btw not saying AI sucks it's phenomenal but it's different process

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

        Why don't you define what "thinking" is for us

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

          You're just one of the over hyped blind people . Did Beethoven train himself on anything similar to the pieces he wrote ? What you could do to train neural networks to write music you just put so many samples so it could extract the patterns and then it tries to do something with it . We don't count on the patterns we can deduct things and ideas that can't be transformed into digital data and as I said The AI is amazing but it's different I'm not trying to say that it's not interesting it's the future

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

            It solved backspace... I don't know what "thinking" means but that's not trivial at all and I was very surprised it managed to do so. Definitely doing more than just implementing a problem statement.

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

              if we don't know what thinking is then how could we say the AI thinks the computer doesn't think it only calculates .. but the point is this process is different from ours . For example how could you train the neural network to write a joke with that kind of process that will never make it write an actual new funny joke and that's the difference digital data can't save all of our ideas in a way the computer can understand and use this information to create and it will only create things based on samples it was trained but we can close our eyes and imagine something that never existed and make it come true (like a war for example let's kill each other isn't that beautiful) i know the joke isn't in the right place XD

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

                By this metric a machine will never be able to think even after its ability surpasses human ability

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

                  when it comes to calculations the machine will always surpass the human but the problem is the way it calculates is different when a human wants to calculate 1+0=1 that's similar how the computer calculate but when we need to know is that a dog or a cat we simply know it in instance but the AI should get every pixel in the image and compare it with the previous data to decide but should we call that thinking ? for someone that doesn't know what AI is will say this is thinking but it's actually calculations and this is something we have we do calculate but that's not the only thing we have when someone just simply deduct an idea that never existed before we could call that intelligence I guess and I don't mean an idea that never existed in the world but he was never trained to anything that helped him to build that idea and for me I prepare samples by myself to train the neural network and if i fail to prepare the samples in a certain way the AI gets confused and can't decide anything

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

                  Actually, I think that some processes in our brains are similar to what NNs do. For example, image recognition part could be quite similar. On the other hand, when it comes to understanding things and abstract reasoning then the processes are really different.

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

            All of the creative things about human are result of billions of years evolution. It took many trial and error to reach that phase. Humans are still far from perfect being. AI already doing some impressive task. I don't see why AI cant acquire characteristics that humans or others animals have and be better at it.

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

              before the human was able to invent some machine that walks 50 miles per hour and the speed kept increasing but that doesn't mean we will invent something that can travel at the speed of light someday there are limitations always . Anyone who worked with neural networks knows the limitations and the AI isn't evolving by itself that's the human job to develop it

              → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it
      One more meme :)
      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am a newbie and I am proud to do better than AI :D

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

Let's write complex explanation in the problem statement so the AI doesn't understand shit muahaha

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

We shall leave competitive programming to our robot overlords.

Jokes aside, this is pretty interesting! I'm looking forward to seeing the results

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

As a tester, I highly recommend to participate (yep, the quality of all problems is insane)!

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

AI vs coders: let's conquer Ai guyz(What if I am afraid as hell to lose to an AI).

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

We are happy to be the authors of the first round that AlphaCode will participate in.

Now we need story in questions.

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

God bless me . At least In this, I want to defeat AI.

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

Imagine AlphaCode FST'd

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

    Will it downvote the round announcement blog then lol?

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

Will AI steal all of the tester jobs???

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

Just imagining out of curiosity...The face of AI after WA on Pretest 2 XD

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

will be so funny if all three of them get disqualified for same solution

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

This is the moment our future is going to be decided.

We either dominate those ridiculous bots or they're going dominate us in the future.
I need one hundred percent effort from each one of you participating.
We need to freaking crush them once and for all.

Everybody focus this round — this time it's not about rating, it's about something bigger.

Good luck humans

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

How to say all the best to AI

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

    Train them with authors' solutions :)

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

      Why not train me with author solutions. I will win this war for humans :p

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

        Why not train authors with author solutions

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

          That doesn't make sense... Does it?

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

As a tester, I hope I'm stronger than AI. Have a good first round of human vs AI!

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

Well,Alphacode!That sounds so interesting!

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

It would be scary if those AI can use strong computing ability to stress test all coders in the same room as them. If the round is edu or div.3 they may be the best "hackers" XD

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

I don't even believe AI can solve problem A in div2, wait and see

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

guys to whom you bet your money on? ME or Alpha Code (you can take a look at my profile before betting)

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

Well, I am all set to get my revenge back for being beaten by AlphaGo xD

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

CP contests were never more interesting.

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

It is time to give the way for John Connor.

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

Time to introduce flavor text.

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

Pretty scared AI will beat everyone.

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

If Anton is coordinator, no way that AI solves more than one problem...

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

I'm willing to compete against AI this Sunday!! I stopped playing chess because of AlphaZero, is someone thinking of retiring if AlphaCode performs better than humans?

Yes, I wanna retire and live far away in the mountains

NO, I WILL STILL FIGHTING

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

    I stopped playing chess because of AlphaZero Stockfish was not strong enough? :)

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

It would be great if tourist participates in this round. We would get to see tourist vs alphacode. I don't know why but I feel like tourist will win.

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

    AlphaCode current rating is estimated to be 1238 points. I am sure tourist will win against a pupil.

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

      Oh, really? I actually didn't know this. Thanks for sharing.

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

Wow! 1250 score distributed for the second problem? Is that more score than usual?

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

Don't let the robots defeat us!

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

Soon I could boast that I had dueled with AI on behalf of mankind. XD

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

May be in the future, AlphaCode will host rounds(and create them)

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

Come on AI lets have a fair game, i hope you a win today but not in future..

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

Hope that tourist can fight back for mankind. Best wishes.

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

    AlphaCode's rating is predicted to be in the range Pupil-Specialist. So tourist need not fight, even we can :rofl

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

I hope everyone will raise their ratings after giving this contest

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

    The rating is calculated in such a way that the mean rating change is zero. Therefore it can't be all positive. Just saying.

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

As a tester, I'm happy to return red colour :)

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

Humanforces vs AIforces

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

Maybe you have forgotten to notice AlphaCoder's accounts, like me before.

SelectorUnlimited

WaggleCollide

AngularNumeric

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

If we create a problem with a well-written and AI-friendly description where the task is to create an AI to solve Codeforces problem, will the AI understand it and create an AI like itself?

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

There are several ways DeepMind can cheat: — some of the writers/testers are related to DeepMind, so * the problem statement is made easy for the AI to understand, or * even worse, the problems may be leaked — humans could rephrase the problem statements so the AI can understand — or simply, humans can submit a solution instead

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

    No authors are connected to DeepMind whatsoever, and I'm 95% sure the same holds for testers. And no, the statements weren't trained on the AI, so to speak. As for the last option, well, the goal is not to deliver a message or prove a point but to perform an in-field run, so I doubt that would happen either.

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

      Who knows about the human submitting the solution maybe if the results were so embarrassing something like that could happen

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

        I can't see any possibly embarrassing circumstance in which such measures would be meaningful. No one seriously expects AlphaCode to solve more than one problem, if that. Saying "we tried" or "it worked after we rewrote the statement formally" is fine.

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

          I guess you're right it's completely pointless if it didn't work they will have to lie every time . never mind that was stupid thought

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

Please Provide the user id with which AlphaCode will participate. I wanna add him as friend.

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

Will the AI spam wrong solutions until it gets a correct solution? lol it will be fun to see.

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

Imagine if AI rage quit on problem A!

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

As an AI I feel sad.

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

Can AC (AlphaCode) can get AC in an Interactive Problem?
Because Humans can.

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

AlphaCode gonna destroy me..

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

AlphaCode (after being underestimated by the community)-> AlphaQ

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

Would the AI solving multiple problems at a time, or just single one? Their submission time are so close.

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

It seems very unlikely that these robots are able to solve problems above 1500 accoding to their submissions. :)

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

People talking AI can solve this that,

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

Hope I will reach to the pupil today. Waiting for very long.

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

This battle will be legendary!

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

Why are there three AI bots? Why not combine them to create one super bot (which uses all three solutions one by one)?

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

    Well either they are the same model in the end or they want to compare performance of different methods. Don't forget that the momentary goal is not to win; the goal is to find out how to win.

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

    Oh, gr8. When 3 AI bots compete from as a single account, they're a super bot.

    but when my 3 friends do the same, they are called a ... cheater? smh.

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

    girl on codeforces rare ,indian rarer , expert rarer^2

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

The paragraph mentioning AlphaCode participation is now gone?

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

    Yeah guys We are very sorry to inform you that

    we fucked up due to some technical reasons that we are working hard on

    we misinterpreted a meme as a secondary source some miscommunication has happened within the team and

    there was literally zero chance AlphaCode would participate in a live contest it is unlikely that an in-field test will be performed at such an early stage of the project.

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

      AlphaCode:

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

      So sad to read it. I was eagerly waiting to defeat bot in this round. ):

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

      it is unlikely that an in-field test will be performed at such an early stage of the project.

      AI will wait for a Div 3 contest :)

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

        <s>text</s>

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

          If this works, why is it not strikethroughed for you?

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

            Because when you type <s>text</s> you really do get text, and if you want to type <s>text</s> you have to type &lt;s&gt;text&lt;/s&gt; (and to type that, you have to HTML-escape it once again, and so on)

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

Hey cheaters! Now is your time! You can copy the AI's code and make it skipped! Ahahahahahaha! For the human begin!

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

Interesting question: Will AI skip some problem in order to solve other problems that are maybe will be easier or AI will solve problems one by one. (For example skip C to solve D and etc).

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

Good luck everyone! Hope we will kick AI's ass out

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

God damnit I prepared this joke if i defeated AI :
I defeated AI but Magnus Carlsen couldn't gg

But there won't be a battle :/

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

But the time 14:00 UTC, the 3 AI accounts have not yet registered this contest. I wonder if Alphacode will use them to participate the contests, or other account?

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

What is Al? Please don't downvote it.

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

where are the bots ??

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

Hello AI, where are U

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

It seems that AI is fooling us! It didn’t even register for the contest!

What’s worse than AI beating humans is AI cheating humans!

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

I remember for sure that there were AI handles here.... What happened? Is the uprising of the machines stopped?

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

Did this announcement used to contain the misinformation that the AI bots from Google were going to participate in the round? Then Alexdat2000 realized that this is not true and simply erased it from the announcement without saying anything. Dude, come on, just say you were wrong

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

I hate speed-forces rounds like this -_- and huge gap of problems -_-

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

Just solved B. after going through a lot of fucked up approaches. I would like to know what problem setter smoked when he thought of this problem. That thing must be good.

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

Weak Pretests for A.

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

So you just added shitty constructive problems because robots were going to participate?

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

Maybe at least AI would had fun with the problems.

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

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

Please explain the relevance of problem B?

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

Not sure why people hated B isn't that the most fun thing about problem solving when the solution isn't obvious and the problem author tricks you to think in a direction while the solution is out of the box

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

    my solution doesnt even make sense, just xor all values and check for same parity. Bruh...

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

      yes because xor operations and plus operations gives the same parity as a result and that means bob and alice answers have different parity and it should be the one similar to the needed answer parity

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

I really liked the problemset. One of the best div. 2 rounds, I have seen in quite a while.

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

The verdict of interactive problem is super confusing. I get TL while it should be WA.

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

Solution B was greatest anime betrayal.

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

However, not about div2ABC, but about one certain type of problem I hate with passion (as a participant). You are given number and a set of arithmetic operations you can perform on it. Determine whether you can transform the number to another number.

I see more than one operation, and my blood starts boiling. Honestly, the most artificial type of all problems. Look at me, I came up with 2304984092384 operations and stared at numbers to notice an obscure property. Now you find this property and forget about it forever because it's absolutely useless anywhere but this problem. Wow, so cool.

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

Speedforces

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

My approach for Problem D: Finding Zero

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

    My approach

    • Write bruteforce to find the patterns.
    pattern finding bruteforce
    • Don't have enough time to code the solution.

    ...

    Profit!

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

First you try to get clout with AIs then weak pretests, and stupid constructive problems.

→ Reply
»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it
How bad could it be?
→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Solved B < 15 min due to 'guessing' and 'pattern finding'. Seems like those bad guessing problems unless someone can give me a reasonable proof to solution.

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

    If $$$a_i$$$ is odd, applying any of operations flips the parity, and if $$$a_i$$$ is even it won't change the parity. And since x and x+3 have different parity, you can get solution using number of odd $$$a_i$$$.

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

      nice, btw the problem felt really weird. It was clearly pointing at the property b = x+3(cuz like why not b equal any random number) then tried some cases and realized the parity stuff

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

        Well,I think this trick is very normal. Whatever $$$b$$$ equals to,it is really easy to think about parity because of the fact that ⊕ and $$$+$$$ has the same parity.

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

          The way this problem statement is constructed it qualifies as april fools fun. Is this really what we want in usual contests?

          Edit: I show you what I wrote at minute ~10 in the contest, just before quit:

          /**
 * We obviously have to find some more or less "funny" observations.
 * It is kind of unpredictable if I find them in reasonable time or not.
 * So, basically I am out here. Sic.
 *
 * ***
 * However, what observations could be usefull here?
 * Something about x+3, why 3?
 * Can we simply find if Alice succeeds somehow and ignore x+3?
 *
 * Consider the last bit in y...
 * Why/How it is garanteed that exactly one of both gets y?
 */
void solve() {
}
          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But if the statement is

            $$$b=x+1$$$

            or

            $$$\text{Alice chooses an odd number and Bob chooses an even number}$$$,

            the problem will be much easier.

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

              Well, it is an easy problem. Trying to make it more interesting by obfuscating the problem statement is really, really bad style.

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

                What you said makes sense,but I think the problem creator just wanted to make the idea more hideen :) .

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

Nice round. I liked all problems even though I could solve only up to D. Btw how many problems did the AI solve?:))

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

I don't know what to say about B, but i spent 1.5 hours and couldn't solve it at all :(

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

The arrangement of B and C is not good, it took me 10 minutes to solve C and 2 hours trying to figure out how to solve B

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

Don't know but to be honest ,these two guys(Alice and Bob) and their weird games have fucked me badly in my life than anyone else

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

    Probably not two guys since Alice is a girl's name.

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

Disbalanced contest (B and C have to swap and really weak pretests for A)

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

E is cute, I like how natural both the idea and the resulting solution are.

A, C and D are pretty cool problems as well.

B on the other hand is not a problem I like. It feels really really forced with the "It is guaranteed that on the jury tests, exactly one of your friends could have actually gotten that number". Also what even is the point of $$$x + 3$$$ instead of $$$x + 1$$$???

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

    I thought the same about $$$x+3$$$, though I guess using $$$x+1$$$ would make the observation more obvious.

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

    Trying to mislead AIs

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

    100% I needed more time because of 3 instead of 1 :D

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

    Also what even is the point of x+3 instead of x+1

    Just to make idea about parity less obvious. We wanted to make $$$x^2-1$$$, but it made the problem ridiculously hard

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

      Man if the authors really want to fu** with us they really can Lol

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

The only real programming problems (E and F) turned out to be too hard for me :/

In E I guess that if one array has more than one occurence of certain number we can put half of them in L and other half of them in R, right?

Problem A was great imo :)

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

I was just several seconds late for hacking a submission of Problem A. Basically when I finished typing the input, I got a message saying the solution had been hacked or resubmitted. Speed matters.

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

It would be funny if AI gets plag, AI not able to solve any question and then buying from telegram

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

I hate pB.

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

I hope an open-source project is born and we get at least virtual participation of a bot in the future.

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

Hence proved, humanity's greatest threat isn't AI but humans Itself :(

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

I want to ask one thing, why would you create something shit like problem B, Instead just give an implementation problem or something else. What is so educative about this problem?.

I don't like these kinds of problems where some people see some observation and get AC while others struggle. What skill do I lack to deal with these shitty problems?

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

Problems A, C, D were interesting. B was very bad. E was easier(too obvious solution) for its position imo.

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

Any hint on E? (I came up with some greedy solutions but got WA)

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

    I believe it is max-flow. ( Didn't have time to implement and test it)

    Idea, find out which number of which array belongs to the Right segment.

    Therefore build a maxFlow graph: You have 1 source node, n nodes (for each array one), number-of-distinct-numbers-in-all-arrays nodes and the sink.

    You connect:

    • each of the n-array nodes with the source with weight length of this array divided by 2

    • each of the n-array nodes with all the distinct number which ocurr in it with weight 1 (or if it occurs more than once, then a higher number)

    • from each number node to the sink with weight "the total number of occurences in all arrays divided by 2"

    if the max flow is the half of all numbers in all arrays, the answer is true. and you need to read the flows to get the answer.

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

      You're on the right track with the graph modeling but it isn't max flow.

      Consider two types of nodes:

      • Array nodes which represent a position in one of the arrays.

      • Value nodes which represent some value. (There are at most $$$2 \cdot 10^5$$$ distinct values)

      For some position $$$j$$$ in the $$$i$$$-th array, we create an edge between the array node for this position and the value node for $$$a_{i, j}$$$.

      Let us consider marking a positon as $$$L$$$ to be equivalent to directing its corresponding edge towards the value node, and $$$R$$$ to be equivalent to directing it towards the array node.

      So now for $$$|L| = |R|$$$, we need in-degree $$$=$$$ out-degree for all array nodes. Additionally for the set to be balanced, we would also clearly need in-degree $$$=$$$ out-degree for all value nodes.

      This is clearly impossible if any value occurs an odd number of times since the corresponding value node will have odd degree, otherwise it is always possible.

      So we have a graph where every node has even degree and we want to find a way of directing the edges for in-degree $$$=$$$ out-degree. Remind you of something?

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

      Unfortunately I think max flow is too slow :( . I tried several different implementations of max flow during the contest and they all TLE'd on test 3, and if you filter by TLE on test >= 3 on https://mirror.codeforces.com/contest/1634/status/E it seems I'm not alone.

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

        I also had some thoughts on maxflow but based on the constraints I didn't implement it

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

          Correct me if I am wrong, I think the complexity of Dinic on a bipartite graph is O(sqrt(V) * E), you have |V| = |E| = O(10^5)?

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

            To my understanding, $$$\mathcal O(E \sqrt V)$$$ complexity is only achieved when the graph is a unit network. Despite this, I still figured flow was worth a try because it's well-known that max flow algorithms run much faster than their proven time complexities, and I've gotten AC on problems with bounds where it looks like flow shouldn't pass before.

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

              May I ask the reason why Qwerty1232 got accepted by this submission which using dinic (145470307). I think maybe he construct graph using Chunking. Amazing!

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

                After reading that submission, I realized I had an unnecessary layer in my flow construction during contest! I've rewritten my code to fix that and now I get AC when using KACTL's push relabel implementation. Note that you still need a pretty good flow implementation, for example the Atcoder library implementation doesn't pass.

                Oh and I guess to answer your question about Qwerty1232's submission, I don't fully understand their flow implementation, but it looks like these lines:

                static constexpr double TL = 0.5;
if (clock() * 1.0 / CLOCKS_PER_SEC > TL) {
    break;
}

                play a huge role in letting the code pass. When I commented those lines out, the code TLEs. It appears they run standard Dinic's algorithm for 0.5 seconds, and then they switch over to an alternative dfs2 procedure that appears to just be naive repeated DFS with a visited array. My guess is because of how shallow the graph is, preprocessing good augmenting paths with a BFS isn't helpful and just takes unnecessary time.

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

$$$B$$$ is more like a puzzle description than a CP problem. $$$y$$$ in the problem description is replaceable by an arbitrary even or odd integer without referencing the exact value. I think stating $$$y$$$ exactly as a way of distraction is not a good idea in a CP contest.

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

    yeah, but if they specified the parity, it would instantly give off a hint?

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

      True, so this means that the problem quality itself is debatable, as it turned out to be just a distracting description masking a very simple problem.

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

how can I see AI's performance in this contest ?

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

Once again, Alice and Bob screwed me over with their weird games. F*ck my life.

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

My approach for D gets wrong answer on pretest 5. The idea is find the max difference for first 4 numbers (4 operations), use 2 more to find which of those 3 is not used, so I get min and max (call them p1, p2) numbers among first 4. After that, just iterate i from 5 to n, and do at most 2 operations for each one, first ask for (p1, p2, i), and if difference is higher, ask now (other, p2, i) where other is some position I know it's bad, and if I get the same answer, then p1 is not needed, so I update p1 = i, otherwise p2 is not needed, so p2 = i. Operations: 6 + 2*(n-4) = 2n-2. What did I do wrong?

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

    I did exactly that to get the same result :( https://mirror.codeforces.com/contest/1634/submission/145465061 Somebody explain

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

      So my code fails for the array 2 1 1 2 0. The problem is it fails to give the min max pair for the first 4 numbers. I can't come up with a way to find the min max of first 4 numbers using only those. If you find a way, that should solve my problem (hopefully this was your problem too)

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

        Yeah I have the same issue, kept seeing 'allsame' variable in passed submissions, I get what that means now. Thanks!

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

Does anyone know what pretest 4 and 5 of problem D is?

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

    They are both max-tests. Test 4 has $$$n = 4$$$ and all combinations of $$$a_i \le 3$$$, and test 5 has $$$n = 5$$$ and all combinations of $$$a_i \le 2$$$.

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

hello ai ，what about you？

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

I think AI-squad won, because they succesfully used misleading for them in problem B against human beings

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

Damn! Too much bad pretests for Task A. This will cost me my Expert rank :))

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

Me face when couldn't solve B because -3 % 2 = -1

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

I liked C, D and E but absolutely hate problem B and the pretests for problem A.
Hit and Trial problems like B are just bad in my opinion and it becomes more luck based than skill based. No wonder why it has such less number of solves.
A should have had more pretests. It was full of hacks and provided an unfair advantage (even huge advantages) to some participants who were able to hack solutions. Some participants even managed to get more points from hacks than by solving the problem itself.

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

    Why would you hate B? Hit and Trial you call it ? It's a simple problem on parity check. And C ? I find it funny that I guessed the solution for C that got Accepted. Absolutely loved problems D and E.

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

      The thing is, Problem is simple but people think differently. You thought about parity first that's why you got it in a short time, some people (like me) didn't think about this and played with various patterns and cursed the setter so hate is completely justified.

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

        The only thing I want to say is, setter needs to be appreciated for such a wonderful problem or at least should not be hated.

        Just general suggestion, when it's div2 A/B and it seems pretty hard, maybe you need to "change your approach" is the hint :).

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

          I don't hate the contest. As already mentioned, I liked more than half of the problems that I tried and one problem doesn't make the contest bad. I have upvoted the contest blog. I only hate problem B simply because I didn't find it interesting and a little bit trolling (and looks like I am not the only one who feels so). Even A was not a bad problem but had some poor preparation.
          I always appreciate the efforts of the contest panel and I just wanted to express my opinion so that the setters may improve on such things in the future.

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

      How would parity check cross your mind if not by hit and trial? Obviously, the most general way of approaching problems involving XOR is to go with individual bits and derive some interesting observation that way. But here, it was just about questioning why $$$x+3$$$ and why the additional constraint on the tests guaranteed to be having exactly one answer.
      And I liked the proof for C's solution. In my opinion, it was some very decent use of arithmetic progressions to make a very natural problem. (And as you can see from my username, I Love Constructives)

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

        another way of looking at xor problems is even-odd.

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

        Let me show you another thought progress without guessing parity right away. It's also the thought process I had in the contest.

        First of all, XOR and ADDITION are nearly the same. XOR is ADDITION without carry. It is often hard to find easy invariants or algorithms for the carry, so I assumed, the solution has to be done without carry, since it is a B.

        The least significant bit is the only one not affected by the carry. So it seemed natural too look at it. Especially since x and x+3 have a different value on the least significant bit. Also the second bit, but analyzing the least significant one was enough to find a solution.

        Maybe for me it also helped, that I played https://nandgame.com/ not long ago and built a full adder.

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

Can anyone explain how to even approach for B??

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

:v

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

I think there were a few flaws about this round

Problem A: weak pretests

Problem B : cool problem but i think it requires more thinking than regular div2 B .

Problem C: I dont know why this problem is even there .Just implementation based and a lot of cases(for me). Because of which was not able to read D+ problems.

Didn't quite liked the round but it was a great effort by you guys. i genuinely hope we will get good contests from you next time.

P.S. : i lost expert to this round phewwwwww

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

    I strongly disagree about Problem C being "implementation based". There is a general solution that works for even $$$n$$$, and a small edge case to handle for $$$k = 1$$$. The overall solution isn't tough to implement at all — 145416321

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

      But do you really think it is of Div2 C standard ? i literally got the logic for it instantly ,on the other hand problem B was really cool. I guess swapping the positions of Problems B and C was not a bad idea .

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

        he was talking about the part, where you said it had a lot of cases, not about it's position.

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

        Hmm fair enough, I am a bit biased there since I solved B in around 5 mins whereas I took around 25 mins for C, but the solve counts seem to support your point.

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

    lot of cases?

    • n % 2 == 0: YES, print even and odd rows
    • else:
      • k == 1: YES, print one number on each row
      • else: NO
    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For C it was thinking up the proof that took some time, nothing to implement here

    void solve() {
    int n, k;
    cin >> n >> k;
    if (k == 1) {
        cout << "YES\n";
        for (int i = 1; i <= n * k; i++)
            cout << i << '\n';
        return;
    }
    if (n & 1) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    for (int i = 1, cnt = 1; i <= n * k; i++) {
        if (i & 1){
            cout << i << " \n"[(cnt++)%k==0];
        }
    }
    for (int i = 1, cnt = 1; i <= n * k; i++) {
        if (!(i & 1)){
            cout << i << " \n"[(cnt++)%k==0];
        }
    }
}
    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F was somewhat straightforward if you have already solved 446C - DZY Loves Fibonacci Numbers. Why such a tight TL tho?

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

    IMO the TL wasn't tight. The linear model solution passes under half the TL even on Python, and a higher TL would allow for sqrt decomposition or segment tree-based solutions to pass, and increase the probability of some weird hashing-based solutions to pass (which has actually happened during the testing phase), which was not intended.

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

Lots of hate towards B, but even though I had the same issues as everyone (only solved it close to the end and after C), I don't think it's a bad problem.

I don't think it's necessarily about some people seeing an observation about parity and other don't (although arguably it means some people do solve it much quicker).

You could try computing the set numbers you can get with this process with brute force. In reality it's a huge set of numbers that grows exponentially with the input array size. Or is it? I didn't think too much about it, but I couldn't come up with a quick abstract argument why wouldn't it collapse just to a few numbers in practice, so I though it was quicker to write some code to check.

Arguably it's a skill any competitive programmer is capable of (doesn't require you to have a specific bright idea about the problem), and a reasonable thing to do when you can't come up with a quick solution. Also it's useful for testing the correctness of more clever solution anyway.

So the sim looks somewhat like:

def sim(a: List[int], x: int):
    cur: Set[int] = {x}
    for c in a:
        nxt = set()
        for q in cur:
            nxt.add(q + c)
            nxt.add(q ^ c)
        cur = nxt
    return cur

Then I tried generating random arrays a and initial number x, and seeing what I could get. If you inspect the set of numbers you can get, you'll notice that either all numbers in the sim results are even, or all odd, this is clearly a pattern.

After trying it with x + 3 and comparing whether you get even or odd results, you essentially come to the actual solution.

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

my submission Time limit exceed on testcase 178

codeforces is too slow, AI lost to human

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

What Happened did we win or loose??

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

My solution of D failed 10 times on 1000 random tests of n<=20 and it still passed system test. Wow. submission

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

I got sick and my brain overheated trying to solve problem B.

I think it is another variant of covid
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The writers must have forgotten that B,C are for humans to solve.

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

Why didn't AI take part in today's contest ? Are they scared ?

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

Alternative approach for problem D, which guarantees solving in one fewer query (worst case 2*N - 3). (Submission here)

Perform N - 2 queries of the type (1,2,j) for 3 <= j <= N, and note an index (not necessarily unique, but this is unimportant since ties can only occur at the maximum value, not at the zero) which gives the maximum query value. Call this best_idx1, and the maximum query value best1.

Then perform N - 3 queries of the type (1,best_idx1,j) for 3 <= j <= N and j != best_idx1. This time call the maximum query value best2 and its corresponding index best_idx2.

Then we are reduced to casework.

Case 1: If best2 > best1, then we know that the maximum and minimum value pair is contained in the tuple (1,best_idx1,best_idx2), and we also know that it is not contained in the tuples (1,2,best_idx1) or (1,2,best_idx2). By elimination we see that the pair (best_idx1,best_idx2) will definitely give us the correct answer. Total 2*N - 5 queries.

Case 2: If best2 == best1, then the max/min pair is contained in both (1,2,best_idx1) and (1,best_idx1,best_idx2). Since there is only one zero, we know that it is in both tuples, so we can safely return the two common elements (1,best_idx1). Total 2*N - 5 queries.

Case 3: If best2 < best1, then we know that the tuple (1,2,best_idx1) contains the max/min pair, but that the tuple (1,best_idx1,best_idx2) does not. Therefore the answer cannot be (1,best_idx1), and therefore element 2 is definitely in the max/min pair. We need to determine whether (1,2) or (2,best_idx1) is the max/min pair, and we can do this by querying (1,2,best_idx2) and (2,best_idx1,best_idx2). The max/min pair is the first two elements of whichever query gives the greater result, and thus we have solved this case in 2*N - 3 queries.

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

    Same as your thought.

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

    had the same solution. +1

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

    Actually, in Case 3, you don't need to query (1,2,best_idx2), because you've queried that in the first pass. So, in total, there's only $$$2n-4$$$ queries.

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

      Very good point. A further improvement.

      I was lazy and didn't store the results of my queries but that does indeed save another query.

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

For Problem B, I just simulate two FST(Finite State Machine, like DFA in principles of compilers) consisting four status(00, 01, 10, 11) to search for some patterns when I can't figure out what problem writer's thinking. One of the FST is for plus operation, while another for xor operation.

Maybe you can try this way to think about this problem, though I didn't notice the parity trick when I was in the contest.

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

Hello , I am new to codeforces and I appeared in this contest. I had a doubt with my code for the first problem . I dont know where do I post it. I have pasted my submission link. Can someone please help me figure out why did this not work?

https://mirror.codeforces.com/contest/1634/submission/145446176

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

    Hi, in the second for where you find a j that s[j]!=s[n-j-1], you need a break because you found that the string is not a palindrome, but in the next iterations you will set incorretly count = 1 if you find a j that s[j]==s[n-j-1].

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

Really poor pretest 2 in Problem A, so from the next time please try to make some strong pretest.

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

It seems that AlphaCode turned into AlphaPigeon

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

Good contest(except pretest in problem A)

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

downvoted for having B as bitwise problem + AI didn't participate

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

Problem B was really tricky

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

Congrats sus!!!

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

when will the problems be given ratings? isn't it taking more time than usual?

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

Me : problem B from this contest is trash https://mirror.codeforces.com/contest/1688/problem/C : hold my beer

→ Reply