Problem Statement
The night sky over TopCity can be viewed as a two-dimensional plane.
There are N stars in the sky.
Each star is a point, and the points are all distinct.
The coordinates of the stars are (X[0], Y[0]), (X[1], Y[1]), ..., (X[N-1], Y[N-1]).
Mr. X, a photographer, is going to make a collection of pictures of the sky.
Each picture he is going to take will be a rectangle with sides are parallel to the X-axis and Y-axis of the plane of the night sky.
In other words, he will choose four real numbers XL, XR, YL, YR such that XL < XR and YL < YR, and he will take a picture containing all points (x, y) such that XL ⦠x ⦠XR and YL ⦠y ⦠YR.
Each star has a light of a slightly different color. Therefore, it is possible to tell one star from another in a picture.
Two pictures are considered different if they contain a different combination of stars.
In other words, two pictures are different if there is a star that is in one of them but not in the other.
(If two pictures have different dimensions but contain the same subset of stars, they are considered identical.)
Mr. X wants to make a collection of different pictures.
Additionally, he does not want the empty picture. Each picture in his collection must contain at least one star.
Calculate and return the largest possible number of pictures in the collection.
Definition
- Class:
- StarsInTheSky
- Method:
- countPictures
- Parameters:
- int, int[], int[]
- Returns:
- int
- Method signature:
- int countPictures(int N, int[] X, int[] Y)
- (be sure your method is public)
Constraints
- N will be between 1 and 15.
- The length of arrays X and Y will be exactly N each.
- All of X[0], X[1], ..., X[N-1] will be between 0 and 1,000,000,000 (1 billion).
- All of Y[0], Y[1], ..., Y[N-1] will be between 0 and 1,000,000,000 (1 billion).
- The coordinates of stars, (X[0], Y[0]), (X[1], Y[1]), ..., (X[N-1], Y[N-1]), will be all different.
Examples
4
{1, 2, 3, 4}
{1, 1, 1, 1}
Returns: 10
In this example, Mr.X can add 10 kinds of pictures of sky of TopCity, as follows for examples: When he set XL = 0.5, XR = 1.5, YL = 0.5, YR = 1.5, he can take a picture which contains 1st star. When he set XL = 1.5, XR = 2.5, YL = 0.5, YR = 1.5, he can take a picture which contains 2nd star. When he set XL = 2.5, XR = 3.5, YL = 0.5, YR = 1.5, he can take a picture which contains 3rd star. When he set XL = 3.5, XR = 4.5, YL = 0.5, YR = 1.5, he can take a picture which contains 4th star. When he set XL = 1, XR = 2, YL = 0, YR = 2, he can take a picture which contains 1st and 2nd star. When he set XL = 2, XR = 3, YL = 0, YR = 2, he can take a picture which contains 2nd and 3rd star. When he set XL = 3, XR = 4, YL = 0, YR = 2, he can take a picture which contains 3rd and 4th star. When he set XL = 1, XR = 3, YL = 0, YR = 2, he can take a picture which contains 1st, 2nd, and 3rd star. When he set XL = 2, XR = 4, YL = 0, YR = 2, he can take a picture which contains 2nd, 3rd, and 4th star. When he set XL = -10, XR = 10, YL = -10, YR = 10, he can take a picture which contains 1st, 2nd, 3rd, and 4th star. In contrast, for example, it is impossible for him to take a picture of which contains 1st and 4th star only. Also, note that he will not add a picture which contains no star into his collection.
4
{100, 200, 200, 100}
{100, 100, 200, 200}
Returns: 9
In this example, Mr.X can add 9 kinds of pictures of sky of TopCity, as follows for examples: When he set XL = 50, XR = 150, YL = 50, YR = 150, he can take a picture which contains 1st star. When he set XL = 150, XR = 250, YL = 50, YR = 150, he can take a picture which contains 2nd star. When he set XL = 150, XR = 250, YL = 150, YR = 250, he can take a picture which contains 3rd star. When he set XL = 50, XR = 150, YL = 150, YR = 250, he can take a picture which contains 4th star. When he set XL = 0, XR = 300, YL = 50, YR = 150, he can take a picture which contains 1st and 2nd star. When he set XL = 0, XR = 300, YL = 50, YR = 150, he can take a picture which contains 3rd and 4th star. When he set XL = 50, XR = 150, YL = 0, YR = 300, he can take a picture which contains 1st and 4th star. When he set XL = 150, XR = 250, YL = 0, YR = 300, he can take a picture which contains 1st and 4th star. When he set XL = 0, XR = 300, YL = 0, YR = 300, he can take a picture which contains 1st, 2nd, 3rd, and 4th star.
3
{10000, 11000, 12000}
{52000, 50000, 51000}
Returns: 7
Since N = 3, there are 2^3 - 1 = 7 possible combinations of stars in a picture. In this example, Mr.X can take pictures for all of them, so the answer is 7.
7
{0, 6, 2, 3, 4, 0, 6}
{0, 0, 4, 5, 6, 10, 10}
Returns: 45
In this example, the stars in a sky from TopCity is arranged alike "Seven Stars of Orion".
15
{3, 141592653, 589793238, 462643383, 279502884, 197169399, 375105820, 974944592, 307816406, 286208998, 628034825, 342117067, 982148086, 513282306, 647093844}
{1, 414213562, 373095048, 801688724, 209698078, 569671875, 376948073, 176679737, 990732478, 462107038, 850387534, 327641572, 735013846, 230912297, 24924836}
Returns: 613
Please note that, in this problem, N is at most 15 for any input.
1
{0}
{0}
Returns: 1
2
{0, 0}
{0, 1}
Returns: 3
2
{1, 0}
{0, 0}
Returns: 3
2
{1, 0}
{1, 0}
Returns: 3
2
{0, 1}
{1, 0}
Returns: 3
3
{0, 0, 0}
{1, 0, 2}
Returns: 6
3
{2, 1, 0}
{0, 0, 0}
Returns: 6
3
{0, 0, 1}
{1, 0, 0}
Returns: 6
3
{0, 1, 0}
{1, 1, 0}
Returns: 6
3
{1, 1, 0}
{0, 1, 0}
Returns: 6
3
{1, 0, 1}
{0, 1, 1}
Returns: 6
3
{0, 0, 1}
{1, 0, 2}
Returns: 6
3
{1, 0, 0}
{1, 2, 0}
Returns: 7
3
{0, 1, 1}
{0, 2, 1}
Returns: 6
3
{0, 0, 1}
{2, 1, 0}
Returns: 6
3
{0, 1, 1}
{1, 2, 0}
Returns: 7
3
{1, 1, 0}
{0, 1, 2}
Returns: 6
3
{0, 2, 1}
{0, 1, 0}
Returns: 6
3
{2, 1, 0}
{0, 1, 0}
Returns: 7
3
{1, 0, 2}
{1, 0, 1}
Returns: 6
3
{2, 0, 1}
{0, 1, 0}
Returns: 6
3
{2, 1, 0}
{1, 0, 1}
Returns: 7
3
{0, 2, 1}
{1, 0, 1}
Returns: 6
3
{2, 1, 0}
{2, 1, 0}
Returns: 6
3
{1, 0, 2}
{2, 0, 1}
Returns: 7
3
{1, 2, 0}
{0, 2, 1}
Returns: 7
3
{0, 1, 2}
{1, 2, 0}
Returns: 7
3
{2, 0, 1}
{1, 2, 0}
Returns: 7
3
{0, 2, 1}
{2, 0, 1}
Returns: 6
15
{6, 5, 4, 3, 2, 1, 0, 7, 8, 9, 10, 11, 12, 13, 14}
{0, 1, 2, 3, 4, 5, 6, 14, 13, 12, 11, 10, 9, 8, 7}
Returns: 1072
15
{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}
{0, 100000000, 200000000, 300000000, 400000000, 500000000, 600000000, 700000000, 800000000, 900000000, 1000000000, 1001, 869120, 19980412, 220284}
Returns: 120
15
{0, 100000000, 200000000, 300000000, 400000000, 500000000, 600000000, 700000000, 800000000, 900000000, 1000000000, 787788, 2563125, 13333, 1998299}
{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}
Returns: 120
4
{433877691, 405974365, 405974365, 433877691}
{373822177, 38186484, 373822177, 38186484}
Returns: 9
4
{966481945, 754969147, 754969147, 273592919}
{332470216, 530155787, 332470216, 332470216}
Returns: 11
6
{665781247, 773955727, 773955727, 665781247, 285312078, 285312078}
{824304401, 63410273, 824304401, 124329115, 63410273, 124329115}
Returns: 21
8
{530910459, 530910459, 514819630, 391302745, 391302745, 514819630, 391302745, 514819630}
{48078050, 368220615, 333906826, 333906826, 48078050, 48078050, 368220615, 368220615}
Returns: 31
9
{626671843, 363270029, 626671843, 522516319, 363270029, 522516319, 363270029, 522516319, 626671843}
{435584044, 435584044, 171622687, 735439684, 735439684, 171622687, 171622687, 435584044, 735439684}
Returns: 36
6
{959208967, 959208967, 959208967, 527746033, 527746033, 527746033}
{675104509, 458556746, 917004619, 458556746, 393050866, 891282281}
Returns: 23
11
{557990495, 266775265, 708201909, 557990495, 266775265, 266775265, 557990495, 266775265, 708201909, 557990495, 708201909}
{360196271, 654924585, 562649858, 654924585, 360196271, 901482049, 562649858, 562649858, 519686958, 901482049, 360196271}
Returns: 58
13
{633116620, 387120108, 726341023, 633116620, 387120108, 633116620, 387120108, 387120108, 726341023, 726341023, 726341023, 633116620, 387120108}
{754740627, 150465019, 754740627, 150465019, 623635966, 623635966, 340815523, 754740627, 150465019, 340815523, 623635966, 340815523, 838159045}
Returns: 73
15
{357093400, 357093400, 254697247, 272359525, 254697247, 357093400, 272359525, 272359525, 357093400, 254697247, 254697247, 272359525, 272359525, 357093400, 254697247}
{227950492, 97093464, 513711271, 251410688, 227950492, 251410688, 97093464, 542117384, 542117384, 542117384, 97093464, 227950492, 513711271, 513711271, 251410688}
Returns: 90
11
{869414564, 874763822, 869414564, 874763822, 874763822, 869414564, 869414564, 869414564, 869414564, 869414564, 874763822}
{896227902, 896227902, 322625059, 322625059, 955647639, 943338426, 116554806, 677905267, 955647639, 13161044, 116554806}
Returns: 63
12
{86743145, 436956338, 86743145, 86743145, 86743145, 436956338, 436956338, 436956338, 86743145, 436956338, 86743145, 436956338}
{342092372, 342092372, 518454762, 386389023, 578088105, 518454762, 394589670, 59715441, 394589670, 386389023, 765289080, 578088105}
Returns: 68
13
{542804927, 542804927, 879791729, 879791729, 879791729, 542804927, 879791729, 542804927, 879791729, 542804927, 879791729, 542804927, 542804927}
{627904089, 210307559, 833620486, 723890937, 627904089, 136733800, 136733800, 723890937, 210307559, 97817339, 93962458, 93962458, 833620486}
Returns: 76
14
{564359667, 741115249, 564359667, 741115249, 741115249, 564359667, 741115249, 741115249, 741115249, 564359667, 564359667, 741115249, 564359667, 564359667}
{240040326, 14872909, 112783110, 240040326, 112783110, 909737969, 762904282, 169985294, 495412280, 14872909, 169985294, 909737969, 762904282, 495412280}
Returns: 84
8
{722301904, 361034909, 127767529, 159684959, 175124398, 159684959, 385166340, 385166340}
{69832436, 536305755, 69832436, 536305755, 536305755, 69832436, 69832436, 536305755}
Returns: 36
10
{914114680, 365399374, 464566237, 252186892, 328643731, 787098210, 633903689, 822185416, 818817490, 324063309}
{611739556, 824855756, 824855756, 824855756, 824855756, 611739556, 824855756, 824855756, 824855756, 824855756}
Returns: 68
12
{505520601, 227850799, 222814335, 750665542, 569388100, 282330411, 536707588, 613262109, 318532945, 51713144, 228940346, 304139640}
{391285689, 173014191, 391285689, 391285689, 173014191, 173014191, 173014191, 391285689, 173014191, 391285689, 173014191, 391285689}
Returns: 102
15
{761956280, 71022089, 522913613, 859576551, 582095802, 466331198, 986965208, 941287781, 466331198, 460703002, 247987888, 859576551, 306871475, 645831241, 379812288}
{699535543, 329253851, 699535543, 699535543, 699535543, 329253851, 329253851, 699535543, 699535543, 329253851, 699535543, 329253851, 329253851, 329253851, 699535543}
Returns: 143
9
{847757535, 493202076, 518831905, 518831905, 518831905, 875305497, 493202076, 518831905, 493202076}
{200136011, 560184677, 768562844, 951714562, 394696942, 851612919, 781430836, 871371837, 819968938}
Returns: 77
11
{956052731, 242632734, 824748987, 956052731, 242632734, 956052731, 956052731, 311337004, 824748987, 311337004, 824748987}
{19181556, 166217307, 615221797, 661640614, 618719126, 447202651, 830783308, 817749563, 802229446, 686811214, 349608250}
Returns: 135
13
{504547591, 835263194, 877639831, 835263194, 877639831, 808437960, 808437960, 808437960, 835263194, 835263194, 808437960, 808437960, 504547591}
{691055851, 108920646, 140727024, 600817816, 375887105, 188893909, 570612733, 56856337, 161284420, 712181494, 958427259, 556522067, 374659938}
Returns: 223
15
{895253789, 797118673, 87866784, 178166572, 797118673, 895253789, 895253789, 895253789, 797118673, 895253789, 87866784, 895253789, 178166572, 87866784, 87866784}
{244925256, 962884293, 418003108, 246643492, 870095599, 594407032, 682386003, 538749356, 538749356, 253025230, 868887624, 978800442, 380369699, 637182606, 51536511}
Returns: 219
14
{125517300, 252336745, 473623001, 112496724, 161590613, 245094306, 225170077, 225170077, 290903865, 809985667, 108896592, 108896592, 290903865, 227421355}
{654185554, 396763431, 977394391, 125954936, 396763431, 654185554, 786256457, 213136547, 227062752, 227062752, 125954936, 875334973, 654185554, 227062752}
Returns: 255
14
{192248524, 657624738, 167685338, 592558429, 215698299, 576904320, 757121813, 770409675, 770409675, 981033780, 210374556, 770409675, 167685338, 210374556}
{847334811, 629976488, 483170264, 402598694, 164296097, 899988466, 629976488, 164296097, 847334811, 899988466, 277355839, 610626832, 621275687, 899988466}
Returns: 262
15
{756252832, 601487903, 965044078, 738787678, 971030456, 474854532, 474854532, 364762630, 364762630, 738787678, 709020473, 170272627, 364762630, 971030456, 601487903}
{88031079, 738178319, 267426566, 738178319, 156527651, 987627309, 474643762, 615357797, 156527651, 154769361, 88031079, 267426566, 474643762, 583703602, 171702680}
Returns: 362
15
{306411942, 620527704, 997410725, 39191104, 39191104, 39191104, 504625463, 880510003, 224886658, 620527704, 538933564, 173932553, 620527704, 224886658, 306411942}
{129919306, 982598630, 607310380, 171854206, 510896516, 751956889, 41653722, 41653722, 510639011, 510896516, 607310380, 383474663, 562757565, 171854206, 982598630}
Returns: 302
14
{608973281, 5396747, 669408861, 87943367, 87943367, 649298733, 408603793, 246721270, 596860999, 521800554, 214020439, 206590423, 954476433, 543629901}
{464193868, 115163070, 180894731, 115770176, 989617623, 652373724, 250345213, 308716898, 130717294, 115163070, 115770176, 372518074, 962407902, 115770176}
Returns: 318
14
{292800871, 307759280, 215770061, 925909552, 306296617, 74231222, 700682562, 419457989, 715532654, 292800871, 591001835, 418829992, 63129404, 591001835}
{485617754, 883063423, 840751467, 672140002, 796159139, 94673841, 966663698, 371288260, 168212518, 652110388, 747586639, 693672001, 957751701, 629033646}
Returns: 361
15
{500867546, 236537774, 30398840, 284012441, 97768196, 698804123, 298726002, 30398840, 733852473, 398720046, 392788242, 897416979, 809233638, 466543393, 576756273}
{814170969, 218973630, 375030947, 934072659, 888604126, 401236363, 317389115, 999757694, 375030947, 620788813, 994089794, 387052406, 24156630, 943468732, 514214248}
Returns: 560
15
{890146788, 214385159, 551700255, 624691300, 915307164, 499856536, 475564845, 915307164, 133673665, 854239363, 915307164, 854239363, 854239363, 66067554, 214385159}
{268700727, 338125932, 117572411, 268700727, 136002086, 454157145, 853199305, 140873103, 553490556, 866152364, 181931213, 338125932, 11907819, 268700727, 454157145}
Returns: 352
14
{598942824, 275711747, 869969669, 190954742, 785653390, 759091835, 268592692, 127592065, 567447104, 11195310, 658386752, 363207157, 598942824, 759091835}
{886402321, 61037511, 863716989, 681895130, 138094388, 126555634, 629545479, 493214875, 42627518, 757416365, 329159455, 542101488, 689189076, 762975499}
Returns: 502
14
{555369229, 805555113, 775159981, 746885461, 399669134, 532574804, 258212178, 225090911, 972888362, 742193790, 522601546, 313094618, 461294285, 411085629}
{562157466, 52900598, 785125495, 493336123, 347533710, 189376358, 52900598, 694461249, 736410215, 507042059, 486249157, 998683376, 893349946, 500433250}
Returns: 471
15
{794081192, 733689798, 868715843, 410364411, 733689798, 773133773, 855123570, 966930048, 509396077, 232827536, 938209622, 45576735, 239353539, 571588410, 774543198}
{768487693, 294466934, 588403346, 169589805, 618274583, 768487693, 540411377, 376084374, 859357801, 124021309, 381149415, 376084374, 740219494, 471015787, 849455866}
Returns: 561
15
{950070769, 37136417, 142652855, 950070769, 474282954, 170548861, 984661459, 713296382, 814919691, 338558657, 680522885, 89748808, 680522885, 427833419, 568734916}
{313935118, 624530186, 233841996, 59162412, 712252871, 686816774, 975589267, 118210051, 904854097, 813110353, 282500411, 769487539, 456464905, 167852272, 813110353}
Returns: 451
4
{1, 2, 3, 4 }
{1, 1, 1, 1 }
Returns: 10
4
{1, 1, 2, 2 }
{1, 2, 1, 2 }
Returns: 9
4
{0, 0, 1, 1 }
{0, 3, 1, 2 }
Returns: 11