Basically, I did not understand the problem statement. Could any one explain why the example output is 10? If anyone can explain it based on the example input(3 2;
S 1 2; D 3 2), it would help me to understand this problem statement.
Here is the problem link:
http://www.usaco.org/index.php?page=viewproblem2&cpid=920&lang=en
Thanks,
Figured it out. The answer is in binary format.
Seems the reference code( Contest Results) for generating output does not make sense. Why there is only MSB is non-zero? If the answer is “3”, how can below reference code generate correct results?
I mean if the variable “answer” in below code is 3 in decimal number, then the binary output should be “11”. How is it possible that only one digit is non-zero???
if (impossible) fout << “0\n”;
else {
fout << “1”;
for (int i=0; i<answer; i++) fout << “0”;
fout << “\n”;
}
The thing is, the answer will always be a power of 2. Try to figure out why.
Suppose we find out that some nodes have to have a certain arrangement that allow for them to have a valid grass planting. Then, there are 2 arrangements possible for that group of nodes (Since there are 2 types of grass, just flip the types of grass). We can keep applying this for all the connected components of the graph. So, the answer will be 0 (one or more connected components doesn’t have a valid arrangement) or 2 to the number of connected components.
Thanks @pavanscoding ,
Your reasoning are really helpful. But I am still not clear about claim “it is impossible” , if only one of connected components doesn’t have a valid arrange(In one path, variable “impossible” is set to true) and other connected components have valid arrangements(it will not set variable “impossible” to true in this path, but it is set to true in other paths). Can we still claim answer is 0?
bool impossible;
void visit(int x, int v)
{
L[x] = v;
for (auto n : S_nbrs[x]) {
if (L[n] == 3-v) impossible = true;
if (L[n] == 0) visit(n, v);
}
for (auto n : D_nbrs[x]) {
if (L[n] == v) impossible = true;
if (L[n] == 0) visit(n, 3-v);
}
}
We can still claim the answer is 0 because the connected component is still part of the graph. Instead of thinking in binary let’s suppose that they ask us for the decimal number of ways we can plant grass in the field. (The answer to the sample test case will be 2). Then, to find the answer, we will keep multiplying the number of ways we can plant grass in each connected component. If the component has a valid configuration, then we can say the number of ways we can plant grass in that connected component is 2. However, if the connected component does not have a valid configuration, then the number of ways we can plant grass in that configuration is 0. Suppose we have k valid connected components and n-k invalid connected components. Then, the answer is
Based on this, you can see that the number of connected components is either a power of 2, or is 0. You can also see that if we have even 1 invalid connected component, then we have 0 possible configurations for the field. And of course 0 in binary is 0.
Thanks for your comments and explanation in detail. It is really helpful.
No problem 