1

I'm having issues figuring out how to solve this problem without using recursion (I'm not sure how to solve things recursively). Its a program that determines the winner of a Tideman election and I'm getting the "skips middle pair" error. I've adjusted my approach multiple times and have come up with this idea:

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{

//Going through each pair and determining if it can be locked.     
    for (int i = 0; i < pair_count; i++)
    {
        locked[pairs[i].winner][pairs[i].loser] = true;

        if (canilock(candidate_count))
        {
            locked[pairs[i].winner][pairs[i].loser] = false;
        }
    }


    return;
}

bool canilock(int k)
{

//creating an int r that I will increment every time there is a unique locked winner
//creating an array of bools that is true when candidate k is a winner at least once

    int r = 0;
    bool edge[k];
    for (int i = 0; i < k; i++)
    {
        edge[i] = false;
    }

    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < k; j++)
        {
            if (locked[i][j] == true)
            {
                edge[i] = true;
            }

        }
    }

    for (int i = 0; i < k; i++)
    {
        if (edge[i] == true)
        {
            r++;
        }
    }

//if the number of unique winners is equal to the number of candidates then there is a loop by definition
    if (r == k)
    {
        return true;
    }

    return false;

}

Not sure why this would skip middle pair. Does this problem want the program to work such that there is never a loop even if the loop doesn't change the winner? For instance, if there are 5 candidates and 3 of them are somehow in a loop, but the source/winner is not. Does the problem call for even the submatrix to be unlooped? If so, how do I do that?

  • I've changed my approach to remove any assumption and I'm still getting the "skips middle pair" error. – timmy a May 26 at 16:43

You must log in to answer this question.

Browse other questions tagged .