Problem:
 Score : 500 points    Problem Statement Snuke, who loves animals, built a zoo.  There are N animals in this zoo. They are conveniently numbered 1 through N , and arranged in a circle.
The animal numbered i (2≤i≤N-1) is adjacent to the animals numbered i-1 and i+1 . Also, the animal numbered 1 is adjacent to the animals numbered 2 and N , and the animal numbered N is adjacent to the animals numbered N-1 and 1 .  There are two kinds of animals in this zoo: honest sheep that only speak the truth, and lying wolves that only tell lies.  Snuke cannot tell the difference between these two species, and asked each animal the following question: "Are your neighbors of the same species?" The animal numbered i answered s_i . Here, if s_i is o , the animal said that the two neighboring animals are of the same species, and if s_i is x , the animal said that the two neighboring animals are of different species.  More formally, a sheep answered o if the two neighboring animals are both sheep or both wolves, and answered x otherwise.
Similarly, a wolf answered x if the two neighboring animals are both sheep or both wolves, and answered o otherwise.  Snuke is wondering whether there is a valid assignment of species to the animals that is consistent with these responses. If there is such an assignment, show one such assignment. Otherwise, print -1 .      Constraints  3 ≤ N ≤ 10^{5}  s is a string of length N consisting of o and x .         Input The input is given from Standard Input in the following format:  N  s       Output If there does not exist an valid assignment that is consistent with s , print -1 .
Otherwise, print an string t in the following format. The output is considered correct if the assignment described by t is consistent with s .   t is a string of length N consisting of S and W .  If t_i is S , it indicates that the animal numbered i is a sheep. If t_i is W , it indicates that the animal numbered i is a wolf.         Sample Input 1 6
ooxoox      Sample Output 1 SSSWWS  For example, if the animals numbered 1 , 2 , 3 , 4 , 5 and 6 are respectively a sheep, sheep, sheep, wolf, wolf, and sheep, it is consistent with their responses. Besides, there is another valid assignment of species: a wolf, sheep, wolf, sheep, wolf and wolf.  Let us remind you: if the neiboring animals are of the same species, a sheep answers o and a wolf answers x . If the neiboring animals are of different species, a sheep answers x and a wolf answers o .          Sample Input 2 3
oox      Sample Output 2 -1  Print -1 if there is no valid assignment of species.       Sample Input 3 10
oxooxoxoox      Sample Output 3 SSWWSSSWWS

Solution (Python):
from collections import defaultdict


def solve(s, l):
    for now in range(1, len(s) + 1):
        now %= len(s)
        pre = now - 1
        nex = (now + 1) % len(s)

        
        if l[pre] is not None and l[nex] is not None:
            if l[now] == 1:
                if s[now] == "o":
                    if l[nex] != l[pre]:
                        return False
                else:
                    if l[nex] == l[pre]:
                        return False
            else:
                if s[now] == "o":
                    if l[nex] == l[pre]:
                        return False
                else:
                    if l[nex] != l[pre]:
                        return False

        
        if l[pre] is not None and l[nex] is None:
            
            if l[now] == 1:
                
                if s[now] == "o":
                    l[nex] = l[pre]

                
                else:
                    l[nex] = -1 * l[pre]
            
            else:
                
                if s[now] == "o":
                    l[nex] = -1 * l[pre]
                
                else:
                    l[nex] = l[pre]

    return True


def main():
    N = int(input())
    S = input()

    for a, b in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:
        ans = [None] * N
        ans[0], ans[1] = a, b

        if solve(S, ans):
            print(*["S" if x == 1 else "W" for x in ans], sep="")
            return

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
n =int(input())
s = input()
s = list(s)
for i in range(len(s)):
    if s[i] =='o':
        s[i] = int(1)
    else:
        s[i] = int(-1)

syoki_list = [[1,1],[1,-1],[-1,1],[-1,-1]]
a = "-1"
for i in range(len(syoki_list)):
    t = []
    t.append(syoki_list[i][0])
    t.append(syoki_list[i][1])
    for j in range(2,n+1):
        t.append(t[j-2] * t[j-1] * s[j-1])
    if t[0] == t[n] and t[1] == t[n-1] * t[n]*s[0]:
        for i in range(n+1):
            if t[i] == 1:
                t[i] = "S"
            else:
                t[i] = "W"
        a= "".join(t[:n])
        break

print(a)

Solution (Python):
import itertools
N = int(input())
s = list(map(lambda x: True if x == "o" else False, list(input())))

f = lambda x,y: not(x^y)

def hantei(N,s):
    for onetwo in itertools.product((True, False), (True, False)):
        res = {}
        for n in range(N):
            if n == 0:
                res[n] = onetwo[0]
            elif n == 1:
                res[n] = onetwo[1]
            else:
                res[n] = f(res[n-2], f(res[n-1], s[n-1]))
        
        if not ((res[1] == res[N-1]) ^ res[0]) == s[0]:
            if not ((res[0] == res[N-2]) ^ res[N-1]) == s[N-1]:
                print(''.join(map(lambda x: "S" if x == True else "W", res.values())))
                return True

    return False

if not hantei(N, s):
    print(-1)

Solution (Python):


import sys
N = int(input())
ipt = list(input())
stR = ["S" for i in range(N)]

def sheep(stg):
     return stg
def wolf(stg):
    if stg == "S":
        return "W"
    else:
        return "S"
def modN (i):
    return i%N
def check ( num1,num2 ):
    stR[0]=num1
    stR[1]=num2
    for i in range(N+2):
        if stR[modN(i+1)] == "S" and ipt[modN(i+1)]=="o"  :
            stR[modN(i+2)]=sheep(stR[modN(i)])
        elif stR[modN(i+1)] == "W" and ipt[modN(i+1)]=="x":
            stR[modN(i+2)]=sheep(stR[modN(i)])
        else:
            stR[modN(i+2)]=wolf(stR[modN(i)])
    
    if stR[0]==num1 and stR[1]==num2:
        print("".join(stR))
        return True
    else:
        return False

if check("S","W"):
    sys.exit()
else:
    
    if check("W","W"):
        sys.exit()
    else:
        
        if check("W","S"):
            sys.exit()
        else:
            
            if check("S","S"):
                sys.exit()
            else:
                print(-1)

Solution (Python):
N = int(input())
t = list(input())
Ans = ['n' for _ in t]
 
def judge(prevSW, SW, ox):
    if SW == 'S':
        if ox == 'o':
            return prevSW
        else:
            if prevSW == 'S':
                return 'W'
            else: return 'S'
    elif SW == 'W':
        if ox == 'x':
            return prevSW
        else:
            if prevSW == 'S':
                return 'W'
            else: return 'S'
 
def decideorder(startSW):
    Ans[1] = startSW
    for i in range(2,N):
        Ans[i] = judge(Ans[i-2], Ans[i-1], t[i-1])

def check():
    if judge(Ans[-2], Ans[-1], t[-1]) is Ans[0] and judge(Ans[-1], Ans[0], t[0]) is Ans[1]:
        return True
    else:
        return False

Ans[0] = 'S'
decideorder('S')
if check():
    print("".join(Ans))
else:
    decideorder('W')
    if check():
        print("".join(Ans))
    else:
        Ans[0] = 'W'
        decideorder('S')
        if check():
            print("".join(Ans))
        else:
            decideorder('W')
            if check():
                print("".join(Ans))
            else:
                print(-1)

Solution (Python):




from itertools import product

N = int(input())
s = list(input())
assert N == len(s)

def solve(type_b, type_n, ox_n, s=s):
    pass



solve = {"WSo": "W",
         "SSx": "W",
         "WSx": "S",
         "SSo": "S",
         "WWx": "W",
         "SWo": "W",
         "WWo": "S",
         "SWx": "S"}

answer = -1

for n0, n1 in product("SW", "SW"):
    animals = [0 for n in range(N)]
    animals[0] = n0
    animals[1] = n1
    for i in range(2, N):
        animals[i] = solve["{}{}{}".format(animals[i-2], animals[i-1], s[i-1])]
    if solve["{}{}{}".format(animals[-2], animals[-1], s[-1])] == n0 and solve["{}{}{}".format(animals[-1], animals[0], s[0])] == n1:
        answer = ""
        for animal in animals:
            answer += animal

print(answer)

Solution (Python):
N = int(raw_input())
s = raw_input()
def opp(a):
	return 'S' if a == 'W' else 'W'
def det(a0, a1):
	ap = a0
	ac = a1
	ans = a0

	for c in s[1:]+s[:2]:
		ans += ac
		if (c == 'o' and ac == 'S') or (c == 'x' and ac == 'W'):
			an = ap
		else:
			an = opp(ap)
		ap = ac
		ac = an
	if ans[-2:] == ans[:2]:
		return ans[:-2]
	else:
		return None
for pref in ["SS", "SW", "WW", "WS"]:
	ans = det(pref[0], pref[1])
	if ans:
		break
print -1 if not ans else ans

Solution (Python):
import sys

sys.setrecursionlimit(int(2E5))

SHEEP = True
WOLF = False


def print_tree(tree):
    print(''.join(['S' if e else 'W' for e in tree]))


def calc_next_animal(tree, cur_pos):
    if answer[cur_pos]:
        if tree[cur_pos] == SHEEP:
            return tree[cur_pos - 1]
        else:
            return not tree[cur_pos - 1]
    else:
        if tree[cur_pos] == SHEEP:
            return not tree[cur_pos - 1]
        else:
            return tree[cur_pos - 1]


def calc_prev_animal(tree, cur_pos):
    if answer[cur_pos]:
        if tree[cur_pos] == SHEEP:
            return tree[cur_pos + 1]
        else:
            return not tree[cur_pos + 1]
    else:
        if tree[cur_pos] == SHEEP:
            return not tree[cur_pos + 1]
        else:
            return tree[cur_pos + 1]


def wfs(tree, cur_pos, N):
    tree[cur_pos + 1] = calc_next_animal(tree, cur_pos)
    cur_pos += 1
    if cur_pos == N - 1:
        return tree[0] == calc_next_animal(tree, cur_pos) and tree[cur_pos] == calc_prev_animal(tree, 0)
    else:
        return wfs(tree, cur_pos, N)


if __name__ == '__main__':
    N = int(input())
    answer = [True if i == 'o' else False for i in input().rstrip()]
    aa = [[WOLF, WOLF]
        , [WOLF, SHEEP]
        , [SHEEP, SHEEP]
        , [SHEEP, WOLF]]
    super_list = [0] * int(2E5)
    for a in aa:
        super_list[:2] = a
        if wfs(super_list, 1, N):
            print_tree(super_list[:N])
            break
    else:
        print(-1)

Solution (Python):
N = int(raw_input())
s = raw_input()
assert(3 <= N <= 1e5)
assert(len(s) == N)

res = []
sheep = 'S'
wolf = 'W'
container = [val for val in s]
o = 'o'
x = 'x'
passed = False
res0 = [sheep, sheep]
res1 = [sheep, wolf]
res2 = [wolf, sheep]
res3 = [wolf, wolf]
RES = [res0, res1, res2, res3]
for res in RES:
    passed1 = False
    passed2 = False
    for i in xrange(1, len(container) - 1):
        val = container[i]
        if res[i] == sheep:
            if val == o:
                res.append(res[i - 1])
            else:
                if res[i - 1] == sheep:
                    res.append(wolf)
                else:
                    res.append(sheep)
        else:
            if val == o:
                if res[i - 1] == sheep:
                    res.append(wolf)
                else:
                    res.append(sheep)
            else:
                res.append(res[i - 1])
    if (res[0] == sheep):
        if (container[0] == o) and (res[-1] == res[1]):
            passed1 = True
        elif (container[0] == x) and (not (res[-1] == res[1])):
            passed1 = True
    else:
        if (container[0] == o) and (not (res[-1] == res[1])):
            passed1 = True
        elif (container[0] == x) and (res[-1] == res[1]):
            passed1 = True

    if (res[-1] == sheep):
        if (container[-1] == o) and (res[-2] == res[0]):
            passed2 = True
        elif (container[-1] == x) and (not (res[-2] == res[0])):
            passed2 = True
    else:
        if (container[-1] == o) and (not (res[-2] == res[0])):
            passed2 = True
        elif (container[-1] == x) and (res[-2] == res[0]):
            passed2 = True
    if passed1 and passed2:
        passed = True
        break

if passed:
    print ''.join(res)
else:
    print -1

Solution (Python):
from itertools import product as prod

n = int(input())
ss = list(input())

def next_anim(a_0, a_1, s):
    if s == "o":
        if a_1 == "S":
            return a_0
        else:
            return "W" if a_0 == "S" else "S"
    else:
        if a_1 == "S":
            return "W" if a_0 == "S" else "S"
        else:
            return a_0

ans = -1
anims = ["" for _ in range(n)]
for fst, snd in prod(["W", "S"], repeat=2):
    anims[:2] = [fst, snd]
    for i in range(2, n):
        anims[i] = next_anim(anims[i-2], anims[i-1], ss[i-1])
    tmp_anim = next_anim(snd, fst, ss[0])
    tmp_anim2 = next_anim(anims[-2], anims[-1], ss[-1])
    if tmp_anim == anims[-1] and tmp_anim2 == anims[0]:
        ans = "".join(anims)
        break

print(ans)

Solution (Python):
import itertools
N = int(input())
s = list(input())

def hantei(N,s):
    for onetwo in itertools.product((0, 1), (0, 1)):
        res = {}
        for n in range(N):
            if n == 0:
                res[n] = onetwo[0]
            elif n == 1:
                res[n] = onetwo[1]
            else:
                if res[n-1] == 0 and s[n-1] == "o":
                    res[n] = res[n-2]
                elif res[n-1] == 0 and s[n-1] == "x":
                    res[n] = 1 if res[n-2] == 0 else 0
                elif res[n-1] == 1 and s[n-1] == "o":
                    res[n] = 1 if res[n-2] == 0 else 0
                elif res[n-1] == 1 and s[n-1] == "x":
                    res[n] = res[n-2]
        
        if (res[1] == res[N-1]) and res[0] == 0 and s[0] == "x":
            continue
        if (res[1] == res[N-1]) and res[0] == 1 and s[0] == "o":
            continue
        if (res[1] != res[N-1]) and res[0] == 0 and s[0] == "o":
            continue
        if (res[1] != res[N-1]) and res[0] == 1 and s[0] == "x":
            continue
        
        if (res[0] == res[N-2]) and res[N-1] == 0 and s[N-1] == "x":
            continue
        if (res[0] == res[N-2]) and res[N-1] == 1 and s[N-1] == "o":
            continue
        if (res[0] != res[N-2]) and res[N-1] == 0 and s[N-1] == "o":
            continue
        if (res[0] != res[N-2]) and res[N-1] == 1 and s[N-1] == "x":
            continue

        print(''.join(map(lambda x: "S" if x == 0 else "W", res.values())))
        return True

    return False

if not hantei(N, s):
    print(-1)

Solution (Python):

def getLnInputs():
    return input().split()


def getLnIntInputs():
    return list(map(int, getLnInputs()))


def is_next_sheep(isCurrentSheep, response, isPreviousSheep):
    isNextSame = not (isCurrentSheep ^ response)
    return not (isNextSame ^ isPreviousSheep)


def resolve_hypothesis(firstIsSheep, lastIsSheep, responseArray):
    res_str = "S" if firstIsSheep else "W"

    isCurrentSheep = firstIsSheep
    isPreviousSheep = lastIsSheep

    for i in range(len(responseArray) - 1):
        isNextSheep = is_next_sheep(isCurrentSheep, responseArray[i], isPreviousSheep)
        res_str += "S" if isNextSheep else "W"
        isCurrentSheep, isPreviousSheep = isNextSheep, isCurrentSheep

    if isCurrentSheep != lastIsSheep or is_next_sheep(isCurrentSheep, responseArray[-1], isPreviousSheep) != firstIsSheep:
        return -1

    return res_str


def main():
    input()
    s = input()

    responseArray = list(map(lambda c: c == "o", list(s)))

    for i in range(2):
        for j in range(2):
            firstIsSheep = bool(i)
            lastIsSheep = bool(j)
            res = resolve_hypothesis(firstIsSheep, lastIsSheep, responseArray)

            if res == -1:
                continue

            print(res)
            return

    print(-1)
    return


main()

Solution (Python):
import sys

N = int(input())
stemp = input()
s = [True if stemp[i]== 'o' else False for i in range(N)]

T = [True, True] 

for i in range(2,N+1):
    if s[i-1]^T[i-1]==True:
        T.append( not T[i-2])
    else:
        T.append( T[i-2])

if T[N] == T[0] and ((T[1]==T[N-1]) != (T[0] != s[0])):
    output = ['S' if T[i] == True else 'W' for i in range(N)]
    for i in range(N):
        print(output[i], end='')
    print()
    sys.exit()

T = [True, False] 

for i in range(2,N+1):
    if s[i-1]^T[i-1]==True:
        T.append( not T[i-2])
    else:
        T.append( T[i-2])

if T[N] == T[0] and ((T[1]==T[N-1]) != (T[0] != s[0])):
    output = ['S' if T[i] == True else 'W' for i in range(N)]
    for i in range(N):
        print(output[i], end='')
    print()
    sys.exit()

T = [False, True] 

for i in range(2,N+1):
    if s[i-1]^T[i-1]==True:
        T.append( not T[i-2])
    else:
        T.append( T[i-2])

if T[N] == T[0] and ((T[1]==T[N-1]) != (T[0] != s[0])):
    output = ['S' if T[i] == True else 'W' for i in range(N)]
    for i in range(N):
        print(output[i], end='')
    print()
    sys.exit()

T = [False, False]

for i in range(2,N+1):
    if s[i-1]^T[i-1]==True:
        T.append( not T[i-2])
    else:
        T.append( T[i-2])

if T[N] == T[0] and ((T[1]==T[N-1]) != (T[0] != s[0])):
    output = ['S' if T[i] == True else 'W' for i in range(N)]
    for i in range(N):
        print(output[i], end='')
    print()
    sys.exit()

print(-1)

Solution (Python):
n = int(input())
s = input()

sw = [1,0]
ss = [1,1]
ws = [0,1]
ww = [0,0]

def nxt(tf, last):
    if tf=='x' and last=='S':
        return ''

for idx,c in enumerate(s):
    if idx==0:
        continue
    if c == 'x':
        sw.append(sw[-1]^sw[-2])
        ss.append(ss[-1]^ss[-2])
        ws.append(ws[-1]^ws[-2])
        ww.append(ww[-1]^ww[-2])
    else:
        sw.append(1*(not(sw[-1]^sw[-2])))
        ss.append(1*(not(ss[-1]^ss[-2])))
        ws.append(1*(not(ws[-1]^ws[-2])))
        ww.append(1*(not(ww[-1]^ww[-2])))

c=s[0]
if c == 'x':
    sw.append(sw[-1]^sw[-2])
    ss.append(ss[-1]^ss[-2])
    ws.append(ws[-1]^ws[-2])
    ww.append(ww[-1]^ww[-2])
else:
    sw.append(1*(not(sw[-1]^sw[-2])))
    ss.append(1*(not(ss[-1]^ss[-2])))
    ws.append(1*(not(ws[-1]^ws[-2])))
    ww.append(1*(not(ww[-1]^ww[-2])))


def f(seq):
    
    return seq[-2:]==seq[:2]

def pp(seq):
    print(''.join(map(lambda x:'S' if x else 'W', seq[:-2])))

if f(sw):
    pp(sw)
elif f(ss):
    pp(ss)
elif f(ws):
    pp(ws)
elif f(ww):
    pp(ww)
else:
    print(-1)

Solution (Python):
from collections import defaultdict


def solve(s, l):

    for i in range(1, len(s) - 1):
        
        if l[i] == 1:
            if s[i] == "o":
                l[i + 1] = l[i - 1]
            else:
                l[i + 1] = -1 * l[i - 1]
        
        else:
            if s[i] == "o":
                l[i + 1] = -1 * l[i - 1]
            else:
                l[i + 1] = l[i - 1]

    if l[0] == 1:
        if s[0] == "o":
            ok1 = l[1] == l[-1]
        else:
            ok1 = l[1] != l[-1]
    
    else:
        if s[0] == "o":
            ok1 = l[1] != l[-1]
        else:
            ok1 = l[1] == l[-1]

    if l[-1] == 1:
        if s[-1] == "o":
            ok2 = l[0] == l[-2]
        else:
            ok2 = l[0] != l[-2]
    
    else:
        if s[-1] == "o":
            ok2 = l[0] != l[-2]
        else:
            ok2 = l[0] == l[-2]

    return ok1 and ok2

def main():
    N = int(input())
    S = input()
    ans = [None] * N
    ans[0] = 1
    ans[1] = 1
    if solve(S, ans):
        print(*["S" if x == 1 else "W" for x in ans], sep="")
        return

    ans = [None] * N
    ans[0] = 1
    ans[1] = -1
    if solve(S, ans):
        print(*["S" if x == 1 else "W" for x in ans], sep="")
        return

    ans = [None] * N
    ans[0] = -1
    ans[1] = 1
    if solve(S, ans):
        print(*["S" if x == 1 else "W" for x in ans], sep="")
        return

    ans = [None] * N
    ans[0] = -1
    ans[1] = -1
    if solve(S, ans):
        print(*["S" if x == 1 else "W" for x in ans], sep="")
        return

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(raw_input())
s = raw_input()

D = ["SS", "SW", "WS", "WW"]
A = "SW"

s += s[0]
for d in D:
    a = d
    for i in range(1, N+1):
        k = 0
        if a[i] == "W":
            k += 1
        if s[i] == "x":
            k += 1
        if a[i-1] == "W":
            k += 1
        a += A[k % 2]
    if a[:2] == a[-2:]:
        print a[:-2]
        exit()
print -1