Reckless drivers

See the original problem on HackerRank.

Solutions

You might see this problem as one on intervals. Here, the input is sorted and the lenght of each interval is fixed (the duration of the recording). Every interval spans from ts[i] to ts[i] + duration (excluded).

The solution to this problem is the cardinality of the set containing all the seconds recorded. For example, consider this input:

1
2

3 5
2 4 10

First, the app records from 2 to 7 (excluding the latter):

1

2 3 4 5 6

In the meantime, from 4 to 9 (excluding the latter):

1
2

2 3 4 5 6
    4 5 6 7 8

Finally, from 10 to 15 (excluding the latter):

1
2
3

2 3 4 5 6
    4 5 6 7 8  
               10 11 12 13 14

If we intersect all such sequences we get:

1

2 3 4 5 6 7 8 10 11 12 13 14

The cardinality of this set is 12, as expected.

One valid solution consists in simulating the creation of this set. Here is an example by Omar Chehaimi:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

duration = list(map(int, input().split()))[1]

samples = list(map(int, input().split()))
t_0 = samples[0]
t_last = samples[0]

set_res = []
for t in samples:
    set_res.extend([t+j for j in range(duration)])

print(len(set(set_res)))

The solution passes all the test cases, however it is \(O(N \cdot duration)\) that is expensive when \(duration\) is close to \(N\).

We can do better by counting the number of integers that every trigger (ts[i]) contributes with.

We have to distinguish two cases:

1. ts[i] does not overlap with the previous ts[i-1]
2. ts[i] does overlap with the previous ts[i-1]

The former is easy: the number of seconds that ts[i] adds to the counter is just duration. For example, consider ts[2]:

1
2
3

ts[0]  2 3 4 5 6
ts[1]      4 5 6 7 8  
ts[2]                 10 11 12 13 14

Since ts[2] does not overlap with ts[1], it adds 5 brand new integers to the party.

On the other hand, ts[1] adds only 2 new integers to the party. Indeed, 2 is the just the difference ts[1] - ts[0] = 4 - 2. We assume that ts[0] does not overlap with any preceding triggers, for this reason we initialize the counter to duration.

To sum it up: the solution is the sum 5 + 2 + 5, or:

1
2
3

duration +
ts[1] - ts[0] +
duration

Maybe you are already seeing a pattern here: when ts[i] overlaps with ts[i-1] then the contribution is ts[i] - ts[i-1], otherwise it is equal to duration.

We can turn this idea into code by explicitly checking against the “overlapping condition”:

1

interval1.end >= interval2.begin

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

auto cnt = duration;
for (auto i=1u; i<ts.size(); ++i)
{
    pair<int, int> prev = {ts[i-1], ts[i-1] + duration - 1};
    pair<int, int> curr = {ts[i], ts[i] + duration - 1};
    if (prev.second >= curr.first)
    {
        cnt += curr.second - prev.second;
    }
    else
    {
        cnt += duration;
    }
}
cout << cnt;

However, we can do even better. First of all, curr.second - prev.second can be reduced to ts[i] + duration - 1 - (ts[i-1] + duration - 1) = ts[i] - ts[i-1]:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

auto cnt = duration;
for (auto i=1u; i<ts.size(); ++i)
{
    if (ts[i-1] + duration - 1 >= ts[i])
    {
        cnt += ts[i] - ts[i-1];
    }
    else
    {
        cnt += duration;
    }
}
cout << cnt;

Actually, you can notice that the condition can be rewritten as duration > ts[i] - ts[i-1] and that such a condition is none other than choosing either duration or ts[i] - ts[i-1] depending on which is the smallest…this leads to:

1
2
3
4
5
6

auto cnt = duration;
for (auto i=1u; i<ts.size(); ++i)
{
    cnt += min(duration, ts[i] - ts[i-1]);
}
cout << cnt;

Intuitively, every ts[i] can’t contribute more than duration and at least ts[i] - ts[i-1] seconds.

Playing with patterns

The code above can be written in terms of the well-known pattern zip | map | reduce. In C++:

1
2
3
4
5

cout << inner_product(next(begin(ts)), end(ts), begin(ts), duration, 
        plus<>{}, [=](auto curr, auto prev) {
            return min(duration, curr - prev);
        }
    );

C++ ranges make things a bit nicer:

1

std::cout << accumulate(zip_with([=](auto i, auto j) { return min(duration, j - i); }, ts, tail(ts)), 0);

Try it on Compiler Explorer.

And this is an awesome application of pattern with Linq by Silvestro Pomes:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

static void Main(String[] args) {       
    var duration = Int32.Parse(Console.ReadLine().Split(" ")[1]);
    var detections = Console.ReadLine().Split(" ").Select(s => Int32.Parse(s)).ToList();

    var totalDuration = detections
        .Take(detections.Count-1)
        .Zip(detections.Skip(1), (first, second) => Math.Min(second-first, duration))
        .Sum() + duration;    
    Console.WriteLine(totalDuration);        
}

Here is another slick solution in Python by Andrea Battistello:

1
2
3
4
5
6
7

N, duration = list(map(int, input().split()))
times = list(map(int, input().split()))

diffs = [t2 - t1 for t1,t2 in zip(times, times[1:] + [max(times) + duration + 1])]
res = sum([min(d, duration) for d in diffs])

print(res)