kingofnumbers's blog

By kingofnumbers, history, 8 years ago, In English

Hello CodeForces Community! I would like to take this opportunity to extend this invitation for CodeChef February Cook-Off. As usual it is scheduled for the second last Sunday of the month.

Joining me on the problem setting panel, we have:

  • Problem setter and Editorialist: kingofnumbers (Hasan Jaddouh)

  • Contest Admin:PraveenDhinwa (Praveen Dhinwa)

  • Tester: Errichto (Kamil Debowski)

  • Language Verifier : arjunarul (Arjun Arul)

  • Russian Translator : CherryTree (Sergey Kulik)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: VNOI Team

I hope you will enjoy solving the problem set. Please feel free to provide your feedbacks in the comments section after the contest. You can find the rest of the details about the contest below.

Time: 19th February 2017 (2130 hrs) to 20th February 2017 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK79

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to [email protected])

Good Luck! Hope to see you participating!!

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Two hours remaining to start!

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Very interesting round. I am really happy after doing this contest :)

Somehow I have opinion that problems were a little more tricky then hard, but at the end looks that problemset is well-balanced.

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

    I'm really glad to hear that.

    indeed, it was more of thinking problem-set than implementation one, even the fourth problem had very simple implementation and the hardest one has medium-difficulty implementation

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

Maybe I didn't participate but I also think problems were interesting.

#Announcement. We look for setters for next short contests (cook-off and lunchtime) and for single hard problems (or ideas for hard problems, if you don't want to prepare them) for Long contests. You can write to me PM on Codeforces, later we can chat about your proposals via e-mail, hangouts or facebook.

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

    I have solve a problem is similar to mixing flavors. The problem has form of three queries: 1. Add a number. 2. Remove a number. 3. Ask maximum subset xor. I remember this problem exists on google.

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Had a terrible match. The Chairs question really teaches me a good lesson.

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

for problem "chairs" , my idea was to find total no of gaps , where a gap is defined as a non-zero sequence of zeros between any two 2 ones.

n = 10

string = 11001001000

gaps = 3

my ans = max(gaps -1,0)

any counter cases for this idea ?? as i got WA..

link to my code https://www.codechef.com/viewsolution/12897714

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

    n=6 and string=100100?

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

    The case you provided is already the counter case ???

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

      my bad

      i wanted to write

      ans = max(gaps-1,0)

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

        Actually the answer is 4 for this case. I think you misread the problem ?

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

          yeah , i misread it Thanks for pointing out!

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

          How is the answer 4?

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

            I guess he meant "2" :P

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

              I think the answer should be 5.

              Original string: 11001001000.

              Final String: 11100000001

              Did I misread the problem?

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

                Sorry, thought you/he meant: n=6 and string=100100?

                for Original string: 11001001000. (n=11) I suppose answer shall be "4" (which is right)

                not sure which is clockwise or AC, but it will be either: 00001111000

                or: 11110000000

                (depending on what is anticlockwise)

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

                Isn't the process be:

                • Initially, 11001001000.
                • Get the 8th to the left, 11001010000.
                • Get the 7th to the left, 11001100000.
                • Get the 6th to the left, 11011000000.
                • Get the 5th to the left, 11110000000.

                So 4 steps in total.

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

                  Agree with percywtc, simply just ignore the biggest block of zeroes ^_^

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

                  I misread the problem :/

                  Thought you can't jump over a child :(

                  Thanks a lot!

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

Can someone please explain how to solve ADDMULT? I did not quite get the approach mentioned in the editorial, more specifically how H is defined and how it is used.

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

    let H be maximum number of non-neighboring ones in the array

    It's the maximum possible size of the subsequence of the array that satisfies two conditions:

    • Each element is 1
    • No two taken elements are neighbours in the array.

    For example, for array 101100000 it's H = 2 but for 101000100 it's H = 3 because in the latter array we can choose 3 ones that are not neighbours with each other.

    The solution is about showing that one player wants to minimize H, while the other wants to maximize it. At the end P1 wins if H = 1, and P0 wins if H = 0.

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

      Thanks. Is there any intuition behind choosing the specific parameter H? I've understood the solution but could not understand why that specific parameter (longest subsequence of non-adjacent ones) is important.

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

        I got it this way: for strings of length 1, 2, ... I wrote down binary strings for which each player wins (you can do it on paper or you can write a brute force). It shows that the number of 1's isn't enough for determine a winner. One of my thoughts was: for a player wanting to get 1 at the end, it's better if 1's are far away from each other. It makes sense because two neighbouring 1's can be changed into 0 by an opponent.

        In two-player games we often can define some number that e.g. one player wins if this number is positive — it's a known fact. So I tried to find such a thing. The number of blocks of 1's didn't make sense. Then I looked at binary strings that I've written down before and after a while got a correct idea: the maximum possible number of non-neighbouring 1's. It took maybe a minute to prove the correctness (experience with maths is useful here).

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

    Sorry I can not read the whole editorial, but I saw the code is bigger than mine and there is some dp. I have possible easier solution:

    First change all numbers to become zero or one. After it you have several groups of ones and some groups of zeroes. Chefu can win only in case he has last move and stays at least one one. So, in each step he need to maximize amount of ones and Chef wants to minimize it ( maximize amount of zeroes).

    Best move for Chef is choosing two consecutive ones and change it with zero ( ones -=2 , zeroes++), in case there is no group with consecutive ones best move for Chef is choosing consecutive one and zero and replace with zero ( ones--). In case there is no single one, he only can decrease zeroes (zeroes -- ).

    Best move for Chefu is decreasing zeroes — it can do it by choosing two zeroes or choosing one one and one zero ( zeroes -- ). Normally in case no zeroes in the array he need to decrease amount of ones (ones--).

    At the end we need to check only is the last element one or zero. In case it is one, winner is Chefu otherwise winner is Chef.

    Finding whether exists some consecutive group with more ones and decreasing that group by two elements can be done by multiset.

    Here is the code : https://paste.ubuntu.com/24033434/

    Notice I wrote some special cases separately , but it is not needed. With normal implementation it could be done in 40 lines.

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

      Are you sure you opened a right editorial? Our codes don't contain any dp, and my code has 32 lines (I was a tester).

      So, in each step he need to maximize amount of ones and Chef wants to minimize it ( maximize amount of zeroes).

      It isn't enough. Consider a situation when an array is 1010 and it's a turn of player who wants to get 1 at the end. He can change an array to 110 or 101 but only the latter gives him a win (for 110 his opponent will make a move leading to 00).

      If I'm not mistaken, your solution is correct by coincidence — the order in which you make operations in your code turns out to be correct. I guess that proving the correctness formally wouldn't be easy here.

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

        I thought about this code : https://paste.ubuntu.com/24033542/

        I can not tell I have exact proof, I did it more by intuition — cases when Chef has last move are clear I believe... But this case will happen only if you have 1010101... And in that moment you have many possible ways how to choose one and zero. But it turns out that in case when Chefu is on the move (and also has last move) always we will have even amount of numbers. So zero must be at left end or at right end — so he will never make group of two ones, he can always choose way to merge that situation stays 101...01. Why it is not optimal to merge two ones, because after that move Chef can kill two ones instead of 1.

        Again I know this is not formal proof, but I do not see anything wrong in this logic. Everything which I said is correct.

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

          I thought about this code : https://paste.ubuntu.com/24033542/

          Ok, I understand. Most of that code is commented in /* */ characters and that part contains some dp that is not used in the intended solution.

          But this case will happen only if you have 1010101...

          What is "this case"?

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

            I thought about case which you gave me as counter example. If you have some groups of ones bigger than 1, than you can have case without some zero at the end and Chefu is on the move , for example : 111011 — but in my solution when you merge that groups it will become 11111 ( I will count it as two groups not as one with bigger size, I know it is not correct), but still in my set will become some group with bigger size than 1 ( it won't have correct size but it will be detected and in some of next moves I can separate it again — effect is the same ). Anyway I didn't go so deeply during the contest, you can try to hack it, but still I believe it is correct :D

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

              That counter example is indeed of form 1010... but it shows that it isn't true that players should care about the number of 1's and 0's in the sequence. Your whole proof is based on that assumption. You used words "best move" in meaning "move that leads to best value of number of 1's", didn't you?

              you can try to hack it, but still I believe it is correct

              I already admitted that your program is correct. Your proof isn't though.

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

                Ok, you are right... I know official solution and it is nice. Anyway I got AC and that is only counting :P

»
8 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

In MIXFLVOR, can anybody tell me how to support deleting the earliest added element? I can't understand this editorial (deleting earliest added element onwards).

I understood what the author wanted to say after looking at his code, but there are a lot of things missing from the editorial :/

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

    If you know how to support deleting latest added element, you can support deleting earliest added element by using two-stack trick.

    what are the a lot of things you think they are missing in editorial?