Can this be done more efficiently?

[Nineshadow]

Ok so , after quite a lot of processing, I end up with a matrix of 1-s and 0-s.

Example :

1 0 1 1 1 0 10 1 1 1 0 0 10 1 0 1 0 1 00 0 0 0 1 1 0

The 1-s can form different "groups" if they are directly adjacent to each other ( not diagonally ) , for example :

 

0 1 0

1 1 1

 

The bolded 1-s are part of a single group.

 

I need to output the size of the biggest group in the matrix (with the most 1-s).

 

The problem I'm talking about is task 3. Also, keep in mind this is translated with Google Translate , I'm not sure how much sense it makes.

 

Residents of Codeland war has been declared by merciless barbarians Town Common, more numerous and specialized in the fight. Since among codelandieni there a wizard old former student of the Faculty of Automatic Control and Computers, he has pledged to use the latest power to send you to you, students, base locations are situated fighters Codeland, that ye may join them in the safest bases. Magic, however, is more complicated than that, and you, the students, you must prove worthy of the access it! Data transmitted encrypted wizard come to you, along with a parchment that explains the rules decryption.

Task 1

40% of the score on tests

The first prime number, b, is the main ingredient of magic. This is followed by the dimensions of the land on which bases are located, m and n, which is structured like a matrix. The land contains lines between 0 and m-1 and columns between 0 and n-1. Until the meeting of -1, you will be offered a series of numbers that you must decoded; b represents the maximum number of bits that you can retain once.

Considering that b is equal to 3, and the sequence numbers 2, 3, 1, 5, 1 (binary, 10, 11, 1, 101), the newly formed thread will be 1 0 1 1 1 0, as follows:

take those two bits of 2 because not reach the limit of b; (1 0)

of the 2 bits of three, we can only take the first time I've reached the maximum number of bits that can retain them at once; (1 0 1)

the second bit of number three is ignored;

we only bit of '1'; (1 0 1 1)

Consider just the first 2 bits of 5 and ignore the past because it exceeds the limit imposed by b. (1 0 1 1 1 0)

The first part of this theme involves finding the bitstream using your number b and string of numbers provided by the wizard.

Task 2

30% of the score on tests

The new coordinates can be extracted string bases where soldiers are located; to meeting the pair {-1, -1}, you are offered every type [x, y] to be interpreted as follows:

the number of bits formed in the range [x, y] represents the position in the array;

Consider the sequence of bytes 1 0 1 0 1 1 1 0 1, x = 3, y = 7, m = 4, n = 5. The number you dialed is 14 (0 1 1 1 0), and the correspondence of the array illustrated in the image below.

where y <x, x> = dimensiune_sir_biti or y <0, the pair {x, y} is ignored and passed to the next;

if x <0 then x = 0;

where y> = dimensiune_sir_biti when y = position of the last bit of the string (dimensiune_sir_biti - 1);

where y - x> 30, y is reduced as necessary to form a maximum of 31 bits (⇐2147483647);

where in the interval [x, y] to form a number that exceeds that of the matrix, the number will be reduced to the value of the modulo m * n.

To get the score of the second task, you must display a row, separated by space coordinates bases.

Task 3

30% of the score on tests

Once you find the coordinates of the bases are situated soldiers must find the safest "meeting grounds". A meeting of the bases is more bases of any property that can be reached only by passing any other bases. Switching from a base to another can be done in either direction up, down, left or right (not diagonally). Safety is the number of bases included in a meeting. We believe that the matrix base is identified by the number 1, and the absence of base in that position is given the number 0.

Input data

From the keyboard you get on the first line three variables b, m and n, representing the decryption key, the number of land lines of war and the number of columns. On the next line you'll get a string of numbers that end with -1. On the following lines you will get two numbers x and y, meaning above and on the bottom line you will find the pair [-1, -1].

Output Data

In the "codewar.out" will display on the first line bitstream found after the fulfillment of the task 1, all numbers dialed on the next line at TASK 2 and the last line on the cell coordinates of top-left of the safest meeting and the number of bases making up. If several meetings with the same maximum number of bases will be displayed all on different lines. The format is as follows: SIR_DE_BITI SIR_DE_NUMERE NR_BAZE LIN LIN COL COL NR_BAZE ...

Example

Input

4 4 2 19 8 5 1 6 -1 1 2 1 4 2 5 8 17 4 5 19 2 3 -1 -1 -1

Output

0 1 0 0 1 1 0 0 0 1 1 1 0 1 4 9 14 4 14 2 0 1 2

Explanations

The binary string is 10, 10011, 1000, 1, 110. The new string formed will be 1 0 1 0 0 1 0 0 0 1 1 1 0, as follows:

take those two bits of 2 because not reach the limit of b; (1 0)

of the 5 bits of 19, we can only take the top 3, at which time we reached the maximum number of bits that can retain them at once; (1 0 1 0 0)

the last two bits of 19 are ignored;

Take the 4 bits of 8 because not reach the limit of b; (1 0 1 0 0 1 0 0 0)

we only bit of number 1 and complete a single bit left until the limit of b bits; (1 0 1 0 0 1 0 0 0 1)

We take all the bits of the number 6 because it does not reach the limit of b; (1 0 1 0 0 1 0 0 0 1 1 1 0)

The positions in the matrix are:

1 (0 1)

4 (0 1 0 0)

9 (1 0 0 1)

14 (0 1 1 1 0)

20% (4 * 4) = 4 (1 0 1 0 0)

128 + 8 + 4 + 2 = 142% (4 * 4) = 14 (1 0 0 0 1 1 1 0)

2 (1 0)

Matrix will look like this:

1 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0

The surest basis is given by the meeting of the two settlements on the first line (line 0), from the second column (column 1).

Details of the implementation theme

1 <m, n <400

0 <b <31

 

For the first example matrix, the result would be 8.

1 0 1 1 1 0 1

0 1 1 1 0 0 1

0 1 0 1 0 1 0

0 0 0 0 1 1 0

 

I did it pretty easily using a flood fill-like algorithm, while also setting each 1 I access to 0 so I won't encounter it again.

Do you guys know any other and more efficient way this could be done?

//example matrixint v[] = {1, 0, 1, 1, 1, 0, 1,           0, 1, 1, 1, 0, 0, 1,           0, 1, 0, 1, 0, 1, 0,           0, 0, 0, 0, 1, 1, 0          };int n = 4, m = 7;int k = 0;void flipAdjacent1(int* nums, int rows, int cols, int index){    stack<int> group;    group.push(index);    while(!group.empty())    {        int topIndex = group.top();        group.pop();        if(nums[topIndex]==1)k++;        nums[topIndex] = 0;        int row = topIndex / cols;        int col = topIndex % cols;        if(row > 0 && nums[(row - 1) * cols + col] == 1)            group.push((row - 1) * cols + col);        if(col < cols - 1 && nums[row * cols + col + 1] == 1)            group.push(row * cols + col + 1);        if(row < rows - 1 && nums[(row + 1) * cols + col] == 1)            group.push((row + 1) * cols + col);        if(col > 0 && nums[row * cols + col - 1] == 1)            group.push(row * cols + col - 1);    }}int groupOf1(int* nums, int rows, int cols){    int max = 0;    if(nums == NULL || rows <= 0 || cols <= 0)        return 0;    for(int i = 0; i < rows * cols; ++i)    {        k = 0;        if(nums[i] == 1)        {            flipAdjacent1(nums, rows, cols, i);            if(k > max) max = k;        }    }    return max;}int main(){    cout << groupOf1(v, n, m);    return 0;}

[Nineshadow]

Also added the entire problem for those interested.

[Nineshadow]

Nobody?

[as96]

Like a karnaugh map?

[BrightCandle]

Its of the order of O(2*n) so its about as good as the algorithm can be. The code however is hard to follow and this contributes as to why you aren't getting many comments, its bad code for a variety of reasons.

 

Personally I would go about approaching this a little differently, I would create a set of tuples (x,y) and then iterate through those, when finding a 1 I would do a similar algorithm that you have used to find the group but then return the tuple (size, remainingLocations) and then continue iteration on the remainingLocations. Thus we would avoid iterating over locations we know have been visited and should tend towards O(1*n). Whether or not its faster is hard to know as the Set implementation operation is going to impact performance enormously. Still its an O(n) algorithm and its obvious we must visit every location so it can never become sub O(n) so its of the right order even if it does some rework checking locations that are now 0 when we know actually we set them that way.

[Nineshadow]

Its of the order of O(2*n) so its about as good as the algorithm can be. The code however is hard to follow and this contributes as to why you aren't getting many comments, its bad code for a variety of reasons.

 

Personally I would go about approaching this a little differently, I would create a set of tuples (x,y) and then iterate through those, when finding a 1 I would do a similar algorithm that you have used to find the group but then return the tuple (size, remainingLocations) and then continue iteration on the remainingLocations. Thus we would avoid iterating over locations we know have been visited and should tend towards O(1*n). Whether or not its faster is hard to know as the Set implementation operation is going to impact performance enormously. Still its an O(n) algorithm and its obvious we must visit every location so it can never become sub O(n) so its of the right order even if it does some rework checking locations that are now 0 when we know actually we set them that way.

 

It doesn't iterate through already discovered locations when "building" the group.

 

How it works:

We go through our matrix, until we find a 1. Then, we create a stack to hold positions of the adjecent 1-s , then we use the top element in the stack as our new reference cell and so on, until the stack becomes empty. At the same time, every 1 which I encounter is set to 0 so I don't run up against it again. Then I keep iterating through the matrix , until I find another 1 , and do the same thing again.

[BrightCandle]

It doesn't iterate through already discovered locations when "building" the group.

 

How it works:

We go through our matrix, until we find a 1. Then, we create a stack to hold positions of the adjecent 1-s , then we use the top element in the stack as our new reference cell and so on, until the stack becomes empty. At the same time, every 1 which I encounter is set to 0 so I don't run up against it again. Then I keep iterating through the matrix , until I find another 1 , and do the same thing again.

 

Your outer loop revisits the zeros and checks those. So you tend towards visiting every location twice in the worst case.

 

This code has global side effects and it has local side effects as well, I am not a fan of either as it makes it hard to read and understand. It might be the most efficient way but I think my functional approach makes the system easier to follow and potentially faster as well all without changing the original data.