Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

VandanRogheliya's blog

Can someone help me find mistake in my code?
By VandanRogheliya, history, 6 years ago, In English

While solving this question I came up with this solution. I was getting WA. I checked my code 5 times, I was not able to find a mistake. Then Finally I checked the editorial, it was the same dp but in an iterative form. Can someone point out the mistake?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I think this line is wrong else Max = max(Max, recFun(dp,j));. Why is it there?

i.e. Let $$$P_{smax}$$$ be the position of the max S values. If this is in the first half of the array you will have $$$dp[P_{smax}]=2$$$ at some point of time, which is not correct.

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    If I do not put else Max = max(Max, recFun(dp,j)); then for the test cases where $$$s[0]$$$ is not included will fail.

    And I did not get your 2nd point. You are trying to say if max from array S is in the first half then code would fail? If so, I checked, the code works for that test case.

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I modified your code, this works. 80869160

      Still I think the else Max = max(Max, recFun(dp,j)); is wrong. Imaging s[100] there is the max value of all s[]. At dp[200] there is some value!=1, say 42. In this case you will have dp[100]=42, too. And mayby dp[50]=43, what is completly wrong.

      So, after I removed that line it still not worked. The reason is that then not all dp states get calculated. Imagine the max s[] value at idx=1, then there is no recusion at all. So I changed the code that the recFun() is called for every index starting at n backwards to 1.

      → Reply
»
6 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

The mistake is that it fails test case 2.

→ Reply
»
6 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Maybe this is not the simplest test case, but here it goes:

1
16
4 5 6 1 6 6 6 2 6 6 6 6 6 6 6 3

(The only positions that matter here are the ones that don't contain 6)

Your output is 4, but answer is 3.

The reason is (I think)

else Max = max(Max, recFun(dp,j))

→ Reply