### kingofnumbers's blog

By kingofnumbers, history, 4 years ago,

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)

• 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 winners@codechef.com)

Good Luck! Hope to see you participating!!

• +83

 » 4 years ago, # |   0 Two hours remaining to start!
 » 4 years ago, # |   +13 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.
•  » » 4 years ago, # ^ |   +6 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
 » 4 years ago, # | ← Rev. 2 →   0 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.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   +18
•  » » » 4 years ago, # ^ |   0 The main difficulty in these two problems is different fortunately, so I don't see an issue here.
•  » » » 4 years ago, # ^ |   0 and this problem asks to support deleting earliest added element only, maybe yours is more general but does its complexity work here?
 » 4 years ago, # |   +1 Had a terrible match. The Chairs question really teaches me a good lesson.
 » 4 years ago, # | ← Rev. 2 →   +3 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 = 10string = 11001001000gaps = 3my 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
•  » » 4 years ago, # ^ |   +3 n=6 and string=100100?
•  » » 4 years ago, # ^ |   +11 The case you provided is already the counter case ???
•  » » » 4 years ago, # ^ |   0 my badi wanted to writeans = max(gaps-1,0)
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Actually the answer is 4 for this case. I think you misread the problem ?
•  » » » » » 4 years ago, # ^ |   0 yeah , i misread it Thanks for pointing out!
•  » » » » » 4 years ago, # ^ |   0 How is the answer 4?
•  » » » » » » 4 years ago, # ^ |   0 I guess he meant "2" :P
•  » » » » » » » 4 years ago, # ^ |   +8 I think the answer should be 5. Original string: 11001001000.Final String: 11100000001Did I misread the problem?
•  » » » » » » » » 4 years ago, # ^ |   +3 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: 00001111000or: 11110000000(depending on what is anticlockwise)
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 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.
•  » » » » » » » » » 4 years ago, # ^ |   +3 Agree with percywtc, simply just ignore the biggest block of zeroes ^_^
•  » » » » » » » » » 4 years ago, # ^ |   +13 I misread the problem :/Thought you can't jump over a child :(Thanks a lot!
 » 4 years ago, # |   +10 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.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   +5 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.
•  » » » » 4 years ago, # ^ |   +5 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).
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 4 years ago, # ^ |   0 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"?
•  » » » » » » 4 years ago, # ^ |   0 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
•  » » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » » » 4 years ago, # ^ |   0 Ok, you are right... I know official solution and it is nice. Anyway I got AC and that is only counting :P
 » 4 years ago, # | ← Rev. 4 →   0 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 :/
•  » » 4 years ago, # ^ |   0 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?