Editorials - C For Code 02 - Coding Club - ISM Dhanbad

Cartman Reverses String 200 pts

Difficulty Level: Cake Walk

Just take the input in a string (character array), find the no. of elements in the string and start printing character by character from the end of the string.

Here is the code for the problem:

http://www.codechef.com/viewplaintext/2405460

Raise the Power 300 pts

Difficulty Level: Easy

Prerequisite: Divide and Conquer, Modular Arithmetic

If you are not acquainted with basic modular arithmetic, I recommend you to read basic number theory. Here are some modular arithmetic properties that are used here:

(A*B) mod M = (A mod M) * (B mod M)

(A^B) mod M = (A mod M) ^ B

Now since A can be as large as 10^18, we first take A=A mod (1,000,000,007).

Let me show the algorithm for solving A^B if B is very large with an example.

Let A = 3 and B = 18.

3^18 = (3^9) * (3^9)

3^9 = 3 * (3^4) * (3^4)

3^4 = (3^2) * (3^2)

3^2 = 3 * 3

So, we calculated 3^18 in just 4 steps. In this manner we can calculate A^B in O(log B).

Here is the code for this problem:

http://www.codechef.com/viewplaintext/2405463

How to Handle the Fans 500 pts

Difficulty Level: Medium

Prerequisite: Binary Indexed Tree

Binary Indexed Tree is a data structure that is used to calculate the cumulative frequency. If we use an array to store the no. of fans at each point and then count them one by one, the time complexity will become O(N*Q) and it will give TLE.

Binary Indexed Tree allow us to update the no. of fans at each point and count the no. of fans from office A to B in log N steps. So the time complexity of algorithm will be O(Q * log N), this will work fine.

To read about Binary Indexed Trees, please read this:

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Here is the solution for this problem:

http://www.codechef.com/viewplaintext/2405466