'Distirbute Candy - Finding minimum reproducible example of the problem

The question is to distribute candies to N children.Each child has a rating. Distribution should be such that each child have at least one candy and children with higher rating gets more candies than their neighbors. Find minimum number of candies for such distribution.

Approach:

  iterate each child.
       if (rating of curr child < rating of next child)
              add to total and increase candy
       else if (rating of curr child equal to rating of next child)
              we can bring down candy for next child to 1
       else if ( rating of curr child > rating of next child)
              {     // if child ratings are {4 3 2 5} then 
                    //optimal is {3 2 1 2}
                  //the detailed code is below
              }

The detailed code is :

int n = A.size();
int count  = 0;
int step = 1;
int i = 0;
bool run = true;
while(run){
    if(i+1 ==n){
        count+=step;
        run = false;
    }
    else if(A[i+1] > A[i]){
        count+=step;
        step++;
        i+=1;;
    }else if(A[i+1] == A[i]){
        count+=step;
        step = 1;
      
        i+=1;
    }else {
        int j = i;
        while(A[i+1] < A[i]&& (i+1)<n){
            i+=1;
        }
        
        int x = i-j;
        step = max(step,x+1);
        count+=step;
        count+=((x*(x+1))/2);
        step = 2;
        if(i==n-1)
            run = false;
        i+=1;
        
    }
}


 return count;

The code doesn't produce expected output. Due to huge size of test case, I cannot determine cause of error. Can someone provide sample test case where it breaks?

The failed test case is attached in below link. The first number denotes size of array. Breaking test case

c++arraysalgorithmdata-structuresgreedy


Solution 1:[1]

If you only need an example that exposes an error in your code, use 3 2 2 and stop reading.

I would suggest a very literal solution to the problem:

  1. Initialize a result array of equal size as the A array with value 1 for each position (each child gets at least one candy)
  2. Forward iterate the arrays and apply following logic
  3. Backward iterate the arrays and apply following logic
  4. Compute the sum of the result array

Logic for steps 2 and 3:

if (A[current] > A[previous] && result[current] <= result[previous])
    result[current] = result[previous] + 1;

Solution 2:[2]

iterate each child. if (rating of curr child < rating of next child) add to total and increase candy else if (rating of curr child equal to rating of next child) we can bring down candy for next child to 1 else if ( rating of curr child > rating of next child) { // if child ratings are {4 3 2 5} then //optimal is {3 2 1 2} //the detailed

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 grek40
Solution 2 Nguy?n Lân

Related Questions