CODERE3 - Coder Express 3!! - SOLUTION

CODERE3 - Coder Express 3!! is very easy DP problem.

I've solved this problem in O(n^2), but there is a better solution also, which runs in O(n(logn)) time complexity.

This problem is based on longest increasing sub-sequence (link for n*logn recursive DP for LIS).

There are two arrays, l[] and r[]. ith index of l[] tells the longest increasing sub-sequence till ith element, and same is for r[].

For finding longest increasing sub-sequence, we will traverse i 0 to n, and j from i+1 to n, and will check following conditions:

if (a[i] < a[j] && l[j] < l[i] + 1)

                    l[j] = l[i] + 1

And by doing same thing in reverse order, we can get r[].

After calculating l[] and r[], we will find the point where l[i] + r[i] is max. 

This was explanation for O( n^2 ), now try to think solving this problem in   O(n(logn)). 

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

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