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

Автор farmersrice, 5 лет назад, По-английски

Today I want to share some interesting problems, that are very algorithm-like/logical in terms of thinking but are not really standard (kind of like some good ad-hoc question you can share with your friend). I'm not exactly sure what to call these, but they are very interesting to me and I hope they are interesting to you as well. If you have something similar, please share.

For some people they are quickly solvable and for other people (like me lol) it is near impossible. I tried to make the problem statements as interesting as possible. Images and problem statements are mostly compiled by me.

I will put up solutions in a day or two (viewing the solution kind of ruins the problem, much more than for ordinary Codeforces problems). Think! It's really much more fun than regular problems. Double promise!


Two papers

source: unknown

You are playing a game against a magician! (You slept at 4 am last night. Who knows how you got here? Maybe you should sleep more. cough cough Savior-of-Cross) The guy says he's in charge of every const int MAGIC ever written. He also promises to show you some magic in his new mind game. You're a little skeptical.

Here's how it works. The magician enters the magic room and takes two pieces of paper, and writes two arbitrary real numbers on them, each in range from $$$0$$$ to $$$1$$$. Once the numbers are written, they cannot be changed. Then, you enter the magic room. You can pick exactly one piece of paper and look at the number written on it. Then, you must submit one of the two papers to the magician. Your goal is to submit the paper which has the greater number written on it. (If the two numbers are the same, then you win by default.)

Example: The magician writes down numbers $$$0.7$$$ and $$$0.8$$$ on a paper. You pick one paper and it is revealed to have the value $$$0.7$$$. If you submit the paper you looked at, you'll lose, because $$$0.7$$$ < $$$0.8$$$; by the same logic, if you submit the paper you did not look at, you'll win.

Figure 1: All the information you'll get.

One last thing: The magician is also a mind reader. He will know everything about your strategy before he even writes the numbers down. And when he knows your strategy, it will be hard to beat him!

You hate losing, and you love winning. Luckily for you, there's a strategy that guarantees you a win probability strictly greater than $$$50$$$%. You're going to show that pesky magician what you're made of, right? His magic constants have given you wayyyyyy too many FSTs. Now it's your chance to get back at him by beating him at his own game. What's your plan?


One hundred prisoners

source: unknown

Uh oh. After you cheesed a data-structure-heavy problem that was meant to be solved in $$$O(n\ \sqrt{n}\ log\ n)$$$ with some sketchy $$$O(n^2)$$$ with pragmas, bitset, and the magic of low constant, the Codeforces Police (who strictly enforce algorithmic ideas) have finally caught you. You've just been put in Algorithm Prison, where inmates are condemned to solve high constant implementation problems with 0.5 second time limits for the rest of their lives. There are a total of $$$n = 100$$$ prisoners in the prison (including yourself).

The guards have a special challenge, since you're so smart. If you solve it, then you get to go free! No pragmas this time, though.

Each prisoner is assigned an integer from 0 through $$$n - 1$$$, inclusive. There can be multiple inmates with the same number assigned to them. There can be numbers that are not assigned to any prisoner.

The numbers are hidden from anyone's knowledge from an entire week, giving you ample time to strategize with your fellow inmates. The guards have already told you how it works ahead of time: On the day of the challenge, all prisoners are put in a giant circular room. No communication of any form is allowed between prisoners once they've entered the room. (This is strictly enforced by the Magic Duck, who will instantly eat any bit of information transmitted between prisoners, no matter what form this information takes.) Each prisoner can see the numbers assigned to all the other prisoners, but cannot see the number assigned to them.

Figure 2: The Magic Duck. He's hungry — for KNOWLEDGE. Quack.

After everyone has seen everyone else's numbers, all prisoners are taken into solitary rooms. Each prisoner must attempt to guess his or her own number. If at least one prisoner guesses his or her number correctly, everyone gets to go free!

But you hate relying on luck and probabilities. Remember that one time when you wrote a randomized hashing solution that was just impossible to break, but you ended up getting Wrong answer on test 147? That ain't happening again. This time, you're going to find a mind-blowing, stunning algorithm that guarantees victory for you and all your buddies. The question is: What's the algorithm?

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

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

My favorite:

There are $$$2n$$$ IOI gold medalists in the jail. antontrygubO_o, the evilest person in the world, gives them the chance to escape with the following procedure: he will take a photo of each medalist and put all the photos in the room with image down in order, unknown to the medalists. Today they can discuss their strategy, but will be separated tomorrow. After that, they will come into the room one by one, and will have $$$n$$$ attempts to find their own photo. One attempt is: flip the photo you choose to see the image on it. If you don't find your photo in $$$n$$$ attempts, antontrygubO_o will force you to read his dunk memes. (After a medalist finished, all cards are placed back image down).

However, antontrygubO_o didn't know that medalists have an accomplice farmersrice, who can look at the photos beforehand and can swap any two photos he wants (at most once).

Help them to define a strategy so that no one has to read dunk memes

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

    it is easy, how could it be your favourite smh

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

    Does this work:

    Spoiler

    Very nice...

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

      Yes!

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

        Doesn't this require the pictures and inmates to be numbered? Otherwise, how will you know which cycle contains your photo?

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

          They can discuss strategy, so they will just number each other off.

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

            Still, photos need to be numbered, don't they?

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

              The photo number is the same as the number of the prisoner who is in the photo.

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

                How do you know which picture to flip first? Obviously, you do not know whose face is on the picture before making a move.

                Subsequently, which photo to flip next? You cannot know, if they are not numbered (e.g. chaotically layed out in the room).

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

                  The images are not thrown around randomly. You can pick any picture you want to flip. The photo you flip next is given by the index of the current photo's person's number.

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

      I think this doesn't work because the order of entrance is arbitrary (possibly picked by anton).

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

Two papers:

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

    My friend found this paper.

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

    Two papers (same solution with thought process).

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

source: some drank dude told this problem to Marcin_smu

Somewhere in the server room of ITMO, there lies an $$$8 \times 8$$$ chessboard where every cell is white or black, possibly forming some mysterious pattern. One of the cells contains a secret to becoming nutella in CF. Mike doesn't normally let anyone near the chessboard (well, Gennady sometimes comes there to play some crazy version of checkers with himself) but there are two possible exceptions for people with rating at least 2600.

  1. Knowledge for a soul — You will learn how the grid looks like and which cell contains the secret. The price is your soul. Just before you get cast down to hell (and banned from CF), you will be able to quickly repaint at most one cell (black to white or the other way around).
  2. Guess the cell — You can see how the grid looks like and guess which cell contains the secret. Success means you get to know the secret. But if you fail, the worst possible fate awaits you, something too cruel to possibly be true. You will lose all your contribution and your comments will forever stay hidden because of too negative feedback.

One day, you got an interesting message from a stranger:

sir ,sell ur soul and repaint some cell in such a way that I could later guess the special cell after seeing how the grid looks like ,thx!!

That indeed sounds like the best possible plan. You can discuss the strategy with your new friend now. After that, you will sell your own soul, see the grid and know which cell is special, repaint at most one cell, and then your friend will try to guess the special cell just by looking at the grid. What strategy you two should choose?

Related pic, Gennady playing checkers against himself:

  • »
    »
    5 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +9 Проголосовать: не нравится
    Spoiler
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +44 Проголосовать: не нравится

    Isn't it from the last gp of spb?

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

      I didn't participate and I heard this puzzle more than a year ago. But apparently it's same :(

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

        I've seen this puzzle on at least 3 different occasions not even including gp of spb XD Seems like this is pretty popular.

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

Most of the problems you mentioned can be found here: http://datagenetics.com/blog.html

»
5 лет назад, # |
  Проголосовать: нравится +96 Проголосовать: не нравится
$n$ prisoners
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

(Countably) infinitely many mathematicians walk into a pub queue. Each of them is given a hat, either white or black; nobody knows which hat he has (they were distracted by calculating the value of $$$(-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3$$$ at the very moment of obtaining a hat). There is no first person in this queue, but there is the last one.

Each of them is promised to receive a free pint of beer if he guesses his hat color only seeing all the guys before him in the queue. At 11:55 the first of them is asked to give his answer so that nobody except the beer guy hears it. At 11:57.5 the second of them is asked, at 11:58.75 the third etc. Mathematicians will be happy iff only finite number of them doesn't get any beer by 12:00.

By a happy coincidence, all these mathematicians discussed a strategy yesterday (just in case). Can they succeed independently of the beer guy's actions

  1. if each of them knows his position in the queue (that is, how many other guys are before him),
  2. if no one of them knows his position in the queue.
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    There is even harder version of this — someone wrote a real number on their hats instead of 0/1.

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

    Any hints?

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

      For the first subproblem:

      Hint

      Second subproblem:

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

    Ok, Unless this is not a joke I'm going to put some concerns which were born during discussion of this task with my fellows.

    If we want to use AC (Axiom of Choice) or any its equivalent from Set Theory prospective (such as Zorn's statement) mathematicians should agree on a fixed function of choice for 'algorithm' to work right? If there're several such functions, how do they agree on such a function?

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

    There is no first person in this queue

    At 11:55 the first of them is asked

    Wait, what?

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

      The last of them is asked, then the second from the end, etc. Also position = the number of guys after him, not before

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

Source: someone in the IMC 2019

All the $$$n$$$ people who solved the other puzzles in this thread are taken to a prison for being too smart. As an ironic punishment, they can get free if they solve the following supposedly impossible puzzle.

The prisoners are given a short time to discuss strategy. After that they are put into solitary confinement. At irregular intervals one prisoner is brought to a dark cellar with only a lamp in it. (edit: Initially the lamp is turned off.) The prisoner can switch the lamp on or off, or exclaim "All of us have already been here!". If he or she is right, everyone is set free. If he or she is wrong, they are all sent to an even worse prison with an even harder puzzle.

To ensure no one forgets why they are being punished, it is guaranteed that everyone is brought to the lamp room an infinite number of times.

Obviously the guards thought this is impossible to solve. Is it?

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

    Is this FFT?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится
    Solution
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      Consideration
  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    It is the last, sixth task for 9 classes at the Moscow Mathematical Olympiad 2003.

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

i have solution for the problem two papers but im not sure about it can someone pls tell me whether is it correct or not solution :: pick a paper see the number if the number is strictly greater than 0.5 pick it otherwise pick the other paper

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

    The wizard knows that you are going to do that. So he can for example will put 0.7 and 0.8 on the papers. You will succeed with probability 0.5, but you want to succeed with probability strictly greater than that.

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

I have modification of Prisoners problem brought by a discussion with my colleague.

So, we have $$$N$$$ wizard sitting at the round table. Every wizard wears a hat colored in one of three ways (see the picture). Every wizard can see hats of his/her neighbor (left and right).

They can't exchange any bit of information (again Magic Duck wearing special magic hat will swallow every bit of information). Everyone should guess (with one attempt) what's the type of hat they're wearing.

Again their goal is to guarantee that one wizard will guess correctly.

I don't think it's solvable for every N, but for some there's an algorithm.

P.S. $$$N=3$$$ is just the same as prisoners problem.

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

    It bothers me that the first hat has two colors :|

    Is this some modified version of the German flag?

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

      I'm not into any kind of things related to any particular nation:) It's just modification related to CF-ranking system :P

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

    It is not solvable for $$$N=1, 2$$$ otherwise it is solvable, isn't it? Moreover $$$N - 3$$$ wizards can get drunk in the table and don't need to tell any color, and you just solve the problem with remaining 3 wizards, as in the original problem for $$$N = 3$$$. Did I miss something in the new problem?

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

      True for $$$N=1,2$$$, nut for general case this probably won't work.

      Well, if you choose only 3 wizards it's not the same as we have in case of $$$N=3$$$. The reason is if you choose A,B,C to reside consecutively at the table then B can see A and C while A can see only B (and other wizard but not C, only in case $$$N=3$$$), same for C accordingly.

      Other words, the circular property plays crucial role here.

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

    Ok, we found a paper related for this problem. Even though it looks similar to Prisoners, we solution is kinda hardcore for Hats Problem. For those whoa are interested: