1
\$\begingroup\$

I am currently trying to solve this problem on Codechef:

Before the start of each stage, N weapons appear on the screen in circular order. Each weapon has an integer associated with it, which represents its level. The chef can choose two adjacent weapons of the same level and fuse them into a single weapon of level A+1, where A is the level of the weapons before fusing. Both the old weapons will disappear and the new weapon will be placed in the place of the old weapons, shrinking the circle.

Chef can fuse as many times as he wants, and in each stage, he wants to make a weapon with as high a level as possible. Each stage is independent of other stages.

Please help Chef by figuring out the maximum level of a weapon that he can get in each stage.

However, my code seems to exceed the time limit. Can someone please tell me how to optimize this code to prevent it from exceeding the time limit?

#include <iostream>

using namespace std;

class Set
{
public:
    int data[200000];
    int length;
};

int findMax(int data[], int size)
{
    int max = data[0];
    for (int i = 1; i < size; i++)
    {
        if (max < data[i])
        {
            max = data[i];
        }
    }

    return max;
}

void mergeData(int data[], int &size)
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            if (data[i] == data[j])
            {
                data[i]++;

                for (int k = j; k < size - 1; k++)
                {
                    data[k] = data[k + 1];
                }
                size--;

                mergeData(data, size);
            }
        }
    }
}

//Main function
int main()
{
    int numSets;
    cin >> numSets;

    Set* sets = new Set[100];
    for (int i = 0; i < numSets; i++)
    {
        cin >> sets[i].length;
        for (int j = 0; j < sets[i].length; j++)
        {
            cin >> sets[i].data[j];
        }
    }

    for (int i = 0; i < numSets; i++)
    {
        mergeData(sets[i].data, sets[i].length);
        cout << findMax(sets[i].data, sets[i].length) << endl;
    }

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ This isn't a coding style question; it's a "find me an efficient algorithm" question. You can't magically make a bad algorithm "fast" by tweaking its style. Since all the solutions to CodeChef problems are public, why don't you just look at one of the existing solutions? \$\endgroup\$ – Quuxplusone Nov 17 '17 at 6:08
2
\$\begingroup\$

Looking at your merge_data() function, you'll notice that as soon as it finds 2 matching values, it combines them and recurses. What happens during and after the recursion? Let's take a look.

Suppose we have this set:

3,8,4,2,2,7,14

We first get 3. Next we start walking the rest of the list. We compare against 8. No match. We compare against 4. No match. We do this until we run out of things to compare. Then we increment i. We check the rest of the array. Etc. Eventually we come to the 2. We compare to the next value and there is a match! We combine them and recurse. What happens now? We start by comparing 3 to 8, which we've already done. Then again with 4, which we've also already done. So we're doing a bunch of work over and over again.

Then, eventually we return from our recursion. Now we go on to process the rest of the array. There's 2 problems here: 1) At this point, the recursion we're returning from has already processed the rest of the array, and 2) the array is no longer the same size, but we're going to process to the end of the original array anyway!

I haven't worked out a full solution, but hopefully the above is enough to help you see what's wrong with your current solution.

\$\endgroup\$
  • \$\begingroup\$ Sorting is completely out of the question, as the "weapons" have to be adjacent: "The chef can choose two adjacent weapons ". The index is important. \$\endgroup\$ – Zeta Nov 17 '17 at 7:01
  • \$\begingroup\$ Ah, I missed that point. I will update this. Thanks for pointing that out! \$\endgroup\$ – user1118321 Nov 17 '17 at 7:13
  • \$\begingroup\$ Thank you. I realised that my for loop was going through the whole array a lot! \$\endgroup\$ – kimchiboy03 Nov 18 '17 at 0:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.