qhung312's blog

Need help with 1345C
By qhung312, history, 5 years ago, In English

1345C - Hilbert's Hotel requires you to check if all (i + arr[i]) % n is distinct, so I did:

for (int i = 0; i < n; i++) {
  ll x;
  cin >> x;
  arr[i] = (i + x) % n;
  s.insert(arr[i]);
}
cout << ((s.size() == n) ? "YES" : "NO") << '\n';

This got WA on test 2, whereas if I change it to:

arr[i] = ((i + x) % n + n) % n;

This got AC. But aren't (i + x) % n and ((i + x) % n + n) % n the same thing?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by qhung312 (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

You need to handle the case when $$$i$$$ $$$+$$$ $$$a[i]$$$ is negative.

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

(i+x) can be negative and C++ will give negative remainder.

((i + x) % n + n) % n here you are changing the negative remainder to positive.

If i + x is positive then (i + x) % n = ((i + x) % n + n) % n

Try running this in c++

cout << (-8)%5 << " " << ((-8)%5+5)%5 << "\n";
cout << (8)%5 << " " << ((8)%5+5)%5;
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

For a positive a[i] : yes, both are same.
(in this problem a[i]=i+a[i])
But when a[i]<0 : -(n-1) <= a[i]%n <=0, to brimg this value in between [0,n) we add +n to this value and take the modulus again to make it lie in the said range.
Ex : -8%5=2 as -8 is 2 ahead of multiple of 5(i.e. -10) but modulus operator will compute this value to be -3, so we add +5 to this and take % with 5 again to get the correct answer!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks. I didn't know the % operator behaved like that for negative numbers, so I was expecting a positive result every time.

    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Because (0-1)%3 equals to -1, so you need to add n.

→ Reply