Hi,

I'm trying to understand the given below programming problem

https://codeforces.com/problemset/problem/1051/D

Doubt:

1) What is component here ? Is it something in grid or something else ?

Can anyone help me to understand this problem please ?

Thanks

There is a definition of "component" in the link you gave us. It's some sort of inductive definition, and those are hard to get used to. In this case, the definition might not even be correct. There are other ways to define the same concept.

Two cells are in the same component if and only if you can reach from one to the other stepping only between neighbors.

EDIT: That was an interesting problem. Too bad the link is now broken. Is it available anywhere else?

Fun with polynomials!

If n=3 and k=4, compute the following polynomial: https://www.wolframalpha.com/input/?i=Expand+[[1,1,1,1]]+*+[[1,1,1,x],[x,1,x^2,x],[x,x^2,1,x],[x,1,1,1]]^(3-1)+*+[[x],[x^2],[x^2],[x]]

The coefficient of x^4 is the answer.

Actually, I can't think of any other way to solve this problem.

On 10/1/2018 at 12:51 PM, gamelearner said:

Hi,

I'm trying to understand the given below programming problem

https://codeforces.com/problemset/problem/1051/D

Doubt:

1) What is component here ? Is it something in grid or something else ?

Can anyone help me to understand this problem please ?

 

Thanks

 

Components have a good inductive definition:

Quote

Two cells A and B belong to the same component

• if they are neighbours,
• or if there is a neighbour of A that belongs to the same component with B.

While not what is usually meant with the word, neighbours are also defined satisfactorily:

Quote

Two cells are considered neighbours if they have a common border and share the same color.

In other words, the "components" are the connected components of the undirected graph that has the grid cells as nodes and edges between "neighbours". Are you familiar with graphs?

The example figure has 4 components, two white and two grey.

If you understand the examples (take your time to work them out on paper, the more complex first one with its 12 solutions in particular), it's only a matter of counting the colourings efficiently. Since it's homework, no hints about algorithms except that it's an easy and fun problem.

This is easy? I am very good at this kind of thing and I didn't think it was all that easy. I mean, I knew how to approach it right away because I am familiar with the much-harder problem of counting legal positions in go. But if I hadn't know that, I think I would have had a hard time.

Did you notice n can be up to 1000?