Nearest Opposite Parity (Codeforces 1272E)
Tags: Others, shortest paths

You are given an array $$$a$$$ consisting of $$$n$$$ integers. In one move, you can jump from the position $$$i$$$ to the position $$$i - a_i$$$ (if $$$1 \le i - a_i$$$) or to the position $$$i + a_i$$$ (if $$$i + a_i \le n$$$).For each position $$$i$$$ from $$$1$$$ to $$$n$$$ you want to know the minimum the number of moves required to reach any position $$$j$$$ such that $$$a_j$$$ has the opposite parity from $$$a_i$$$ (i.e. if $$$a_i$$$ is odd then $$$a_j$$$ has to be even and vice versa).

Input: The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$a$$$.The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

Output: Print $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$, where $$$d_i$$$ is the minimum the number of moves required to reach any position $$$j$$$ such that $$$a_j$$$ has the opposite parity from $$$a_i$$$ (i.e. if $$$a_i$$$ is odd then $$$a_j$$$ has to be even and vice versa) or -1 if it is impossible to reach such a position.


Sample Inputs:
10
4 5 7 6 7 5 4 4 6 4

Sample Outputs:
1 1 1 2 -1 1 1 3 1 1

Solution (Python):
""""""
from sys import stdin, stdout
get_string = lambda : stdin.readline().strip()
get_intmap = lambda : map(int, get_string().split())

def testcase():
    n = int(input())
    adj = [[] for i in range(n + 1)]
    (odd_vertices, even_vertices) = ([], [])
    for (ind, ai) in zip(range(1, n + 1), get_intmap()):
        (ind1, ind2) = (ind - ai, ind + ai)
        if ind1 >= 1:
            adj[ind1].append(ind)
        if ind2 <= n:
            adj[ind2].append(ind)
        if ai % 2 == 1:
            odd_vertices.append(ind)
        else:
            even_vertices.append(ind)
    distance = [-1] * (n + 1)
    for frontier in (even_vertices, odd_vertices):
        used = [0] * (n + 1)
        for v in frontier:
            used[v] = 1
        curr_distance = 0
        nxt = []
        while len(frontier):
            curr_distance += 1
            for u in frontier:
                for v in adj[u]:
                    if not used[v]:
                        used[v] = 1
                        distance[v] = curr_distance
                        nxt.append(v)
            frontier = nxt
            nxt = []
    print(' '.join([str(i) for i in distance[1:]]))
testcase()
quit()
for t in range(int(input())):
    testcase()

Solution (Python):
input()
n = map(int, input().split())
n = list(n)
ans = len(n) * [-1]
a = []
go = [[] for _ in range(len(n))]
for (i, x) in enumerate(n):
    for y in (x, -x):
        y += i
        if y >= 0 and y < len(n):
            if x % 2 != n[y] % 2:
                ans[i] = 1
                a.append(i)
            else:
                go[y].append(i)
while len(a) != 0:
    b = []
    for x in a:
        for y in go[x]:
            if ans[y] == -1:
                ans[y] = ans[x] + 1
                b.append(y)
    a = b
for (i, x) in enumerate(ans):
    ans[i] = str(x)
print(' '.join(ans))

Solution (Python):
input()
n = map(int, input().split())
n = list(n)
ans = len(n) * [-1]
a = []
go = [[] for _ in range(len(n))]
for (i, x) in enumerate(n):
    for y in (x, -x):
        y += i
        if y >= 0 and y < len(n):
            if x % 2 != n[y] % 2:
                ans[i] = 1
                a.append(i)
            else:
                go[y].append(i)
while len(a) != 0:
    b = []
    for x in a:
        for y in go[x]:
            if ans[y] == -1:
                ans[y] = ans[x] + 1
                b.append(y)
    a = b
for (i, x) in enumerate(ans):
    ans[i] = str(x)
print(' '.join(ans))