Wrong Solution got Accepted


  • 0

    My first attempt is to write a brutal DFS, which accepted. However, I found if I change it to a clearly wrong solution, it still can be accepted. But I failed to come up with a test case to catch it. Can anyone help me make one? Wrong one in comment

    class Solution {
    public:
        bool PredictTheWinner(vector<int>& nums) {
            int res=DFS(nums,0,nums.size()-1,true);
            int sum=0;
            for(int it:nums)
                sum+=it;
            return res>=sum-res?true:false;
        }
        
        int DFS(vector<int>& nums, int left, int right, bool first) {
            if(left==right)
                return first?nums[left]:0;
                //return nums[left];
            else
                if(first)
                    return max(nums[left]+DFS(nums,left+1,right,!first), nums[right]+DFS(nums,left,right-1,!first));
                else
                    return min(DFS(nums,left+1,right,!first), DFS(nums,left,right-1,!first));
        }
    };
    

  • 0

    How do you know it's "clearly wrong"?


  • 0

    @StefanPochmann I think about it Intuitively, by skipping check if it's my turn, the first player wil pickup more scores then he could.

    For input like [1, 5, 233, 7], he could pickup 239 instead of 234.


  • 0

    @luming89 But that only means that your DFS function is "wrong" (I put that in quotes because you never specified what it's supposed to do). Not that the solution is wrong.


  • 0

    @StefanPochmann I'm using the DFS to mimic MaxMin algorithm, so if it picks something not supposed in the last turn, it is wrong i believe.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.