CODELABS3277 Challenge #2 Solution and Discussion

I hope that you all have enjoyed these problems which were hosted at Hackerearth as a part of this contest.

So the general view about the problems is that all these problems require mathematical and logical thinking. The concept that one needs to solve these problems are geometry(that is properties of Circle), combinatorics, binary exponentiation or fast multiplication, etc. 
Here are the solutions in C++ for your reference.

Problem: Boy and the mountain
This question says yes to find the number of ways in which boy can reach the top to the mountain by taking steps 1 unit, or by jump. For example, let us suppose that the height of the mountain is 4 unit, then he can reach the top in the following ways
1+1+1+1 = 4 (i.e by walking 1 step at a time)
1+2+1 = 4
1+3 = 4
3+1 = 4
2+2 = 4
0+4 = 4 (i.e, by making direct jump)
2+1+1 = 4
1+1+2 = 4
So for H=4, we have above 8 ways. 

Now the questions have turned to a simple problem that is in how many ways we can write H in the form of the sum of positive integers which comes to be 2^(H-1).

Now according to the given problems H can take value up to 10^18 so by simple iteration, this can't be solved, so for this, you need Binary Exponentiation (Fast Multiplication) concept.

Problem: Easy Series
This is the most straight forward question of this contest as everything is given to you and you don't need to think of the logic for solving the problem, you just need to develop a good strategy for writing the code.

  • Given X can take value up to 10^7 so we can't store all Fibonacci numbers in array else you will get Memory Exceeded error.
  • Your algorithm should run in O(n) time complexity else TLE error.
  • Given T is <= 10 so total max computation needed is 10^7*10 ≈ 10^8.

Problem: Circular Temple and the Road
This problem belongs to the geometry part, in this, you will first need to solve the equation of Circle and Line to get the intersection point and then you need to check which of these coordinates lies near to the Monks position, that is your answer.

Problem: Counting valid bracket Sequence
This problem can be solved by two methods:

  • Brute force technique
    • since the constraint is less so we can generate all the strings containing braces of size=number of left side braces + the number of right side braces.
    • After this check all the strings for validity using stack and it is valid then increment the counter else not.
  • Catalan's Number (My favorite)
    • This gives the number of valid parenthesis expressions that can be formed by n right brace and n left side brace.  It is possible for parenthesis expression to be valid when (n==m) else not.
      • n- number of the left braces,
      • m- number of right braces

Problem: No consecutive letters
It is given that no to alphabets should be considered to be the same. This means that all are different from each other, so instead of character, we will be using their index positions to be the identifying number of characters.

Example: let the character be aba,  we will be considering this to be the set of 3 integers {1,2,3} and we will play with this to get the solution.
So the ordered set following the given condition would be {1}, {2}, {3}, {1,3} and {3,1}. So answer =5.

Now, thinking for general formula, if we consider sets of 1 element we have nCo sets, considering 2 elements, if we take 1 then 2 we can't take and so own, so we have (n-1)C(1),.....(n-r)Cr such that n-r > r.
And this will be our solution.

Thank You
Happy Coding & Enjoy!

If you find any error or ambiguity, then do comment.