SRM 739, D1, 250-Pointer (ForumPostEasy)

James S. Plank

Tue Sep 18 17:11:37 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 hash: 3fb71b8ff650e949d611b4050b5cf256
answers.txt. MD5 hash: 8027b3d0a676ce06248ed2d7c740b53c
Problem Given in Topcoder: January, 2018
Competitors who opened the problem: 179
Competitors who submitted a solution: 163
Number of correct solutions: 107
Accuracy (percentage correct vs those who opened): 59.8%
Average Correct Time: 24 minutes, 15 seconds.

In Case Topcoder's Servers are Down

Here's a summary of the problem:

You are visiting a web site where people may make posts.
After each post are two lines of text.
The first line is the time when the post was made, in the format hh:mm:ss, with a 24-hour specification.
The second line says one of three things relative to the current time:
1. If the posting was made less than 60 seconds ago, it says "few seconds ago".
2. Otherwise, if the posting was made less than an hour ago, and the time was between i minutes ago and i minutes+59 seconds ago, then it says "i minutes ago".
3. Otherwise, if the time was between between i hours ago and i hours+59+minutes+59 seconds ago, then it says "i hours ago".
Your method receives two vectors of strings. The first has all of the exact times of the postings.
The second has these relative times. Entry i of the second matches entry i of the first.
The vectors are the same size, which is between 1 and 50.
Return the hh:mm:ss string of the earliest possible time to which these vectors could correspond.
If the vectors are inconsistent, then return "impossible."

Examples

Example 0:

{"12:12:12"}
{"few seconds ago"}
Returns: "12:12:12"

Example 1:

{"23:23:23","23:23:23"}
{"59 minutes ago","59 minutes ago"}
Returns: "00:22:23"

Example 2:

{"00:10:10","00:10:10"}
{"59 minutes ago","1 hours ago"}
Returns: "impossible"

Example 2:

{"11:59:13","11:13:23","12:25:15"}
{"few seconds ago","46 minutes ago","23 hours ago"}
Returns: "11:59:23"

Testing yourself

Compile to a.out, and the output of tests.sh should match answers.txt In your a.out, if you give it a dash for a command line, then it will read all of the exact times on the first line, and all of the relative times on the second line. The relative times should have dashes instead of spaces, and it will convert them to spaces after reading them in:

UNIX> ./a.out -
12:12:12
few-seconds-ago
12:12:12
UNIX>

Hints

When approaching Topcoder problems, my thought process usually goes, "Enumeration, Dynamic Programming, Something Else." If you use this approach, you'll come upon the solution pretty quickly -- instead of trying to calculate the time, simply enumerate all times. There are only 3600*24 = 86,400 of them. Enumerate them from smallest to largest. For each time t, run through all of the posts, and see if they are all legal at time t. If they are, then return t.

With 50 posts, doing O(1) work for each post, the running time is roughly calc 86400x50 = 4,320,000. That's easily within Topcoder's limits.

You'll benefit from some pre-processing. I created three arrays of integers:

time[i] is the exact time of posting i, measured in seconds since midnight.
least[i] is the smallest difference from now until posting i.
most[i] is the largest difference from now until posting i.

To illustrate, here are the arrays for example 3:

time = { 43,153, 40,403, 44,715 }
least = { 0, 2760, 82,800 }
most = { 59, 2819, 86,399 }

These arrays make it pretty easy for you to calculate the actual difference from time t, and then whether the "shown" difference is in the right interval. For example, when t is 43,163 (corresponding to 11:59:23), then you have:

For post 0, the difference is 10, which is between 0 and 59.
For post 1, the difference is 2760, which is between 2760 and 2819.
For post 2, the difference is -1552. The negative value means that the post had to have been made yesterday, so add 86,400 to it: 84,848, which is indeed between 82,800 and 86,399.

So, that time is ok, and you return it.

When you enumerate the values of t, simply enumerate the numbers from 0 to 86,399. When you get a legal one, you can create the return string and exit.