Did anyone attend the ACM Programming Contest at Wilkes University?

[mikelish]

I am looking for help in solving problem A from the contest.

Basically every team who entered the contest got A right. Just curious of your solution.

It deals with Permutation Recovery programming.

Text

 

[Kyteland]

The algorithm to solve this isn't terribly hard.

In the test case, parse the input in to arrays of some kind that represent each permutation.

in
{8 5 0 1 2 1 2 0 0 10 9 8 7 6 5 4 3 2 1 0 0}

out
{
{5 0 1 2 1 2 0 0}
{9 8 7 6 5 4 3 2 1 0 0}
}

Once you have that, feed the input into a function that reconstructs the data for each set. Basically, start with the smallest number and put it in its place. The value at that numbers position is its position in the array ignoring positions already filled.

so in the example data = {5 0 1 2 1 2 0 0}, data[0] = 5, so you should put the number 1 in the 6th open position.

data[0] = 5 result = {0 0 0 0 0 1 0 0}

The next element, data[1] = 0, so put the number 2 in the 1st open position.

data[1] = 0 result = {2 0 0 0 0 1 0 0}

The next element, data[2] = 1, so put the number 3 in the 2nd open position.

data[2] = 1 result = {2 0 3 0 0 1 0 0}

etc,

In c++ that would look something like this:

vector<uint> rebuildData(vector<uint> data)
{
vector<uint> result(data.size(), 0);

for (uint idxData=0; idxData<data.size(); idxData++)
{
uint idxResult=0;

// skip positions that have already been filled
while (result[idxResult] != 0)
{
idxResult++;
}

// Find the index for the current number
for (uint count=0; count<data[idxData]; count++)
{
idxResult++;

// skip positions that have already been filled
while (result[idxResult] != 0)
{
idxResult++;
}
}

// Store the number at the index
result[idxResult] = idxData+1;
}

return result;
}

 

[SophalotJack]

are you serious.... is this some sort of middle school competition?

 

[Kyteland]

Originally posted by: SophalotJack
are you serious.... is this some sort of middle school competition?

The ACM competitions are generally fairly difficult. There are a lot of problems and limited time to do them. If you think it's so easy, you're free to submit your own answers.

And your clock starts......

Now.

 

[eLiu]

Some of these are incredibly easy... geez. I have a friend on Duke's ACM team and the problems he has shown me are a lot harder, lol.