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

FRNDCIRC - FRIEND CIRCLE - SOLUTION

FRNDCIRC - FRIEND CIRCLE is an easy DSU problem. If  DSU is an "alien" term for you, I recommend you to, understand Disjoint set union first and then try solving this problem!

If you want to solve easier problem based on DSU, try solving FOXLINGS. If you find difficulty in solving this problem you can refer to the tutorial.

In this problem, in each test case, we are given 'n' , number of  new friendships. For each such new forming friendship, we need to find the total number of people in their friend circle!

So, for each query, if the new friends were already in the same friend circle, their friendship will not affect the size of friend circle. But if they were not friends before, we will perform union operation on their friend circles, and the new size of friend circle will be, friend1_cirlce_size + friend2_cirlce_size.

I know, now you can code solution for this problem easily, isn't it?
More hint? You need to use STL (unordered_map) to solve this problem.

If you find any problem in solving this question, 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