Trying to solve The Bovine Shuffle from USACO Silver December 2017 Contest. Problem link here: https://usaco.org/index.php?page=viewproblem2&cpid=764
Testcases 3,5, & 7 are giving wrong answer. I cannot find out why.
My approach is to use the floyd cycle detection algorithm to count the number of elements in a cycle in the functional graph componennts.
On all 3 testcases, my code is giving an output that is 1 more than the correct answer, e.g. for testcase 3 the correct answer is 26, but my code is outputting 27.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector <string> vs;
typedef pair<int, int> pii;
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define endl "\n"
int floyd(int start, vb& visited, vi& next) {
vb on_stack(visited.size());
int a = start;
int b;
a = next[a];
b = next[a];
while(a!=b && (on_stack[a] || !visited[a]) && (on_stack[b] || !visited[b])) {
on_stack[a] = true;
on_stack[b] = true;
visited[a] = true;
visited[b] = true;
a = next[a];
b = next[next[b]];
}
int c = start;
while(c!=b && (on_stack[c] || !visited[c]) && (on_stack[b] || !visited[b])) {
on_stack[c] = true;
on_stack[b] = true;
visited[b] = true;
visited[c] = true;
b = next[b];
c = next[c];
}
if(!((on_stack[c] || !visited[c]) && (on_stack[b] || !visited[b]) && (on_stack[a] || !visited[a]))) {
return -1;
}
return c;
}
int main() {
freopen("shuffle.in", "r", stdin);
// the following line creates/overwrites the output file
freopen("shuffle.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vi next(n);
for(int i = 0; i < n; i++) {
cin >> next[i];
next[i]--;
}
vb visited(n);
int res = 0;
for(int i = 0; i < n; i++) {
int orig_c = floyd(i, visited, next);
if(orig_c==-1) {
continue;
}
int c = next[orig_c];
res++;
while(c!=orig_c) {
c = next[c];
res++;
}
}
cout << res << endl;
return 0;
}
Testcase 3:
Input:
600
414 527 92 381 357 274 63 171 197 482 106 526 285 328 537 306 47 130 314 258 325 496 583 346 15 568 435 165 244 351 488 409 277 579 189 385 4 252 555 200 133 61 477 169 140 413 227 187 295 540 196 371 435 179 468 202 498 303 118 493 53 357 302 81 87 242 466 90 245 420 41 130 232 518 298 372 82 276 310 128 568 257 498 154 187 366 107 84 420 225 329 472 333 30 304 420 271 169 509 516 341 550 397 324 219 446 447 52 122 156 180 89 165 429 242 351 194 101 435 365 325 515 588 57 544 292 228 566 460 137 233 552 438 29 276 408 475 122 459 596 30 38 436 194 219 429 544 412 529 130 177 5 44 164 414 339 207 41 305 419 529 289 370 118 318 397 525 544 271 384 291 300 173 126 245 391 306 540 555 587 70 483 343 465 398 508 556 5 549 12 423 229 300 544 347 369 341 23 312 11 406 2 62 331 479 306 121 537 245 427 523 66 309 17 283 459 525 238 463 225 1 37 453 300 580 551 69 72 574 132 82 131 134 495 461 364 200 582 300 197 160 574 14 469 591 296 327 267 285 541 491 285 577 343 337 308 46 157 380 19 288 213 149 173 460 10 537 411 343 588 7 502 314 373 122 56 420 200 322 105 140 212 141 468 306 229 528 351 385 59 121 425 23 270 597 482 31 285 293 373 273 51 26 586 423 500 41 243 99 114 99 591 325 591 210 382 220 137 133 356 195 5 180 570 274 177 451 56 461 143 180 485 194 206 222 368 105 14 362 555 127 460 545 203 203 507 585 422 43 469 529 590 473 109 559 499 37 409 554 249 304 134 134 249 91 355 368 547 369 130 501 247 589 198 450 191 104 434 364 498 54 293 487 526 153 197 176 189 358 130 437 61 15 322 61 105 429 428 51 549 557 303 195 298 500 44 240 3 229 4 501 282 48 139 560 552 336 135 140 93 16 328 505 30 50 565 486 230 144 536 178 101 239 372 150 490 168 389 493 396 144 145 430 191 283 141 142 370 27 33 462 43 361 118 424 162 82 310 391 226 597 568 78 235 91 227 125 258 15 369 406 159 513 587 101 547 127 595 317 153 379 530 547 491 48 371 52 481 432 194 458 428 513 287 415 356 513 291 13 280 411 170 190 75 156 42 21 34 388 89 539 167 371 485 57 418 7 461 50 438 406 260 18 319 546 184 74 459 474 438 490 284 8 79 358 515 472 130 301 260 219 239 426 589 475 234 158 482 94 559 71 500 218 440 570 164 23 395 374 248 232 263 283 591 93 392 258 316 522 558 575 492 548 152 232 422 138 141 55 231 99 126 482 317 317 203 232 340 597 5 339 581 19 22 571 463 413 580 178 86
CORRECT OUTPUT: 26
my output: 27