SRM-04 Report

Results:
Congratulations Participants! You did a great job in the contest. Kudos to our top 5 programmers of SEPT18:
1.Aditya Loke
2.Vipul Singh Raghuvanshi
3.Kaustubh Badrike
4.Mithil Kiran Poojary
5.Ninad Chavan

Editorial:

1. Cibin Challenges Harsh
Prerequisites : None
Difficulty : Very easy
Solution type : Simple math and conditionals
For each test case, find the sum of all the trials. Then check if the sum is greater than or less than the minimum points required. Print the difference between the sum of trials and required points if the trial points are less than required points. Print “Harsh Wins” otherwise.

2. Chopper Challenge
Prerequisites : None
Difficulty : Easy
Solution type : String Handling
For each case, input needs to be taken till the pointer encounters a “.” The input needs to be converted into numbers, and sorted. Print the index of each number, in order of input taken.

3. Ghost game
Prerequisites : Binary Search
Difficulty : Medium
Solution type : Optimization, Binary Search
The given sequence can be modified into a cumulative sequence which denotes the total number of stairs till a particular floor.
Now to reach to the floor which has total stairs close to the ones given in the queries, a linear search algorithms fails leaving us with TLE.
As max value of N is 10^6 and that of Q is 10^5, the total operations linear search will perform are close to 10^11. While computers can perform only 10^9 operations in 1 second, hence the TLE.
If you observe carefully, the sequence once modified into a cumulative sequence is always sorted in increasing order.
So we are free to perform Binary Search instead of linear search. This will solve the problem in less than 10^7 operations.


Solutions: Click Here
(Note: The solutions are accessible only using GST email addresses)

Thank you, everyone, for participating! Stay tuned for more contests.



  6    0  
Created On: September 29, 2018 10:07 PM


Comments
There are no comments!

Create an account or login to write a comment

Supported by our Coding Partner