# 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