So I was trying to upsolve IOI 2024 Q6 Sphinx. In the editorial phase 2 states to split the condensed graph into two sets, and perform binary search on these sets for every colour, to determine which components have what colour. However, each binary search needs $\log N\approx8$ queries to perform the actual binary search, along with an additional query to "confirm" that no other component in the set has that colour. Along with the rest of the solution, this gives a query count of $3N+a+N\log N$, where $a$ is the number of monochromatic components. This means that, in the worst case, the solution would take $4N+N\log N$, which is up to $3000$ queries, more than is allowed in the problem. At first, I thought that there would be some amortisation which keeps the query count under the limit of $2750$ queries, but then I made the following construction:↵
↵
Consider the test case with $N=250$ vertices, all with different colours. Then, the graph is constructed by taking the first 248 vertices, and for each of these vertices construct an edge between that vertex and both vertices 249 and 250 (1-indexed). Testing this test case on the model code provided by IOI, it took $2977>2750$ queries to finish?↵
↵
↵
↵
Is this a counterexample to the model solution for IOI Sphinx? The testcase I used is below, you can test it out yourself.↵
↵
<spoiler summary="Test case used">↵
~~~~~↵
250 496↵
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249↵
248 0↵
249 0↵
248 1↵
249 1↵
248 2↵
249 2↵
248 3↵
249 3↵
248 4↵
249 4↵
248 5↵
249 5↵
248 6↵
249 6↵
248 7↵
249 7↵
248 8↵
249 8↵
248 9↵
249 9↵
248 10↵
249 10↵
248 11↵
249 11↵
248 12↵
249 12↵
248 13↵
249 13↵
248 14↵
249 14↵
248 15↵
249 15↵
248 16↵
249 16↵
248 17↵
249 17↵
248 18↵
249 18↵
248 19↵
249 19↵
248 20↵
249 20↵
248 21↵
249 21↵
248 22↵
249 22↵
248 23↵
249 23↵
248 24↵
249 24↵
248 25↵
249 25↵
248 26↵
249 26↵
248 27↵
249 27↵
248 28↵
249 28↵
248 29↵
249 29↵
248 30↵
249 30↵
248 31↵
249 31↵
248 32↵
249 32↵
248 33↵
249 33↵
248 34↵
249 34↵
248 35↵
249 35↵
248 36↵
249 36↵
248 37↵
249 37↵
248 38↵
249 38↵
248 39↵
249 39↵
248 40↵
249 40↵
248 41↵
249 41↵
248 42↵
249 42↵
248 43↵
249 43↵
248 44↵
249 44↵
248 45↵
249 45↵
248 46↵
249 46↵
248 47↵
249 47↵
248 48↵
249 48↵
248 49↵
249 49↵
248 50↵
249 50↵
248 51↵
249 51↵
248 52↵
249 52↵
248 53↵
249 53↵
248 54↵
249 54↵
248 55↵
249 55↵
248 56↵
249 56↵
248 57↵
249 57↵
248 58↵
249 58↵
248 59↵
249 59↵
248 60↵
249 60↵
248 61↵
249 61↵
248 62↵
249 62↵
248 63↵
249 63↵
248 64↵
249 64↵
248 65↵
249 65↵
248 66↵
249 66↵
248 67↵
249 67↵
248 68↵
249 68↵
248 69↵
249 69↵
248 70↵
249 70↵
248 71↵
249 71↵
248 72↵
249 72↵
248 73↵
249 73↵
248 74↵
249 74↵
248 75↵
249 75↵
248 76↵
249 76↵
248 77↵
249 77↵
248 78↵
249 78↵
248 79↵
249 79↵
248 80↵
249 80↵
248 81↵
249 81↵
248 82↵
249 82↵
248 83↵
249 83↵
248 84↵
249 84↵
248 85↵
249 85↵
248 86↵
249 86↵
248 87↵
249 87↵
248 88↵
249 88↵
248 89↵
249 89↵
248 90↵
249 90↵
248 91↵
249 91↵
248 92↵
249 92↵
248 93↵
249 93↵
248 94↵
249 94↵
248 95↵
249 95↵
248 96↵
249 96↵
248 97↵
249 97↵
248 98↵
249 98↵
248 99↵
249 99↵
248 100↵
249 100↵
248 101↵
249 101↵
248 102↵
249 102↵
248 103↵
249 103↵
248 104↵
249 104↵
248 105↵
249 105↵
248 106↵
249 106↵
248 107↵
249 107↵
248 108↵
249 108↵
248 109↵
249 109↵
248 110↵
249 110↵
248 111↵
249 111↵
248 112↵
249 112↵
248 113↵
249 113↵
248 114↵
249 114↵
248 115↵
249 115↵
248 116↵
249 116↵
248 117↵
249 117↵
248 118↵
249 118↵
248 119↵
249 119↵
248 120↵
249 120↵
248 121↵
249 121↵
248 122↵
249 122↵
248 123↵
249 123↵
248 124↵
249 124↵
248 125↵
249 125↵
248 126↵
249 126↵
248 127↵
249 127↵
248 128↵
249 128↵
248 129↵
249 129↵
248 130↵
249 130↵
248 131↵
249 131↵
248 132↵
249 132↵
248 133↵
249 133↵
248 134↵
249 134↵
248 135↵
249 135↵
248 136↵
249 136↵
248 137↵
249 137↵
248 138↵
249 138↵
248 139↵
249 139↵
248 140↵
249 140↵
248 141↵
249 141↵
248 142↵
249 142↵
248 143↵
249 143↵
248 144↵
249 144↵
248 145↵
249 145↵
248 146↵
249 146↵
248 147↵
249 147↵
248 148↵
249 148↵
248 149↵
249 149↵
248 150↵
249 150↵
248 151↵
249 151↵
248 152↵
249 152↵
248 153↵
249 153↵
248 154↵
249 154↵
248 155↵
249 155↵
248 156↵
249 156↵
248 157↵
249 157↵
248 158↵
249 158↵
248 159↵
249 159↵
248 160↵
249 160↵
248 161↵
249 161↵
248 162↵
249 162↵
248 163↵
249 163↵
248 164↵
249 164↵
248 165↵
249 165↵
248 166↵
249 166↵
248 167↵
249 167↵
248 168↵
249 168↵
248 169↵
249 169↵
248 170↵
249 170↵
248 171↵
249 171↵
248 172↵
249 172↵
248 173↵
249 173↵
248 174↵
249 174↵
248 175↵
249 175↵
248 176↵
249 176↵
248 177↵
249 177↵
248 178↵
249 178↵
248 179↵
249 179↵
248 180↵
249 180↵
248 181↵
249 181↵
248 182↵
249 182↵
248 183↵
249 183↵
248 184↵
249 184↵
248 185↵
249 185↵
248 186↵
249 186↵
248 187↵
249 187↵
248 188↵
249 188↵
248 189↵
249 189↵
248 190↵
249 190↵
248 191↵
249 191↵
248 192↵
249 192↵
248 193↵
249 193↵
248 194↵
249 194↵
248 195↵
249 195↵
248 196↵
249 196↵
248 197↵
249 197↵
248 198↵
249 198↵
248 199↵
249 199↵
248 200↵
249 200↵
248 201↵
249 201↵
248 202↵
249 202↵
248 203↵
249 203↵
248 204↵
249 204↵
248 205↵
249 205↵
248 206↵
249 206↵
248 207↵
249 207↵
248 208↵
249 208↵
248 209↵
249 209↵
248 210↵
249 210↵
248 211↵
249 211↵
248 212↵
249 212↵
248 213↵
249 213↵
248 214↵
249 214↵
248 215↵
249 215↵
248 216↵
249 216↵
248 217↵
249 217↵
248 218↵
249 218↵
248 219↵
249 219↵
248 220↵
249 220↵
248 221↵
249 221↵
248 222↵
249 222↵
248 223↵
249 223↵
248 224↵
249 224↵
248 225↵
249 225↵
248 226↵
249 226↵
248 227↵
249 227↵
248 228↵
249 228↵
248 229↵
249 229↵
248 230↵
249 230↵
248 231↵
249 231↵
248 232↵
249 232↵
248 233↵
249 233↵
248 234↵
249 234↵
248 235↵
249 235↵
248 236↵
249 236↵
248 237↵
249 237↵
248 238↵
249 238↵
248 239↵
249 239↵
248 240↵
249 240↵
248 241↵
249 241↵
248 242↵
249 242↵
248 243↵
249 243↵
248 244↵
249 244↵
248 245↵
249 245↵
248 246↵
249 246↵
248 247↵
249 247↵
~~~~~↵
</spoiler>↵
↵
Edit: I used the `model_solution/solution.cpp` file, apparantly it works on other solutions.↵
↵
Edit: This testcase also breaks some people's solutions, [https://oj.uz/submission/1372712](https://oj.uz/submission/1372712) for example.
↵
Consider the test case with $N=250$ vertices, all with different colours. Then, the graph is constructed by taking the first 248 vertices, and for each of these vertices construct an edge between that vertex and both vertices 249 and 250 (1-indexed). Testing this test case on the model code provided by IOI, it took $2977>2750$ queries to finish?↵
↵
↵
↵
Is this a counterexample to the model solution for IOI Sphinx? The testcase I used is below, you can test it out yourself.↵
↵
<spoiler summary="Test case used">↵
~~~~~↵
250 496↵
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249↵
248 0↵
249 0↵
248 1↵
249 1↵
248 2↵
249 2↵
248 3↵
249 3↵
248 4↵
249 4↵
248 5↵
249 5↵
248 6↵
249 6↵
248 7↵
249 7↵
248 8↵
249 8↵
248 9↵
249 9↵
248 10↵
249 10↵
248 11↵
249 11↵
248 12↵
249 12↵
248 13↵
249 13↵
248 14↵
249 14↵
248 15↵
249 15↵
248 16↵
249 16↵
248 17↵
249 17↵
248 18↵
249 18↵
248 19↵
249 19↵
248 20↵
249 20↵
248 21↵
249 21↵
248 22↵
249 22↵
248 23↵
249 23↵
248 24↵
249 24↵
248 25↵
249 25↵
248 26↵
249 26↵
248 27↵
249 27↵
248 28↵
249 28↵
248 29↵
249 29↵
248 30↵
249 30↵
248 31↵
249 31↵
248 32↵
249 32↵
248 33↵
249 33↵
248 34↵
249 34↵
248 35↵
249 35↵
248 36↵
249 36↵
248 37↵
249 37↵
248 38↵
249 38↵
248 39↵
249 39↵
248 40↵
249 40↵
248 41↵
249 41↵
248 42↵
249 42↵
248 43↵
249 43↵
248 44↵
249 44↵
248 45↵
249 45↵
248 46↵
249 46↵
248 47↵
249 47↵
248 48↵
249 48↵
248 49↵
249 49↵
248 50↵
249 50↵
248 51↵
249 51↵
248 52↵
249 52↵
248 53↵
249 53↵
248 54↵
249 54↵
248 55↵
249 55↵
248 56↵
249 56↵
248 57↵
249 57↵
248 58↵
249 58↵
248 59↵
249 59↵
248 60↵
249 60↵
248 61↵
249 61↵
248 62↵
249 62↵
248 63↵
249 63↵
248 64↵
249 64↵
248 65↵
249 65↵
248 66↵
249 66↵
248 67↵
249 67↵
248 68↵
249 68↵
248 69↵
249 69↵
248 70↵
249 70↵
248 71↵
249 71↵
248 72↵
249 72↵
248 73↵
249 73↵
248 74↵
249 74↵
248 75↵
249 75↵
248 76↵
249 76↵
248 77↵
249 77↵
248 78↵
249 78↵
248 79↵
249 79↵
248 80↵
249 80↵
248 81↵
249 81↵
248 82↵
249 82↵
248 83↵
249 83↵
248 84↵
249 84↵
248 85↵
249 85↵
248 86↵
249 86↵
248 87↵
249 87↵
248 88↵
249 88↵
248 89↵
249 89↵
248 90↵
249 90↵
248 91↵
249 91↵
248 92↵
249 92↵
248 93↵
249 93↵
248 94↵
249 94↵
248 95↵
249 95↵
248 96↵
249 96↵
248 97↵
249 97↵
248 98↵
249 98↵
248 99↵
249 99↵
248 100↵
249 100↵
248 101↵
249 101↵
248 102↵
249 102↵
248 103↵
249 103↵
248 104↵
249 104↵
248 105↵
249 105↵
248 106↵
249 106↵
248 107↵
249 107↵
248 108↵
249 108↵
248 109↵
249 109↵
248 110↵
249 110↵
248 111↵
249 111↵
248 112↵
249 112↵
248 113↵
249 113↵
248 114↵
249 114↵
248 115↵
249 115↵
248 116↵
249 116↵
248 117↵
249 117↵
248 118↵
249 118↵
248 119↵
249 119↵
248 120↵
249 120↵
248 121↵
249 121↵
248 122↵
249 122↵
248 123↵
249 123↵
248 124↵
249 124↵
248 125↵
249 125↵
248 126↵
249 126↵
248 127↵
249 127↵
248 128↵
249 128↵
248 129↵
249 129↵
248 130↵
249 130↵
248 131↵
249 131↵
248 132↵
249 132↵
248 133↵
249 133↵
248 134↵
249 134↵
248 135↵
249 135↵
248 136↵
249 136↵
248 137↵
249 137↵
248 138↵
249 138↵
248 139↵
249 139↵
248 140↵
249 140↵
248 141↵
249 141↵
248 142↵
249 142↵
248 143↵
249 143↵
248 144↵
249 144↵
248 145↵
249 145↵
248 146↵
249 146↵
248 147↵
249 147↵
248 148↵
249 148↵
248 149↵
249 149↵
248 150↵
249 150↵
248 151↵
249 151↵
248 152↵
249 152↵
248 153↵
249 153↵
248 154↵
249 154↵
248 155↵
249 155↵
248 156↵
249 156↵
248 157↵
249 157↵
248 158↵
249 158↵
248 159↵
249 159↵
248 160↵
249 160↵
248 161↵
249 161↵
248 162↵
249 162↵
248 163↵
249 163↵
248 164↵
249 164↵
248 165↵
249 165↵
248 166↵
249 166↵
248 167↵
249 167↵
248 168↵
249 168↵
248 169↵
249 169↵
248 170↵
249 170↵
248 171↵
249 171↵
248 172↵
249 172↵
248 173↵
249 173↵
248 174↵
249 174↵
248 175↵
249 175↵
248 176↵
249 176↵
248 177↵
249 177↵
248 178↵
249 178↵
248 179↵
249 179↵
248 180↵
249 180↵
248 181↵
249 181↵
248 182↵
249 182↵
248 183↵
249 183↵
248 184↵
249 184↵
248 185↵
249 185↵
248 186↵
249 186↵
248 187↵
249 187↵
248 188↵
249 188↵
248 189↵
249 189↵
248 190↵
249 190↵
248 191↵
249 191↵
248 192↵
249 192↵
248 193↵
249 193↵
248 194↵
249 194↵
248 195↵
249 195↵
248 196↵
249 196↵
248 197↵
249 197↵
248 198↵
249 198↵
248 199↵
249 199↵
248 200↵
249 200↵
248 201↵
249 201↵
248 202↵
249 202↵
248 203↵
249 203↵
248 204↵
249 204↵
248 205↵
249 205↵
248 206↵
249 206↵
248 207↵
249 207↵
248 208↵
249 208↵
248 209↵
249 209↵
248 210↵
249 210↵
248 211↵
249 211↵
248 212↵
249 212↵
248 213↵
249 213↵
248 214↵
249 214↵
248 215↵
249 215↵
248 216↵
249 216↵
248 217↵
249 217↵
248 218↵
249 218↵
248 219↵
249 219↵
248 220↵
249 220↵
248 221↵
249 221↵
248 222↵
249 222↵
248 223↵
249 223↵
248 224↵
249 224↵
248 225↵
249 225↵
248 226↵
249 226↵
248 227↵
249 227↵
248 228↵
249 228↵
248 229↵
249 229↵
248 230↵
249 230↵
248 231↵
249 231↵
248 232↵
249 232↵
248 233↵
249 233↵
248 234↵
249 234↵
248 235↵
249 235↵
248 236↵
249 236↵
248 237↵
249 237↵
248 238↵
249 238↵
248 239↵
249 239↵
248 240↵
249 240↵
248 241↵
249 241↵
248 242↵
249 242↵
248 243↵
249 243↵
248 244↵
249 244↵
248 245↵
249 245↵
248 246↵
249 246↵
248 247↵
249 247↵
~~~~~↵
</spoiler>↵
↵
Edit: I used the `model_solution/solution.cpp` file, apparantly it works on other solutions.↵
↵
Edit: This testcase also breaks some people's solutions, [https://oj.uz/submission/1372712](https://oj.uz/submission/1372712) for example.
