BUGLIFE – A Bug’s Life

Problem statement: BUGLIFE

Look at it as a graph, with bugs as vertices and interactions as edges. Check whether the graph is Bipartite or not. (A million ways to do that, coloring is one of them).


FRNDZND – Friend Zoned

Problem statement: FRNDZND

There are some things you should know about xor:

a ^ a = 0

a ^ a ^ a ^ a .. even number of times = 0

a ^ a ^ a… odd number of times = a

L and R will give you a continuous segment of the array and you have to find all possible subsets. Suppose the elements in the contiguous segments are a and b.

Subsets: {} , {a}, {b}, {a,b}

so result = (a) ^ (b) ^ (a^b)

In the above expression a occurs even number of times and so does b so the result is zero. This can be extended for contiguous segments of length > 2 also.

So the only queries for which the result wont be zero are segments of length 1 i.e. when l=r and the answer is array[l].


BTCODE_D – Maximum Profit

Problem statement: BTCODE_D

This problem should not make you sweat.

A[i][j] – number of waiters in ith restaurant at time slot j

B[i][j] – number of customers in ith restaurant at time slot j

C[i][j] – price each customer is willing to pay in ith restaurant at time slot j

As one waiter can serve one customer total price at time slot j in ith restaurant can be

C[i][j] * min( A[i][j],  B[i][j] )

You will have to find the maximum of this price for each restaurant and add them to give the answer.

In short, calculate:

∑ max( C[i][j] * min( A[i][j],  B[i][j] ) ) for all i.



ABSP1 – abs(a-b) I

Problem statement: ABSP1

This is a pen and paper problem.

Suppose you have 4 elements. a1, a2, a3, a4;

Sum = (a1-a2) + (a1-a3) + (a1-a4) + (a2-a3) + (a2-a4) + (a3-a4). All sums are positive because the array is in non decreasing order.

This sum can be rearranged to give:

Sum = 3 * ( a1 – a4 ) + 1 * ( a2 – a3 )

In general this can be written as:

sum = (n-1) * ( a[1]-a[n] ) + (n-3) * (a[2]-a[n-1]) + (n-5) * (a[3]-a[n-2]) …….and so on.

I don’t think there is anything left to explain. Move on.