SuperSubset
SRM 798 · 2021-01-22 · by lazy_fox
SRM 798 · 2021-01-22 · by lazy_fox · Dynamic Programming, Math, Recursion
Problem Statement
Problem Statement
You're given a sequence A of N positive integers and a positive integer Y.
Let S be any subset of the set {0, 1, 2, 3, ..., N-1}. The weight of S, denoted w(S), is defined as the number of subsets {x1, x2, ..., xk} of S such that A[x1] + A[x2] + ... + A[xk] = Y.
For example, suppose A = {1, 10, 40, 70, 71, 100, 111, 200} and Y = 111.
For the set S1 = {0, 1, 2, 3, 4, 5} we have w(S1) = 3 because of the three subsets {0, 1, 5}, {0, 2, 3}, and {2, 4}:
- A[0] + A[1] + A[5] = 1 + 10 + 100 = 111,
- A[0] + A[2] + A[3] = 1 + 40 + 70 = 111, and
- A[2] + A[4] = 40 + 71 = 111.
For the set S2 = {2, 5, 6, 7} we have w(S2) = 1 because the only subset of S2 with the required property is {6}, with A[6] = 111.
Find the sum of w(S) over all subsets of the sequence {0, 1, 2, 3, ..., N-1}. Return this sum modulo 109+7.
Constraints
- A will have between 1 and 3000 elements, both inclusive.
- A[i] will have between 1 and 9999, both inclusive.
- Y will be between 1 and 9999, inclusive.
Examples
0)
{1, 10, 40, 70, 71, 100, 111, 200}
111
Returns: 256
1)
{ 185, 7, 23, 224, 205, 173, 136, 230, 96, 109, 41, 232, 213, 97, 6, 297, 223, 34, 248, 115, 220, 90, 12, 35, 73, 274, 172, 214, 89, 223, 191, 274, 229, 213, 197, 185, 137, 84, 167, 232, 192, 207, 216, 105, 55, 273, 153, 277, 6, 100, 91, 277, 189, 154, 11, 262, 128, 234, 227, 216, 157, 169, 241, 137, 133, 190, 22, 269, 273, 188, 253, 165, 146, 220, 21, 201, 192, 173, 177, 250, 25, 20, 226, 213, 173, 289, 226, 300, 222, 204, 268, 130, 72, 260, 19, 204, 149, 40, 225, 122, 279, 229, 38, 124, 148, 110, 24, 39, 34, 253, 40, 58, 272, 266, 271, 144, 6, 248, 196, 279, 152, 215, 161, 223, 174, 179, 179, 23, 218, 155, 196, 248, 83, 233, 71, 230, 94, 147, 20, 127, 99, 60, 185, 122, 77, 207, 265, 82, 206, 160, 60, 57, 126, 220, 32, 300, 98, 210, 74, 67, 64, 269, 14, 146, 253, 137, 127, 46, 283, 146, 224, 133, 205, 160, 254, 281, 118, 218, 62, 24, 130, 174, 80, 7, 93, 111, 6, 243, 72, 131, 9, 187, 151, 75, 32, 155, 211, 158, 252, 245, 56, 176, 77, 260, 35, 30, 241, 153, 299, 54, 176, 180, 227, 7, 187, 72, 118, 192, 66, 241, 75, 126, 128, 225, 200, 211, 80, 162, 121, 31, 106, 176, 258, 182, 135, 293, 263, 127, 197, 262, 181, 72, 141, 159, 130, 27, 230, 247, 271, 47, 240, 97, 173, 67, 21, 72, 277, 152, 234, 97, 183, 91, 272, 140, 273, 159, 184, 287, 285, 80, 248, 217, 203, 141, 128, 33, 219, 109, 31, 241, 156, 270, 37, 28, 88, 58, 151, 65, 261, 136, 213, 195, 227, 237, 87, 199, 95, 270, 237, 131, 102, 185, 100, 56, 77, 227, 140, 295, 35, 171, 236, 242, 192, 272, 269, 280, 81, 120, 96, 42, 255, 8, 236, 181, 296, 22, 131, 142, 44, 68, 25, 197, 4, 176, 252, 80, 102, 92, 74, 188, 14, 61, 130, 257, 33, 150, 288, 165, 269, 83, 206, 276, 143, 194, 208, 190, 267, 39, 32, 10, 158, 56, 258, 213, 231, 210, 292, 84, 53, 117, 23, 66, 178, 204, 74, 262, 54, 62, 126, 74, 196, 84, 49, 90, 277, 257, 280, 295, 47, 63, 57, 256, 118, 14, 168, 100, 223, 211, 235, 27, 27, 257, 92, 256, 213, 218, 217, 266, 279, 95, 39, 226, 178, 140, 16, 206, 148, 47, 200, 246, 109, 8, 253, 226, 22, 120, 77, 296, 82, 63, 23, 160, 19, 166, 116, 283, 83, 84, 248, 113, 178, 39, 91, 107, 230, 106, 64, 77, 152, 16, 74, 260, 23, 26, 237, 96, 197, 65, 92, 30, 127, 166, 189, 197, 83, 56, 180, 218, 192, 179, 30, 121, 217, 120, 228, 198, 277, 291, 274, 180, 6, 99, 139, 81, 176, 127, 176, 72, 191, 19, 101, 69, 184, 42, 266, 267, 97, 197, 184, 288, 75, 265, 109, 44, 137, 88, 241, 165, 130, 267, 45, 188, 65, 235, 268, 241, 62, 143, 64, 4, 162, 165, 73, 97, 258, 90, 115, 54, 286, 50, 94, 60, 67, 254, 103, 203, 93, 44, 119, 222, 10, 163, 109, 126, 98, 128, 66, 211, 23, 182, 214, 184, 46, 38, 32, 55, 127, 199, 160, 112, 248, 253, 224, 14, 258, 78, 268, 50, 121, 139, 24, 182, 1, 132, 60, 150, 12, 177, 60, 34, 58, 26, 269, 155, 63, 300, 209, 242, 198, 69, 105, 198, 73, 28, 263, 31, 158, 283, 80, 30, 121, 103, 212, 121, 287, 23, 23, 298, 199, 134, 31, 257, 159, 299, 111, 274, 50, 20, 267, 300, 88, 71, 249, 160, 151, 211, 242, 8, 193, 74, 37, 65, 228, 300, 238, 214, 22, 260, 263, 221, 93, 45, 177, 4, 95, 39, 277, 197, 58, 243, 196, 197, 65, 144, 109, 267, 106, 50, 274, 299, 123, 63, 63, 51, 114, 300, 16, 136, 11, 31, 108, 104, 75, 36, 107, 222, 74, 135, 118, 184, 129, 13, 80, 245, 208, 240, 212, 13, 42, 185, 63, 164, 299, 178, 266, 113, 229, 282, 300, 240, 12, 159, 95, 138, 194, 253, 59, 19, 139, 228, 202, 267, 292, 34, 263, 199, 25, 174, 264, 66, 111, 78, 230, 109, 255, 247, 273, 184, 280, 24, 175, 291, 182, 269, 181, 127, 273, 291, 146, 111, 219, 99, 129, 210, 184, 91, 161, 209, 265, 124, 274, 75, 201, 255, 235, 208, 254, 260, 91, 233, 283, 17, 276, 165, 285, 156, 43, 9, 146, 188, 119, 116, 39, 247, 26, 222, 37, 186, 182, 53, 61, 208, 127, 13, 162, 114, 220, 115, 125, 62, 100, 107, 78, 75, 23, 114, 230, 66, 122, 127, 5, 292, 243, 43, 238, 20, 265, 27, 257, 146, 79, 17, 105, 258, 81, 267, 71, 1, 133, 195, 114, 284, 53, 244, 58, 76, 57, 287, 193, 231, 166, 197, 222, 108, 240, 212, 179, 256, 238, 135, 153, 16, 203, 258, 273, 35, 276, 95, 35, 160, 41, 201, 144, 146, 144, 201, 273, 252, 240, 165, 182, 105, 61, 156, 264, 52, 67, 194, 59, 56, 80, 264, 71, 282, 221, 96, 16, 248, 190, 103, 107, 283, 55, 2, 128, 198, 255, 100, 149, 194, 264, 83, 50, 76, 238, 65, 180, 56, 258, 290 }
3754
Returns: 788499765
2)
{ 105, 98, 25, 49, 32, 245, 55, 56, 103, 53, 133, 274, 135, 100, 74, 111, 88, 66, 59, 80, 296, 93, 198, 215, 285, 90, 293, 39, 16, 138, 64, 172, 235, 88, 220, 18, 85, 27, 126, 239, 131, 10, 212, 265, 110, 285, 76, 249, 102, 186, 29, 97, 278, 278, 11, 262, 68, 55, 52, 135, 193, 115, 6, 179, 255, 225, 249, 91, 3, 74, 29, 134, 83, 292, 150, 244, 28, 277, 245, 129, 162, 273, 225, 139, 2, 287, 152, 121, 42, 203, 255, 286, 70, 260, 216, 24, 237, 216, 166, 239, 289, 246, 124, 124, 237, 274, 119, 16, 250, 63, 144, 112, 87, 120, 2, 89, 158, 154, 209, 199, 108, 216, 236, 177, 175, 204, 200, 111, 119, 117, 102, 108, 62, 225, 283, 298, 198, 101, 13, 148, 164, 208, 11, 250, 27, 12, 90, 185, 217, 51, 135, 25, 266, 123, 201, 140, 26, 153, 3, 144, 269, 156, 3, 31, 80, 285, 80, 30, 138, 145, 229, 53, 52, 239, 2, 131, 2, 144, 67, 219, 194, 201, 243, 159, 75, 143, 50, 100, 47, 104, 296, 16, 259, 298, 98, 91, 35, 177, 120, 224, 21, 100, 276, 125, 38, 29, 255, 39, 172, 21, 9, 65, 273, 251, 275, 48, 146, 25, 199, 192, 180, 246, 259, 139, 296, 56, 281, 82, 285, 100, 5, 5, 199, 280, 181, 288, 8, 135, 78, 180, 207, 87, 296, 232, 89, 271, 31, 286, 47, 229, 178, 226, 175, 188, 64, 222, 296, 44, 3, 280, 195, 7, 36, 145, 38, 217, 184, 97, 103, 262, 28, 62, 100, 24, 293, 188, 294, 23, 174, 40, 3, 103, 265, 229, 42, 81, 150, 37, 176, 152, 16, 123, 210, 104, 19, 247, 20, 203, 44, 174, 216, 71, 235, 15, 146, 227, 254, 191, 249, 179, 282, 4, 33, 299, 232, 75, 131, 82, 163, 6, 233, 231, 180, 143, 34, 199, 141, 105, 153, 184, 278, 120, 7, 265, 134, 204, 191, 139, 95, 192, 70, 76, 195, 102, 126, 126, 228, 256, 207, 91, 14, 192, 21, 193, 34, 54, 143, 174, 210, 47, 110, 187, 166, 168, 151, 51, 71, 94, 190, 217, 37, 259, 45, 231, 112, 170, 108, 40, 126, 67, 130, 191, 258, 202, 83, 43, 7, 278, 268, 216, 24, 129, 154, 242, 48, 5, 292, 171, 150, 233, 87, 186, 243, 183, 168, 55, 105, 27, 146, 282, 145, 27, 172, 102, 228, 254, 196, 234, 283, 216, 201, 7, 96, 54, 248, 144, 110, 291, 14, 259, 224, 152, 196, 166, 87, 115, 272, 191, 142, 117, 172, 286, 195, 43, 140, 122 }
6197
Returns: 367071093
3)
{ 173, 115, 16, 237, 111, 22, 103, 29, 198, 242, 32, 225, 90, 276, 191, 195, 235, 46, 159, 86, 68, 195, 38, 203, 31, 143, 49, 72, 23, 41, 196, 247, 208, 212, 184, 70, 285, 38, 98, 182, 31, 182, 106, 120, 209, 49, 67, 143, 146, 225, 280, 213, 171, 70, 167, 253, 264, 215, 24, 287, 8, 272, 285, 215, 235, 220, 284, 219, 258, 134, 152, 40, 15, 258, 160, 223, 58, 278, 118, 255, 202, 97, 167, 124, 166, 86, 77, 182, 52, 100, 220, 59, 123, 204, 25, 57, 124, 9, 27, 81, 142, 179, 172, 208, 188, 31, 182, 297, 60, 299, 251, 13, 96, 169, 137, 13, 254, 213, 246, 6, 64, 165, 116, 187, 69, 141, 295, 192, 201, 74, 24, 94, 252, 195, 1, 191, 278, 182, 187, 37, 233, 189, 50, 28, 57, 238, 92, 63, 150, 90, 120, 265, 254, 287, 151, 22, 127, 198, 213, 79, 23, 288, 172, 274, 183, 172, 216, 160, 106, 102, 248, 38, 42, 297, 117, 150, 234, 260, 212, 135, 49, 83, 100, 3, 70, 2, 76, 248, 251, 41, 27, 273, 28, 198, 298, 210, 122, 213, 121, 279, 66, 121, 16, 107, 117, 184, 257, 103, 195, 220, 289, 244, 55, 88, 298, 176, 142, 73, 123, 92, 165, 149, 117, 193, 99, 114, 154, 272, 79, 27, 250, 144, 147, 17, 3, 15, 200, 11, 169, 146, 282, 158, 89, 36, 297, 138, 211, 138, 263, 34, 282, 127, 234, 98, 19, 84, 211, 173, 55, 289, 251, 56, 185, 97, 72, 187, 111, 23, 249, 280, 169, 230, 137, 9, 266, 133, 147, 228, 23, 109, 261, 4, 235, 247, 101, 6, 82, 11, 230, 137, 52, 180, 192, 236, 276, 16, 174, 138, 38, 122, 117, 258, 51, 5, 267, 68, 190, 113, 296, 212, 273, 8, 215, 259, 254, 67, 264, 36, 129, 193, 224, 180, 124, 167, 167, 99, 182, 92, 237, 272, 213, 105, 229, 16, 110, 195, 83, 299, 59, 78, 262, 31, 86, 176, 290, 91, 294, 5, 178, 122, 250, 153, 54, 73, 20, 220, 172, 201, 12, 160, 172, 276, 264, 101, 291, 125, 47, 126, 123, 106, 203, 84, 188, 40, 11, 229, 183, 4, 234, 112, 178, 183, 265, 231, 255, 284, 202, 178, 236, 265, 89, 160, 241, 105, 12, 283, 229, 110, 108, 104, 215, 63, 239, 103, 102, 250, 83, 36, 5, 16, 148, 234, 250, 164, 216, 257, 199, 118, 186, 134, 82, 275, 45, 74, 131, 108, 57, 59, 218, 164, 214, 132, 226, 153, 286, 80, 154, 121, 167, 210, 136, 66, 144, 138, 229, 59, 94, 127, 228, 31, 13, 10, 57, 109, 135, 187, 217, 191, 298, 134, 107, 263, 17, 84, 115, 55, 215, 268, 175, 82, 230, 62, 199, 73, 251, 128, 183, 96, 6, 111, 127, 18, 172, 183, 179, 6, 122, 95, 249, 171, 280, 55, 133, 296, 190, 248, 102, 105, 267, 28, 238, 248, 142, 136, 72, 92, 15, 255, 188, 21, 117, 14, 90, 40, 248, 268, 45, 121, 114, 45, 291, 93, 151, 124, 141, 41, 123, 242, 197, 141, 22, 186, 89, 163, 73, 160, 254, 88, 166, 141, 160, 282, 206, 249, 21, 206, 269, 118, 26, 82, 214, 69, 175, 65, 192, 15, 157, 66, 8, 105, 206, 29, 290, 294, 191, 62, 206, 197, 149, 71, 89, 8, 105, 47, 9, 125, 252, 277, 294, 277, 58, 208, 97, 284, 24, 288, 298, 180, 105, 58, 284, 11, 86, 25, 56, 29, 86, 261, 277, 287, 84, 65, 46, 188, 111, 106, 64, 114, 134, 58, 143, 244, 17, 239, 227, 40, 227, 277, 271, 83, 34, 6, 93, 171, 82, 201, 199, 219, 213, 227, 205, 296, 292, 3, 235, 154, 160, 299, 268, 294, 108, 110, 237, 124, 48, 163, 215, 26, 139, 237, 109, 172, 294, 253, 95, 75, 153, 293, 293, 66, 272, 250, 113, 263, 252, 48, 168, 111, 46, 135, 156, 153, 296, 92, 28, 96, 255, 294, 173, 145, 230, 33, 69, 223, 286, 163, 49, 190, 207, 41, 7, 178, 290, 172, 192, 293, 219, 60, 156, 16, 246, 11, 220, 294, 103, 247, 89, 109, 292, 13, 253, 273, 46, 73, 247, 83, 235, 295, 272, 194, 35, 31, 71, 77, 202, 263, 69, 120, 74, 224, 187, 71, 287, 106, 64, 141, 104, 152, 249, 95, 217, 253, 67, 262, 78, 13, 44, 12, 7, 67, 257, 93, 149, 28, 169, 50, 42, 290, 221, 167, 265, 107, 237, 251, 212, 1, 91, 15, 204, 91, 161, 120, 96, 227, 133, 173, 291, 176, 236, 49, 295, 193, 142, 143, 220, 62, 193, 13, 51, 165, 179, 16, 272, 167, 18, 235, 167, 161, 2, 123, 251, 162, 294, 98, 141, 127, 270, 183, 54, 206, 232, 48, 150, 125, 191, 121, 186, 135, 133, 289, 299, 63, 56, 22, 229, 73, 257, 148, 233, 10, 22, 236, 171, 15, 33, 63, 193, 55, 246, 247, 12, 177, 294, 161, 53, 236, 281, 290, 122, 165, 278, 173, 227, 85, 194, 207, 158, 202, 106, 142, 211, 127, 77, 134, 194, 162, 196, 86, 216, 141, 32, 279, 69, 78, 139, 173, 65, 119, 163, 187, 35, 192, 59, 261, 277, 4, 219, 186, 206, 25, 27, 168, 203 }
4174
Returns: 254217192
4)
{ 298, 109, 179, 126, 289, 119, 297, 21, 295, 140, 214, 221, 14, 259, 288, 57, 45, 81, 33, 149, 190, 86, 64, 59, 104, 221, 207, 238, 233, 123, 206, 282, 231, 84, 159, 220, 254, 155, 292, 248, 46, 206, 220, 60, 216, 260, 116, 260, 92, 200, 161, 281, 38, 224, 91, 141, 144, 298, 130, 128, 172, 35, 161, 102, 118, 19, 73, 72, 225, 117, 71, 271, 74, 291, 82, 289, 2, 249, 1, 93, 148, 161, 73, 237, 136, 215, 77, 279, 264, 207, 158, 135, 241, 70, 237, 111, 140, 61, 234, 64, 177, 56, 86, 2, 98, 167, 291, 99, 167, 291, 191, 15, 203, 15, 251, 38, 282, 80, 68, 245, 286, 225, 80, 278, 46, 68, 140, 185, 180, 125, 300, 109, 181, 138, 110, 278, 56, 100, 77, 223, 142, 19, 237, 44, 86, 239, 133, 67, 18, 200, 63, 55, 176, 194, 33, 221, 261, 224, 105, 193, 49, 105, 1, 229, 242, 110, 206, 297, 262, 34, 219, 103, 105, 207, 199, 242, 198, 31, 60, 215, 231, 122, 22, 158, 16, 106, 79, 28, 29, 235, 220, 77, 39, 220, 5, 32, 30, 263, 81, 291, 48, 51, 145, 204, 10, 43, 145, 207, 74, 204, 173, 56, 78, 194, 213, 93, 299, 43, 120, 28, 278, 92, 156, 16, 11, 161, 100, 92, 175, 232, 134, 274, 282, 31, 178, 43, 73, 74, 249, 198, 30, 174, 5, 107, 119, 270, 251, 170, 12, 122, 249, 289, 213, 104, 57, 276, 16, 156, 119, 242, 139, 253, 216, 172, 283, 145, 215, 107, 218, 215, 57, 247, 88, 61, 105, 259, 30, 55, 128, 42, 177, 128, 30, 89, 231, 138, 64, 299, 293, 183, 240, 131, 187, 155, 55, 221, 299, 269, 79, 269, 183, 135, 267, 23, 196, 72, 33, 277, 178, 160, 70, 54, 287, 100, 195, 269, 289, 10, 267, 282, 244, 207, 164, 182, 113, 218, 102, 164, 238, 181, 184, 173, 67, 150, 195, 262, 273, 227, 291, 151, 138, 60, 256, 176, 211, 150, 144, 200, 212, 163, 233, 155, 69, 148, 37, 233, 118, 190, 96, 55, 122, 279, 227, 189, 181, 173, 202, 153, 151, 192, 55, 40, 252, 63, 215, 214, 212, 111, 113, 175, 273, 97, 30, 93, 245, 118, 77, 62, 59, 173, 168, 181, 203, 95, 69, 83, 19, 22, 288, 170, 214, 94, 209, 217, 156, 176, 182, 120, 286, 295, 294, 10, 143, 75, 154, 87, 192, 230, 200, 3, 154, 68, 183, 57, 214, 3, 191, 232, 76, 178, 153, 289, 272, 114, 257, 127, 289, 139, 246, 26, 185, 292, 35, 27, 66, 240, 166, 10, 169, 65, 12, 23, 132, 246, 131, 97, 300, 21, 29, 75, 251, 233, 116, 222, 46, 124, 100, 34, 262, 98, 59, 198, 141, 145, 277, 206, 84, 142, 215, 5, 206, 278, 27, 90, 223, 157, 186, 274, 229, 266, 49, 179, 199, 216, 100, 244, 39, 252, 30, 1, 101, 88, 250, 241, 285, 226, 198, 68, 67, 113, 72, 25, 90, 150, 114, 65, 58, 51, 38, 287, 17, 138, 165, 267, 53, 17, 210, 92, 20, 239, 144, 172, 79, 93, 112, 63, 71, 9, 182, 137, 173, 6, 213, 15, 207, 26, 79, 265, 129, 168, 3, 145, 6, 167, 111, 58, 235, 72, 201, 254, 63, 44, 177, 141, 189, 288, 255, 259, 49, 188, 147, 273, 193, 60, 287, 152, 137, 117, 116, 265, 37, 118, 161, 42, 36, 23, 151, 23, 147, 52, 28, 209, 147, 205, 101, 35, 244, 55, 45, 292, 242, 192, 265, 187, 3, 3, 38, 139, 172, 205, 156, 208, 74, 68, 1, 161, 91, 151, 183, 237, 254, 263, 197, 153, 167, 297, 239, 110, 51, 284, 154, 44, 175, 118, 282, 229, 172, 71, 67, 43, 27, 274, 250, 152, 42, 250, 13, 184, 153, 247, 172, 158, 209, 68, 10, 75, 116, 249, 237, 166, 232, 90, 261, 158, 259, 295, 86, 130, 117, 204, 173, 144, 178, 174, 295, 271, 176, 59, 206, 28, 6, 77, 237, 266, 196, 247, 93, 11, 247, 29, 228, 178, 118, 240, 87, 76, 234, 172, 257, 51, 127, 181, 246, 4, 55, 240, 26, 282, 299, 231, 61, 56, 7, 297, 21, 254, 295, 113, 264, 241, 193, 191, 170, 10, 131, 256, 137, 116, 179, 94, 218, 6, 274, 163, 9, 80, 155, 87, 61, 153, 17, 121, 260, 76, 170, 32, 29, 164, 145, 293, 105, 37, 235, 274, 99, 117, 282, 235, 285, 160, 80, 202, 165, 54, 117, 226, 185, 271, 12, 246, 175, 80, 118, 134, 155, 287, 165, 184, 203, 61, 228, 59, 150, 214, 84, 248, 83, 65, 234, 67, 225, 14, 20, 89, 119, 136, 66, 3, 106, 129, 300, 280, 209, 170, 165, 63, 208, 82, 246, 110, 142, 225, 168, 291, 139, 4, 290, 273, 68, 276, 39, 292, 41, 58, 133, 211, 246, 250, 213, 103, 79, 265, 135, 287, 134, 299, 49, 41, 80, 47, 203, 274, 23, 122, 16, 161, 125, 6, 133, 193, 33, 223, 236, 73, 33, 120, 283, 30, 70, 247, 132, 148, 211, 266, 134, 96, 17, 234, 189, 148, 32, 91, 121, 55, 264, 137, 267, 89, 194, 100, 33, 226, 74, 268, 50, 158, 88, 32, 187, 209, 278, 19, 56, 241, 284, 241, 88, 52, 226, 276, 200, 258, 118, 20, 12, 82, 208, 278, 170, 101, 129, 254, 78, 203, 221, 127, 60, 60, 158, 247, 268, 188, 17, 75, 180, 52, 67, 267, 104, 293, 295, 3, 250, 112, 22, 261, 193, 230, 290, 114, 82, 119, 67, 160, 73, 40, 286, 184, 151, 196, 182, 119, 83, 198, 245, 14, 250, 12, 280, 53, 4, 274, 107, 5, 138, 128, 17, 30, 109, 6, 196, 191, 176, 262, 102, 248, 53, 87, 132, 204, 282, 65, 74, 116, 263, 18, 129, 264, 81, 161, 68, 84, 186, 174, 88, 23, 53, 104, 53, 162, 162, 248, 104, 37, 261, 205, 285, 14, 43, 168, 217, 25, 232, 42, 192, 246, 59, 73, 209, 140, 233, 28, 275, 170, 201, 115, 193, 254, 270, 297, 167, 131, 296, 270, 168, 256, 226, 204, 21, 268, 71, 289, 44, 54, 30, 288, 300, 141, 60, 260, 32, 44, 40, 58, 213, 240, 172, 157, 245, 142, 153, 111, 272, 200, 132, 191, 208, 109, 94, 228, 77, 216, 269, 172, 270, 50, 159, 21, 190, 218, 32, 273, 13, 71, 31, 226, 63, 202, 82, 59, 95, 287, 222, 119, 186, 53, 9, 93, 214, 103, 73, 42, 18, 41, 213, 39, 90, 124, 59, 32, 93, 91, 56, 106, 213, 86, 31, 27, 40, 164, 86, 186, 202, 7, 4, 88, 111, 13, 232, 24, 115, 4, 65, 184, 96, 30, 223, 238, 153, 33, 21, 245, 123, 76, 50, 88, 214, 132, 114, 5, 48, 199, 190, 249, 257, 194, 88, 68, 258, 72, 91, 124, 127, 208, 7, 223, 237, 281, 160, 89, 14, 180, 85, 188, 7, 135, 275, 220, 18, 141, 224, 65, 91, 166, 66, 48, 59, 205, 115, 16, 276, 257, 139, 103, 164, 197, 25, 152, 178, 236, 240, 191, 167, 25, 78, 173, 211, 105, 93, 228, 245, 68, 293, 35, 233, 110, 82, 43, 14, 248, 110, 290, 205, 248, 144, 68, 197, 168, 272, 74, 155, 211, 264, 21, 287, 93, 193, 197, 197, 37, 177, 141, 157, 221, 176, 141, 30, 9, 184, 43, 257, 293, 84, 213, 293, 227, 32, 189, 146, 3, 14, 300, 214, 29, 72, 252, 121, 17, 201, 18, 105, 77, 210, 13, 297, 137, 154, 78, 146, 89, 172, 154, 133, 8, 66, 177, 234, 97, 117, 132, 100, 130, 183, 65, 158, 255, 68, 279, 23, 268, 48, 127, 96, 257, 192, 144, 94, 45, 221, 239, 185, 145, 144, 17, 152, 209, 246, 137, 57, 62, 268, 208, 192, 203, 24, 101, 209, 92, 131, 231, 111, 178, 109, 207, 135, 300, 102, 228, 96, 75, 218, 280, 219, 113, 49, 122, 21, 294, 258, 129, 55, 278, 37, 298, 180, 112, 151, 140, 203, 281, 122, 66, 159, 230, 24, 45, 282, 125, 24, 129, 199, 293, 109, 117, 105, 209, 238, 177, 254, 248, 5, 60, 225, 93, 58, 156, 205, 260, 47, 159, 240, 168, 276, 150, 149, 299, 194, 182, 124, 217, 11, 22, 209, 171, 191, 65, 79, 180, 241, 32, 127, 246, 91, 103, 90, 200, 10, 46, 159, 56, 257, 151, 275, 232, 300, 124, 231, 194, 57, 106, 162, 67, 179, 123, 237, 69, 187, 67, 249, 128, 150, 127, 125, 241, 282, 214, 192, 291, 12, 103, 99, 268, 253, 125, 251, 252, 248, 181, 197, 5, 286, 59, 123, 165, 233, 60, 285, 119, 178, 285, 246, 28, 164, 122, 20, 145, 88, 211, 187, 99, 65, 37, 118, 17, 162, 68, 21, 161, 249, 217, 165, 286, 27, 40, 202, 259, 151, 239, 78, 28, 223, 75, 55, 138, 249, 74, 282, 36, 37, 169, 134, 101, 205, 3, 170, 118, 70, 190, 279, 70, 158, 195, 108, 185, 234, 9, 143, 84, 299, 272, 164, 274, 99, 218, 111, 47, 44, 93, 134, 132, 13, 19, 284, 269, 21, 153, 87, 90, 42, 65, 160, 200, 11, 267, 136, 245, 27, 30, 80, 26, 2, 243, 299, 152, 161, 109, 250, 256, 253, 83, 87, 17, 101, 122, 286, 121, 275, 124, 262, 68, 240, 121, 19, 250, 139, 154, 194, 218, 184, 274, 243, 237, 216, 293, 140, 128, 153, 89, 135, 158, 171, 221, 174, 271, 95, 159, 143, 69, 34, 104, 136, 273, 277, 207, 223, 115, 60, 116, 84, 295, 141, 26, 283, 57, 70, 122, 236, 275, 210, 71, 132, 132, 43, 57, 154, 137, 268, 296, 257, 1, 152, 145, 274, 128, 51, 196, 294, 110, 63, 78, 157, 204, 155, 139, 12, 277, 261, 299, 251, 222, 69, 134, 54, 164, 190, 207, 300, 157, 203, 9, 210, 54, 153, 183, 233, 203, 130, 226, 64, 192, 55, 220, 147, 210, 59, 210, 186, 71, 209, 188, 292, 29, 21, 45, 192, 262, 4, 244, 171, 206, 252, 80, 11, 104, 14, 295, 58, 143, 220, 121, 86, 27, 93, 285, 236, 203 }
2610
Returns: 202723905
13)
{1, 2, 3}
3
Returns: 6
w( { } ) = 0 w( { 1 } ) = 0 w( { 2 } ) = 0 w( { 3 } ) = 1 w( { 1, 2 } ) = 1 w( { 1, 3 } ) = 1 w( { 2, 3 } ) = 1 w( { 1, 2, 3 } ) = 2
14)
{1, 1, 1, 1, 1}
4
Returns: 10
Each of the five 4-element sets of indices has weight 1 and the only 5-element set of indices has weight 5.
Submissions are judged against all 46 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SuperSubset with a public method int solve(vector<int> A, int Y) · 46 test cases · 2 s / 256 MB per case