PROBLEM LINK:
Setter-
Tester- Animesh Fatehpuria Hasan Jadouh (@kingofnumbers)
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY-MEDIUM
PRE-REQUISITES:
Greedy (somewhat) , Implementation
PROBLEM:
You given N timestamps, each with recording of some time. Now, some timestamps have incorrect/invalid entries, which are denoted by ‘?’. You can fill any entry in place of ‘?’ . You need to find the minimum time elapsed since starting time (in seconds) stamp.
QUICK EXPLANATIONS:
We use modular approach of programming to tackle the implementation part and reuse code. We notice greedy will hold, i.e. its always best to assign a timestamp the possible value closest to previous timestamp’s time. We also see, that there are around only few candidate values for each timestamp which can minimize time. With this, we keep a count of days passed and time assigned to the previous stamp for comparison, and finally calculate answer as 86400*Days+TimeOfCurrentStamp.
EXPLANATION:
The editorial just has a single section- telling how to find the value to assign to current timestamp to minimize total time. Tackling implementation is tackled in the same section.
One thing we must be clear of, is that greedy holds good in this question. Such a case does not exist, where assigning a timestamp farther from previous stamp will decrease answer. Think it this way, if I assign the time stamp closest value possible to previous one, then I may be able to assign the next stamp a closer value. And if I cannot assign next stamp a closer value even after assigning current stamp a value as close to previous as possible, then any other value wont help as well.
How to calculate best time to assign to current stamp-
This section is best done with illustrations. I will first tell the candidate values, and later justify them with an example.
Split the time into 3 parts, Hour, Minute and Seconds. Now for each of these 3 parts, we see that the best values are found by-
- Assigning 0 to all ?
- Manipulating ? to get a value closest to previous stamps Hour/Minute/Second (depending on part of stamp we are referring to)
- Manipulating ? to get a value closest to previous stamps Hour+1/Minute+1/Second+1 (depending on part of stamp we are referring to)
Now, to prove and justify this, we will take examples.
Suppose my previous stamp stamp is 14:40:31 , and my current stamp is 0?:??:10. Clearly, the second stamp is recorded on the next day. In this case, I have to bring the value closest to previous day’s 14:40:31. If I assign 0 in place of ?, then I get 00:00:10, which is closest time possible. This justifies the first point.
Next example, say my previous stamp is 14:14:14 and my current stamp is 14:??:39. Clearly, assigning a value of 14 to ?? will be optimum. Now, what do I mean by “closest value possible to previous stamp”?
If my current stamp were 14:?9:50, then also, simply copying digit at previous stamp would help. My stamp would be 14:19:50. But what if, instead of ?9 I had ?1 ? Meaning, current stamp would be 14:?1:50. Copying previous time stamp’s value will make it 14:11:50 and will be chaotic! In this case, its best to assign ? as charAtPreviousStamp+1,i.e. 1+1=2. Meaning, assigning it the label 14:21:50. This is how we will be making cases in program as well, so pay attention as when which procedure is applied.
Lets say my previous stamp was 19:40:32, and my current stamp is ?2:11:20, clearly, we have to assign 1+1=2 to the ? for minimum time.
And thats pretty much the end of logic of this question. The important concept is that, you must be clear on what value to assign to a time stamp. As for implementation, I recommend you to sit back and think first.
Clearly, there are many things which we will be doing multiple times, like comparing current assignment to previous timestamp, or checking possible values to assign to the ? &etc. I recommend to make functions and follow the modular approach. Identify which things you will be doing again and again, find out which portion has relation just with inputs passed (and nothing else in the main code) and make a function of it. Once you identify what tools you need to tackle this question, the question will be a cakewalk. If you try to just cluster everything inside main, no functions, this question might seem MOTI to you (Mother Of Terrific Implementation).
SOLUTION:
I will upload mine, and both the tester’s solution for you to see and compare. In case you got the logic, but are unable to implement it, or are getting WA, just have a check with the solutions.
Editorialist (C++)
Animesh (JAVA)
Hasan (C++)
CHEF VIJJU’S CORNER:
1.If you look at my solution, you will find I used operator overloading there. Its nice and quite convenient to do so for such objects.The only case where one must be careful is overloading them. Eg- In correct overloading/defining operator for sort function will result in infinite loop. (Weak ordering concept)
2.Operator overloading also comes to play when you want to declare sets, or priority queue of custom data type/objects. Ever wonder what that 1000 line error was when you declared a set of your custom object? Now you know 
3.An interesting exercise will be to prove that the three cases I mentioned are exhaustive. They are correct, of course, but how will you formally prove that they are exhaustive? The proof will go on lines of, start with seconds. See when minute part of current time stamp is lesser, equal, or greater than minute part of previous time stamp. See that for each case, an action is assigned. Then repeat for minute and hours &etc. till you exhaust the possibilities.