Problem Statement
You are writing a program for a very simple processor. It is attached to a slow memory system that contains n bytes, numbered 0 to n - 1. The processor has a cache which holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1.
In order to keep the processor as simple as possible, the programmer must directly control the cache. To access some byte in memory, the program must first set the cache base address. Any bytes that are in the new range that were not in the old range are read from the memory store, but bytes that were in both the old and new ranges are simply kept in the cache and do not require a read from the memory store.
You wish to optimize a program to use as few memory reads as possible. The bytes that the program accesses, in the order it accesses them, are given in addresses. Determine the minimum number of bytes that must be read from the memory store. Note that when the program starts, the cache is in a special empty state, so the first cache update always requires k bytes to be read.
Definition
- Class:
- ContiguousCache
- Method:
- minimumReads
- Parameters:
- int, int, int[]
- Returns:
- long
- Method signature:
- long minimumReads(int n, int k, int[] addresses)
- (be sure your method is public)
Constraints
- n will be between 1 and 1,000,000,000, inclusive.
- k will be between 1 and n, inclusive.
- addresses will contain between 1 and 50 elements, inclusive.
- Each element of addresses will be between 0 and n-1, inclusive.
Examples
100
3
{0, 2, 16, 13}
Returns: 7
The first access must read bytes 0 to 2, inclusive. For the second access, no reads are needed, since 2 is already cached. For the third access, the base address should be set to 14. Then for the final access, the base address is set to 13, and only one additional byte must be read.
100
10
{1,10,19,28,30,37}
Returns: 29
1000000000
500000000
{0, 999999999, 1, 500000000, 500000001, 987654321}
Returns: 1987654320
1
1
{0}
Returns: 1
1
1
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
Returns: 1
1000
11
{0,10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490}
Returns: 275
49500
11000
{49000,48000,47000,46000,45000,44000,43000,42000,41000,40000,39000,38000,37000,36000,35000,34000,33000,32000,31000,30000,29000,28000,27000,26000,25000,24000,23000,22000,21000,20000,19000,18000,17000,16000,15000,14000,13000,12000,11000,10000,9000,8000,7000,6000,5000,4000,3000,2000,1000,0}
Returns: 46004
100
5
{0,50,49,51,48,52}
Returns: 10
100
5
{50,49,51,48,52,47,53,46,54,50}
Returns: 15
100
30
{69,6,52,66,62,4,50,85,93,95,50,6,38,76,82,40,70,93,64,46,23,8,4,33,60,71,25,82,13,23,22,33,52,64,35,34,35,77,67,16,90,9,70,70,43,77,67,62,9,88}
Returns: 651
1000000000
1000000000
{0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999}
Returns: 1000000000
1000000000
999999999
{0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999}
Returns: 1000000048
1000000000
100000000
{846737518,135567346,774537425,772670038,975506079,332031636,226757473,221119719,829391373,539011146,214711102,947125693,952310683,663069199,727778583,460765457,816913555,720610255,682165856,44035369,385152457,584551798,558515391,762286702,604909418,201641426,597435560,338880853,478185503,632576974,678752690,893683838,469008466,67567402,518457273,824924158,284980066,249028694,84088974,799641398,17026147,132343832,589254653,778619595,387312537,792255432,218794596,746118472,393455854,459355544}
Returns: 3746423525
1000000000
2
{539502238,974547283,212241408,104396577,27910883,153766988,370910869,549152611,460103649,595300424,63902829,564495557,650801271,130513693,971795910,259912016,116253376,201071800,205015641,236747635,413617740,745747255,466347665,63998630,502333018,925061382,794806955,172009965,137991811,910916166,391667211,39700313,441869419,768854351,537621911,829837893,55029740,739642064,876821669,312594541,236571457,626103009,803482092,878272038,30977520,167772815,477577364,184513819,184513819,162838059}
Returns: 98
13
4
{ 3, 4, 9, 8, 4, 3, 8, 9, 6 }
Returns: 13
13
4
{ 4, 3, 8, 9, 3, 4, 9, 8, 6 }
Returns: 13
100
2
{0, 2}
Returns: 3
8
2
{7}
Returns: 2
5
3
{1,2,3}
Returns: 3
1000000000
500000000
{0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999,0,999999999}
Returns: 25000000000
10
3
{2, 3, 1, 8, 7, 9}
Returns: 6
1000000000
500000000
{0, 999999999, 1, 500000000, 500000001, 987654321 }
Returns: 1987654320
1000000000
100000000
{100000000, 199999999, 10004000, 100001000, 104000000, 107000000, 100200000, 200000123, 200000120, 200000133, 900000000, 900120000, 950000000, 900330120, 870000000, 880000100, 880000100, 810000100, 1, 999999999, 1, 999999999, 1, 999999999, 1, 999999999, 1, 999999999, 1, 599999999, 599999998, 699999999, 1, 100000000, 300000000, 500000000, 400000001, 400000000, 400000002, 400010000, 0, 1, 2, 800000000, 300000000, 350000000, 290000000, 360000000, 280000000, 1234 }
Returns: 2319992038
1000000000
250000000
{785923848, 214968828, 216071525, 762674661, 405942601, 221266229, 90811307, 476818886, 496650084, 492578234, 28351115, 154035003, 343299087, 780940108, 996093805, 69824650, 281405883, 508099430, 702462741, 633484021, 43231270, 203784004, 959421105, 184879475, 83739605, 140162685, 486790270, 444325237, 831498005, 326745319, 559322789, 77297062, 740713284, 465966360, 662241748, 533962536, 371512663, 233517659, 752461441, 148943144, 344063777, 498294814, 194396619, 421954630, 941959394, 340083408, 156669017, 564712783, 267154874, 503447879 }
Returns: 5739462683
1000000000
747474
{7, 4, 5, 1, 2, 100000, 74, 74, 747474 }
Returns: 747474
8
6
{4 }
Returns: 6
1000000000
400000000
{0, 999999999, 1, 500000000, 50000003, 987654322 }
Returns: 1749999998
7
5
{3 }
Returns: 5
1000000000
1000000
{1, 999999999, 1, 999999999 }
Returns: 4000000
1000000000
333333333
{1, 333333333, 333333334, 999999999, 1, 2, 1, 1, 333333333, 333333332, 0, 804289383, 846930886, 681692777, 714636915, 957747793, 424238335, 719885386, 649760492, 596516649, 189641421, 25202362, 350490027, 783368690, 102520059, 44897763, 967513926, 365180540, 540383426, 304089172, 303455736, 35005211, 521595368, 294702567, 726956429, 336465782, 861021530, 278722862, 233665123, 145174067, 468703135, 101513929, 801979802, 315634022, 635723058, 369133069, 125898167, 59961393, 89018456, 628175011 }
Returns: 5323306528
1000000000
500000000
{702196450, 43781767, 719747633, 520122086, 528724140, 777016718, 763429057, 89555339, 602575640, 579992783, 847198012, 859271014, 40821354, 350290088, 306614229, 887432189, 943208578, 688923877, 421428285, 885084437, 55969802, 85835175, 17415133, 445581665, 751642680, 716639840, 942648752, 389915222, 517125952, 151951098, 790257082, 265042266, 621515031, 646210088, 433650283, 919076723, 33630725, 773077691, 346912339, 932485990, 957573015, 715980456, 772635602, 526119558, 713161812, 647543370, 83741207, 407209604, 987430102, 26780391 }
Returns: 5576502266
1000000000
12456789
{10, 500000000, 400000000, 1000, 23434, 13451345, 66643, 1212, 1232, 4234, 999999999, 32452345, 2345, 56, 34565656, 234234, 23546, 11111, 8999, 2343, 10, 500000000, 400000000, 1000, 23434, 13451345, 66643, 1212, 1232, 4234, 999999999, 32452345, 2345, 56, 34565656, 234234, 23546, 11111, 8999, 2343, 3456546, 43, 54643634, 234234, 78978, 342, 5763, 245, 345734, 345 }
Returns: 240652795
87
65
{12, 62, 2, 4, 81, 77, 42, 72, 72, 2, 60, 16, 29, 2, 33, 16, 49, 66, 6, 21, 24, 76, 65, 73, 67, 43, 10, 4, 44, 59, 28, 72, 44, 30 }
Returns: 117
1000000000
500000000
{0, 999999999, 1, 500000000, 500000001, 987654321, 324325, 6235, 623, 532, 623623, 1, 1, 1, 1, 1, 1, 3, 34, 52, 62, 52, 8678, 1, 1, 34, 52378, 1, 1, 56359, 234, 5, 23, 5, 23, 64, 324, 6, 324, 6523, 324, 6, 324, 347832, 654, 324, 23, 5, 623, 4345 }
Returns: 2475308641
3
3
{1 }
Returns: 3
11
4
{10, 9, 5, 4, 1, 0 }
Returns: 10
36
8
{28, 2, 10, 35, 10, 6, 8, 7, 17, 24, 6, 2, 12, 2, 20, 13, 33, 3, 2, 29, 2, 33, 35, 28, 10, 9, 28, 8, 26, 31, 5, 31, 27, 35 }
Returns: 152
1000000000
50
{527944804, 291582194, 63967152, 136191754, 701878821, 363885003, 651734927, 363081166, 510505595, 257102581, 396072282, 749488120, 393924802, 490731330, 880593629, 103158519, 35477436, 228297880, 983098007, 677232817, 630955429, 266116770, 71618782, 827454347, 377219342, 915566406, 710936702, 116451335, 833827503, 128293936, 886221094, 963021614, 807027674, 925691959, 743263171, 134246895, 323625684, 792084510, 113852095, 487684303, 721325751, 624763054, 25692980, 381381737, 762357046, 840893771, 541658101, 588103135, 462081183, 837569124 }
Returns: 2500
10000000
5053
{257, 17765, 32165, 3789, 3850, 3815, 31357, 28518, 15900, 3159, 27263, 19887, 25241, 538, 31687, 28002, 1824, 3814, 22150, 2299, 8973, 6194, 10152, 16842, 6723, 23274, 16052, 22087, 27177, 29798, 17140, 4773, 10226, 30621, 17367, 12202, 13346, 25238, 10387, 5053, 18253, 2080, 17166, 10817, 15394, 16835, 2559, 17697, 15017, 32246 }
Returns: 158176
1000000000
250000000
{0, 249999999, 410000000, 400000000, 420000000, 600000000, 999999999, 750000000, 600000000, 250000000, 499999999, 749999998, 800000000, 0, 249999999, 400000000, 999999999, 750000000, 600000000, 250000000, 499999999, 749999998, 800000000, 0, 249999999, 400000000, 999999999, 750000000, 600000000, 250000000, 499999999, 749999998, 800000000, 0, 249999999, 400000000, 999999999, 750000000, 600000000, 250000000, 499999999, 749999998, 800000000, 0, 249999999, 400000000, 999999999, 750000000, 600000000 }
Returns: 5900000008
826
630
{532 }
Returns: 630
5
5
{2 }
Returns: 5
1000000000
2000000
{1999999, 1000000, 2999999 }
Returns: 2000000
49999
1000
{500, 1500, 2500, 3500, 4500, 5500, 6500, 7500, 8500, 9500, 10500, 11500, 12500, 13500, 14500, 15500, 16500, 17500, 18500, 19500, 20500, 21500, 22500, 23500, 24500, 25500, 26500, 27500, 28500, 29500, 30500, 31500, 32500, 33500, 34500, 35500, 36500, 37500, 38500, 39500, 40500, 41500, 42500, 43500, 44500, 45500, 46500, 47500, 48500, 49500 }
Returns: 25025
50
3
{20, 18, 16, 12, 11 }
Returns: 8
20
10
{0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19, 0, 19 }
Returns: 500
18919111
91912
{0, 392382, 434, 2000, 161111, 178812, 178811, 189191, 27, 178811, 189192, 139132, 39232, 12812, 189192, 139132, 12811, 189191, 139131, 39232, 12812, 189191, 139131, 3922, 12812 }
Returns: 1150197
1000000
1000
{1, 900, 1800, 2700, 5000, 5500, 6000, 6500, 7000, 12000, 12999, 13998, 14997, 20000, 21000, 22000, 23000, 30000, 30001, 29999, 30002, 29750, 30250 }
Returns: 9003
1000000000
1001
{1000, 2000, 1500 }
Returns: 1001
1000
21
{20, 30, 10 }
Returns: 21