FIXEDPTS - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given N and K, decide if there exists a permutation of [1, N] with exactly K fixed points.
A fixed point is an index i with P_i = i.

EXPLANATION:

Observe that if if N-1 elements are in their places, then the last element must also be in place because it has nowhere else to go.

So, if K = N-1 no solution can exist - if we have N-1 fixed points we’ll also have N.

For every K other than N-1, a solution exists.
One simple construction is as follows:

  • Set P_i = i for 1 \le i \le K.
    This gives us K fixed points.
  • Now, if K = N we’re done.
    Otherwise, because we’re working with K \ne N-1, we must have K \le N-2.
    Since exactly K elements have been placed so far, this means we have at least 2 elements remain.
  • The remaining elements are [K+1, K+2, \ldots, N].
    We can simply rotate this sequence one step, to obtain [N, K+1, \ldots, N-1].
    The final permutation is thus
    [1, 2, \ldots, K, N, K+1, K+2, \ldots, N-1]
    which has exactly K fixed points.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    
    if k == n-1: print('No')
    else: print('Yes')