Editorial

Starting this year, i.e. Season 11, we will be publishing Editorials about CodeVita questions asked in Round 1 of CodeVita. We start with 5 questions and describe the approaches to solve them. Please note, the methods mentioned in the editorial are just one amongst the many ways a programming problem can be solved. The initiative to publish Editorials is influenced by participants' demand for Solution or Test Cases. Since we won't be sharing either of these, publishing editorial is the next best thing that we can do!

Hope participants find it useful and it brings closure to those participants who narrowly missed solving the entire problem(s).

In this first editorial, we have chosen 6 less solved problems. We won't be publishing anything for unsolved problems of this round. Time permitting, we will publish more editorials for other problems of this round, but since Zone 2 is in another 2 weeks time, we could be pressed for time. So, no promises, but we will give our best to bring out remaining editorials.

Editorial - 1

Conflict Free Team

Problem Overview: This problem can be represented as a graph with weighted vertices (employee skill value). After constructing the graph from the given input, you need to find the set of vertices which are non-adjacent to each other, and the sum of their weights (employee skill value) should be maximum.

Approach: The problem can be solved using recursion. The idea is to consider two cases for each vertex:

- Exclude the current vertex: If you exclude the current vertex, then you will not include the skill value of the vertex in the set.
- Include the current vertex: If you include the current vertex, then you need to exclude its neighbors as the adjacent nodes can't be in the set together. After excluding neighbors, add the weight of the current vertex to the sum.
- Process all vertices of the graphs in this manner. The sequence of vertices that maximizes the sum of skill values is the answer.

Score of Cells

Problem Overview: Given a 2d array, score of a particular cell A is the number of ways in which you can reach the cell A, obeying the given rules. That is, we can only move from the current cell to either down/right cell, only if the value those cells hold is not lesser than the value in the current cell. Find the indices of cells with given score.

Approach: This can be solved using dynamic programming. Initialize M x N DP matrix with all zeros of size n, then we simply iterate from one cell to another. If the next cell is reachable from the current cell (obeying the given rule above) then we increment the count in the dp matrix every time the cell is reachable. Continue this approach for all the cells. Finally, print the coordinates of the cells with a score equals to K.

Harmonic Homology

Problem Overview: You will be given the hierarchy of the tunes, two melodies (sequence of tunes separated by -), and three integers A, B, and C. Each time you will be allowed to do two operations i.e., compare the letters at ith index of melody1 and melody2 or remove a letter at ith index of melody1 or melody2. When you compare, if tunes are similar, then concordance score will be increased by A else decreased by B. If you prefer to remove a tune from one of the string, concordance score will be decreased by C. Find the maximum concordance score possible.

Approach: This problem can be solved by using Needleman Wunsch Algorithm,(https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm#:~:text=The%20Needleman%E2%80%93Wunsch%20algorithm%20is,programming%20to%20compare%20biological%20sequences.) which is a string alignment algorithm with an additional use of a graph for the given hierarchy. Write a function for finding the level of a given tune in the hierarchy. Use the Needleman Wunsch Algorithm for implementing the above given rules.

String From Rank

One approach to solving this problem involves generating all permutations of strings with the given length, sorting them lexicographically, and selecting the element based on its rank. However, this method becomes inefficient for longer strings due to the extensive computation involved. A more optimal strategy is to deduce the character at the specified index directly. When permutations are sorted lexicographically, an intriguing pattern emerges. The leftmost character repeats n times until the next character in the sequence appears. Subsequently, this next character repeats n times, and so on. By identifying the value of n and dividing it into the given rank, we can determine the leftmost character. This process can then be iterated for the remaining characters in the string, providing a more efficient and insightful solution to the problem which finishes in given time and memory constraints. This question is devised to induce a TLE or MLE for a naive implementation.

Bouncing Balls

The conventional method involves meticulously tracking the movement of each ball, checking for overlaps at every step until either the balls coincide or return to their initial positions. If, throughout this process, the balls never overlap at any step, it can be concluded that they will never intersect. To optimize computation, a more efficient approach is to separate the horizontal and vertical movements of the balls. Initially, assess the overlap during the vertical movement and then during the horizontal movement. The critical step involves combining the results of these individual checks and identifying the specific step at which both vertical and horizontal overlaps align. If such alignment is not achieved, it signifies that the balls will never intersect. This reduces the computation. Once they are reduced into vertical and horizontal components one can figure out when they overlap on vertical and horizontal axes. The step at which both overlap will be GCD of:

- Multiplication of step at which they overlap on vertical and
- Multiplication of step which they overlap on horizontal.

It forms a Linear Diophantine equation which is solved to get output without iteration.