Divine Array (Codeforces 1602B)
Tags: Others, implementation

Black is gifted with a Divine array $$$a$$$ consisting of $$$n$$$ ($$$1 \le n \le 2000$$$) integers. Each position in $$$a$$$ has an initial value. After shouting a curse over the array, it becomes angry and starts an unstoppable transformation.The transformation consists of infinite steps. Array $$$a$$$ changes at the $$$i$$$-th step in the following way: for every position $$$j$$$, $$$a_j$$$ becomes equal to the number of occurrences of $$$a_j$$$ in $$$a$$$ before starting this step.Here is an example to help you understand the process better:  Initial array:$$$2$$$ $$$1$$$ $$$1$$$ $$$4$$$ $$$3$$$ $$$1$$$ $$$2$$$After the $$$1$$$-st step:$$$2$$$ $$$3$$$ $$$3$$$ $$$1$$$ $$$1$$$ $$$3$$$ $$$2$$$After the $$$2$$$-nd step:$$$2$$$ $$$3$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$2$$$After the $$$3$$$-rd step:$$$4$$$ $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$4$$$...... In the initial array, we had two $$$2$$$-s, three $$$1$$$-s, only one $$$4$$$ and only one $$$3$$$, so after the first step, each element became equal to the number of its occurrences in the initial array: all twos changed to $$$2$$$, all ones changed to $$$3$$$, four changed to $$$1$$$ and three changed to $$$1$$$.The transformation steps continue forever.You have to process $$$q$$$ queries: in each query, Black is curious to know the value of $$$a_x$$$ after the $$$k$$$-th step of transformation.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2000$$$) — the size of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the initial values of array $$$a$$$.The third line of each test case contains a single integer $$$q$$$ ($$$1 \le q \le 100\,000$$$) — the number of queries.Next $$$q$$$ lines contain the information about queries — one query per line. The $$$i$$$-th line contains two integers $$$x_i$$$ and $$$k_i$$$ ($$$1 \le x_i \le n$$$; $$$0 \le k_i \le 10^9$$$), meaning that Black is asking for the value of $$$a_{x_i}$$$ after the $$$k_i$$$-th step of transformation. $$$k_i = 0$$$ means that Black is interested in values of the initial array.It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2000$$$ and the sum of $$$q$$$ over all test cases doesn't exceed $$$100\,000$$$.

Output: For each test case, print $$$q$$$ answers. The $$$i$$$-th of them should be the value of $$$a_{x_i}$$$ after the $$$k_i$$$-th step of transformation. It can be shown that the answer to each query is unique.

Note: The first test case was described ih the statement. It can be seen that:   $$$k_1 = 0$$$ (initial array): $$$a_3 = 1$$$;  $$$k_2 = 1$$$ (after the $$$1$$$-st step): $$$a_1 = 2$$$;  $$$k_3 = 2$$$ (after the $$$2$$$-nd step): $$$a_2 = 3$$$;  $$$k_4 = 1$$$ (after the $$$1$$$-st step): $$$a_6 = 3$$$. For the second test case, Initial array:$$$1$$$ $$$1$$$After the $$$1$$$-st step:$$$2$$$ $$$2$$$After the $$$2$$$-nd step:$$$2$$$ $$$2$$$......It can be seen that:   $$$k_1 = 0$$$ (initial array): $$$a_1 = 1$$$;  $$$k_2 = 1000000000$$$: $$$a_2 = 2$$$; 

Sample Inputs:
2
7
2 1 1 4 3 1 2
4
3 0
1 1
2 2
6 1
2
1 1
2
1 0
2 1000000000

Sample Outputs:
1
2
3
3
1
2

Solution (Python):
import sys
inp = sys.stdin.readline

def solve():
    n = int(inp())
    a = [list(map(int, inp().split()))]
    while True:
        c = [0] * (n + 1)
        for i in a[-1]:
            c[i] += 1
        b = [c[i] for i in a[-1]]
        if b == a[-1]:
            break
        a.append(b)
    ans = []
    for i in range(int(inp())):
        (x, k) = map(int, inp().split())
        ans.append(str(a[min(len(a) - 1, k)][x - 1]))
    print('\n'.join(ans))

def main():
    for i in range(int(inp())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import queue
import math
import sys
import bisect
import string
import collections

def new(x):
    cnt = {i: 0 for i in range(1, n + 1)}
    for i in range(n):
        cnt[x[i]] += 1
    ans = [0 for i in range(n)]
    for i in range(n):
        ans[i] = cnt[x[i]]
    return ans
for _ in range(int(sys.stdin.readline())):
    n = int(input())
    a = list(map(int, sys.stdin.readline().split()))
    q = int(input())
    mem = [a]
    k = new(a)
    ans = []
    while k != mem[-1]:
        mem.append(k)
        k = new(mem[-1])
    mem.append(k)
    for i in range(q):
        (x, y) = map(int, sys.stdin.readline().split())
        if y >= len(mem):
            y = -1
        x -= 1
        ans.append(mem[y][x])
    print(*ans, sep='\n')

Solution (Python):
from collections import defaultdict

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = [a]
    while True:
        counts = defaultdict(int)
        for ele in ans[-1]:
            counts[ele] += 1
        new = []
        for ele in ans[-1]:
            new.append(counts[ele])
        if new == ans[-1]:
            break
        else:
            ans.append(new)
    (q, tot) = (int(input()), [])
    for _ in range(q):
        (x, k) = map(int, input().split())
        if k >= len(ans):
            tot.append(ans[-1][x - 1])
        else:
            tot.append(ans[k][x - 1])
    for ele in tot:
        print(ele)
for i in range(int(input())):
    solve()