TellBagsApart
TCO21 Round 3 · 2021-04-13 · by misof
Problem Statement
Lucy has two bags. The bags have numbers 1 and 2 on them. One of them (but we do not know which one) contains four white and four black marbles, the other contains twenty white and twenty black marbles. The bags are opaque, so we cannot see what's inside.
We would like to determine which bag is which.
Consider the following experiment:
- We choose a bag.
- Lucy draws a random marble from the chosen bag.
- She shows us the marble.
- She returns the marble back into the bag.
It should be clear that in terms of our goal the above experiment is useless: even if we are allowed to repeat it multiple times, we cannot use it to learn anything useful about the two bags.
Perhaps surprisingly, the situation changes completely once we modify the experiment slightly:
- We choose a bag.
- Lucy draws two random marbles from the chosen bag, one after another.
- She shows us the two marbles in the order in which she drew them.
- She returns both marbles back into the bag.
We have performed the two-marble version of the experiment exactly 2500 times. For each round we recorded the number of the bag we chose (1 or 2) and the colors of the two marbles Lucy drew (WW, BW, WB, or BB).
Note that while the marbles were always drawn at random (with all random choices being uniform and mutually independent), the bag from which Lucy drew in each round was chosen by us, and not necessarily uniformly at random. You do not know anything about how we selected the bag from which Lucy should draw in each round. In particular, you should not expect that each bag was chosen approximately 50 percent of the time.
There are eight possible records for a single experiment: 1WW, 1BW, 1WB, 1BB, 2WW, 2BW, 2WB, 2BB. As different draws are mutually independent and their order does not matter, we just kept a count for each record.
You are given these counts: eight integers that correspond to the eight records in the order given above. Given this information, determine the number of the bag that contains the smaller number of marbles.
-----------------------------------
Each test case contains N independent queries. In the examples we have N = 4 and N = 20, in each other test case N = 100. In each query you are given the eight counts as described above, and your task is to determine which bag has the smaller number of marbles.
The input is given as the
Return a
Your answer for a test case will be accepted if and only if its accuracy is at least 94 percent.
(I.e., you need to get Example 0 completely correct, you can make up to 1 mistake in Example 1, and in each other test case you can make up to 6 mistakes.)
Notes
- All tests for this problem were prepared before the round by actually simulating the process from the problem statement. More precisely, we prepared the generator, ran it exactly once and used the tests it generated.
- Custom challenges for this problem will not be allowed, as we cannot guarantee that you generated them in a fair way.
- During the challenge phase you can only use the example tests as possible challenge inputs.
- There are exactly 20 test cases. (This includes the two examples.)
- Under these conditions, the reference solution would pass system tests with probability significantly over 99.99 percent.
Constraints
- In the test case in Example 0, records contains 4*8 elements.
- In the test case in Example 1, records contains 20*8 elements.
- In each other test case, records contains 100*8 elements.
- All elements of records are non-negative.
- If we break records into groups of 8, the sum of each such group is exactly 2500.
- Each query in records was generated as described in the problem statement.
{262, 371, 340, 277, 303, 304, 333, 310,
296, 326, 370, 275, 312, 329, 284, 308,
265, 402, 372, 279, 279, 317, 307, 279,
112, 160, 121, 102, 497, 497, 505, 506}
Returns: "1111"
When generating this test case, we used the following strategies to select the bag for Lucy: Query 0: we first chose bag 1 exactly 1250 times and then bag 2 exactly 1250 times. (Note that 262+371+340+277 = 303+304+333+310 = 1250.) Query 1: in each round of the experiment we chose the bag at random. Query 2: we started by choosing bag 1, and each time Lucy drew two black marbles, we flipped to the other bag. Query 3: we were choosing the bags in the cyclic order 1,2,2,2,2. The return value is correct: in each query bag 1 was the one with fewer marbles.
{401, 405, 345, 358, 203, 295, 284, 209,
348, 380, 396, 361, 221, 274, 307, 213,
361, 347, 410, 347, 246, 287, 298, 204,
301, 389, 412, 304, 253, 289, 280, 272,
303, 450, 388, 290, 270, 286, 246, 267,
328, 354, 326, 362, 254, 305, 309, 262,
290, 362, 391, 296, 285, 282, 313, 281,
338, 335, 345, 335, 220, 338, 335, 254,
309, 356, 348, 323, 239, 344, 343, 238,
264, 368, 365, 258, 301, 312, 328, 304,
256, 368, 343, 295, 296, 323, 319, 300,
275, 318, 383, 258, 320, 340, 306, 300,
275, 301, 323, 309, 273, 372, 366, 281,
263, 331, 290, 309, 277, 358, 395, 277,
261, 310, 291, 259, 301, 407, 379, 292,
256, 318, 297, 257, 325, 358, 366, 323,
284, 287, 274, 286, 294, 406, 358, 311,
266, 271, 282, 256, 282, 395, 429, 319,
270, 274, 278, 268, 308, 396, 404, 302,
203, 283, 299, 229, 368, 401, 377, 340}
Returns: "22211212211122212221"
For each i from 0 to 19, inclusive, when generating query i we used the strategy that in each round bag 1 was chosen with probability (60-i) percent. The return value is correct for each of the 20 queries.
{42, 52, 64, 40, 605, 572, 576, 549, 556, 581, 616, 546, 46, 61, 56, 38, 214, 290, 281, 207, 380, 352, 401, 375, 288, 366, 391, 291, 269, 301, 304, 290, 310, 457, 401, 307, 263, 277, 240, 245, 253, 315, 341, 271, 308, 339, 320, 353, 225, 230, 226, 213, 330, 471, 463, 342, 128, 200, 153, 130, 468, 453, 501, 467, 309, 407, 424, 301, 279, 247, 286, 247, 346, 467, 468, 337, 203, 229, 237, 213, 117, 139, 113, 122, 400, 568, 591, 450, 69, 116, 111, 74, 526, 546, 547, 511, 565, 605, 647, 590, 19, 32, 19, 23, 28, 45, 63, 44, 550, 614, 607, 549, 313, 486, 452, 329, 230, 232, 239, 219, 352, 428, 401, 413, 198, 250, 286, 172, 633, 607, 647, 613, 0, 0, 0, 0, 567, 609, 599, 585, 26, 36, 47, 31, 178, 179, 183, 175, 380, 512, 503, 390, 157, 214, 235, 161, 425, 433, 450, 425, 420, 525, 562, 385, 156, 145, 148, 159, 286, 316, 322, 251, 331, 343, 350, 301, 262, 402, 370, 283, 291, 296, 320, 276, 388, 467, 511, 360, 197, 190, 225, 162, 367, 533, 532, 382, 173, 174, 176, 163, 221, 299, 312, 247, 327, 380, 329, 385, 7, 7, 3, 4, 613, 632, 616, 618, 178, 247, 241, 201, 417, 395, 440, 381, 94, 93, 106, 75, 471, 612, 597, 452, 76, 82, 85, 72, 495, 564, 593, 533, 0, 0, 0, 0, 524, 747, 717, 512, 401, 561, 584, 395, 134, 155, 152, 118, 29, 27, 31, 40, 520, 673, 682, 498, 180, 220, 200, 197, 395, 494, 478, 336, 165, 241, 243, 168, 389, 445, 430, 419, 226, 304, 287, 224, 358, 374, 374, 353, 470, 642, 647, 483, 63, 60, 66, 69, 52, 66, 65, 53, 532, 602, 565, 565, 388, 399, 361, 366, 193, 299, 289, 205, 372, 372, 419, 377, 197, 270, 274, 219, 261, 351, 343, 273, 297, 317, 329, 329, 573, 587, 605, 522, 44, 70, 53, 46, 426, 462, 411, 481, 165, 197, 225, 133, 530, 688, 713, 515, 9, 15, 10, 20, 25, 26, 26, 28, 515, 699, 700, 481, 251, 356, 334, 271, 292, 346, 308, 342, 216, 162, 217, 181, 364, 507, 472, 381, 367, 507, 505, 400, 211, 159, 188, 163, 525, 642, 672, 485, 42, 49, 44, 41, 397, 536, 583, 401, 146, 165, 138, 134, 470, 604, 624, 442, 89, 86, 85, 100, 170, 229, 225, 178, 450, 444, 439, 365, 175, 169, 193, 165, 374, 506, 508, 410, 319, 492, 395, 342, 248, 257, 243, 204, 387, 379, 340, 376, 209, 303, 293, 213, 603, 672, 629, 596, 0, 0, 0, 0, 33, 34, 44, 28, 508, 689, 674, 490, 376, 534, 508, 380, 164, 161, 203, 174, 251, 326, 332, 239, 358, 343, 330, 321, 34, 58, 38, 57, 519, 607, 684, 503, 577, 559, 601, 579, 29, 61, 48, 46, 502, 728, 695, 575, 0, 0, 0, 0, 263, 300, 292, 253, 328, 348, 363, 353, 167, 151, 146, 148, 411, 584, 496, 397, 31, 37, 36, 36, 577, 563, 626, 594, 118, 142, 141, 129, 422, 555, 579, 414, 185, 198, 208, 205, 362, 489, 491, 362, 479, 510, 482, 385, 114, 203, 193, 134, 583, 612, 631, 598, 20, 14, 22, 20, 354, 404, 441, 401, 205, 250, 247, 198, 294, 438, 431, 299, 249, 281, 265, 243, 187, 202, 200, 178, 375, 498, 507, 353, 289, 409, 434, 290, 265, 284, 274, 255, 332, 412, 442, 265, 262, 263, 288, 236, 185, 218, 231, 148, 431, 453, 444, 390, 167, 160, 160, 139, 383, 547, 550, 394, 31, 29, 34, 31, 513, 696, 665, 501, 556, 557, 577, 517, 56, 107, 64, 66, 389, 389, 397, 359, 199, 261, 288, 218, 214, 316, 308, 260, 324, 337, 370, 371, 246, 380, 349, 277, 296, 336, 299, 317, 357, 394, 428, 372, 197, 292, 264, 196, 228, 238, 227, 231, 319, 464, 439, 354, 365, 456, 507, 327, 203, 219, 222, 201, 239, 293, 321, 243, 320, 349, 379, 356, 496, 675, 687, 494, 44, 38, 38, 28, 146, 148, 129, 133, 400, 576, 553, 415, 69, 91, 103, 96, 544, 537, 561, 499, 287, 362, 365, 282, 290, 341, 284, 289, 60, 82, 71, 71, 479, 644, 612, 481, 362, 407, 391, 392, 228, 265, 249, 206, 212, 274, 292, 218, 397, 371, 352, 384, 7, 15, 16, 9, 505, 719, 696, 533, 251, 249, 252, 199, 332, 438, 438, 341, 460, 608, 615, 468, 77, 94, 92, 86, 485, 637, 680, 476, 60, 56, 55, 51, 0, 0, 0, 0, 576, 699, 692, 533, 112, 126, 120, 115, 433, 576, 577, 441, 593, 645, 646, 584, 5, 12, 9, 6, 457, 665, 658, 463, 52, 74, 71, 60}
Returns: "1211112111212112222111111111212122111122122121211111212221122112122222121112222112211121122122112221"
{595, 587, 624, 551, 34, 36, 42, 31, 530, 549, 605, 581, 47, 63, 68, 57, 506, 682, 675, 486, 33, 36, 47, 35, 606, 629, 608, 549, 29, 33, 29, 17, 502, 710, 772, 516, 0, 0, 0, 0, 536, 597, 601, 557, 41, 68, 47, 53, 569, 627, 668, 570, 15, 22, 14, 15, 489, 653, 643, 500, 57, 44, 58, 56, 614, 609, 614, 578, 26, 14, 28, 17, 484, 641, 666, 539, 35, 51, 39, 45, 558, 600, 559, 611, 34, 51, 58, 29, 636, 604, 627, 614, 7, 6, 1, 5, 609, 562, 570, 552, 51, 65, 53, 38, 575, 597, 643, 588, 24, 28, 30, 15, 580, 612, 593, 585, 24, 30, 39, 37, 582, 687, 602, 576, 15, 15, 8, 15, 521, 686, 665, 477, 35, 32, 40, 44, 589, 577, 544, 561, 47, 55, 73, 54, 533, 653, 674, 471, 37, 44, 47, 41, 580, 568, 639, 560, 35, 41, 43, 34, 603, 624, 610, 562, 20, 29, 27, 25, 609, 647, 615, 607, 5, 4, 4, 9, 593, 621, 633, 627, 6, 10, 4, 6, 528, 648, 658, 541, 36, 30, 29, 30, 596, 587, 640, 528, 31, 45, 41, 32, 526, 683, 672, 521, 27, 27, 22, 22, 558, 639, 688, 615, 0, 0, 0, 0, 571, 591, 584, 604, 30, 39, 45, 36, 589, 630, 683, 571, 6, 7, 8, 6, 493, 657, 643, 498, 48, 53, 58, 50, 469, 692, 692, 476, 44, 47, 33, 47, 514, 690, 718, 528, 12, 18, 11, 9, 569, 609, 626, 617, 21, 15, 23, 20, 555, 690, 677, 496, 18, 19, 24, 21, 498, 677, 687, 512, 30, 36, 29, 31, 534, 698, 703, 538, 5, 7, 9, 6, 549, 567, 586, 584, 46, 61, 56, 51, 634, 643, 619, 604, 0, 0, 0, 0, 528, 653, 643, 504, 34, 43, 51, 44, 487, 630, 707, 457, 50, 46, 55, 68, 474, 635, 675, 481, 48, 73, 52, 62, 554, 587, 575, 562, 50, 63, 58, 51, 569, 642, 619, 583, 14, 20, 36, 17, 488, 628, 688, 495, 51, 49, 54, 47, 519, 665, 657, 492, 32, 52, 42, 41, 537, 731, 738, 494, 0, 0, 0, 0, 502, 682, 692, 551, 18, 17, 18, 20, 483, 640, 666, 544, 36, 33, 40, 58, 526, 680, 620, 476, 48, 53, 54, 43, 572, 619, 564, 528, 55, 60, 58, 44, 503, 617, 695, 493, 39, 54, 56, 43, 563, 686, 672, 532, 19, 9, 4, 15, 589, 649, 599, 640, 10, 4, 4, 5, 556, 653, 619, 580, 21, 25, 19, 27, 499, 695, 664, 534, 22, 28, 32, 26, 595, 568, 610, 611, 25, 31, 32, 28, 607, 649, 645, 567, 5, 9, 11, 7, 504, 665, 657, 463, 49, 51, 56, 55, 601, 604, 596, 603, 20, 33, 25, 18, 579, 661, 607, 561, 17, 37, 24, 14, 601, 581, 645, 583, 20, 23, 27, 20, 534, 582, 621, 566, 44, 45, 59, 49, 531, 679, 706, 502, 20, 27, 17, 18, 504, 641, 683, 494, 49, 38, 38, 53, 517, 634, 676, 502, 37, 42, 46, 46, 488, 658, 664, 504, 43, 44, 51, 48, 525, 748, 704, 493, 9, 9, 5, 7, 533, 617, 664, 483, 52, 49, 51, 51, 581, 659, 611, 632, 9, 1, 6, 1, 538, 601, 579, 572, 47, 73, 46, 44, 643, 650, 620, 587, 0, 0, 0, 0, 547, 565, 630, 576, 35, 53, 52, 42, 495, 622, 693, 490, 48, 48, 52, 52, 544, 593, 616, 522, 52, 56, 70, 47, 524, 610, 602, 537, 37, 75, 54, 61, 499, 700, 689, 540, 23, 20, 17, 12, 503, 688, 718, 532, 19, 17, 14, 9, 502, 697, 667, 509, 28, 32, 34, 31, 598, 641, 634, 590, 6, 8, 12, 11, 550, 722, 687, 524, 8, 4, 4, 1, 558, 595, 556, 562, 46, 66, 61, 56, 594, 628, 624, 596, 16, 11, 18, 13, 479, 664, 685, 505, 43, 37, 44, 43, 527, 639, 557, 608, 43, 51, 31, 44, 613, 616, 599, 536, 31, 39, 36, 30, 596, 641, 672, 591, 0, 0, 0, 0, 498, 688, 613, 481, 61, 57, 53, 49, 525, 638, 639, 508, 48, 46, 49, 47, 493, 679, 674, 527, 24, 32, 40, 31, 566, 582, 576, 554, 44, 56, 68, 54, 606, 593, 620, 548, 26, 35, 37, 35, 495, 648, 648, 480, 60, 56, 56, 57, 472, 630, 676, 534, 39, 41, 54, 54, 560, 582, 604, 549, 39, 60, 60, 46, 471, 698, 663, 504, 47, 38, 30, 49, 530, 739, 645, 560, 10, 5, 5, 6, 599, 584, 643, 601, 18, 16, 27, 12, 589, 666, 598, 618, 5, 5, 11, 8, 509, 638, 693, 490, 39, 41, 50, 40, 483, 689, 732, 512, 22, 21, 18, 23}
Returns: "2212122121222222121222212122211121112211122111111211221221222211111122221221112122122211122112112211"
{19, 18, 13, 18, 530, 686, 732, 484, 59, 66, 59, 56, 461, 690, 668, 441, 48, 43, 37, 54, 500, 693, 629, 496, 52, 67, 58, 51, 591, 567, 565, 549, 18, 38, 37, 20, 584, 611, 616, 576, 12, 14, 19, 8, 572, 624, 628, 623, 40, 69, 75, 49, 544, 594, 564, 565, 0, 0, 0, 0, 547, 746, 712, 495, 0, 0, 0, 0, 614, 633, 643, 610, 0, 0, 0, 0, 628, 628, 592, 652, 28, 42, 54, 39, 550, 633, 592, 562, 61, 48, 69, 64, 486, 637, 639, 496, 4, 7, 10, 6, 545, 655, 732, 541, 23, 56, 41, 38, 544, 643, 590, 565, 49, 64, 48, 47, 558, 576, 589, 569, 20, 29, 21, 26, 533, 687, 703, 481, 9, 10, 14, 6, 490, 746, 689, 536, 4, 7, 11, 5, 526, 713, 686, 548, 38, 34, 26, 25, 488, 698, 670, 521, 46, 48, 63, 45, 549, 600, 560, 589, 22, 22, 20, 22, 514, 662, 700, 538, 24, 22, 32, 19, 589, 618, 628, 568, 19, 15, 19, 20, 535, 682, 679, 531, 55, 65, 64, 58, 575, 578, 575, 530, 21, 49, 42, 32, 582, 588, 595, 591, 51, 45, 49, 48, 483, 630, 688, 506, 14, 13, 14, 8, 520, 694, 718, 519, 7, 7, 7, 4, 642, 635, 611, 587, 0, 0, 0, 0, 619, 645, 639, 597, 25, 33, 35, 26, 597, 637, 569, 578, 28, 33, 45, 32, 572, 596, 618, 576, 24, 25, 28, 21, 588, 596, 602, 616, 33, 49, 60, 37, 569, 611, 610, 531, 40, 42, 57, 28, 490, 658, 699, 486, 13, 11, 8, 14, 517, 722, 711, 504, 44, 58, 60, 70, 573, 547, 595, 553, 25, 44, 50, 29, 509, 689, 680, 474, 35, 42, 51, 36, 508, 676, 622, 530, 27, 31, 22, 20, 653, 582, 601, 564, 23, 25, 25, 17, 545, 644, 650, 571, 3, 5, 7, 8, 615, 629, 645, 588, 19, 24, 33, 19, 593, 632, 628, 552, 13, 25, 18, 15, 499, 700, 728, 502, 21, 19, 10, 23, 633, 589, 630, 575, 44, 62, 67, 53, 558, 590, 540, 586, 48, 47, 57, 50, 482, 671, 623, 522, 19, 19, 34, 18, 570, 636, 615, 589, 45, 38, 37, 29, 522, 737, 638, 454, 5, 5, 3, 4, 532, 706, 718, 527, 13, 16, 19, 22, 469, 727, 726, 508, 22, 17, 25, 23, 476, 736, 651, 550, 9, 20, 23, 9, 619, 608, 647, 565, 30, 35, 39, 30, 573, 628, 607, 558, 21, 17, 20, 23, 526, 712, 662, 519, 24, 22, 22, 26, 503, 678, 696, 529, 2, 7, 5, 7, 600, 641, 640, 598, 20, 37, 37, 31, 577, 618, 587, 593, 8, 13, 13, 10, 536, 720, 704, 496, 0, 0, 0, 0, 624, 660, 650, 566, 15, 14, 14, 8, 529, 688, 727, 505, 50, 46, 66, 50, 564, 615, 635, 474, 5, 9, 8, 3, 576, 626, 657, 616, 31, 37, 32, 28, 611, 568, 594, 599, 30, 40, 29, 31, 496, 686, 663, 525, 25, 27, 40, 30, 608, 628, 574, 568, 43, 22, 38, 39, 489, 697, 673, 499, 24, 37, 29, 29, 513, 694, 691, 483, 44, 48, 57, 41, 568, 603, 601, 538, 40, 61, 53, 39, 568, 617, 613, 509, 12, 24, 21, 24, 536, 716, 690, 477, 21, 43, 34, 28, 571, 652, 620, 531, 54, 51, 54, 34, 556, 611, 573, 567, 51, 52, 57, 46, 488, 678, 678, 450, 50, 44, 37, 57, 476, 672, 672, 492, 52, 63, 56, 41, 557, 588, 600, 543, 24, 21, 32, 25, 577, 618, 634, 569, 40, 36, 46, 26, 566, 571, 639, 576, 25, 45, 36, 22, 579, 654, 566, 573, 24, 34, 30, 27, 549, 689, 646, 501, 7, 18, 10, 9, 569, 638, 631, 618, 31, 26, 27, 21, 493, 710, 669, 523, 35, 49, 36, 33, 492, 632, 723, 500, 9, 9, 4, 5, 577, 631, 690, 575, 35, 35, 29, 39, 489, 682, 710, 481, 8, 12, 9, 8, 547, 701, 702, 513, 6, 13, 11, 5, 621, 629, 637, 578, 19, 16, 16, 16, 569, 665, 654, 545, 28, 29, 36, 36, 514, 659, 700, 498, 51, 47, 54, 38, 502, 664, 680, 464, 41, 44, 64, 50, 537, 618, 576, 570, 17, 27, 23, 21, 596, 605, 632, 579, 28, 36, 32, 42, 507, 648, 684, 523, 0, 0, 0, 0, 644, 646, 611, 599, 17, 14, 13, 7, 479, 736, 674, 560, 0, 0, 0, 0, 545, 720, 698, 537, 31, 37, 22, 28, 524, 680, 682, 496, 65, 58, 58, 55, 507, 648, 639, 470, 15, 28, 36, 25, 583, 640, 621, 552, 13, 15, 14, 12, 601, 657, 603, 585, 0, 0, 0, 0, 638, 652, 615, 595}
Returns: "2221111211122112222121211221111112212211112112122221122112122112122112112211112122122122211212222111"
Submissions are judged against all 22 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TellBagsApart with a public method string whichBagIsSmaller(vector<int> records) · 22 test cases · 2 s / 256 MB per case