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

Skip to content
# Spoj Editorials

## BUGLIFE – A Bug’s Life

## FRNDZND – Friend Zoned

## ARMY – Army Strength

## ABSYS – Anti-Blot System

## ADDREV – Adding Reversed Numbers

## CODCHESS – Naya Shatranj (New Chess)

## FCTRL2 – Small factorials

## RANJAN02 – Tower Of Hanoi – Revisited

## BTCODE_D – Maximum Profit

## ABSP1 – abs(a-b) I

by Piyush Kumar

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

Advertisements

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

Problem statement: ARMY

As the weakest monsters are killed. The one who has the strongest monster will win. Just find out the team that has the strongest monster (monster with maximum strength).

Problem statement: ABSYS

Go through the string from left to right. Pick out the number which contains the words ‘machula’. The other two numbers can be used to find out this number using the equation. Replace the old number with the new number. Done!

Problem statement: ADDREV

I bet you a 1000 dollars to find me an easier question than this (except for Life, Universe and Everything). Just reverse both the given numbers. Add them and reverse the result. You are done.

Problem statement: CODECHESS

This is a simple pen and paper observation problem. For all odd sizes of the ‘maidaans'(chessboards) A will win and B will win in rest of the cases.

Problem statement: FCTRL2

**N! = N * (N-1) * (N-2) ….. * 1**

Use a language which provides Big Integer library.

Problem statement: RANJAN02

The idea is to come up with a recurrence. Solve for smaller n using pen and paper untill you arrive at the following recurrence:

**ToH (n) = 3 * ToH(n-1) + 2**

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.

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.