SRM 706, D2, 250-Pointer (ThreeIncreasing)

James S. Plank

Sat Dec 22 10:49:34 EST 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 hash: ffca61f795e02f4e0b5ffdda104d76fe
answers.txt. MD5 hash: 85049871b28db1886235cfd6f7ab31f4
Problem Given in Topcoder: January, 2017
Competitors who opened the problem: 404
Competitors who submitted a solution: 377
Number of correct solutions: 314
Accuracy (percentage correct vs those who opened): 77.72%
Average Correct Time: 13 minutes, 42 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

You are given three values, which in the problem are the numbers of candies in three boxes. The boxes are labeled a, b and c.
You want to eat the minimum number of candies, such that when you look at the candies remaining in the boxes, a < b < c.
Return the minimum number of candies that you eat.
If it's impossible, return -1.
a, b and c are all less than or equal to 3000.

The examples

Example	a	b	c	Answer
0	15	40	22	19
1	5	6	6	2
2	6	1	3000	-1
3	6	4	2	-1
4	4	2	6	3
5	1	1234	3000	0
6	2789	2400	1693	1806

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, scroll down and read what I've written below.

This is a problem that you simply have to think about in the right order. First off, think about when will you return -1?

Is there a value c that will always require you to return -1?
Is there a value b that will always require you to return -1?
When it comes to returning -1, does the value of a ever matter?

Answer these questions, and go ahead and write code to return -1 when you have to. Your code should work on examples 2 and 3.

Now, assume that you're in a situation when you are not returning -1. Answer this question:

Is there ever a time when you would ever eat candies from the third box?

You should see that the answer to this is, "no." So, the first thing to do is eat just enough candies so that b is less than c. And the second thing to do is eat just enough candies to that a is less than b. And you're done.