Блог пользователя mukundagarawal9

https://codeforces.me/problemset/problem/2008/D help with this problem

Автор mukundagarawal9, история, 28 часов назад, По-английски

In this problem my approach is — if a element is at the index at which it should be i.e , i == p[i] , then answer of index i is 1 if we have character 0 at this index otherwise if this element is in loop with another element i.e , i == p[p[i]] (for ex — 2,1) , then we will increase the answer at this index if character at this position i and character at position p[i] is 0. Now for rest all elements we can calculate number of zeros excluding previous indexes and fill the number of zeros for their answer. But i my code is giving wrong answer at testcase-2 and the testcase size is large so i cannot get the permutation at this place. my code is — https://codeforces.me/contest/2008/submission/307104614 .
Please help where i am wrong .

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
28 часов назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

hint:

dsu
→ Ответить
»
25 часов назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

A permutation can be partitioned into multiple disjoint cycles. Your solution assumes the given permutation is made up of multiple size 1 or 2 (i == p[i] || i == p[p[i]]) cycles and a big one of size > 2 (in which you count the black nodes with noz). However it fails when you have multiple cycles of size > 2. Here's a testcase:

1
6
2 3 1 5 6 4
000000

the expected output should be 3 3 3 3 3 3, but your solutions prints 6 6 6 6 6 6

→ Ответить