Hilbert’s Hotel Editorial | Explained | CodeForces

This is another editorial post of the code forces problem Hilbert’s Hotel.

Problem

Hilbert’s Hotel is a very unusual hotel since the number of rooms is infinite! In fact, there is exactly one room for every integer, including zero and negative integers. Even stranger, the hotel is currently at full capacity, meaning there is exactly one guest in every room. The hotel’s manager, David Hilbert himself, decides he wants to shuffle the guests around because he thinks this will create a vacancy (a room without a guest).

For any integer k and positive integer n, let k modn denote the remainder when k is divided by n. More formally, r=kmodn is the smallest non-negative integer such that k−r is divisible by n. It always holds that 0≤known≤n−1. For example, 100mod12=4 and (−1337)mod3=1

Then the shuffling works as follows. There is an array of n integers a0,a1,…,an−1. Then for each integer k, the guest in room k is moved to room number k+akmodn

After this shuffling process, determine if there is still exactly one guest assigned to each room. That is, there are no vacancies or rooms with multiple guests.

Input

Each test consists of multiple test cases. The first line contains a single integer

t (1≤t≤104) — the number of test cases. Next 2t lines contain descriptions of test cases.

The first line of each test case contains a single integer

n (1≤n≤2⋅105) — the length of the array.

The second line of each test case contains n integers

a0,a1,…,an−1 (−109≤ai≤109).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅105

Output

For each test case, output a single line containing “YES” if there is exactly one guest assigned to each room after the shuffling process, or “NO” otherwise. You can print each letter in any case (upper or lower).

Detailed Editorial

As mentioned in the problem, for each integer k (0 ≤ k ≤ ∞), the guest in room k is moved to room number (k+a[k % n]).

We have to determine that after shuffling if there is exactly one guest assigned to each room or not.

We know that (k % n) will always lie between [0, n-1], for assigning every guest to a different rooms every element in the array (a[] % n) should be different.

So, basically we will check that for every element in array a[], the value is different and should lie between [0, n-1] and if this is the situation, collision will never happen.

Code in C++

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ull unsigned long long
#define ld long double
 
#define mod 1000000007
 
int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    
    ll t = 1;
    cin >> t;
    
    while(t--)
    {
        ll n;
        cin >> n;
        
        vector<ll> input(n);
        for(ll i = 0; i < n; i++)
        {
            cin >> input[i];
        }
        
        set<ll> s;
        for(ll i = 0; i < n; i++)
        {
            ll x = i + input[i];
            x = x % n;
            
            if(x < 0) x = x+n;
    
            s.insert(x);
        }
        
        
        if(s.size()!=n) cout<<"NO";
        else cout<<"YES";
        
        cout<<"\n";
    }
    return 0;
}

Hope you love Hilbert’s Hotel Editorial Try these editorial too and Read about BackTracking Here

Leave a Comment

Your email address will not be published. Required fields are marked *