KingdomSplit
2022 TCO Round 3 · 2022-04-14 · by misof
2022 TCO Round 3 · 2022-04-14 · by misof · Graph Theory, Greedy, Recursion
Problem Statement
Problem Statement
King Karol currently has one child. His wife, queen Quinoa is currently expecting their second offspring.
In this kingdom each child is either born with blue eyes or with red eyes. A blue-eyed child (such as the king's three-year-old son Adam) is calm and likes even numbers. A red-eyed child is the exact opposite: such a child is wild and likes odd numbers.
The new child will be called Booboo. Once Booboo is born, the king would like to write his last will in which he'll divide the kingdom between Adam and Booboo.
The kingdom is an undirected graph that may contain self-loops and multiple edges. (A self-loop x-x contributes 2 to the degree of x.)
The kingdom has N vertices and they are numbered 0 to N-1.
The king's last will has to divide all vertices into two disjoint sets A (for Adam) and B (for Booboo). Each child will also get the edges that have both endpoints in their set. (The queen will get all edges between A and B.)
King Karol wants to split the kingdom so that each child will be happy with the smaller kingdom they receive. There are two conditions he wants to satisfy:
- Each blue-eyed child should receive a kingdom in which all the vertices have an even degree.
- Each red-eyed child should receive a kingdom in which all the vertices have an odd degree.
(Remember that these degrees only include the edges that child inherited.)
You are given Booboo's eye color in the
Determine whether it's possible to split the given kingdom in two according to the king's wishes. If no, return {-1}. If yes, find any valid split (A, B) and return A.
Notes
- If a solution exists, you may return any valid solution. The values in the returned A do not have to be sorted but A must not contain duplicates.
- Splits where one child gets all N vertices are allowed.
Constraints
- eyes will be either "blue" or "red".
- N will be between 1 and 500, inclusive.
- X will contain between 0 and 1500 elements, inclusive.
- Y will contain the same number of elements as X.
- Each element in X and Y will be between 0 and N-1, inclusive.
Examples
0)
"blue"
7
{}
{}
Returns: {1, 4, 3 }
Seven vertices, no edges. Two children, each has blue eyes. The king can split the kingdom completely arbitrarily, each possible split is valid.
1)
"red"
7
{}
{}
Returns: {6, 5, 4, 3, 2, 1, 0 }
Here the red-eyed child (Booboo) cannot get any vertices - and so Adam must get all of them.
2)
"red"
3
{0, 0}
{1, 2}
Returns: {2 }
Booboo cannot get no vertices at all because then Adam gets all three and his kingdom contains some odd vertices. Booboo cannot get just one vertex because then that vertex has an even degree (zero is even). Booboo cannot get all three vertices because then vertex 0 is even. Booboo cannot get {1, 2} because then both have degree zero. Thus, there are exactly two valid solutions: either Adam gets {1} and Booboo gets {0,2}, or Adam gets {2} and Booboo gets {0,1}. Hence, you may return either {1} or {2}.
3)
"blue"
8
{6, 1, 4, 7, 7, 5, 2, 3, 0, 6, 1}
{3, 0, 2, 4, 4, 4, 6, 5, 5, 4, 1}
Returns: {6, 5, 4, 3, 1 }
Adam's kingdom will include the edges 6-3, 5-4, 3-5, 6-4, and 1-1. In his kingdom each vertex has degree 2, which is even. Booboo will get the vertices {0, 2, 7} and no edges at all. Again, in this kingdom all vertices have even degrees and so blue-eyed Booboo is happy.
4)
"blue"
500
{180, 32, 220, 283, 232, 292, 175, 131, 262, 197, 200, 315, 20, 407, 214, 337, 12, 490, 52, 0, 135, 482, 494, 405, 246, 370, 279, 4, 469, 417, 460, 161, 290, 218, 117, 121, 267, 263, 183, 226, 490, 123, 17, 287, 191, 366, 352, 180, 307, 175, 285, 294, 390, 100, 122, 403, 430, 373, 468, 478, 18, 64, 170, 50, 185, 296, 196, 260, 276, 416, 129, 49, 332, 446, 451, 116, 474, 357, 432, 171, 111, 241, 381, 56, 395, 213, 309, 180, 345, 446, 146, 450, 395, 414, 122, 414, 284, 472, 133, 182, 272, 289, 20, 247, 159, 288, 399, 202, 133, 483, 373, 265, 409, 113, 310, 58, 321, 430, 106, 194, 248, 129, 492, 309, 473, 285, 76, 227, 7, 87, 280, 321, 411, 389, 42, 38, 136, 261, 416, 318, 279, 243, 400, 410, 223, 187, 470, 388, 16, 311, 135, 460, 329, 311, 264, 483, 345, 465, 241, 468, 362, 326, 408, 487, 161, 424, 11, 295, 124, 108, 177, 220, 490, 443, 354, 94, 90, 240, 471, 101, 65, 50, 69, 373, 401, 291, 176, 270, 200, 55, 136, 227, 0, 334, 62, 212, 34, 189, 10, 135, 21, 71, 92, 378, 261, 427, 251, 102, 400, 395, 415, 253, 270, 232, 288, 290, 5, 355, 37, 89, 427, 77, 471, 278, 173, 325, 443, 23, 449, 318, 120, 364, 31, 193, 63, 11, 45, 154, 27, 450, 280, 157, 122, 313, 458, 375, 273, 77, 281, 296, 390, 139, 316, 439, 292, 41, 288, 251, 175, 284, 26, 488, 58, 211, 213, 181, 464, 155, 288, 432, 388, 250, 306, 71, 32, 497, 260, 59, 462, 236, 334, 402, 232, 421, 9, 222, 414, 288, 267, 390, 494, 33, 400, 404, 147, 401, 360, 250, 257, 58, 386, 125, 180, 407, 169, 85, 236, 11, 300, 50, 343, 235, 481, 235, 141, 326, 278, 351, 355, 352, 470, 12, 493, 286, 96, 421, 347, 146, 20, 395, 134, 277, 247, 196, 35, 369, 402, 55, 450, 266, 363, 302, 306, 244, 275, 381, 404, 185, 296, 159, 210, 394, 349, 458, 459, 104, 374, 323, 46, 480, 52, 262, 414, 156, 207, 488, 170, 275, 428, 184, 435, 55, 417, 477, 47, 437, 318, 380, 218, 184, 25, 179, 298, 442, 28, 473, 200, 324, 413, 137, 130, 107, 148, 107, 238, 435, 338, 420, 418, 489, 153, 227, 478, 397, 225, 162, 442, 345, 28, 79, 297, 245, 0, 14, 216, 443, 234, 266, 224, 314, 417, 440, 131, 150, 52, 155, 63, 477, 86, 216, 172, 254, 218, 489, 120, 257, 291, 262, 134, 160, 284, 11, 470, 311, 344, 447, 194, 438, 495, 467, 304, 301, 356, 304, 353, 319, 469, 236, 315, 285, 91, 349, 359, 193, 417, 21, 92, 313, 475, 92, 319, 39, 248, 210, 30, 114, 236, 90, 476, 306, 203, 2, 319, 71, 380, 37, 286, 199, 0, 196, 255, 379, 233, 322, 191, 374, 62, 261, 205, 52, 44, 404, 215, 210, 481, 455, 281, 53, 436, 316, 89, 462, 340, 255, 243, 224, 305, 424, 47, 202, 268, 258, 167, 221, 383, 467, 100, 161, 203, 434, 38, 67, 485, 364, 497, 249, 170, 332, 332, 53, 129, 248, 404, 498, 47, 182, 496, 15, 202, 319, 41, 307, 114, 264, 329, 107, 259, 131, 365, 439, 391, 496, 156, 256, 310, 58, 467, 287, 31, 146, 368, 90, 249, 356, 123, 207, 312, 242, 3, 301, 446, 204, 311, 120, 320, 491, 283, 191, 410, 403, 54, 172, 32, 80, 302, 54, 122, 432, 443, 93, 40, 72, 263, 86, 368, 84, 39, 47, 64, 301, 201, 441, 178, 62, 492, 212, 150, 281, 327, 112, 347, 469, 177, 393, 46, 328, 160, 52, 18, 103, 415, 286, 69, 493, 169, 479, 497, 46, 426, 163, 393, 366, 339, 480, 483, 469, 219, 259, 279, 293, 385, 394, 348, 461, 180, 408, 266, 265, 217, 326, 224, 223, 346, 211, 372, 251, 11, 99, 495, 167, 25, 307, 480, 219, 461, 51, 224, 395, 298, 63, 49, 433, 171, 223, 378, 466, 30, 170, 499, 403, 386, 95, 467, 416, 342, 209, 240, 379, 468, 474, 265, 243, 354, 264, 61, 477, 472, 117, 101, 321, 13, 276, 252, 166, 471, 72, 345, 83, 396, 148, 37, 24, 382, 428, 463, 309, 152, 22, 328, 316, 436, 342, 3, 131, 176, 462, 98, 284, 110, 189, 461, 189, 68, 103, 493, 229, 315, 17, 407, 379, 416, 154, 308, 342, 153, 215, 56, 216, 431, 214, 177, 387, 254, 493, 131, 23, 370, 289, 369, 352, 466, 251, 117, 138, 207, 29, 446, 12, 201, 97, 392, 213, 187, 266, 45, 176, 369, 495, 444, 319, 453, 321, 173, 225, 443, 428, 34, 451, 33, 498, 242, 136, 32, 83, 104, 116, 475, 216, 241, 406, 101, 151, 3, 58, 309, 288, 417, 6, 128, 273, 109, 272, 190, 241, 469, 493, 109, 170, 205, 466, 19, 344, 330, 300, 212, 166, 415, 411, 275, 176, 458, 3, 55, 10, 159, 405, 24, 311, 111, 421, 420, 432, 268, 442, 313, 1, 17, 446, 283, 301, 25, 196, 457, 390, 237, 97, 45, 494, 141, 481, 345, 476, 325, 454, 202, 261, 178, 19, 453, 33, 155, 307, 365, 159, 26, 312, 469, 226, 237, 208, 373, 368, 170, 368, 46, 129, 436, 456, 485, 215, 191, 480, 50, 362, 193, 193, 90, 151, 15, 15, 294, 499, 346, 295, 415, 453, 499, 97, 64, 287, 114, 44, 3, 216, 218, 213, 362, 216, 296, 375, 65, 78, 395, 369, 378, 486, 379, 436, 192, 275, 328, 464, 235, 134, 327, 422, 328, 75, 38, 20, 302, 123, 416, 374, 300, 65, 36, 464, 8, 70, 62, 265, 399, 65, 313, 437, 476, 483, 149, 291, 308, 450, 214, 280, 381, 493, 249, 313, 437, 297, 445, 12, 85, 400, 412, 306, 277, 296, 421, 324, 370, 74, 476, 118, 434, 60, 77, 458, 464, 145, 315, 247, 459, 413, 333, 250, 235, 421, 437, 309, 158, 209, 385, 474, 490, 230, 310, 93, 6, 219, 413, 403, 478, 446, 249, 250, 374, 208, 175, 191, 284, 154, 409, 459, 157, 201, 426, 423, 192, 18, 319, 390, 269, 137, 72, 239, 200, 51, 427, 451, 394, 337, 55, 303, 17, 188, 480, 326, 420, 456, 174, 339, 346, 292, 384, 75, 0, 133, 179, 81, 317, 439, 20, 408, 412, 211, 246, 367, 165, 75, 136, 482, 131, 169, 209, 336, 57, 105, 462, 496, 490, 342, 478, 90, 318, 450, 118, 471, 144, 340, 125, 235, 356, 392, 270, 174, 473, 79, 484, 270, 184, 57, 459, 74, 471, 90, 289, 473, 116, 276, 432, 292, 401, 270, 425, 397, 164, 327, 405, 327, 277, 105, 404, 326, 127, 485, 20, 187, 480, 194, 459, 386, 88, 250, 311, 477, 375, 461, 371, 87, 473, 447, 98, 206, 411, 372, 342, 27, 240, 167, 280, 467, 276, 38, 132, 48, 70, 435, 342, 420, 263, 382, 296, 342, 483, 106, 140, 305, 199, 445, 56, 130, 283, 183, 61, 192, 190, 332, 272, 115, 148, 128, 495, 311, 346, 357, 333, 164, 291, 19, 388, 496, 316, 106, 151, 228, 395, 472, 446, 166, 386, 58, 74, 303, 93, 451, 447, 465, 133, 175, 140, 48, 150, 106, 19, 391, 455, 138, 313, 333, 111, 101, 349, 252, 253, 39, 195, 332, 11, 335, 392, 483, 303, 76, 54, 454, 214, 154, 473, 112, 436, 211, 384, 97, 44, 109, 328, 324, 448, 340, 114, 280, 45, 284, 214, 158, 161, 191, 466, 60, 46, 354, 160, 232, 108, 393, 60, 334, 44, 274, 340, 174, 389, 290, 352, 247, 407, 112, 30, 163, 157, 405, 374, 377, 341, 404, 194, 135, 392, 303, 30, 38, 131, 234, 258, 112, 262, 261, 248, 145, 163, 223, 264, 127, 312, 348, 436, 359, 328, 450, 168, 292, 324, 107, 445, 292, 422, 90, 96, 122, 385, 21, 15, 355, 311, 435, 260, 440, 460, 416, 310, 133, 376, 311, 150, 459, 101, 175, 303, 442, 309, 322, 451, 286, 172, 258, 88, 382, 397, 434, 167, 190, 94, 80, 338, 372, 252, 38, 18, 200, 237, 476, 355, 230, 150, 318, 48, 404, 327, 356, 252, 414, 321, 439, 495, 138, 170, 144, 355, 111, 419, 422, 463, 358, 435, 414, 218, 38, 130, 313, 195, 165, 235, 149, 82, 123, 93, 185, 117, 472, 158, 18, 110, 353, 294, 242, 12, 182, 4, 322, 145, 140, 283, 212, 387, 271, 472, 120, 232, 232, 27, 420, 467, 42, 369, 66, 375, 206, 226, 95, 126, 23, 205, 344, 231, 272, 268, 51, 285, 13, 278, 229, 276, 248, 430, 301, 82, 81, 403, 387, 486, 122, 141, 343, 163, 99, 285, 493, 345, 436, 252, 260, 410, 380, 140, 235, 130, 172, 268, 59, 491, 113, 389, 498, 130, 401, 485, 115, 16, 400, 70, 125, 352, 377, 450, 473, 364, 478, 229, 376}
{365, 445, 397, 43, 165, 372, 280, 377, 330, 335, 493, 487, 110, 165, 490, 320, 48, 405, 133, 265, 80, 142, 184, 71, 383, 84, 40, 446, 94, 416, 28, 436, 395, 260, 91, 309, 468, 469, 331, 414, 284, 313, 314, 52, 146, 21, 410, 164, 94, 44, 230, 141, 50, 152, 100, 303, 386, 385, 253, 319, 479, 369, 73, 395, 488, 442, 69, 124, 364, 275, 434, 123, 311, 159, 131, 344, 378, 459, 494, 232, 414, 13, 158, 468, 96, 381, 467, 13, 220, 89, 137, 450, 357, 249, 96, 229, 6, 189, 325, 126, 205, 259, 91, 402, 491, 90, 91, 308, 25, 110, 161, 312, 206, 335, 153, 375, 137, 320, 47, 155, 117, 22, 287, 241, 475, 460, 417, 156, 120, 151, 426, 233, 91, 90, 283, 155, 405, 235, 148, 149, 313, 379, 26, 427, 157, 465, 19, 337, 443, 35, 312, 306, 204, 290, 259, 217, 74, 193, 196, 336, 277, 114, 271, 286, 211, 354, 227, 276, 416, 453, 93, 129, 205, 164, 468, 171, 460, 63, 193, 222, 71, 45, 376, 222, 127, 120, 1, 131, 277, 418, 12, 410, 172, 203, 440, 272, 155, 365, 101, 129, 34, 347, 25, 124, 89, 312, 180, 177, 42, 350, 255, 133, 143, 393, 305, 188, 104, 416, 24, 422, 133, 249, 119, 340, 55, 270, 429, 156, 94, 203, 143, 379, 302, 467, 364, 103, 270, 143, 389, 82, 82, 163, 78, 142, 246, 50, 146, 355, 133, 77, 200, 345, 112, 113, 410, 385, 404, 91, 44, 470, 148, 264, 74, 498, 417, 238, 398, 151, 16, 483, 54, 454, 348, 284, 492, 113, 106, 54, 100, 255, 196, 154, 366, 130, 6, 438, 171, 184, 215, 49, 45, 492, 168, 474, 133, 273, 427, 118, 297, 482, 368, 353, 462, 70, 125, 344, 470, 410, 254, 282, 357, 323, 102, 395, 17, 379, 85, 12, 291, 445, 445, 160, 116, 351, 187, 432, 117, 125, 250, 189, 103, 422, 442, 217, 95, 237, 304, 314, 499, 113, 18, 394, 208, 238, 477, 118, 216, 467, 392, 9, 216, 316, 262, 491, 33, 251, 99, 200, 96, 370, 1, 122, 252, 266, 6, 428, 281, 479, 151, 245, 160, 156, 312, 358, 340, 265, 363, 354, 381, 320, 258, 192, 319, 113, 345, 27, 111, 111, 390, 251, 301, 225, 255, 433, 204, 278, 205, 71, 214, 182, 6, 356, 268, 173, 279, 380, 54, 391, 312, 185, 428, 261, 444, 197, 134, 78, 497, 453, 27, 110, 27, 288, 134, 352, 132, 90, 191, 453, 314, 191, 118, 292, 296, 489, 283, 415, 443, 474, 68, 120, 54, 454, 68, 184, 440, 26, 74, 375, 472, 89, 199, 394, 429, 393, 355, 340, 138, 267, 32, 319, 374, 272, 498, 78, 481, 460, 123, 499, 164, 232, 438, 265, 377, 363, 134, 48, 179, 390, 131, 4, 323, 283, 142, 273, 137, 238, 268, 314, 239, 450, 77, 186, 69, 343, 439, 106, 10, 50, 27, 196, 252, 105, 336, 345, 270, 344, 294, 80, 323, 358, 188, 29, 285, 380, 93, 449, 281, 122, 246, 498, 396, 245, 218, 29, 359, 254, 355, 359, 446, 352, 396, 445, 119, 262, 294, 166, 261, 112, 198, 379, 233, 69, 327, 86, 87, 449, 101, 411, 170, 0, 303, 267, 376, 102, 280, 434, 229, 83, 149, 267, 328, 222, 335, 241, 283, 223, 441, 351, 10, 85, 298, 219, 204, 487, 493, 16, 285, 25, 31, 310, 353, 52, 106, 246, 96, 408, 282, 457, 16, 404, 273, 459, 394, 61, 8, 169, 132, 245, 142, 50, 466, 387, 378, 337, 59, 183, 247, 4, 142, 292, 235, 448, 470, 228, 95, 63, 489, 479, 132, 188, 238, 27, 251, 354, 16, 218, 328, 41, 352, 458, 389, 357, 107, 189, 100, 117, 370, 299, 73, 105, 253, 263, 381, 54, 148, 394, 310, 326, 378, 350, 276, 388, 440, 50, 406, 430, 250, 99, 19, 76, 376, 259, 387, 132, 75, 143, 190, 75, 434, 170, 467, 441, 407, 340, 427, 466, 272, 189, 460, 65, 463, 73, 489, 219, 208, 292, 414, 162, 347, 92, 309, 418, 397, 192, 9, 467, 53, 217, 381, 85, 349, 470, 439, 33, 51, 66, 52, 405, 39, 411, 440, 111, 14, 92, 420, 197, 49, 32, 416, 285, 246, 383, 452, 8, 62, 88, 170, 342, 375, 67, 359, 67, 142, 114, 71, 26, 198, 81, 214, 413, 283, 14, 37, 468, 124, 346, 356, 257, 218, 260, 321, 306, 32, 398, 477, 181, 124, 182, 136, 468, 487, 96, 22, 156, 461, 22, 90, 465, 30, 268, 159, 157, 223, 367, 473, 174, 450, 470, 24, 188, 380, 401, 332, 307, 128, 326, 484, 93, 266, 400, 405, 321, 83, 97, 317, 12, 272, 384, 404, 238, 117, 403, 132, 213, 245, 2, 386, 335, 26, 456, 174, 316, 208, 47, 38, 318, 175, 106, 132, 175, 354, 61, 318, 77, 304, 230, 457, 480, 193, 297, 172, 103, 131, 472, 140, 344, 234, 127, 246, 90, 294, 209, 198, 101, 18, 165, 488, 499, 22, 436, 120, 34, 59, 140, 122, 489, 246, 225, 386, 490, 71, 317, 49, 358, 4, 300, 170, 145, 492, 291, 20, 492, 135, 191, 416, 190, 186, 80, 465, 483, 45, 383, 131, 45, 497, 247, 274, 259, 239, 341, 174, 309, 198, 83, 471, 151, 61, 228, 216, 299, 346, 135, 127, 369, 123, 489, 413, 389, 23, 80, 17, 391, 472, 156, 331, 421, 214, 253, 126, 449, 108, 476, 28, 355, 139, 407, 296, 424, 297, 108, 263, 19, 164, 140, 68, 213, 61, 59, 116, 271, 464, 91, 356, 371, 312, 385, 92, 308, 56, 200, 165, 137, 3, 484, 457, 352, 408, 451, 476, 354, 256, 273, 139, 368, 90, 261, 439, 4, 322, 263, 301, 157, 444, 293, 152, 343, 209, 294, 298, 191, 169, 125, 144, 109, 348, 469, 353, 172, 206, 420, 404, 422, 357, 190, 350, 378, 424, 108, 70, 390, 181, 263, 14, 237, 75, 279, 180, 456, 202, 45, 44, 37, 284, 214, 440, 400, 404, 258, 438, 78, 490, 342, 94, 417, 86, 231, 35, 109, 492, 187, 345, 196, 98, 254, 358, 36, 321, 285, 254, 101, 28, 10, 165, 287, 99, 194, 6, 70, 284, 343, 201, 482, 188, 118, 55, 127, 102, 197, 131, 301, 236, 498, 415, 373, 400, 439, 494, 202, 215, 496, 247, 17, 84, 79, 99, 181, 481, 468, 305, 398, 369, 272, 448, 179, 439, 75, 355, 24, 439, 330, 424, 18, 65, 324, 94, 91, 25, 6, 358, 182, 466, 107, 452, 11, 259, 447, 68, 15, 374, 175, 382, 129, 154, 212, 434, 415, 495, 380, 422, 73, 229, 408, 370, 227, 82, 339, 81, 271, 444, 495, 218, 6, 65, 472, 92, 251, 458, 415, 64, 458, 213, 189, 12, 4, 297, 234, 104, 154, 424, 85, 142, 264, 370, 394, 156, 336, 312, 212, 94, 436, 164, 463, 51, 299, 188, 449, 413, 283, 337, 393, 114, 370, 466, 107, 315, 234, 227, 447, 95, 115, 405, 334, 140, 12, 422, 388, 323, 49, 202, 24, 186, 290, 324, 31, 224, 19, 54, 450, 130, 174, 337, 108, 188, 437, 5, 177, 113, 108, 100, 94, 458, 172, 120, 198, 447, 30, 340, 59, 66, 407, 312, 260, 317, 484, 214, 167, 186, 229, 248, 236, 407, 253, 303, 86, 455, 388, 18, 213, 303, 449, 259, 417, 279, 237, 165, 189, 221, 87, 266, 332, 465, 283, 273, 117, 254, 210, 397, 382, 23, 179, 443, 155, 319, 126, 412, 240, 125, 411, 104, 47, 255, 486, 339, 193, 297, 111, 254, 12, 164, 127, 99, 169, 373, 300, 264, 424, 435, 114, 8, 202, 362, 435, 20, 261, 298, 171, 284, 277, 167, 495, 176, 324, 261, 235, 404, 319, 17, 295, 304, 94, 386, 48, 105, 32, 474, 128, 295, 136, 195, 300, 402, 342, 14, 411, 50, 266, 260, 393, 351, 186, 369, 453, 213, 133, 398, 494, 180, 471, 136, 354, 74, 254, 398, 427, 280, 342, 324, 65, 313, 410, 313, 275, 77, 470, 158, 144, 493, 23, 310, 222, 186, 279, 386, 315, 198, 360, 319, 391, 291, 323, 403, 344, 406, 225, 470, 282, 418, 319, 369, 0, 132, 145, 245, 130, 394, 287, 373, 336, 430, 197, 81, 100, 475, 419, 428, 202, 209, 365, 327, 442, 239, 29, 454, 150, 253, 49, 267, 482, 321, 409, 153, 364, 187, 425, 479, 264, 283, 125, 441, 43, 295, 35, 16, 65, 136, 449, 358, 161, 208, 45, 110, 474, 317, 289, 146, 103, 173, 51, 276, 110, 411, 469, 395, 247, 398, 421, 94, 35, 252, 25, 103, 440, 32, 185, 18, 463, 225, 34, 394, 476, 369, 355, 286, 32, 246, 494, 415, 468, 394, 369, 108, 81, 33, 87, 34, 436, 97, 108, 94, 294, 450, 403, 382, 337, 452, 110, 457, 202, 383, 283, 477, 240, 206, 19, 408, 276, 86, 99, 396, 287}
Returns: {497, 496, 493, 492, 491, 489, 487, 483, 482, 478, 477, 476, 475, 473, 470, 469, 467, 466, 465, 462, 461, 459, 456, 455, 452, 448, 442, 438, 436, 433, 431, 430, 429, 428, 427, 426, 422, 420, 414, 412, 411, 408, 407, 406, 405, 404, 403, 401, 396, 395, 394, 392, 389, 387, 386, 385, 384, 383, 380, 377, 375, 374, 372, 368, 365, 361, 359, 358, 355, 354, 353, 352, 348, 346, 344, 342, 340, 339, 337, 336, 335, 332, 330, 327, 326, 324, 323, 322, 318, 317, 316, 315, 312, 311, 301, 300, 299, 294, 288, 286, 285, 284, 283, 281, 279, 278, 276, 272, 271, 269, 268, 267, 266, 265, 261, 259, 258, 254, 252, 251, 247, 246, 243, 242, 238, 237, 236, 234, 232, 231, 230, 229, 224, 223, 222, 219, 216, 214, 212, 210, 202, 201, 200, 196, 191, 190, 189, 188, 187, 186, 185, 182, 181, 179, 174, 172, 171, 170, 168, 167, 166, 163, 159, 158, 155, 150, 147, 141, 140, 139, 137, 135, 132, 131, 129, 128, 127, 125, 124, 121, 120, 118, 116, 113, 110, 109, 108, 105, 98, 97, 95, 93, 92, 91, 89, 88, 85, 82, 81, 76, 75, 74, 71, 67, 65, 64, 60, 58, 56, 55, 54, 53, 52, 51, 50, 48, 47, 44, 41, 40, 37, 36, 32, 29, 26, 23, 22, 20, 18, 17, 15, 14, 12, 11, 10, 9, 8, 2, 1, 0 }
148)
"red"
8
{6, 1, 4, 7, 7, 5, 2, 3, 0, 6, 1}
{3, 0, 2, 4, 4, 4, 6, 5, 5, 4, 1}
Returns: {7, 4, 3, 1 }
Same kingdom as above but now Booboo has red eyes. Adam now gets the edges 7-4, 7-4 and 1-1. His vertices have deg(1) = deg(4) = deg(7) = 2 and deg(3) = 0. Booboo gets the vertices {0, 2, 5, 6} and thus the edges 2-6 and 0-5. In this subgraph each vertex has degree 1.
Submissions are judged against all 149 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class KingdomSplit with a public method vector<int> split(string eyes, int N, vector<int> X, vector<int> Y) · 149 test cases · 2 s / 256 MB per case