How to Find Errors in Algorithms: A Complete Guide

Problem with Your Algorithm: Incorrect Handling of Friends with Negative b_i

Your solution works incorrectly when friends with negative impact on authority require a complex selection order strategy.

Contents

• Main Problems with the Algorithm
• How to Identify Input Data Causing Errors
• Methods for Self-Debugging
• Optimizing the Order of Attracting Friends with Negative b_i
• Correct Solution to the Problem
• Conclusion

Main Problems with the Algorithm

Your algorithm has several critical flaws:

1. Incorrect sorting of friends with negative b_i: You sort bad_cultists by b_i (ascending), but this is not an optimal strategy.

2. Complex and incorrect logic in the loop: The conditions in the while loop are too complex and don’t cover all possible cases.

3. Lack of consideration for interdependence of decisions: When selecting friends with negative b_i, you need to consider that the current choice may affect the ability to select other friends.

As noted in research, greedy algorithms can be characterized as “short-sighted” and “non-recoverable”. They are ideal only for problems with “optimal substructure,” but your implementation doesn’t account for this feature for negative b_i.

How to Identify Input Data Causing Errors

1. Create test cases covering boundary conditions

// Example test cases that can reveal errors:
var test1 = new long[][] {
    new long[] { 10, 5, 0 },  // Requires 10, gives +5
    new long[] { 8, -3, 1 }, // Requires 8, gives -3
    new long[] { 6, -3, 2 }  // Requires 6, gives -3
};

var test2 = new long[][] {
    new long[] { 100, -50, 0 },
    new long[] { 50, -10, 1 },
    new long[] { 60, -40, 2 }
};

var test3 = new long[][] {
    new long[] { 10, -1, 0 },
    new long[] { 9, -1, 1 },
    new long[] { 8, -1, 2 },
    new long[] { 7, -1, 3 },
    new long[] { 6, -1, 4 }
};

2. Implement visualization of the process

Add output of intermediate states to your code:

Console.WriteLine($"Current authority: {authority}");
Console.WriteLine($"Considering friend: a={friend[0]}, b={friend[1]}");
Console.WriteLine($"After adding: {authority + friend[1]}");

3. Use manual tracing method

For complex cases, manually calculate all steps of the algorithm and compare with the expected result.

Methods for Self-Debugging

1. Proof by contradiction method

As recommended in research, use proof by contradiction:

1. Assume your greedy choice is not optimal
2. Take this assumption to an explicit contradiction

2. Break the problem into subproblems

Analyze how the algorithm behaves on different types of input data:

• Only friends with positive b_i
• Only friends with negative b_i
• Mixed cases with different combinations

3. Compare with known algorithms

For friends with negative b_i, this problem is similar to a “knapsack problem” with negative weights. Use approaches from dynamic programming to verify correctness.

4. Create a test generator

Write a program that generates random test cases and checks your solution against them:

Random random = new Random();
for (int i = 0; i < 1000; i++)
{
    long authority = random.Next(-100, 100);
    int n = random.Next(1, 20);
    long[][] cultists = GenerateRandomCultists(n);
    string result = Authority.GetMaxCultists(authority, cultists);
    // Check the result
}

Optimizing the Order of Attracting Friends with Negative b_i

For friends with negative b_i, a more complex strategy is needed:

1. Correct sorting

For friends with negative b_i, sort them by (a_i + b_i) in ascending order. This means we first select those friends with the minimum “threshold after addition.”

2. Using priority queues

As noted in research, greedy algorithms often use priority queues to get the next optimal element.

// For friends with negative b_i, use min-heap by (a_i + b_i)
var heap = new PriorityQueue<long[], long[]>(Comparer<long[]>.Create((x, y) => 
    (x[0] + x[1]).CompareTo(y[0] + y[1])));

3. Feedback algorithm

1. First, add all friends with positive b_i that we can
2. Then iteratively add friends with negative b_i:
   • Add a friend if current authority ≥ a_i
   • After adding, if authority becomes insufficient for some friend, remove the “worst” one (the one with minimum a_i + b_i)

Correct Solution to the Problem

Here’s a corrected version of your algorithm:

public static class Authority
{
    public static string GetMaxCultists(long authority, long[][] potential_cultists)
    {
        var positiveCultists = potential_cultists.Where(x => x[1] >= 0).ToArray();
        var negativeCultists = potential_cultists.Where(x => x[1] < 0).ToArray();
        
        // Sort positive ones by a_i
        Array.Sort(positiveCultists, (x, y) => x[0].CompareTo(y[0]));
        
        // For negative ones, use strategy: sort by (a_i + b_i)
        Array.Sort(negativeCultists, (x, y) => (x[0] + x[1]).CompareTo(y[0] + y[1]));
        
        var selected = new List<long>();
        long currentAuthority = authority;
        
        // Process positive ones
        foreach (var cultist in positiveCultists)
        {
            if (currentAuthority >= cultist[0])
            {
                currentAuthority += cultist[1];
                selected.Add(cultist[2]);
            }
        }
        
        // Create list of negative ones for processing
        var negativeList = negativeCultists.ToList();
        var toAdd = new List<long>();
        
        // Iteratively add negative ones
        bool changed;
        do
        {
            changed = false;
            for (int i = negativeList.Count - 1; i >= 0; i--)
            {
                var cultist = negativeList[i];
                if (currentAuthority >= cultist[0])
                {
                    // Check if we can add this friend
                    toAdd.Add(cultist);
                    negativeList.RemoveAt(i);
                    changed = true;
                }
            }
            
            // Sort by (a_i + b_i) to select the "best"
            toAdd.Sort((x, y) => (x[0] + x[1]).CompareTo(y[0] + y[1]));
            
            // Add all we can
            foreach (var cultist in toAdd)
            {
                if (currentAuthority >= cultist[0])
                {
                    currentAuthority += cultist[1];
                    selected.Add(cultist[2]);
                }
            }
            toAdd.Clear();
            
        } while (changed && negativeList.Count > 0);
        
        // Sort result by addition order
        selected.Sort();
        
        return $"{selected.Count}\n{string.Join(" ", selected)}";
    }
}

Conclusion

To successfully solve greedy algorithm problems with negative values, you need to:

1. Understand the nature of the problem: Problems with negative b_i require a more complex approach than simple sorting.

2. Use the correct sorting strategy: For negative values, the key parameter is (a_i + b_i).

3. Apply iterative methods: Sometimes you need to pass through the list multiple times, adding new friends as “space” becomes available.

4. Test on diverse data: Create tests covering boundary cases and combinations of positive/negative values.

5. Use visualization: Manual tracing and output of intermediate results help understand where the algorithm is going wrong.

As noted in research, “When we’re stuck, we usually debug the code based on test cases, modifying and verifying the greedy strategy step by step.” This approach is particularly important for complex greedy algorithms with negative values.

Sources

1. Basics of Greedy Algorithms Tutorial - HackerEarth
2. Greedy Algorithms - GeeksforGeeks
3. Greedy Algorithms - Hello Algo
4. Greedy Algorithms - Brilliant Math and Science Wiki
5. When to Use Greedy Algorithms - freeCodeCamp