IAPCR2F - Summer Trip - SOLUTION

IAPCR2F - Summer Trip is an easy DSU problem. If you don't know what Disjoint set union is, then you should first understand DSU then try solving this problem!

I've solved this problem using breadth first search (BFS).

There are T test cases, and each test case contains 'n', which denotes the number of students who are going for trip, and 'm'  denotes the number of relations between them.

Next line contains 'n' integers, which denotes the money for ith student, and next 'm' lines tells relationship between students.

After understanding the problem statement it is very clear that we need to form disjoint sets, and find money for each disjoint set.

This can be easily done by applying BFS to each such node, which is not yet visited. If we choose any node and apply BFS, we will visit all the nodes reachable from that node, and we can easily count money for each node, present in that disjoint set.

I think, now its easy to code for this problem. If you find any difficulty in coding part, refer to the following code:

Read More

HERDING - Herding - SOLUTION

HERDING - Herding is an easy DSU problem. If you are not familiar with term DSU, I suggest you to first of all understand DSU, then try solving this problem.

In this problem, we are give a n*m array and  each block of array contains 'N','S','W' or 'E'. 'N' is for north, 'S' for south, 'W' for west and 'E' for east, and they represents the direction of movement of cat if it is on that block.

So, if a cat is present on a block, there is a specific path, which it will follow. If we keep trap at the end of that path, and cat is present anywhere in the path, it will end up in the trap!

So, all we need to do is to find the number of paths, which do not intersect at any point. And we will set traps at the end of every path.

For example:

Input:
3 4
SWWW
SEWN
EEEN

Output:
2

                                                 

There are two paths, one is shown by yellow color and second one by blue.
If we set a trap at any of the yellow block, then all cats which are at yellow path, will end up in that trap, and same for the blue path!

The thing you should notice is, there is only one way possible from each block. So, if we traverse whole n*m map, and connect each block to the next block (according to the given direction), we can find all paths!

So, our answer will be the number of disjoint paths!

Easy, isn't it? Now try implementing this code bye yourself or refer to the following code:

 

Read More

GCPC11J - Time to live - SOLUTION

GCPC11J - Time to live is an easy BFS problem, which can be solved by applying BFS twice. If you are not familiar with the term Breadth First Search (BFS), then i suggest you to first of all understand BFS, then try solving this problem.

In this problem, our job is to minimize the number of TTL we need to send from the router to the farthest computer. So all we need to do is find a node, at which we can keep our router so that, it needs to send minimum number of TTLs to the farthest computer.

This can be done by finding the longest path in given graph, and we can keep our router at the center of the longest path (longest distance b/w two computers). By applying BFS twice, we can find the longest path easily.

If you want to understand, how we gonna find longest path, please see this blog, otherwise continue reading!

In the first BFS we will apply BFS from a random node, I chose 1 for this purpose. And our bfs(1) will return the farthest node from '1'. Then we will apply second BFS from the farthest node selected in bfs(1). This time the farthest distance from selected node will be the longest path in the graph!

That's all you need to do, easy, isn't it? 

Now, 

if(n%2==0) print (longest path length)/2 

else print (longest path length +1)/2

I hope you can implement the code for this problem yourself otherwise refer to the following code:

Read More

FOXLINGS - Foxlings - SOLUTION

I am assuming that you have already understood the problem statement otherwise go back and read the problem statement once again: PROBLEM STATEMENT

If you are not familiar with DSU and path compression, I suggest you to go and read this post first.

There are total N Foxlings , and if one foxling gets a cracker he divides it and give it to his friend too, in this way, if only one member of each friend circle receives a cracker, indirectly whole group will have crackers !

Input contains N the number of foxlings and M, the number of friendships.
Next M lines contains  A B , which means A is friend of B, and B is friend of A.

Initially, there is no friendship, so everyone is their own friend, and there are total N groups. Let us store number of groups in a variable co, i.e., co = N .
So, what we can do is , using union operation at each of the M queries, i.e., finding the root of A and B , and if root(A) ! = root (B) we will do union of them. And every time we do union, we will reduce value of co by one. After all queries the remaining value of co will be our answer!

I hope you can implement the code for this problem yourself otherwise refer to the following code:

Read More