Thread: A Quicker Way Than Brute Force to solve a problem

Say you have a list containing the cases. You compare the sticks that are below( the second in each pair ) with every single above ones ( the first in pair ). If you find one above that isn't equal with any of the belows, you take that pair off the list. If you find no value, then it's Impossible. If the list becomes empty, it's Valid.

I think what I just described is the brute force algo, but why would it take 45 min???

Originally Posted by CommonTater

386 processor, maybe?

And that , but by trial and error I know that extreme slowdown points to ( really ) nasty bugs!

Code:

void conditionTesting (int sticks, int lines, int **conditions){
    int x;
    int y;
    int z;
    int stickisbelow = 0;
    int removed[sticks];
    
    for (x = 0; x < sticks-1; x++)
    {
        removed[x] = 0;
    }
    //tests each stick to see if it can be removed
    for (x = 1; x <= sticks; x++)
    {
        //will see if the stick is below any others, if it isn't, then it can be removed.
        for (y = 0; y < lines; y++)
        {
            if (x == conditions[y][1])
            {
                //increments if it finds the stick below any others
                //if it doesn't increment, that means that the stick is only above
                stickisbelow++;
            }
        }
        
        //if it only is above, then it will remove it from the above columnn and it moves all the sticks that were below it to the above column
        //will also keep track of sticks removed.
        if (stickisbelow == 0)
        {
            for (z = 0; z < lines; z++)
            {
                if (x == conditions[z][0])
                {
                    conditions[z][0] = conditions[z][1];
                    conditions[z][1] = 0;
                    removed[x]++;
                }
            }
        }
    }
    
    //checks to see if all sticks removed, if all the spots are 0 in the array
    int notremoved = 0;
    for (x = 0; x < lines; x++)
    {
        if (conditions[x][0] != 0 || conditions[x][1] != 0)
        {
            notremoved++;
        }
    }
    
    if (notremoved == 0)
    {
        printf("Valid\n");
    }
    else
    {
        printf("Impossible\n");
    }
}

It will take this long if you are checking
if each stick is below another and repeating check until you find it's impossible or if all the sticks are removed.

Is this similar to what you are talking about with the lists?

This isn't full, but it explains what i was working on. I know there must be a faster one, since we are supposed to get it to be able to return an answer in under a minute.

Code:

    int removed[sticks];
     
    for (x = 0; x < sticks-1; x++)
    {
        removed[x] = 0;
    }

I don't know why you aren't initializing the whole thing, but you could throw that loop out entirely:

Code:

int removed[ sticks ] = {0};

You also walk off the end of your array here possibly:

Code:

    for (x = 1; x <= sticks; x++)
    {
        //will see if the stick is below any others, if it isn't, then it can be removed.
        ...
                    removed[x]++;

Quzah.

Your code appears to be O(sticks * lines) in big-Oh notation and I'm guessing that those are high numbers. Any minor tweaks probably wont bring down the execution time that much. I expect that they've got the time limit set such that no O(sticks * lines) implementation can complete in under the time limit.

There are some similarities with how this code operates with that of how a naieve prime sieve works. My thoughts on improving the speed would be to apply the same kind of optimisation that The Sieve of Eratosthenes applies to prime sieving, to this problem.

A totally separate approach is to eliminate the need for looping over every line of the input to check each stick. Instead, when you read the file in sort the over/under relationship into buckets which reduces the search time. What I did for a quick test is have an array called is_above. Each entry in is_above[x] is a list of sticks which are on top of stick x. Se for each input line <upper, lower>, you'd do add_to_list(is_above[lower], upper). You make each entry of is_above a linked list or an array depending on how you want to do it - but I'd recommend a linked list to start since you'll be doing lots of random deletes from it later.

This way, instead of searching over a million lines to see what's possibly above a given stick, you can just check to see if is_above[x] is empty or not. This replaces a search of a million lines with a single test.

Then you just run through is_above[x], looking for entries which are empty and removing them. Removing is simple - add it to the results list and remove all references to stick x in any of the is_above[x] lists. You can do this brute force (i.e. iterate over every entry of each list in each is_above[0..sticks-1]), or you can be smarter and create a second list as well. This one keeps track of all the sticks which are below the current entry. When you remove a given stick x, iterate over this second list (call it is_below[x]) - the full content of this list will be the complete set of is_above[] entries which hold the stick you're removing. You'll then remove x from the lists at each of those locations in is_above[] - that last bit is still a linear search but will still shrink the run time quite a bit.