Game on a Strip August Lunchtime 2020

See here for the problem.
What I did here is that I found the longest and the second-longest substrings of '0’s .
And then applied the following :

if( isEven( longest ) || ( isOdd( longest ) && secondLongest >= ( longest +1 ) / 2 )
“No”
else
“Yes”
But it seems this logic is wrong. Can someone tell a test case which doesn’t works ? Also, what is the correct logic? In brief

You must also consider the case when the longest subarray of zeroes is odd and has a frequency>1

It should be (longest/2) +1

Consider this
1 0 0 0 1 0 0 1
You wanna start from here 1 x 0 0 1 0 0 1
So if she does this: 1 x y 0 1 0 0 1, you lose
So you must start at the mid of empty block to not get trapped by the opponent.
So the actual size will be (size + 1)/2.
If you pick an even sized area, you will always lose.
Also, if there are two areas of odd size of the same size, then your opponent can just copy your every move and win.

1 Like

Oh yes

No wait, According to my code also accounts for frequency>1 and so it puts longest as well as secondLongest as the same largest number , and if you plug that into the procedure i wrote on my post, it prints out “No” which is correct

Can you give me an input which I can’t run from my code which you can see at my post / give me a test case that fails

The basic idea is to count the max and second max. number of zeroes between two consecutive ones. If the max value is even, then he can not win and the answer will be zero. If the max value is an odd number then look for the second max., if the second max. is larger than or equal to half of the max.+1, then also the answer will be No. In all other cases, the answer will be ‘Yes’.
Here is the link to my submission: Game on a strip _ Rishi Garg

1 Like

Understood. doubts cleared

1 Like

Give me your submission.

What exactly does an optimal move mean? N always lands in the middle when it starts?Why?

Optimal move implies that the players will choose the best according to them and to increase their chance of winning and not in a particular fixed pattern.

Hi @gargrishi38 could you please give me a sample input for the second max verification case. Couldn’t understand the solution on that bit. My doubt is for 10010001 if she selects the middle element of 000 she can win right. so could you please explain on this front

Thanks in advance

No, she can’t. If she selects the middle element of (000), then the other player can select any element of 00 (second max. longest string of 0’s). Then the moves will be like (0)0(0)0 and now, it’s her turn and she don’t have any 0 to select.

Got it thanks