Cracking TCS CodeVita

One of my students got below 200 rank in CodeVita 2017. It would have been even better if he had not lost couple of hours due to logistics.

Best way to crack any competitive event is to try and solve the questions from previous years. Understand what you lack and prepare accordingly.

One of the CodeVita 2017 problems was called Mountain Peak Sequence.

Consider the first three natural numbers 1, 2, 3.
These can be arranged in the following ways: 2, 3, 1 and 1, 3, 2.
In both of these arrangements, the numbers increase to a certain point and then decrease.
A sequence with this property is called a "mountain peak sequence".

Given an integer N, write a program to find the remainder of mountain peak arrangements that can be obtained by rearranging the numbers 1, 2, ...., N.

Input Format:
One line containing the integer N
Output Format:
An integer m, giving the remainder of the number of mountain peak arrangements that could be obtained from 1, 2, ...., N is divide by Mod
Constraints:
Mod = 10^9 + 7
N <= 10^9

Example 1
Input
3
Output
2
Explanation
There are two such arrangements: 1, 3, 2 and 2, 3, 1

Example 2
Input
4
Output
6
Explanation
The six arrangements are (1, 2, 4, 3), (1,3,4,2), (1,4,3,2), (2,3,4,1), (2,4,3,1), (3,4,2,1)

Observations

Basically, the numbers in a mountain peak sequence keep on increasing up to a point and then start dropping. So:

  1. the maximum number (N) is at the peak.
  2. the numbers before the peak (upward slope) are in increasing order.
  3. the numbers after the peak (downward slope) are in decreasing order.
  4. N (peak number) cannot occupy first and last slots in the sequence as the upward slope and downward slope, respectively, would be missing. Hence, N can be in any of the N-2 slots of a sequence (except first and last).

Counting

  1. When N is in second slot, the number of ways you can fill the first slot is (N-1) Choose 1 or (N-1)C1.
  2. When N is in third slot, the number of ways you can fill the first two slots is (N-1)C2.
  3. When N is in fourth slot, the number of ways you can fill the first three slots is (N-1)C3.

Answer

The final answer is the summation of below (and the modulo!):

(N-1)C1 + (N-1)C2 + (N-1)C3 + … + (N-1)C(N-2)

But, we know from Binomial theorem, pascal triangle that

(N-1)C0 + (N-1)C1 + (N-1)C2 + … + (N-1)C(N-2) + (N-1)C(N-1) = 2^(N-1)

Therefore, our final answer is 2^(N-1) – (N-1)C0 – (N-1)C(N-1) = 2^(N-1) – 2 (and the modulo).

Again, from Modular Arithmetic, we know that

(A – B) mod C = (A mod C – B mod C) mod C

Finally, the code (in Java)

import java.math.BigInteger;
import java.util.Scanner;

public class MountainPeakSequence {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        if (N>2) {
            BigInteger two = new BigInteger("2");
            BigInteger modulo = new BigInteger("1000000007");
            System.out.println(two.modPow(BigInteger.valueOf(N-1), modulo).subtract(two.mod(modulo)).mod(modulo));
        }
        else
            System.out.println("O");
        s.close();
    }
}

Conclusion

To crack this particular problem of CodeVita, you need good

  1. Analytical abilities
  2. Foundation in Math
  3. Familiarity with programming language libraries

Other problems (specifically, the final round) require knowledge of Data structures and Algorithms, in addition.

Training

If you are interested, please register for Cracking TCS CodeVita.

In this training, we will solve as many previous questions as possible. You will get the Java code for all problems we solve in addition to learning some of the foundational Math, Data structures and Algorithms.