Red Green BabuLand

n3wb13_223 Unlock The Algorithm, Fal...
Limits 1s, 512 MB

King of Babuland is going through a tough time because of a migrating group of bandits which came to his kingdom. The bandits made the king realize that the people of that country don't get enough light in the night. The bandits took advantage of that matter and looted the houses of the innocent civilians of Babuland.

The king is at a loss about what to do. One day after suffering a lot of days the scientists appointed by the king invented a special lamp which dispersed enough light that emitted the darkness for one house fully. So, the king got n\bf{n} Lamps as soon as possible.

But there was a serious issue with the device which was that if two devices were connected there would be an explosion. But the issue was solved almost immediately. The scientists just did a pro scientist move and did something which is called “flipping the parity”. If two lamps with the same parity are connected directly there will be a big explosion. To make it easier to understand the lamps were divided into two classes, Red and Green.

So, there are n\bf{n} lamps for n\bf{n} houses which can be deemed red or green. The lamps are connected through wires that go along the roads that connect one house to another. Every house is connected directly or indirectly. The connection must start from an entrance of the kingdom. There can be multiple entrances. There is always a house at an entrance which is connected to one other house only. The first light must be a red one.

Now the king called the city planners and gave them the task to find out if the whole city can be enlightened using the lamps or not. If yes, the king told specially to see to it that the red light count is maximized while filling the city with lights from the lamps.

You have to help the city planners.

Given n\bf{n} and an adjacency matrix of nn\bf{n*n} denoting the information of the roads, you have to tell if it is possible to enlighten the city and if possible what can be the number of red lights and green lights where the number of red lights are maximized.


The first line of input contains a single integer n\bf{n} denotes the number of Houses.

Then n\bf{n} lines follow each containing either 0\bf{0} or 1\bf{1}. Aij\bf{A_{ij}} means there is a road between ith\bf{i^{th}} house and jth\bf{j^{th}} house.

1n,Aij103\bf{1 \le n, A_{ij} \le 10^3}


Print “Possible! Possible!” and the number of red light and green light where count of red light should be maximized if the kingdom can be enlightened with all green and red lamps otherwise “Pardon Dear Lord! It is not Possible.”.


0 1 0 0 0 0 0
1 0 1 0 1 0 0
0 1 0 1 0 1 0
0 0 1 0 0 0 0 
0 1 0 0 0 1 1
0 0 1 0 1 0 0
0 0 0 0 1 0 0
Possible! Possible!
4 3
0 1 1 1 1
1 0 1 1 0
1 1 0 0 0
1 1 0 0 0
1 0 0 0 0
Pardon Dear Lord! It is not Possible.

In the First Sample Case

Here, the house 1, 4 and 7 has only one house connected to them. So, they are potential starting points as they satisfy the conditions of being entrance of BabuLand.

If we start from house 4 or house 7 we can place 4 red lamps and 3 green lamps. But if we start from house 1 we will get 3 red lamps and 4 green lamps. Thus if we need to maximize the count of the red lamps then house 4 or house 7 should be our starting house.

Be careful about the newline(‘\n’) at the end.


Login to submit.


75% Solution Ratio
SIGMA_77Earliest, 5M ago
Rakib.4411Fastest, 0.0s
Rakib.4411Lightest, 4.9 MB
Rakib.4411Shortest, 1161B
Toph uses cookies. By continuing you agree to our Cookie Policy.