ACM ICPC Asia Chennai regional 2016

Today, i am going to write something off-topic, which is not related to "SPOJ solutions". Well, this is pretty clear from the title that i am going to talk about my experience of ACM ICPC Asia Chennai regional. Overall it was a good experience, but it would have been better if our team would have performed good in contest!

The contest was hosted on codechef, and the problemssetters were previous years ACM ICPC finalists/contestants. There were total 10 problems, and top 4 teams solved 6 of them. We solved just 2 very easy problems. The third problem was based on extended euclidean algorithm. We spend 4 hours trying to solve that problem, but due to lack of knowledge we were not able to solve it.
After a long struggle of 4 hours, we moved on to next problem, which was based on "trie". That problem was solvable, but by the time we started solving that problem it was too late! We had only 14 minutes left to implement "trie". We weren't able to solve this problem too. It was a bad contest for us. We didn't expected that we will perform this bad, but we were happy as we competed with great coders, like Atanu Chakraborty, Rajat de.

What we got to know from that contest was, the biggest difference between small colleges like ours and colleges like IIT Kanpur or IIITH is "coding culture". We don't have that coding culture. There are many more points like our maths club and programming club are two different things, our programming club focuses mainly on first year students, and two major points are, negligible interaction with seniors and we are not that hardworking!

It was a good experience! I hope next year we'll perform better!

Read More

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

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