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,...

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...

Read More

ONEZERO - Ones and zeros -SOLUTION

ONEZERO - Ones and zeros is an easy BFS + Modular Arithmetic problem. I am assuming that you have already understood the problem statement, otherwise go back and read the problem statement again. If you are not familiar to the term BFS, i suggest you to first read basics of BFS. In this problem, we have a made a queue which contains pairs, and each pair consists of a string...

Read More

MCOINS - Coins Game - Solution

MCOINS - Coins Game is an easy bottom-up DP problem. I am assuming that you have already understood the problem statement, otherwise go back and read the problem statement again. In this problem, we have made an array b[] which contains height of different towers, and we have to print a string containing A and B, who's ith element represent the player who will win for the ith tower....

Read More

FARIDA - Princess Farida - SOLUTION

This is an easy DP problem, which can be solved using bottom-up DP. Let us take an array a[] which keeps the number of coins ith monster keeps. Lets make a new array dp[] dp[0]=0; and further for every index i dp[i] = max(a[i] + dp[i-2], dp[i-1]) I hope you can implement the code yourself or refer to the following code: ...

Read More

LOSTNSURVIVED - Lost and survived - 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 this post first. There are 'N' survivors and  'Q' queries in each test case. In each query two survivors become friends uniting their respective groups into a larger...

Read More

CORNET - Corporative Network - SOLUTION

I' am assuming that you've already understood the problem otherwise go back and read the problem once again : PROBLEM STATEMENT. If you are not familiar with DSU, I suggest you to go and read this article first: DSU It is a simple DSU problem in which whenever a query starts with 'I' you have to do union of A and B, where A is always a server, but B may be or may not be a server....

Read More