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

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

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

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

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

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

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