Statistics

Problem Statement for "FunctionalEquation"

Problem Statement

f is a function from integers to integers. In other words, f is defined over integers, and f(x) is an integer for all integers x. You are given an integer C. f is called C-beautiful if the following equality is satisfied for all integers x:



Return the minimal possible value of the following formula when f is C-beautiful:



Use the following recursive definitions to generate the sequences x and y:
  • x[0] = xzero
  • For all integer i between 1 and N-1, inclusive, x[i] = (x[i-1] * xprod + xadd) % xmod
  • y[0] = yzero
  • For all integer i between 1 and N-1, inclusive, y[i] = (y[i-1] * yprod + yadd) % ymod

Definition

Class:
FunctionalEquation
Method:
minAbsSum
Parameters:
int, int, int, int, int, int, int, int, int, int
Returns:
long
Method signature:
long minAbsSum(int C, int N, int xzero, int xprod, int xadd, int xmod, int yzero, int yprod, int yadd, int ymod)
(be sure your method is public)

Notes

  • 64-bit integers should be used to generate the sequences x and y to avoid overflow.

Constraints

  • C will be between 1 and 16, inclusive.
  • N will be between 1 and 10,000, inclusive.
  • xmod and ymod will each be between 1 and 1,000,000,000, inclusive.
  • xzero, xprod and xadd will each be between 0 and xmod - 1, inclusive.
  • yzero, yprod and yadd will each be between 0 and ymod - 1, inclusive.

Examples

  1. 3

    10

    0

    1

    1

    456

    1

    1

    1

    456

    Returns: 0

    f(x) = x + 1 is a 3-beautiful function. Since x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and y = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, the sum of |f(x[i]) - y[i]| is 0.

  2. 4

    10

    0

    1

    1

    456

    1

    1

    1

    456

    Returns: 5

    x and y are the same as in example 0, but f(x) = x + 1 is not a 4-beautiful function.

  3. 16

    10000

    654816386

    163457813

    165911619

    987654321

    817645381

    871564816

    614735118

    876543210

    Returns: 3150803357206

  4. 1

    5934

    74927846

    81480857

    44270004

    85377744

    445349752

    237936238

    176941747

    553475509

    Returns: 826192064195

  5. 1

    10000

    147699711

    68110231

    265456603

    812158120

    47517990

    182546393

    576960918

    686078706

    Returns: 2560688375452

  6. 2

    7367

    110025762

    893294747

    715669847

    979932170

    222156922

    290269007

    68706223

    486937973

    Returns: 2412152751798

  7. 2

    10000

    212567592

    196211064

    121137619

    843638550

    373823875

    136263086

    498416072

    928126552

    Returns: 2969341761391

  8. 3

    636

    458823023

    111509468

    155060020

    941604921

    620938878

    361646331

    65916225

    659998485

    Returns: 172494922206

  9. 3

    10000

    564817402

    142750431

    382045455

    729267237

    37853113

    86806113

    82137026

    98560398

    Returns: 1825669888536

  10. 4

    9345

    439352155

    327925359

    398844030

    718458135

    73660030

    131636287

    67423694

    185252728

    Returns: 2619775228955

  11. 4

    10000

    9275835

    12319869

    8400180

    15934105

    279749904

    109805315

    35610585

    451230257

    Returns: 2165187914265

  12. 5

    2491

    95172609

    164382895

    344966675

    518954510

    592776277

    108002669

    120033497

    843654050

    Returns: 596004732771

  13. 5

    10000

    607525771

    219218649

    643287356

    669566825

    13380803

    35821365

    14142682

    41654185

    Returns: 1677351978846

  14. 6

    9307

    510016244

    238727332

    292425665

    807426510

    589638738

    401170801

    142762906

    944216784

    Returns: 2746278190378

  15. 6

    10000

    93919351

    213421540

    131636656

    225161331

    118506227

    59723643

    41744078

    182095964

    Returns: 705661771196

  16. 7

    7107

    141805243

    402957063

    289631603

    593400969

    139402177

    533004090

    346100850

    668882481

    Returns: 1505051655067

  17. 7

    10000

    71772622

    73164044

    27005862

    86000815

    5748438

    116253679

    537894392

    730103626

    Returns: 3254314678690

  18. 8

    8488

    659169187

    28409913

    378183875

    883570152

    7347798

    70060802

    6364913

    148026996

    Returns: 3203311970591

  19. 8

    10000

    591635571

    653962273

    74652421

    968295563

    216467786

    19740618

    37577381

    241418522

    Returns: 3833983696658

  20. 9

    7679

    542938503

    206695870

    201610954

    928854727

    351329094

    505684556

    399462403

    521884894

    Returns: 2343982908067

  21. 9

    10000

    212677188

    433862532

    276162929

    525440094

    49373640

    478939469

    217079209

    533958747

    Returns: 1767149750066

  22. 10

    5888

    138865765

    237123473

    99354562

    931858669

    49959755

    196796183

    706140952

    825207675

    Returns: 1747727699689

  23. 10

    10000

    9230700

    1222330

    3415086

    9984371

    114468298

    71283494

    189070372

    232021906

    Returns: 1106563559709

  24. 11

    143

    399394688

    227202703

    208346752

    471898586

    68892498

    56246726

    295849487

    338685732

    Returns: 18745735369

  25. 11

    10000

    68043415

    86105649

    87899677

    114316401

    41486561

    33169381

    24337977

    54969875

    Returns: 386790741588

  26. 12

    9269

    19535542

    18591734

    16771103

    23689366

    333349106

    368318229

    148250950

    817376090

    Returns: 1882041785076

  27. 12

    10000

    174332796

    283046337

    275817006

    302247656

    30457374

    3823673

    25720447

    41127596

    Returns: 755011616901

  28. 13

    8731

    58765573

    86262417

    33355022

    220256096

    137668077

    58482455

    76813188

    145222949

    Returns: 542896026559

  29. 13

    10000

    288380741

    76964473

    23634883

    377520761

    120469632

    1506009

    71668959

    166723144

    Returns: 1296255932305

  30. 14

    6136

    228920379

    263526060

    200584307

    934901150

    1116921

    2070187

    2772385

    3224418

    Returns: 1424244849736

  31. 14

    10000

    134707445

    172761231

    79172

    209707627

    95199961

    181241457

    495064395

    509813596

    Returns: 1778192202354

  32. 15

    1718

    309016705

    94994520

    63674453

    458914656

    7905110

    12128135

    11496683

    14238777

    Returns: 199633864720

  33. 15

    10000

    325859158

    466282452

    501708870

    631623003

    35989158

    130019381

    35011394

    133968317

    Returns: 1597511470051

  34. 16

    7481

    30993756

    44696234

    33463367

    81126605

    601214124

    287289792

    40379410

    818041955

    Returns: 2781812799054

  35. 16

    10000

    117429278

    331165382

    692893978

    741274454

    527723017

    623540543

    400089019

    685894564

    Returns: 2395599628795

  36. 16

    10000

    0

    1

    32

    1000000

    527723017

    623540543

    400089019

    685894564

    Returns: 1732193269752

  37. 16

    10000

    31

    1

    32

    1000000

    527723017

    623540543

    400089019

    685894564

    Returns: 1732193269752

  38. 3

    100

    47

    0

    47

    1000

    23

    1

    1

    1000

    Returns: 2500

  39. 3

    101

    47

    0

    47

    1000

    23

    1

    9

    100000

    Returns: 22950

  40. 4

    9876

    42

    0

    47

    1000

    23

    1

    9

    100000

    Returns: 219410154

  41. 7

    9853

    100

    1

    100

    1000

    32154215

    3252151

    24512515

    141536326

    Returns: 347153664344

  42. 16

    10000

    17

    13

    5

    70

    14

    3

    74

    99

    Returns: 179976

  43. 16

    10000

    47

    34

    32

    79

    29

    12

    8

    77

    Returns: 267868

  44. 16

    10000

    999999999

    1

    999999999

    1000000000

    999999999

    1

    999999999

    1000000000

    Returns: 74968

  45. 16

    10000

    999999999

    1

    999999999

    1000000000

    0

    1

    1

    1000000000

    Returns: 9983900394646

  46. 16

    10000

    999999999

    1

    999999999

    1000000000

    176435876

    167435187

    467351289

    1000000000

    Returns: 4977459607130

  47. 16

    3

    1

    2

    3

    61754

    5

    6

    9

    3746

    Returns: 1

  48. 2

    3

    1746

    52486

    16254

    23659449

    1263

    28576

    1965

    9256197

    Returns: 12354086

  49. 16

    10000

    999999999

    1

    0

    1000000000

    6

    3

    1

    10

    Returns: 15000

  50. 16

    10000

    999999999

    1

    1

    1000000000

    499999999

    1

    2

    1000000000

    Returns: 4992049920040

  51. 16

    10000

    121845875

    306684394

    227859661

    481765934

    553475508

    445349752

    532217555

    812669701

    Returns: 2262234548866

  52. 16

    10000

    351323605

    147699711

    149851094

    730417257

    686078705

    326208420

    182546393

    889772844

    Returns: 2756104505611

  53. 16

    10000

    220137366

    81695507

    140839601

    949118331

    715669847

    613711054

    322805950

    873226918

    Returns: 3040228259681

  54. 16

    10000

    68706223

    289224587

    212567592

    777206981

    81288004

    44638386

    418462262

    883488165

    Returns: 2792748689953

  55. 16

    10000

    434026433

    849040635

    941604920

    992516191

    393007530

    36130137

    259570539

    400427945

    Returns: 3504342498595

  56. 16

    10000

    276956481

    164039982

    43643052

    280937364

    2639169

    19133523

    20243344

    23351877

    Returns: 701552611665

  57. 16

    10000

    260469815

    35222838

    72558668

    910500676

    439352155

    327925359

    398844030

    718458135

    Returns: 2745710005657

  58. 16

    10000

    73660030

    131636287

    67423694

    185252728

    9275835

    12319869

    8400180

    15934105

    Returns: 465649048881

  59. 16

    10000

    279749904

    109805315

    35610585

    451230257

    28539563

    117322137

    186532423

    248402491

    Returns: 1476233089237

  60. 16

    10000

    312151265

    287803239

    185905327

    382875696

    109131350

    76757616

    99185151

    120033498

    Returns: 984558894210

  61. 16

    10000

    111792113

    143048379

    105360174

    643287357

    616518298

    807426509

    428861746

    888581008

    Returns: 2746180421153

  62. 16

    10000

    292425665

    90636430

    589638738

    853580353

    284638086

    21648924

    241374931

    401170802

    Returns: 2909204660772

  63. 16

    10000

    131636656

    164411375

    193397423

    339228196

    71540614

    69091682

    136502684

    152299428

    Returns: 908457458838

  64. 16

    10000

    119346575

    599422084

    668882480

    735206213

    393601912

    206698672

    469431496

    808284659

    Returns: 2590763122294

  65. 16

    10000

    37600868

    77443501

    6533929

    361784848

    1388645

    3341438

    348151

    5748439

    Returns: 1793414724283

  66. 16

    10000

    659169187

    28409913

    378183875

    883570152

    7347798

    70060802

    6364913

    148026996

    Returns: 3765129963191

  67. 16

    10000

    591635571

    653962273

    74652421

    968295563

    216467786

    19740618

    37577381

    241418522

    Returns: 3830554493342

  68. 16

    10000

    145299368

    542938503

    243772918

    891777679

    47321621

    42728262

    54445332

    59320409

    Returns: 4127838346458

  69. 16

    10000

    560323007

    212677188

    519625634

    965117086

    533958746

    583332387

    375849286

    852483212

    Returns: 3038180309783

  70. 16

    10000

    45279047

    195224988

    48870213

    217079210

    66084108

    113837252

    40510787

    237123474

    Returns: 760087510961

  71. 16

    10000

    27

    28

    11

    34

    0

    0

    0

    1

    Returns: 20000

  72. 16

    10000

    40

    0

    23

    57

    37

    40

    29

    44

    Returns: 99980

  73. 16

    10000

    11

    20

    9

    31

    17

    2

    8

    18

    Returns: 24663

  74. 16

    10000

    79

    60

    21

    81

    19

    1

    37

    65

    Returns: 162394

  75. 16

    10000

    52

    79

    74

    91

    35

    37

    44

    45

    Returns: 112534

  76. 16

    10000

    37

    22

    36

    64

    54

    34

    10

    77

    Returns: 190784

  77. 16

    10000

    35

    38

    28

    76

    10

    19

    25

    35

    Returns: 91647

  78. 16

    10000

    10

    19

    10

    28

    0

    4

    0

    5

    Returns: 0

  79. 16

    10000

    14

    19

    17

    57

    72

    60

    23

    91

    Returns: 209937

  80. 16

    10000

    65

    87

    79

    96

    16

    10

    97

    98

    Returns: 244589

  81. 1

    1

    0

    86522

    4134

    407635

    1

    0

    21

    2578

    Returns: 0

  82. 16

    1

    0

    135101200

    293

    1000000000

    37619066

    6499

    79

    1000000000

    Returns: 0

  83. 6

    955

    0

    0

    12

    93

    0

    0

    0

    2

    Returns: 12

  84. 8

    785

    7

    532

    3804298

    81380390

    0

    0

    0

    4

    Returns: 15848324277

  85. 8

    7674

    50

    9

    187

    4423

    0

    0

    0

    3

    Returns: 16766300

  86. 3

    1

    71

    42443

    377060

    705190426

    7

    80

    0

    4443

    Returns: 0

  87. 9

    7

    0

    254

    677983

    1000000000

    0

    640

    286

    6026

    Returns: 1046973466

  88. 3

    10000

    2

    0

    0

    18

    668737

    34154

    628

    1000000000

    Returns: 2491194191182

  89. 9

    41

    6

    672

    0

    121172274

    41171

    606386504

    0

    1000000000

    Returns: 9172585980

  90. 9

    4

    0

    6

    4236

    9651

    533

    113478

    399868028

    538424133

    Returns: 40078590

  91. 15

    4

    32876560

    1

    0

    88039523

    14

    92

    274588

    18084460

    Returns: 16866178

  92. 11

    54

    0

    0

    39

    50

    2132

    0

    9442

    85546

    Returns: 0

  93. 6

    7

    0

    9

    0

    46

    8552

    3

    2190

    9390

    Returns: 18290

  94. 9

    6194

    3452064

    6

    5

    91100346

    0

    4

    5

    21

    Returns: 141389525959

  95. 5

    67

    67242

    3215

    392115

    578097

    2

    0

    0

    74

    Returns: 19016059

  96. 9

    919

    417

    1083

    519

    4653

    0

    0

    0

    4

    Returns: 1014354

  97. 1

    10000

    47

    1013

    24

    543990368

    35

    18893

    16

    91693

    Returns: 1365240944232

  98. 6

    2

    61

    548655

    1845320

    662967648

    928

    46

    2950

    5315

    Returns: 0

  99. 12

    8

    0

    1

    69

    620

    82

    0

    7

    230

    Returns: 8

  100. 13

    11

    5

    0

    14

    26

    0

    3451

    320

    829879

    Returns: 1594359

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: