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 winners@codechef.com)
Good Luck! Hope to see you participating!!
Two hours remaining to start!
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.
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
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.
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.
This one: https://www.hackerrank.com/challenges/black-box-1 ?
The main difficulty in these two problems is different fortunately, so I don't see an issue here.
and this problem asks to support deleting earliest added element only, maybe yours is more general but does its complexity work here?
Had a terrible match. The Chairs question really teaches me a good lesson.
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
n=6 and string=100100?
The case you provided is already the counter case ???
my bad
i wanted to write
ans = max(gaps-1,0)
Actually the answer is 4 for this case. I think you misread the problem ?
yeah , i misread it Thanks for pointing out!
How is the answer 4?
I guess he meant "2" :P
I think the answer should be 5.
Original string: 11001001000.
Final String: 11100000001
Did I misread the problem?
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)
Isn't the process be:
So 4 steps in total.
Agree with percywtc, simply just ignore the biggest block of zeroes ^_^
I misread the problem :/
Thought you can't jump over a child :(
Thanks a lot!
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.
It's the maximum possible size of the subsequence of the array that satisfies two conditions:
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.
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.
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).
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.
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).
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.
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.
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.What is "this case"?
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
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?
I already admitted that your program is correct. Your proof isn't though.
Ok, you are right... I know official solution and it is nice. Anyway I got AC and that is only counting :P
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 :/
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?