SRM 714, D2, 250-Pointer (RangeEncoding)

James S. Plank

Wed May 10 01:06:48 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: May, 2017
Competitors who opened the problem: 295
Competitors who submitted a solution: 285
Number of correct solutions: 275
Accuracy (percentage correct vs those who opened): 93.2%
Average Correct Time: 7 minutes, 54 seconds.

In case Topcoder's servers are down, here is a summary of the problem:

You are given a vector of integers, arr.
The integers are distinct, positive, and in increasing order.
The topcoder constraints have the size of arr being between 1 and 50, but you can solve this for array sizes up to 1,000,000.
For any two integers a ≤ b, the "range [a,b]" is composed of all integers i such that a ≤ i ≤ b.
If you view arr as a union of ranges, what is the smallest number of ranges that are required, so that their union is arr.

Examples (these are compiled into the main.cpp program):

Example	Input	Output
0	{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }	1
1	{ 1, 6, 10, 20, 32, 49 }	6
2	{ 2, 4, 5, 6, 8, 9, 10, 11, 12, 15 }	4
3	{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 }	14
4	{ 10, 11, 12, 13, 14, 15, 20, 21, 22, 23, 25, 27, 28, 29, 30, 31, 32, 33 }	4
5	{ 33 }	1

I have also made it so that if you give the test program a number between 6 and 1,000,000, then it generates a random problem with that many elements in arr.

If you compile your program to a.out, then running tests.sh should yield the exact same answer as answers.txt. The whole thing should take under a half of a second.

Hints (or, in this case, not really)

As the numbers above show, this was one of the easiest Topcoder problems ever. I'm not going to give code here -- this is for you to figure out. My one hint is that my for loop was:

  for (i = 1; i < arr.size(); i++) ...