SRM 737, D1, 600-Pointer (GroupTheNumbers)

James S. Plank

Thu Nov 1 21:00:30 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: September, 2018
Competitors who opened the problem: 130
Competitors who submitted a solution: 75
Number of correct solutions: 19
Accuracy (percentage correct vs those who opened): 14.6%
Accuracy (percentage correct vs those who submitted): 25.3%
Average Correct Time: 30 minutes, 45 seconds.

This problem has two challenges:

Figuring out how to partition the numbers into sets.
Performing the calculations on numbers that are huge.

For the first problem, you need to reason through the special cases, and unfortunately, they are not all covered by the examples. However, you need to keep track of the following:

The positive numbers > 1
The negative numbers < -1
The number of 0's.
The number of -1's.
The number of 1's.

With these quantities, you can calculate the answer. Of course, you'll have to solve the second problem to calculate the answer, but solving this first part is the first step. To help you, here are some vectors, and how the partitioning works:

{ -3, -4, 3, 4 }                   -> { -3, -4, 3, 4 }
{ -5, -4, -3, 3, 4 }               -> { -5, -4, 3, 4 }, {-3 }
{ -5, -4, -4, -1 }                 -> { -5, -4, -4, -1 }
{ -5, -4, -4, -1, -1, -1 }         -> { -5, -4, -4, -1 }, { -1, -1 }
{ -3, 1, 1, 1, 1, 4, 6 }           -> { -3 }, { 4, 6 }, { 1 }, { 1 }, { 1 }, { 1 }
{ -3, 0, 1, 1, 1, 4, 6 }           -> { -3 }, { 4, 6 }, { 1 }, { 1 }, { 1 }, { 1 }
{ -3, 0, 1, 1, 1, 4, 6 }           -> { -3, 0 }, { 4, 6 }, { 1 }, { 1 }, { 1 }
{ -3, -2, 0, 1, 1, 4, 6 }          -> { -3, -2 }, { 4, 6 }, { 1 }, { 1 }, { 0 }

So, that's your first job -- to figure out the partitions.

Once you've done that, you now need to make some large calculations. What I did was write some procedures to handle really large numbers, which I represented as deque's of digits. Here were my procedures:

/* Multiply arbitrarily long positive number s, with a
   single digit number n, and change s to reflect the resuilt */

void mult(deque <int> &s, int n);

/* Add two arbitrarily large positive 
   numbers s1 and s2, and put the result into s1 */

void add(deque <int> &s1, deque <int> &s2);

/* Subtract the number s from arbitrarily large number s1, and
   modify s1 to hold the result.  All numbers are positive,
   and s1 is greater than s2. */

void sub(deque <int> &s1, int s2)

/* Multiply arbitrarily long positive number s, with a
   positive integer n.  This calls mult() to do the single
   digit multiplications */

void longmult(deque <int> &s, int n)

This is a problem where the problem itself and the individual components are all really straightforward. You just need to get everything ordered correctly.