1799A - Recent Actions - 800

1799A - Recent Actions (data structures, greedy, implementation, math, 800)

Explanation

On Codeforces, the “Recent Actions” field shows the last n posts with recent actions. Initially, there are posts numbered 1 to n in the field, in order from top to bottom. There are also infinitely many posts not in the field, numbered with integers n+1, n+2, and so on.

When a recent action happens in post p:

• If it is in the “Recent Actions” field, it moves from its position to the top position.
• Otherwise, it is added to the top position, and the post in the bottom position is removed from the “Recent Actions” field.

You know that the next m recent actions (Note, that recent actions only happen with posts with numbers ≥+1.) will happen in the posts p1, p2, ..., pm (n+1 ≤ pi ≤ n+m) at moments of time 1, 2, ..., m. Note that recent actions only happen with posts with numbers ≥ n+1.

For each post i (1 ≤ i ≤ n), find the first time it will be removed from the “Recent Actions” field or say that it won’t be removed.

Example

Analyze example #7:

Input:

3 5
4 5 5 5 4

Consider there is only one test case with n = 3 and m = 5.

The recent actions are p1 = 4, p2 = 5, p3 = 5, p4 = 5, p5 = 4.

Initial state of the “Recent Actions” field: [1, 2, 3].

1. At moment 1 (post 4):

   • Post 4 is not in the “Recent Actions” field. So, it is added to the top position, and the post at the bottom (post 3) is removed.
   • “Recent Actions” field becomes [4, 1, 2].

2. At moment 2 (post 5):

   • Post 5 is not in the “Recent Actions” field. So, it is added to the top position, and the post at the bottom (post 2) is removed.
   • “Recent Actions” field becomes [5, 4, 1].

3. At moment 3 (post 5):

   • Post 5 is already in the “Recent Actions” field. So, it moves to the top position.
   • “Recent Actions” field remains [5, 4, 1].

4. At moment 4 (post 5):

   • Post 5 is already in the “Recent Actions” field. So, it moves to the top position.
   • “Recent Actions” field remains [5, 4, 1].

5. At moment 5 (post 4):

   • Post 4 is already in the “Recent Actions” field. So, it moves to the top position.
   • “Recent Actions” field becomes [4, 5, 1].

In this example, post 1 is never removed, post 2 is removed at moment 2, and post 3 is removed at moment 1. m As initial “Recent Actions” was [1,2,3], the output for this input would be: -1 2 1

Logic

1. Initialize an array tracked_data of size n with all elements set to -1.
   1. This array will be a result array. Set -1 for all elements setting initially that no one element will be removed.
2. Initialize an array recent_posts to keep track on current “recent actions”.
3. Iterate through posts that got from output.
   1. If post is already in recent_posts, it means no need to remove anything, move this “found” post to index 0 and shift other elements in recent_posts.
   2. If post is not in recent_posts, then
      1. add it to index 0 of recent_posts and remove “last” post from recent_posts.
      2. if “last” post in recent_posts is <=n that means that it is to be removed. In tracked_data set current moment when it is removed.
4. Print tracked_data

Solution

This solution works but slow:

def solve():
    n, m = list(map(int, inp().split()))
    posts = list(map(int, inp().split()))
    tracked_data = [-1] * n

    recent_posts = list(range(1, n+1))

    for moment, post in enumerate(posts, 1):
        if post in recent_posts:
            idx = recent_posts.index(post)
            recent_posts = [post] + recent_posts[0:idx] + recent_posts[idx+1:]
        else:
            
            last = recent_posts[-1] # set at what moment removed
            if last <= n:
                tracked_data[last-1] = moment
            if post <= n:
                tracked_data[post-1] = -1
            recent_posts = [post] + recent_posts[0:-1]

    print(*tracked_data)

for _ in range(int(inp())):
    solve()

As a result no need to keep recent_posts always uptodate. We need to follow for the posts that are in range<=n.

All what we need is:

1. to keep last post index to know what post is going to be removed. No need to rearrange array for this.
2. keep data on “already used” posts.

Optimized solution

def solve():
    n, m = list(map(int, input().split()))
    posts = list(map(int, input().split()))
    tracked_data = [-1] * n

    last = n-1
    used_posts = set()
    for moment, post in enumerate(posts, 1):
        if post not in used_posts:
            if last >= 0:
                tracked_data[last] = moment
                last -= 1
                used_posts.add(post)
    print(*tracked_data)


for _ in range(int(input())):
    solve()