mukundagarawal9's blog

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

By mukundagarawal9, history, 28 hours ago, In English

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 .

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
28 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

hint:

dsu
→ Reply
»
25 hours ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply