Editorial for Coding Maniacs contest held on CodeChef dated 12th June

Contest Link: https://www.codechef.com/CMS22020

NOTE :

  • It is highly recommended to first just read the explanation of questions that you were not able to solve and then again try to solve that question without going through the solution and after that, if you got stuck in coding then you can see solutions of that question.
  • If you do not found solution coded in your preferred language, it is always better to understand core logic and code it out yourself.
  1. Ice-Cream Vending Machine – CMAN21:­­

Explanation: In This Question, you are given a table in question in which the cost of different ice-cream flavours, cups, and cones are given. based on which you have to find the total cost of the ice-cream with given valid inputs if the inputs are invalid ( i.e. its value or cost is not defined in the table and if the number of scoops exceeds 3) you have to print “Invalid Entry” (without quotes).

Solution coded in C++: https://ideone.com/nvhnO3

Solution coded in JAVA: https://ideone.com/yuPsX9

Solution coded in Python: https://ideone.com/l02Kto

  1. Guess The Output - CMAN22:

Explanation: This question is based on a trial and error method. In this question as given in hint, you have to use a bitwise operator. In simple words, you need to do bitwise xor of all elements in the given array and then check if the answer is even then print “YES” else print “NO”.

Tip: If you directly take the sum of all elements of array and then checking even or odd will give you same answer (Simple Mathematics).

Solution coded in C++: https://ideone.com/3Z5FtE

Solution coded in JAVA: https://ideone.com/xjIGLI

Solution coded in Python: https://ideone.com/9i632F

  1. Chef And His String Game - CMAN23:

Explanation: This question is based on the combinations of a string.

Step1: You need to sort the given string according to the ASCII values of characters.

Step2: After that, you need to iterate over the string and find the 2 combinations of a string of length ‘N’, 1st should give minimum ASCII sum, and second should give maximum ASCII sum if it is not found in the given string then print “-1” else print the minimum and maximum ASCII sum.

Note: In this combination of string you should not include those characters which have their ASCII values divisible by ‘P’.

Corner Cases which you might miss:

a. The string which only contains characters that are divisible by ‘P’.

b. The string does not have combinations of length “N” in which each character is not divisible by ‘P’.

c. The length of combination i.e. “N” is more than the length of the string.

In all the above corner cases “-1” should be printed.

Solution coded in C++: https://ideone.com/BKmtUb

Solution coded in JAVA: https://ideone.com/HgY1E8

Solution coded in Python: https://ideone.com/toOUjK

  1. Selfie in London - CMAN24:

Explanation: In this question, you simply need to find the slopes of the given mirror co-ordinates and slopes of the given roads. If the slope of the mirror and road is the same (i.e. They are parallel) then the chef can take the selfie else chef cannot take the selfie. You simply need to count how many roads have slope same as the slope of the mirror and output it.

Solution coded in C++: https://ideone.com/6WZuql

Solution coded in JAVA: https://ideone.com/ZY4CtR

Solution coded in Python: https://ideone.com/I2teqL

  1. Help Kiteretsu - CMAN25:

pre-requisite for this question: Catalan Numbers.

Explanation: This question is based on “Dyck Words of a given length and Catalan numbers” just read about it on geeksforgeeks if you have no idea what it is. In this question, you simply need to output the total number of SuperNatural Words as defined in question in the given range. It can be done simply by using the prefix sum array. You need to store all Catalan numbers in the array and make its prefix sum array to answer queries efficiently. Then just use that prefix sum array to answer queries in the given range.

Solution coded in C++: https://ideone.com/wxxy7p

Solution coded in JAVA: https://ideone.com/WLI8ZW

  1. Encrypti Encryption - CMAN26:

Pre-requisite for this question: Graph Theory, Dijkstra’s Algorithm, DP.

Explanation: In this question, you were given a weighted graph of which weights have to be calculated by using the formula as given in the question (simplified formula: the absolute value of ( BB - AA ) ).

After building the weighted graph you have to calculate the minimum distance of each node with every other node.

This can be done with the help of Dijkstra’s Algorithm, but you need to optimize it to answer queries efficiently hence, you will need to make use of Dynamic Programming i.e you need to make a 2-D array (a matrix) which will store the minimum distance of each node with every other node.

This 2-D array is filled with the help of Dijkstra’s Algorithm (left to you as exercise if got stuck see the solution).

After making that 2-D array you now have to encrypt the data in it with the encryption algorithm as given in question (It simply counts number of set bits in given number ).

Now you have to find the maximum value of each row in that 2-D array and count the number of set bits in that number and do its bitwise XOR with each element ( i.e set bits in that element) of that row in the 2-D array. you need to do this for every row of the 2-D array.

After doing this your encrypted model is ready. So for each query, you should output the answer to that query with the help of the 2-D array build (This can be done in O(1) ).

Solution coded in C++: https://ideone.com/ZS5zvu

2 Likes

Can you please share a link to the contest? It’s not visible in the conests list.

Done Thanks for reminding !!