Solving “ Tricolor Arrangement ” Efficiently












4














A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish such a task or prove that such an algorithm does not exist.



Let $mathcal{O}(1)$ be the cost of swapping the counters in the same row.



Iterate over each column. Let us consider that up to column $i-1$, we are done. Now we are at column $i$, there will be three counters, if they are of different colors then we are done, else fix one counter ( say white ) and scan other two rows to get two different color counters ( red and blue ). Running the previous step for a constant number of times ( six ) will solve the problem. More precisely there will be six possibilities in each column (123,132,.....,321), so I will try each of those.



The runtime of the above algorithm will be $mathcal{O}(n^3)$ as there are $n$ columns and time spent on each column is $mathcal{O}(n^2)$.



Question: Is it possible to solve the above-described problem linear time $mathcal{O}(n)$ time as input here has size $mathcal{O}(n)$? I am not even able to come up with an algorithm faster than $mathcal{O}(n^3)$ time.



I have taken this question from the book titled Algorithmic Puzzles ( problem 46 )










share|cite|improve this question






















  • You say counter, is that just something like a pebble or also something that holds a number? Also, what is the initial configuration - random?
    – orlp
    Dec 30 '18 at 10:58










  • @ orlp Each type of a counter is a fixed number. For an example red counter have value 2 and so on
    – aaag
    Dec 30 '18 at 12:05
















4














A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish such a task or prove that such an algorithm does not exist.



Let $mathcal{O}(1)$ be the cost of swapping the counters in the same row.



Iterate over each column. Let us consider that up to column $i-1$, we are done. Now we are at column $i$, there will be three counters, if they are of different colors then we are done, else fix one counter ( say white ) and scan other two rows to get two different color counters ( red and blue ). Running the previous step for a constant number of times ( six ) will solve the problem. More precisely there will be six possibilities in each column (123,132,.....,321), so I will try each of those.



The runtime of the above algorithm will be $mathcal{O}(n^3)$ as there are $n$ columns and time spent on each column is $mathcal{O}(n^2)$.



Question: Is it possible to solve the above-described problem linear time $mathcal{O}(n)$ time as input here has size $mathcal{O}(n)$? I am not even able to come up with an algorithm faster than $mathcal{O}(n^3)$ time.



I have taken this question from the book titled Algorithmic Puzzles ( problem 46 )










share|cite|improve this question






















  • You say counter, is that just something like a pebble or also something that holds a number? Also, what is the initial configuration - random?
    – orlp
    Dec 30 '18 at 10:58










  • @ orlp Each type of a counter is a fixed number. For an example red counter have value 2 and so on
    – aaag
    Dec 30 '18 at 12:05














4












4








4


3





A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish such a task or prove that such an algorithm does not exist.



Let $mathcal{O}(1)$ be the cost of swapping the counters in the same row.



Iterate over each column. Let us consider that up to column $i-1$, we are done. Now we are at column $i$, there will be three counters, if they are of different colors then we are done, else fix one counter ( say white ) and scan other two rows to get two different color counters ( red and blue ). Running the previous step for a constant number of times ( six ) will solve the problem. More precisely there will be six possibilities in each column (123,132,.....,321), so I will try each of those.



The runtime of the above algorithm will be $mathcal{O}(n^3)$ as there are $n$ columns and time spent on each column is $mathcal{O}(n^2)$.



Question: Is it possible to solve the above-described problem linear time $mathcal{O}(n)$ time as input here has size $mathcal{O}(n)$? I am not even able to come up with an algorithm faster than $mathcal{O}(n^3)$ time.



I have taken this question from the book titled Algorithmic Puzzles ( problem 46 )










share|cite|improve this question













A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish such a task or prove that such an algorithm does not exist.



Let $mathcal{O}(1)$ be the cost of swapping the counters in the same row.



Iterate over each column. Let us consider that up to column $i-1$, we are done. Now we are at column $i$, there will be three counters, if they are of different colors then we are done, else fix one counter ( say white ) and scan other two rows to get two different color counters ( red and blue ). Running the previous step for a constant number of times ( six ) will solve the problem. More precisely there will be six possibilities in each column (123,132,.....,321), so I will try each of those.



The runtime of the above algorithm will be $mathcal{O}(n^3)$ as there are $n$ columns and time spent on each column is $mathcal{O}(n^2)$.



Question: Is it possible to solve the above-described problem linear time $mathcal{O}(n)$ time as input here has size $mathcal{O}(n)$? I am not even able to come up with an algorithm faster than $mathcal{O}(n^3)$ time.



I have taken this question from the book titled Algorithmic Puzzles ( problem 46 )







algorithms complexity-theory






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Dec 30 '18 at 7:39









aaag

1,106416




1,106416












  • You say counter, is that just something like a pebble or also something that holds a number? Also, what is the initial configuration - random?
    – orlp
    Dec 30 '18 at 10:58










  • @ orlp Each type of a counter is a fixed number. For an example red counter have value 2 and so on
    – aaag
    Dec 30 '18 at 12:05


















  • You say counter, is that just something like a pebble or also something that holds a number? Also, what is the initial configuration - random?
    – orlp
    Dec 30 '18 at 10:58










  • @ orlp Each type of a counter is a fixed number. For an example red counter have value 2 and so on
    – aaag
    Dec 30 '18 at 12:05
















You say counter, is that just something like a pebble or also something that holds a number? Also, what is the initial configuration - random?
– orlp
Dec 30 '18 at 10:58




You say counter, is that just something like a pebble or also something that holds a number? Also, what is the initial configuration - random?
– orlp
Dec 30 '18 at 10:58












@ orlp Each type of a counter is a fixed number. For an example red counter have value 2 and so on
– aaag
Dec 30 '18 at 12:05




@ orlp Each type of a counter is a fixed number. For an example red counter have value 2 and so on
– aaag
Dec 30 '18 at 12:05










2 Answers
2






active

oldest

votes


















2














An idea can be to reduce this problem to sorting.



Consider a final configuration with each colour appearing exactly once per column. You can move the columns around to obtain a final configuration that looks like that :



aaaaaaaaaaaa|bbbbbbbbbbbbbbb|ccccccccccccccccccc
bbbbbb|ccccc|cccccccc|aaaaaa|aaaaaaaaa|bbbbbbbbb
cccccc|bbbbb|aaaaaaaa|cccccc|bbbbbbbbb|aaaaaaaaa


Where $a, b$ and $c$ are the three distinct colours. We are now going to create that kind of configuration. Let $a_1$ (resp. $b_1$ and $c_1$) denote the number of $a$'s (resp. $b$'s and $c$'s on the first row), same with $2$ on the second row. We can find those by counting, a simple $mathcal{O}(n)$ first pass.



Now let $x_*, y_*$ denote the size of the first and second chunk of the colour $*$ on the second row (i.e. we have $x_a, x_b$, etc...). You can see it that way for the first two rows :



|    a_1    |     b_1   |    c_1    |
| x_b | x_c | y_c | x_a | y_a | y_b |


We then have the following equations :




  • $a_1 = x_b + x_c$

  • $b_1 = y_c + x_a$

  • $c_1 = y_a + y_b$


  • $x_a + y_a = a_2$ and so on.
    $6$ equations with $6$ unknowns : you can find the size of each block - you only need to know the number of times each colours appears on rows 1 and 2.


Now create 3 arrays of weights, one for each row :




  • On the first row, give weight $0$ to elements of colour $a$, $1$ to elements $b$, $2$ to elements of colour $c$.

  • On the second row, give weight $0$ to $x_b$ elements of colour $b$, weight $1$ to $x_c$ elements of colour $c$, etc.

  • Same on the third row, but with the other colours.


This an be done in $mathcal{O}(n)$ by simply iterating the arrays (First row and weight array for the first row) and keeping track of how many elements of each colour we have seen so far.



Then sort each row : we obtain the solution described above. The complexity is then $mathcal{O}(n +f(n))$ where the sorting you use is $mathcal{O}(f(n))$.



So, now, all you have to do is to find a sorting algorithm that is efficient and that fits the problem : it has to sort by swapping elements. At least quicksort works (and you can find the median easily) so you have $O(nlog(n))$ complexity.



I think you could extend it to linear time using a sorting algorithm that counts.






share|cite|improve this answer





















  • Thanks for the answer. I have understood your idea. So now the algorithm will sort each ( suppose each counter have some value ). Note that sorting can be done in $mathcal{O}(n)$ time. Iterate over each column and now the things will be easy by using some pointers. Note that sorting in our case can be done in $mathcal{O}(n)$ time in our case.
    – aaag
    Dec 30 '18 at 11:48





















2














Here is an algorithm with $O(n)$ time-complexity.



First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r_i$, the number of white counters $w_i$, the number of blue counters $b_i$ on row $i$, $i=1,2,3$.



Second, we can solve the following equations for nonnegative integer variables $a_k$, $1le kle6$ in $O(1)$ time.



$$r_1 = a_1 + a_2$$
$$w_1 = a_3 + a_4$$
$$b_1 = a_5 + a_6$$
$$r_2 = a_4 + a_5$$
$$w_2 = a_1 + a_6$$
$$b_2 = a_2 + a_3$$
$$r_3 = a_3 + a_6$$
$$w_3 = a_2 + a_5$$
$$b_3 = a_1 + a_4$$



Third, we arrange the three rows into the following configuration.
$$
begin{array}{|l|l|l|l|l|l|} hline
a_1text{ red} & a_2text{ red} & a_3text{ white} & a_4text{ white} & a_5text{ blue} & a_6text{ blue} \hline
a_1text{ white} & a_2text{ blue} & a_3text{ blue} & a_4text{ red} & a_5text{ red} & a_6text{ white} \hline
a_1text{ blue} & a_2text{ white} & a_3text{ red} & a_4text{ blue} & a_5text{ white} & a_6text{ red} \hline
end{array}
$$





We are done.





Here are a couple of exercises that fill the gap in the above specification of the algorithm.



Exercise 1. Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a_k$, $1le kle6$, given the condition that $r_i+w_i+b_i=n$ for all $i$ and $sum_{i=1}^3r_i=sum_{i=1}^3w_i=sum_{i=1}^3b_i=n$. Show that there is always a solution.





Exercise 2. Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.





Here is a problem that may not be easy to do.



Problem 1. Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant. (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)






share|cite|improve this answer























  • The rearranging is massively simplified and easy to see how it can be done in $O(n)$ time with Dutch national flag problem. The red/blue/white color scheme is also a reference to this.
    – orlp
    Dec 30 '18 at 11:15












  • Thanks for the answer. I am trying to understand your answer. Are you solving the decision version which means yes/no output at the end or also ouput the one of the configuration.
    – aaag
    Dec 30 '18 at 12:02










  • Output all the columns, of course. For example, the first row. Iterate through the counters, moving the red ones to the front. Iterate again, moving the whites one after the red ones. Not terribly efficient, but enough to prove $O(n)$. No need to use sophisticated algorithm such as the one in Dutch national flag problem
    – Apass.Jack
    Dec 30 '18 at 12:05












  • The algorithm for the decision version of the problem is just one phrase, "Return yes".
    – Apass.Jack
    Dec 30 '18 at 12:12












  • @orlp, yes, it is always doable. Notice that we have same number of counter of each color initially. You may want to do my exercise 1.
    – Apass.Jack
    Dec 30 '18 at 12:38













Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102165%2fsolving-tricolor-arrangement-efficiently%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









2














An idea can be to reduce this problem to sorting.



Consider a final configuration with each colour appearing exactly once per column. You can move the columns around to obtain a final configuration that looks like that :



aaaaaaaaaaaa|bbbbbbbbbbbbbbb|ccccccccccccccccccc
bbbbbb|ccccc|cccccccc|aaaaaa|aaaaaaaaa|bbbbbbbbb
cccccc|bbbbb|aaaaaaaa|cccccc|bbbbbbbbb|aaaaaaaaa


Where $a, b$ and $c$ are the three distinct colours. We are now going to create that kind of configuration. Let $a_1$ (resp. $b_1$ and $c_1$) denote the number of $a$'s (resp. $b$'s and $c$'s on the first row), same with $2$ on the second row. We can find those by counting, a simple $mathcal{O}(n)$ first pass.



Now let $x_*, y_*$ denote the size of the first and second chunk of the colour $*$ on the second row (i.e. we have $x_a, x_b$, etc...). You can see it that way for the first two rows :



|    a_1    |     b_1   |    c_1    |
| x_b | x_c | y_c | x_a | y_a | y_b |


We then have the following equations :




  • $a_1 = x_b + x_c$

  • $b_1 = y_c + x_a$

  • $c_1 = y_a + y_b$


  • $x_a + y_a = a_2$ and so on.
    $6$ equations with $6$ unknowns : you can find the size of each block - you only need to know the number of times each colours appears on rows 1 and 2.


Now create 3 arrays of weights, one for each row :




  • On the first row, give weight $0$ to elements of colour $a$, $1$ to elements $b$, $2$ to elements of colour $c$.

  • On the second row, give weight $0$ to $x_b$ elements of colour $b$, weight $1$ to $x_c$ elements of colour $c$, etc.

  • Same on the third row, but with the other colours.


This an be done in $mathcal{O}(n)$ by simply iterating the arrays (First row and weight array for the first row) and keeping track of how many elements of each colour we have seen so far.



Then sort each row : we obtain the solution described above. The complexity is then $mathcal{O}(n +f(n))$ where the sorting you use is $mathcal{O}(f(n))$.



So, now, all you have to do is to find a sorting algorithm that is efficient and that fits the problem : it has to sort by swapping elements. At least quicksort works (and you can find the median easily) so you have $O(nlog(n))$ complexity.



I think you could extend it to linear time using a sorting algorithm that counts.






share|cite|improve this answer





















  • Thanks for the answer. I have understood your idea. So now the algorithm will sort each ( suppose each counter have some value ). Note that sorting can be done in $mathcal{O}(n)$ time. Iterate over each column and now the things will be easy by using some pointers. Note that sorting in our case can be done in $mathcal{O}(n)$ time in our case.
    – aaag
    Dec 30 '18 at 11:48


















2














An idea can be to reduce this problem to sorting.



Consider a final configuration with each colour appearing exactly once per column. You can move the columns around to obtain a final configuration that looks like that :



aaaaaaaaaaaa|bbbbbbbbbbbbbbb|ccccccccccccccccccc
bbbbbb|ccccc|cccccccc|aaaaaa|aaaaaaaaa|bbbbbbbbb
cccccc|bbbbb|aaaaaaaa|cccccc|bbbbbbbbb|aaaaaaaaa


Where $a, b$ and $c$ are the three distinct colours. We are now going to create that kind of configuration. Let $a_1$ (resp. $b_1$ and $c_1$) denote the number of $a$'s (resp. $b$'s and $c$'s on the first row), same with $2$ on the second row. We can find those by counting, a simple $mathcal{O}(n)$ first pass.



Now let $x_*, y_*$ denote the size of the first and second chunk of the colour $*$ on the second row (i.e. we have $x_a, x_b$, etc...). You can see it that way for the first two rows :



|    a_1    |     b_1   |    c_1    |
| x_b | x_c | y_c | x_a | y_a | y_b |


We then have the following equations :




  • $a_1 = x_b + x_c$

  • $b_1 = y_c + x_a$

  • $c_1 = y_a + y_b$


  • $x_a + y_a = a_2$ and so on.
    $6$ equations with $6$ unknowns : you can find the size of each block - you only need to know the number of times each colours appears on rows 1 and 2.


Now create 3 arrays of weights, one for each row :




  • On the first row, give weight $0$ to elements of colour $a$, $1$ to elements $b$, $2$ to elements of colour $c$.

  • On the second row, give weight $0$ to $x_b$ elements of colour $b$, weight $1$ to $x_c$ elements of colour $c$, etc.

  • Same on the third row, but with the other colours.


This an be done in $mathcal{O}(n)$ by simply iterating the arrays (First row and weight array for the first row) and keeping track of how many elements of each colour we have seen so far.



Then sort each row : we obtain the solution described above. The complexity is then $mathcal{O}(n +f(n))$ where the sorting you use is $mathcal{O}(f(n))$.



So, now, all you have to do is to find a sorting algorithm that is efficient and that fits the problem : it has to sort by swapping elements. At least quicksort works (and you can find the median easily) so you have $O(nlog(n))$ complexity.



I think you could extend it to linear time using a sorting algorithm that counts.






share|cite|improve this answer





















  • Thanks for the answer. I have understood your idea. So now the algorithm will sort each ( suppose each counter have some value ). Note that sorting can be done in $mathcal{O}(n)$ time. Iterate over each column and now the things will be easy by using some pointers. Note that sorting in our case can be done in $mathcal{O}(n)$ time in our case.
    – aaag
    Dec 30 '18 at 11:48
















2












2








2






An idea can be to reduce this problem to sorting.



Consider a final configuration with each colour appearing exactly once per column. You can move the columns around to obtain a final configuration that looks like that :



aaaaaaaaaaaa|bbbbbbbbbbbbbbb|ccccccccccccccccccc
bbbbbb|ccccc|cccccccc|aaaaaa|aaaaaaaaa|bbbbbbbbb
cccccc|bbbbb|aaaaaaaa|cccccc|bbbbbbbbb|aaaaaaaaa


Where $a, b$ and $c$ are the three distinct colours. We are now going to create that kind of configuration. Let $a_1$ (resp. $b_1$ and $c_1$) denote the number of $a$'s (resp. $b$'s and $c$'s on the first row), same with $2$ on the second row. We can find those by counting, a simple $mathcal{O}(n)$ first pass.



Now let $x_*, y_*$ denote the size of the first and second chunk of the colour $*$ on the second row (i.e. we have $x_a, x_b$, etc...). You can see it that way for the first two rows :



|    a_1    |     b_1   |    c_1    |
| x_b | x_c | y_c | x_a | y_a | y_b |


We then have the following equations :




  • $a_1 = x_b + x_c$

  • $b_1 = y_c + x_a$

  • $c_1 = y_a + y_b$


  • $x_a + y_a = a_2$ and so on.
    $6$ equations with $6$ unknowns : you can find the size of each block - you only need to know the number of times each colours appears on rows 1 and 2.


Now create 3 arrays of weights, one for each row :




  • On the first row, give weight $0$ to elements of colour $a$, $1$ to elements $b$, $2$ to elements of colour $c$.

  • On the second row, give weight $0$ to $x_b$ elements of colour $b$, weight $1$ to $x_c$ elements of colour $c$, etc.

  • Same on the third row, but with the other colours.


This an be done in $mathcal{O}(n)$ by simply iterating the arrays (First row and weight array for the first row) and keeping track of how many elements of each colour we have seen so far.



Then sort each row : we obtain the solution described above. The complexity is then $mathcal{O}(n +f(n))$ where the sorting you use is $mathcal{O}(f(n))$.



So, now, all you have to do is to find a sorting algorithm that is efficient and that fits the problem : it has to sort by swapping elements. At least quicksort works (and you can find the median easily) so you have $O(nlog(n))$ complexity.



I think you could extend it to linear time using a sorting algorithm that counts.






share|cite|improve this answer












An idea can be to reduce this problem to sorting.



Consider a final configuration with each colour appearing exactly once per column. You can move the columns around to obtain a final configuration that looks like that :



aaaaaaaaaaaa|bbbbbbbbbbbbbbb|ccccccccccccccccccc
bbbbbb|ccccc|cccccccc|aaaaaa|aaaaaaaaa|bbbbbbbbb
cccccc|bbbbb|aaaaaaaa|cccccc|bbbbbbbbb|aaaaaaaaa


Where $a, b$ and $c$ are the three distinct colours. We are now going to create that kind of configuration. Let $a_1$ (resp. $b_1$ and $c_1$) denote the number of $a$'s (resp. $b$'s and $c$'s on the first row), same with $2$ on the second row. We can find those by counting, a simple $mathcal{O}(n)$ first pass.



Now let $x_*, y_*$ denote the size of the first and second chunk of the colour $*$ on the second row (i.e. we have $x_a, x_b$, etc...). You can see it that way for the first two rows :



|    a_1    |     b_1   |    c_1    |
| x_b | x_c | y_c | x_a | y_a | y_b |


We then have the following equations :




  • $a_1 = x_b + x_c$

  • $b_1 = y_c + x_a$

  • $c_1 = y_a + y_b$


  • $x_a + y_a = a_2$ and so on.
    $6$ equations with $6$ unknowns : you can find the size of each block - you only need to know the number of times each colours appears on rows 1 and 2.


Now create 3 arrays of weights, one for each row :




  • On the first row, give weight $0$ to elements of colour $a$, $1$ to elements $b$, $2$ to elements of colour $c$.

  • On the second row, give weight $0$ to $x_b$ elements of colour $b$, weight $1$ to $x_c$ elements of colour $c$, etc.

  • Same on the third row, but with the other colours.


This an be done in $mathcal{O}(n)$ by simply iterating the arrays (First row and weight array for the first row) and keeping track of how many elements of each colour we have seen so far.



Then sort each row : we obtain the solution described above. The complexity is then $mathcal{O}(n +f(n))$ where the sorting you use is $mathcal{O}(f(n))$.



So, now, all you have to do is to find a sorting algorithm that is efficient and that fits the problem : it has to sort by swapping elements. At least quicksort works (and you can find the median easily) so you have $O(nlog(n))$ complexity.



I think you could extend it to linear time using a sorting algorithm that counts.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Dec 30 '18 at 11:17









GBat

1075




1075












  • Thanks for the answer. I have understood your idea. So now the algorithm will sort each ( suppose each counter have some value ). Note that sorting can be done in $mathcal{O}(n)$ time. Iterate over each column and now the things will be easy by using some pointers. Note that sorting in our case can be done in $mathcal{O}(n)$ time in our case.
    – aaag
    Dec 30 '18 at 11:48




















  • Thanks for the answer. I have understood your idea. So now the algorithm will sort each ( suppose each counter have some value ). Note that sorting can be done in $mathcal{O}(n)$ time. Iterate over each column and now the things will be easy by using some pointers. Note that sorting in our case can be done in $mathcal{O}(n)$ time in our case.
    – aaag
    Dec 30 '18 at 11:48


















Thanks for the answer. I have understood your idea. So now the algorithm will sort each ( suppose each counter have some value ). Note that sorting can be done in $mathcal{O}(n)$ time. Iterate over each column and now the things will be easy by using some pointers. Note that sorting in our case can be done in $mathcal{O}(n)$ time in our case.
– aaag
Dec 30 '18 at 11:48






Thanks for the answer. I have understood your idea. So now the algorithm will sort each ( suppose each counter have some value ). Note that sorting can be done in $mathcal{O}(n)$ time. Iterate over each column and now the things will be easy by using some pointers. Note that sorting in our case can be done in $mathcal{O}(n)$ time in our case.
– aaag
Dec 30 '18 at 11:48













2














Here is an algorithm with $O(n)$ time-complexity.



First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r_i$, the number of white counters $w_i$, the number of blue counters $b_i$ on row $i$, $i=1,2,3$.



Second, we can solve the following equations for nonnegative integer variables $a_k$, $1le kle6$ in $O(1)$ time.



$$r_1 = a_1 + a_2$$
$$w_1 = a_3 + a_4$$
$$b_1 = a_5 + a_6$$
$$r_2 = a_4 + a_5$$
$$w_2 = a_1 + a_6$$
$$b_2 = a_2 + a_3$$
$$r_3 = a_3 + a_6$$
$$w_3 = a_2 + a_5$$
$$b_3 = a_1 + a_4$$



Third, we arrange the three rows into the following configuration.
$$
begin{array}{|l|l|l|l|l|l|} hline
a_1text{ red} & a_2text{ red} & a_3text{ white} & a_4text{ white} & a_5text{ blue} & a_6text{ blue} \hline
a_1text{ white} & a_2text{ blue} & a_3text{ blue} & a_4text{ red} & a_5text{ red} & a_6text{ white} \hline
a_1text{ blue} & a_2text{ white} & a_3text{ red} & a_4text{ blue} & a_5text{ white} & a_6text{ red} \hline
end{array}
$$





We are done.





Here are a couple of exercises that fill the gap in the above specification of the algorithm.



Exercise 1. Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a_k$, $1le kle6$, given the condition that $r_i+w_i+b_i=n$ for all $i$ and $sum_{i=1}^3r_i=sum_{i=1}^3w_i=sum_{i=1}^3b_i=n$. Show that there is always a solution.





Exercise 2. Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.





Here is a problem that may not be easy to do.



Problem 1. Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant. (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)






share|cite|improve this answer























  • The rearranging is massively simplified and easy to see how it can be done in $O(n)$ time with Dutch national flag problem. The red/blue/white color scheme is also a reference to this.
    – orlp
    Dec 30 '18 at 11:15












  • Thanks for the answer. I am trying to understand your answer. Are you solving the decision version which means yes/no output at the end or also ouput the one of the configuration.
    – aaag
    Dec 30 '18 at 12:02










  • Output all the columns, of course. For example, the first row. Iterate through the counters, moving the red ones to the front. Iterate again, moving the whites one after the red ones. Not terribly efficient, but enough to prove $O(n)$. No need to use sophisticated algorithm such as the one in Dutch national flag problem
    – Apass.Jack
    Dec 30 '18 at 12:05












  • The algorithm for the decision version of the problem is just one phrase, "Return yes".
    – Apass.Jack
    Dec 30 '18 at 12:12












  • @orlp, yes, it is always doable. Notice that we have same number of counter of each color initially. You may want to do my exercise 1.
    – Apass.Jack
    Dec 30 '18 at 12:38


















2














Here is an algorithm with $O(n)$ time-complexity.



First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r_i$, the number of white counters $w_i$, the number of blue counters $b_i$ on row $i$, $i=1,2,3$.



Second, we can solve the following equations for nonnegative integer variables $a_k$, $1le kle6$ in $O(1)$ time.



$$r_1 = a_1 + a_2$$
$$w_1 = a_3 + a_4$$
$$b_1 = a_5 + a_6$$
$$r_2 = a_4 + a_5$$
$$w_2 = a_1 + a_6$$
$$b_2 = a_2 + a_3$$
$$r_3 = a_3 + a_6$$
$$w_3 = a_2 + a_5$$
$$b_3 = a_1 + a_4$$



Third, we arrange the three rows into the following configuration.
$$
begin{array}{|l|l|l|l|l|l|} hline
a_1text{ red} & a_2text{ red} & a_3text{ white} & a_4text{ white} & a_5text{ blue} & a_6text{ blue} \hline
a_1text{ white} & a_2text{ blue} & a_3text{ blue} & a_4text{ red} & a_5text{ red} & a_6text{ white} \hline
a_1text{ blue} & a_2text{ white} & a_3text{ red} & a_4text{ blue} & a_5text{ white} & a_6text{ red} \hline
end{array}
$$





We are done.





Here are a couple of exercises that fill the gap in the above specification of the algorithm.



Exercise 1. Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a_k$, $1le kle6$, given the condition that $r_i+w_i+b_i=n$ for all $i$ and $sum_{i=1}^3r_i=sum_{i=1}^3w_i=sum_{i=1}^3b_i=n$. Show that there is always a solution.





Exercise 2. Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.





Here is a problem that may not be easy to do.



Problem 1. Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant. (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)






share|cite|improve this answer























  • The rearranging is massively simplified and easy to see how it can be done in $O(n)$ time with Dutch national flag problem. The red/blue/white color scheme is also a reference to this.
    – orlp
    Dec 30 '18 at 11:15












  • Thanks for the answer. I am trying to understand your answer. Are you solving the decision version which means yes/no output at the end or also ouput the one of the configuration.
    – aaag
    Dec 30 '18 at 12:02










  • Output all the columns, of course. For example, the first row. Iterate through the counters, moving the red ones to the front. Iterate again, moving the whites one after the red ones. Not terribly efficient, but enough to prove $O(n)$. No need to use sophisticated algorithm such as the one in Dutch national flag problem
    – Apass.Jack
    Dec 30 '18 at 12:05












  • The algorithm for the decision version of the problem is just one phrase, "Return yes".
    – Apass.Jack
    Dec 30 '18 at 12:12












  • @orlp, yes, it is always doable. Notice that we have same number of counter of each color initially. You may want to do my exercise 1.
    – Apass.Jack
    Dec 30 '18 at 12:38
















2












2








2






Here is an algorithm with $O(n)$ time-complexity.



First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r_i$, the number of white counters $w_i$, the number of blue counters $b_i$ on row $i$, $i=1,2,3$.



Second, we can solve the following equations for nonnegative integer variables $a_k$, $1le kle6$ in $O(1)$ time.



$$r_1 = a_1 + a_2$$
$$w_1 = a_3 + a_4$$
$$b_1 = a_5 + a_6$$
$$r_2 = a_4 + a_5$$
$$w_2 = a_1 + a_6$$
$$b_2 = a_2 + a_3$$
$$r_3 = a_3 + a_6$$
$$w_3 = a_2 + a_5$$
$$b_3 = a_1 + a_4$$



Third, we arrange the three rows into the following configuration.
$$
begin{array}{|l|l|l|l|l|l|} hline
a_1text{ red} & a_2text{ red} & a_3text{ white} & a_4text{ white} & a_5text{ blue} & a_6text{ blue} \hline
a_1text{ white} & a_2text{ blue} & a_3text{ blue} & a_4text{ red} & a_5text{ red} & a_6text{ white} \hline
a_1text{ blue} & a_2text{ white} & a_3text{ red} & a_4text{ blue} & a_5text{ white} & a_6text{ red} \hline
end{array}
$$





We are done.





Here are a couple of exercises that fill the gap in the above specification of the algorithm.



Exercise 1. Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a_k$, $1le kle6$, given the condition that $r_i+w_i+b_i=n$ for all $i$ and $sum_{i=1}^3r_i=sum_{i=1}^3w_i=sum_{i=1}^3b_i=n$. Show that there is always a solution.





Exercise 2. Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.





Here is a problem that may not be easy to do.



Problem 1. Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant. (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)






share|cite|improve this answer














Here is an algorithm with $O(n)$ time-complexity.



First, count how many counters of each color there are on each row. With $O(n)$ time, we will obtain the number of red counters $r_i$, the number of white counters $w_i$, the number of blue counters $b_i$ on row $i$, $i=1,2,3$.



Second, we can solve the following equations for nonnegative integer variables $a_k$, $1le kle6$ in $O(1)$ time.



$$r_1 = a_1 + a_2$$
$$w_1 = a_3 + a_4$$
$$b_1 = a_5 + a_6$$
$$r_2 = a_4 + a_5$$
$$w_2 = a_1 + a_6$$
$$b_2 = a_2 + a_3$$
$$r_3 = a_3 + a_6$$
$$w_3 = a_2 + a_5$$
$$b_3 = a_1 + a_4$$



Third, we arrange the three rows into the following configuration.
$$
begin{array}{|l|l|l|l|l|l|} hline
a_1text{ red} & a_2text{ red} & a_3text{ white} & a_4text{ white} & a_5text{ blue} & a_6text{ blue} \hline
a_1text{ white} & a_2text{ blue} & a_3text{ blue} & a_4text{ red} & a_5text{ red} & a_6text{ white} \hline
a_1text{ blue} & a_2text{ white} & a_3text{ red} & a_4text{ blue} & a_5text{ white} & a_6text{ red} \hline
end{array}
$$





We are done.





Here are a couple of exercises that fill the gap in the above specification of the algorithm.



Exercise 1. Find an algorithm that solves in $O(1)$ time that system of 9 equations for nonnegative integer variables $a_k$, $1le kle6$, given the condition that $r_i+w_i+b_i=n$ for all $i$ and $sum_{i=1}^3r_i=sum_{i=1}^3w_i=sum_{i=1}^3b_i=n$. Show that there is always a solution.





Exercise 2. Check that arrangement in third step can be done in $O(n)$ time by swapping the counters in each row.





Here is a problem that may not be easy to do.



Problem 1. Generalize the problem of tricolor arrangement to $m$ rows and $m$ colors, $m>3$. Solve it with an $O(n)$ algorithm, assuming $m$ is a constant. (Hint, use Hall's marriage theorem to reduce the sum of the number of distinct colors in each row.)







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited 18 hours ago

























answered Dec 30 '18 at 11:13









Apass.Jack

7,3691633




7,3691633












  • The rearranging is massively simplified and easy to see how it can be done in $O(n)$ time with Dutch national flag problem. The red/blue/white color scheme is also a reference to this.
    – orlp
    Dec 30 '18 at 11:15












  • Thanks for the answer. I am trying to understand your answer. Are you solving the decision version which means yes/no output at the end or also ouput the one of the configuration.
    – aaag
    Dec 30 '18 at 12:02










  • Output all the columns, of course. For example, the first row. Iterate through the counters, moving the red ones to the front. Iterate again, moving the whites one after the red ones. Not terribly efficient, but enough to prove $O(n)$. No need to use sophisticated algorithm such as the one in Dutch national flag problem
    – Apass.Jack
    Dec 30 '18 at 12:05












  • The algorithm for the decision version of the problem is just one phrase, "Return yes".
    – Apass.Jack
    Dec 30 '18 at 12:12












  • @orlp, yes, it is always doable. Notice that we have same number of counter of each color initially. You may want to do my exercise 1.
    – Apass.Jack
    Dec 30 '18 at 12:38




















  • The rearranging is massively simplified and easy to see how it can be done in $O(n)$ time with Dutch national flag problem. The red/blue/white color scheme is also a reference to this.
    – orlp
    Dec 30 '18 at 11:15












  • Thanks for the answer. I am trying to understand your answer. Are you solving the decision version which means yes/no output at the end or also ouput the one of the configuration.
    – aaag
    Dec 30 '18 at 12:02










  • Output all the columns, of course. For example, the first row. Iterate through the counters, moving the red ones to the front. Iterate again, moving the whites one after the red ones. Not terribly efficient, but enough to prove $O(n)$. No need to use sophisticated algorithm such as the one in Dutch national flag problem
    – Apass.Jack
    Dec 30 '18 at 12:05












  • The algorithm for the decision version of the problem is just one phrase, "Return yes".
    – Apass.Jack
    Dec 30 '18 at 12:12












  • @orlp, yes, it is always doable. Notice that we have same number of counter of each color initially. You may want to do my exercise 1.
    – Apass.Jack
    Dec 30 '18 at 12:38


















The rearranging is massively simplified and easy to see how it can be done in $O(n)$ time with Dutch national flag problem. The red/blue/white color scheme is also a reference to this.
– orlp
Dec 30 '18 at 11:15






The rearranging is massively simplified and easy to see how it can be done in $O(n)$ time with Dutch national flag problem. The red/blue/white color scheme is also a reference to this.
– orlp
Dec 30 '18 at 11:15














Thanks for the answer. I am trying to understand your answer. Are you solving the decision version which means yes/no output at the end or also ouput the one of the configuration.
– aaag
Dec 30 '18 at 12:02




Thanks for the answer. I am trying to understand your answer. Are you solving the decision version which means yes/no output at the end or also ouput the one of the configuration.
– aaag
Dec 30 '18 at 12:02












Output all the columns, of course. For example, the first row. Iterate through the counters, moving the red ones to the front. Iterate again, moving the whites one after the red ones. Not terribly efficient, but enough to prove $O(n)$. No need to use sophisticated algorithm such as the one in Dutch national flag problem
– Apass.Jack
Dec 30 '18 at 12:05






Output all the columns, of course. For example, the first row. Iterate through the counters, moving the red ones to the front. Iterate again, moving the whites one after the red ones. Not terribly efficient, but enough to prove $O(n)$. No need to use sophisticated algorithm such as the one in Dutch national flag problem
– Apass.Jack
Dec 30 '18 at 12:05














The algorithm for the decision version of the problem is just one phrase, "Return yes".
– Apass.Jack
Dec 30 '18 at 12:12






The algorithm for the decision version of the problem is just one phrase, "Return yes".
– Apass.Jack
Dec 30 '18 at 12:12














@orlp, yes, it is always doable. Notice that we have same number of counter of each color initially. You may want to do my exercise 1.
– Apass.Jack
Dec 30 '18 at 12:38






@orlp, yes, it is always doable. Notice that we have same number of counter of each color initially. You may want to do my exercise 1.
– Apass.Jack
Dec 30 '18 at 12:38




















draft saved

draft discarded




















































Thanks for contributing an answer to Computer Science Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f102165%2fsolving-tricolor-arrangement-efficiently%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Human spaceflight

Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

張江高科駅