The Flipping Game Codeforces

general
,
1

I just learnt maximum subarray sum and tried implementing it in this problem, The Flipping Game, but I am getting WA on 1 test case.

Problem link: http://codeforces.com/contest/327/problem/A

My code: https://www.dropbox.com/s/eb64om2pk1pq77i/CF%20Flipping%20Game.cpp?dl=0

Test case for which my code fails

100

0 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1

I tried debugging and figured out that something is wrong with the maximum sub array function of my program. But couldn’t fix it. Kindly help me understand my error.

2

See what your code is doing, let n=4.

call func(a,4)
    m=4/2 = 2
  /         \
 func(a,2)   func(a,(4-2)) -> see below why this is incorrect. 
 m= 2/2=1          
   /   \           
func(a,1) func(a,1)
 |           |-> this call also returns a[0] which is incorrect, call is for the range (2,2)
\|/
this left call returns a[0] which is correct

In the call func(a,(4-2)) i.e. right recursive call, you intend calculating sum of the range[3,4]. But how does your code know that? You have just passed (a,2) which has nowhere mention of the fact that it corresponds to the range [3,4]. It assumes it to be [0,2] which is absolutely wrong. The call proceeds in the manner your left call func(a,2) proceeds. That’s why upper and lower limit of every range is required in every step of recursion which is different for every recursive call.

I changed your code to this and it works fine, However, there’s a simple O(n) approach(Kadane’s algorithm) for finding the maximum subarray which you can see here.

Hope it clears… :slight_smile:

2 Likes
3

Oh got it I am sorry

4

@damn_me I am so sorry, I really didn’t get what you are trying to say. The 2nd recursive call will return maximum of (0 to 25) and (26 to 50) i.e. ((51/2)+1 to 50) not (25 to 50). I still don’t understand why right halves and left halves are not (mid+1,n) and (0,mid) in all recursive calls.

I read about Kadane’s algorithm as well but wanted to employ Divide and Conquer in this problem to enhance my understanding of recursion.

5

I edited above with the visual of how recursion is proceeding. I think it’ll help, any doubt ask freely :slight_smile: Also, I’d suggest see some video of the same… that may make it more clear.

6

@damn_me thanks a lot, I understood my fault and got it accepted. However, for the following test case the corrected/accepted code returns 2 on my PC

3

1 0 1

But the actual answer is 3, because we can select 0 in our move and change it to 1, thus getting 3 1s and not 2. What could be the problem?

7

See the link again, 87RkJA - Online C++0x Compiler & Debugging Tool - Ideone.com Line 11, it should return a[low], the code gives 3 now. This is the correct answer and the previous accepted one gave wrong as 2. You can please write to the codeforces team as their online judge accepted a wrong solution orlet me know if you haven’t done yet, i’ll mail them.