We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Greedy
- Candies
- Discussions
Candies
Candies
Sort by
recency
|
663 Discussions
|
Please Login in order to post a comment
I did not sove this problem with dynamic programming, I just looked at the cases and where they fail. You can start from the second student and give more candy to the next student who score more than the first and so on, but we don't get to know what peg to choose when the next student score less from 1 to previous student's candy. So. we do nothing and repeat the process doing the same approach from the end trying to find next incements. Here's the code.
Please tell, why this solution is not working. long candies(int n, vector arr) { long sum = 0; vector c(n, 0); c[0] = 1; for (int i = 1; i < n; i++){ if(arr[i-1] < arr[i]){ c[i] = c[i-1] + 1; } else if(arr[i-1] == arr[i]) c[i] = 1; else{ if(c[i-1] != 1){ c[i] = 1; } else{ c[i] = 1; int start = i; while(c[start] == c[start-1] && start >= 1 && start - 1 >= 0){ c[start-1] += 1; start--; } }
} }
sum = std::accumulate(c.begin(), c.end(), sum }
in this sample test case 1 10 2 4 2 6 1 7 8 9 2 1
if we assue me they are sitting in a row first kid(10) should get more candies thand sencond(2) kid as 10 is higher ranking than 2. so distribution should be like 2,1,2,1,2,1,2,3,4,2,1 ... anyways question is not clear
Please tell why my testcases are faling long candies(int n, vector arr) { long ans=1; long curr_val=1; int i; int flag=0; stack st; if(n==1){return 1;} for( i=1;i
}