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 (as number may exceed the integer limit) and an integer.

Now let us talk about the modular arithmetic concept we are going to use in this problem, let us take an example, we have to find 356 % 8, which is equal to 4. Now let us try to find this in the following way:

3 % 8 = 3
now multiply 3 to 10 and add next digit = 3*10+5 = 35

35 % 8= 3
now multiply 3 to 10 and adding next digit = 3 * 10 + 6= 36

36 % 8 =4

By using this method you can be sure that your answer will not be wrong due to integer overflow.

In this problem we will start from 1 and will check if 1 is divisible by n or not, if not then we add 11 and 10 to the queue, and now we know that the remainder of 11 will be ((1 % n) * 10 + 1) % n and for 10 it will be ((1 % n) * 10 + 0) % n at next step, same thing will happen with 11 and 10, and 110, 111, 101, 100 will be added to the queue and so on....

We will repeat this till we didn't find or answer, we can reduce the execution time of code by using visit array.

I hope you can implement the code for this problem yourself otherwise refer to the following code:

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. Now we have to print A if first player wins and B if second player wins.

Now, we have an array a[], which contains result of all towers.

Each player can choose 1,K or L to remove from tower, so if there is a tower with height 1, first player will win. So, we keep a[1] = 1

Now, for every i, A can win only if
a[i-1] = 0 or a[i-K] = 0 or a[i-L] = 0

otherwise B will win.

I hope you can implement the code for this problem yourself otherwise refer to the following code:

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 group. And after each query you have to tell the difference between the group size of largest group and smallest group, for this purpose we will use STL, we can use SET, MULTISET, or MAP, which will keep the group size of each group.
As set, multiset and map keeps the data sorted, for difference between smallest and biggest group you can subtract the first element from last element.

We are keeping a 'parent' array which keeps parent of each survivor, i.e., parent[A] store the parent of Ath survivor. Intially every body is their own parent :P

For all the group members we will find root using root function. Suppose A,B,C,D and E are in a group and parent[A]=A, parent[B]=A, parent[C]=B, parent[D]=C and parent[E]=D.
Then root(A) = root(B) =  root(C) = root(D) = root(E).

After every query we will do union operation if and only if their roots are not equal. After every union we will add group1_size + group2_size into the multiset and will remove group2_size from multiset.

I hope you can implement the code for this problem yourself otherwise refer to the following code:

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. And at every union you have to set distance from A to B = |A-B|%1000.

Now let us talk about the queries starting with 'E'. At every query starting with 'E' you have to tell the distance of that enterprise from its server. It is also possible that the given building is server itself, then the difference will be equal to '0'. We have kept an array 'd' which is storing distance of ith enterprise from its server.
Assume that the query is 'E A' and the enterprise serving to A is D in the following manner:
A -> B -> C -> D
While finding the distance from A to D we will update all distances of enterprises from A to D, i.e., we will update d[A], d[B] and d[C].

While telling the distance from server to that  enterprise you don't need to do any %1000 thing!

Now, I hope you can implement the code yourself or refer to the following code:

Read More