EllysIncrements
TCC19 South America Final · 2019-06-10 · by misof
Problem Statement
Elly has a
Elly wants to change all numbers in her array into primes. Compute and return the smallest number of steps to do that.
Notes
- A prime number is a positive integer with exactly two divisors. The smallest few primes are 2, 3, 5, 7, 11, 13, 17, 19, ...
Constraints
- A will contain between 1 and 100 elements, inclusive.
- Each element of A will be between 1 and 1,000,000, inclusive.
{1, 8, 3, 3, 5, 8, 7, 2, 4}
Returns: 5
One optimal solution is illustrated below. 1 8 3 3 5 8 7 2 4 |--------------| 1 9 4 4 6 9 7 2 4 |-----| 1 9 4 4 6 9 7 3 5 |-----------------| 2 10 5 5 7 10 7 3 5 |--| 2 11 5 5 7 10 7 3 5 |--| 2 11 5 5 7 11 7 3 5
{44}
Returns: 3
{611708,611720,611728,611744,611750,611762,611774,611788,611792,611794,611800,611812,611818,611822,611834,611858,611860,611864,611884,611888,611900,611920,611924,611932,611944,611968,611974,611980,612010,612014,612052,612058,612068,612070,612082,612092,612100,612122,612124,612128,612134,612152,612158,612190,612232,612248,612262,612304,612334,612340,612362,612364,612388,612394,612400,612422,612430,612464,612470,612478,612488,612502,612514,612542,612548,612560,612562,612568,612574,612592,612598,612604,612620,612628,612640,612674,612680,612698,612718,612722,612728,612758,612760,612764,612800,612812,612848,612850,612892,612904,612914,612920,612928,612932,612940,612950,612964,612970,612980,612982}
Returns: 249
A bunch of primes, each decremented by 249. The optimal solution should be to increment the whole range 249 times.
{611707,611719,611727,611743,611749,611761,611773,611787,611791,611793,611799,611811,611817,611821,611833,611857,611859,611863,611883,611887,611899,611919,611923,611931,611943,611967,611973,611979,612009,612013,612051,612057,612067,612069,612081,612091,612099,612121,612123,612127,612133,612151,612157,612189,612231,612247,612261,612303,612333,612339,612361,612363,612387,612393,612399,612421,612429,612463,612469,612477,612487,612501,612513,612541,612547,612559,612561,612567,612573,612591,612597,612603,612619,612627,612639,612673,612679,612697,612717,612721,612727,612757,612759,612763,612799,612811,612847,612849,612891,612903,612913,612919,612927,612931,612939,612949,612963,612969,612979,612981}
Returns: 244
The same bunch of primes, each decremented by 250. Suddenly there is a solution better than 250.
{492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112,492114,492112}
Returns: 139
{611948,611960,611968,611984,611990,612002,612014}
Returns: 9
An optimal solution is to increment everything in the array nine times.
{1, 3, 1, 7, 1, 7, 1, 3}
Returns: 4
An optimal solution is to individually increment each 1 to a 2.
{1000000}
Returns: 3
Even though the initial values are only up to 10^6, Elly may be forced to increment some of the values beyond this range.
Submissions are judged against all 66 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysIncrements with a public method int getMin(vector<int> A) · 66 test cases · 2 s / 256 MB per case