SRM 480, D2, 250-Pointer (Cryptography)

James S. Plank

Thu Dec 20 12:27:25 EST 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
MD5 hash of tests.sh: 473475a0ef150d24d8a2392a29b0b486.
MD5 hash of answers.txt: 45aed9eded08e7bc45553f54594d5928.
Problem Given in Topcoder: August, 2010
Competitors who opened the problem: 755
Competitors who submitted a solution: 709
Number of correct solutions: 694
Accuracy (percentage correct vs those who opened): 91.9%
Average Correct Time: 9 minutes, 35 seconds.

In case the Topcoder servers are down

Here is a summary of the problem:

You are given a vector of integers called numbers.
The elements of numbers will be between 1 and 1000.
The size of numbers will be at least two and at most 50.
Your goal is to add one to exactly one element of numbers, and then calculate the product of all of the elements. The element you choose to increment should be the one that maximizes this product.
Return the product. It will be a long long, and the inputs will guarantee that product does not exceed 2⁶².

Examples

These are all included in main.cpp. If you give the input "-" to main.cpp, then it will read its values from standard input.

0	`{ 1, 2, 3 }`	12
1	`{ 1, 3, 2, 1, 1, 3 }`	36
2	`{1000, 999, 998, 997, 996, 995}`	986074810223904000
3	`{ 1, 1, 1, 1 }`	2

Testing Yourself without Topcoder's Servers

The workflow that I use for Topcoder is as follows:

I implement the class and method in a file that has the class' name. In this case, the file is Cryptography.cpp. This is the "skeleton" file in the bulleted list above. I have already filled in the class definition for you, so all you have to do is implement the method, which in this case is encrypt().
I compile with "g++ main.cpp". You'll note that main.cpp includes Cryptography.cpp. This is in general a really bad practice. You want to include header files, and then link together source files (please see the CS140 lecture in http://web.eecs.utk.edu/~jplank/plank/classes/cs140/Notes/Classes/index.html for a detailed explanation and example). However, it is expedient here, and it's convenient because you can debug your code with main.cpp, and then submit Cryptography.cpp to topcoder.
The result of compilation is an a.out file, which you can execute with ./a.out.

I have included a shell script called tests.sh. It simply runs a bunch of inputs on a.out. Here's an example of calling it:

UNIX> sh tests.sh
12
36
986069860049153880
2
7601258117112660
11654570193710400
92953772500680000
799967508480
307257753600
60949905408
37412763010118496
328150073180160
1386927360000000
103723200000
156764160000
33861058560
303992974847508480
14169988790496000
11069314249061376
65156670562135680
27311800320
2913258700800
4756917475143680
1331646220800000
86802030000
29030400000
UNIX>

How do you know if your code is working? Call tests.sh and store its standard output to a file. Then compare the file with answers.txt. Let me do that here:

UNIX> sh tests.sh > junk.txt
UNIX> diff junk.txt answers.txt
3c3
< 986069860049153880
---
> 986074810223904000
5,10c5,10
< 7601258117112660
< 11654570193710400
......
UNIX>

If the output is non-empty, it means that your program is not working correctly. You can try diff -y, and it will show you the tests that you got wrong, by lining up your file and the answers line-by-line:

UNIX> diff -y junk.txt answers.txt
12								12
36								36
986069860049153880					      |	986074810223904000
2								2
7601258117112660					      |	7654413768281280
11654570193710400					      |	15347582148096000
92953772500680000					      |	113868371313333000
799967508480						      |	1371372871680
307257753600						      |	460886630400
60949905408						      |	81266540544
37412763010118496						37412763010118496
328150073180160						      |	628954306928640
1386927360000000					      |	2037934080000000
103723200000							103723200000
156764160000						      |	250822656000
33861058560						      |	60197437440
303992974847508480						303992974847508480
14169988790496000					      |	14571784313856000
11069314249061376					      |	11602061993668608
65156670562135680					      |	65880633568381632
27311800320						      |	36415733760
2913258700800						      |	5098202726400
4756917475143680						4756917475143680
1331646220800000						1331646220800000
86802030000						      |	115736040000
29030400000							29030400000
UNIX>

As you can see, lines 3, 5, 6, 7, and so on differ. So look at lines three and five of tests.sh:

UNIX> sed -n 3p tests.sh
./a.out 2
UNIX> sed -n 5p tests.sh
echo 12 63 11 57 71 33 47 47 44 65 | ./a.out -
UNIX>

You now have test cases to help you debug! If your output of tests.sh is the same as answers.txt, then you can be satisfied that you have solved the problem!

Hints

Try this first on your own. If you get stuck or frustrated, then come back here and scroll down.

First off, you need to figure out -- given a collection of numbers, which number do I increment so that the product is increased by the largest amount? It shouldn't be too hard to see that you need to increment the smallest number.

[If you want to prove that formally, you can. Suppose you have a collection of numbers whose product is P. And suppose you have two numbers in the collection, a and b such that a < b. If you increment a, you change the product from P to P(a+1)/a. If you increment b, you change the product to P(b+1)/b. Since a < b, we know that (a+1)/a > (b+1)/b. (If you are stuck on that, think about examples: 3/2 is definitely greater than 101/100, right?) That means incrementing a will increase the factor by the greatest amount.]

So, you need to find the minimum element and increment it. You can write your own code to do that in two lines. Or you can use the sort() method from C++'s algorithms package to sort the vector and then increment the first element.

Now how about calculating the product? Since you are told that the product will be ≤ 2⁶², you need to use a 64-bit integer. In C++, this is a long long. Calculate your product using that, and you're done.