SRM 704, D2, 250-Pointer (SwapAndArithmetic)

James S. Plank

Fri Feb 3 14:42:38 EST 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 hash: ea44cca1682b182cf0907f52e85c84ae
answers.txt. MD5 hash: 0c1d33d050ca57cba10f7757eb56f57b
Problem Given in Topcoder: December, 2016
Competitors who opened the problem: 413
Competitors who submitted a solution: 385
Number of correct solutions: 353
Accuracy (percentage correct vs those who opened): 85.47%
Average Correct Time: 8 minutes, 33 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

A vector v of integers is an arithmetic sequence if for each i > 0, (v[i] - v[i-1]) is the same value.
For example, { 1, 2, 3 }, { 2, 4, 6 } and { 10, 9, 8 } are all arithmetic sequences. { 10, 9, 7 } and { 2, 4, 2 } are not.
You are given a vector x which contains between 2 and 50 integers.
The values of x will be between 1 and 1000.
If it is possible to swap an arbitrary number of elements of x to yield an arithmetic sequence, then return "Possible".
Otherwise, return "Impossible".

The examples


"Possible" (swap it to become { 3, 2, 1 } or { 1, 2, 3 }
"Impossible"
"Possible"
"Impossible"
"Possible"

Testing yourself

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt

Hints

Try this on your own. If you get stuck, return here and read what I've written below.

If you're here, think about how much easier the problem is if you sort the input. Now, go back and try to solve it again, and if you get stuck again, come back.

What you want to do is sort the vector. You can do that most easily with the sort() method from the STL algorithms library. You need to include algorithms, and then you can sort the vector with sort(x.begin(), x.end()). Then, the easiest thing to do is try to discover if the vector is not an arithmetic sequence.

The way that I did that was to:

First return "Possible" if x only has one element.
Then, I stored the difference between the first two elements of x into a variable diff.
Then, I checked every adjacenct pair of elements in x. If the difference between any of these is not equal to diff, then you can return "Impossible."
If you have checked all adjacenct pairs of elements, then you can return "Possible."

Example	x	Answer
0	{ 3, 1, 2 }	"Possible" (swap it to become { 3, 2, 1 } or { 1, 2, 3 }
1	{ 1, 2, 4 }	"Impossible"
2	{ 1, 1, 1, 1, 1, 1 }	"Possible"
3	{ 1000, 704, 1 }	"Impossible"
4	{ 7, 3, 11, 5, 1, 9 }	"Possible"