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):
N = int(input())
s = input()

def test(bm, b0):
    b = [True] * N
    b[-1] = bm
    b[0] = b0
    for i in range(N - 2):
        b[i + 1] = b[i - 1]
        if b[i] ^ (s[i] == 'o'):
            b[i + 1] = not b[i + 1]
    
    if b[-2] == ((s[-2] == 'o') == (b[-3] == b[-1])) and b[-1] == ((s[-1] == 'o') == (b[-2] == b[0])):
        printB(b)
        return True
    else:
        return False

def printB(b):
    for i in range(N):
        print('S' if b[i] else 'W', end='')
        
    print()
    

def main():
    if test(True, True):
        return
    elif test(True, False):
        return
    elif test(False, True):
        return
    elif test(False, False):
        return

    print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
def not_animal(animal):
    if animal == 'S':
        return 'W'
    return 'S'

def f(prev, animal, ans):
    x = g(animal, ans)
    if not x:
        return not_animal(prev)
    return prev

def g(animal, ans):
    ret = True
    if ans == 'x':
        ret = False

    if animal == 'S':
        return ret
    return not ret
    
def is_equal(x, y):
    return x == (y[0] == y[1])

N = int(input())
s = input()
circles = [['.' for i in range(N)] for i in range(4)]

_init = [('S', 'S'), ('W', 'W'),('S', 'W'), ('W', 'S')]

if s[0] == 'x':
    _init[:2], _init[2:] = _init[2:], _init[:2]

circles[0][0] = circles[1][0] = 'S'
circles[2][0] = circles[3][0] = 'W'

for i in range(4):
    circles[i][1], circles[i][-1] = _init[i]

for i in range(4):
    for j in range(1, N-2):
        circles[i][j+1] = f(circles[i][j-1], circles[i][j], s[j])



for i in range(4):

    for j in range(N):

        if not is_equal(g(circles[i][j], s[j]), (circles[i][j-1], circles[i][(j+1)%N])):
            break
    else:
        print(''.join(circles[i]))
        break
else:
    print(-1)

Solution (Python):
def SW_next(i, s, t):
    if t[i - 1] == 'S':
        if s[i - 1] == 'o':
            if t[i - 2] == 'S':
                return('S')
            else:
                return('W')
        else:
            if t[i - 2] == 'S':
                return('W')
            else:
                return('S')
    else:
        if s[i - 1] == 'o':
            if t[i - 2] == 'S':
                return('W')
            else:
                return('S')
        else:
            if t[i - 2] == 'S':
                return('S')
            else:
                return('W')

def SW_check(n, s, t):
    i = 2
    while i < n:
        t = t + SW_next(i, s, t)
        i += 1
    if t[0] == SW_next(n, s, t):
        tmp_s = [s[n - 1]]
        tmp_s.append(s[0])
        tmp_t = [t[n - 1]]
        tmp_t.append(t[0])
        if t[1] == SW_next(2, tmp_s, tmp_t):
            print(t)
            return(True)
    return(False)

n = int(input())
s = input()

if not SW_check(n, s, 'SS'):
    if not SW_check(n, s, 'SW'):
        if not SW_check(n, s, 'WS'):
            if not SW_check(n, s, 'WW'):
                print(-1)

Solution (Python):
def solve(votes):
    for start in [(1, 1), (1, 0), (0, 1), (0, 0)]:
        a = animals(start, votes)
        if a[:2] == a[-2:]:
            return a


def animals(start, votes):
    rv = [None] * len(votes)
    rv[:2] = start
    for i in range(1, len(votes) - 1):
        rv[i + 1] = rv[i - 1] ^ rv[i] ^ votes[i]
    return tuple(rv)


def parse(s):
    return tuple(int(v == "o") for v in s + s[:2])


def display(s):
    if not s:
        return "-1"
    return "".join("S" if v else "W" for v in s[:-2])


if __name__ == "__main__":
    import sys
    _n = sys.stdin.readline()
    votes = sys.stdin.readline().strip()
    votes = parse(votes)
    sol = solve(votes)
    print(display(sol))


def test_parse():
    assert parse("ooxoox") == (1, 1, 0, 1, 1, 0, 1, 1)


def test_display():
    assert display((1, 1, 0, 0, 7, 7)) == "SSWW"


def test_animals():
    p = object()  
    assert animals((1, 1), (p, 1, p)) == (1, 1, 1)
    assert animals((1, 1), (p, 0, p)) == (1, 1, 0)
    assert animals((0, 1), (p, 1, p)) == (0, 1, 0)
    assert animals((1, 0), (p, 1, p)) == (1, 0, 0)


def test_animals_lex():
    assert animals((1, 1), parse("ooo")) == (1, 1, 1, 1, 1)
    assert animals((1, 1), parse("xxx")) == (1, 1, 0, 1, 1)


def test_solve_atcoder():
    assert display(solve(parse("oox"))) == "-1"
    assert display(solve(parse("ooxoox"))) == "SSSWWS"
    assert display(solve(parse("oxooxoxoox"))) == "SSWWSSSWWS"

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

def fill():
    for i in range(n-2):
        c = s[i]
        if a[i] == 0: 
            if c == 'o':
                a[i+1] = a[i-1]
            else:
                a[i+1] = a[i-1] ^ 1
        else: 
            if c == 'o':
                a[i+1] = a[i-1] ^ 1
            else:
                a[i+1] = a[i-1]

def isTrue(i):
    flag = False
    if a[i] == 0:
        if s[i] == 'o' and a[i-1] == a[(i+1)%n]:
            flag = True
        elif s[i] == 'x' and a[i-1] != a[(i+1)%n]:
            flag = True
    else:
        if s[i] == 'o' and a[i-1] != a[(i+1)%n]:
            flag = True
        elif s[i] == 'x' and a[i-1] == a[(i+1)%n]:
            flag = True
    return flag

def convert():
    ret = ""
    for v in a:
        if v == 0:
            ret += 'S'
        else:
            ret += 'W'
    return ret

a = [0] * n

a[-1] = 0 
a[0]  = 0 
fill()
if isTrue(n-2) and isTrue(n-1):
    print convert()
    exit()

a[-1] = 0 
a[0]  = 1 
fill()
if isTrue(n-2) and isTrue(n-1):
    print convert()
    exit()

a[-1] = 1 
a[0]  = 1 
fill()
if isTrue(n-2) and isTrue(n-1):
    print convert()
    exit()

a[-1] = 1 
a[0]  = 0 
fill()
if isTrue(n-2) and isTrue(n-1):
    print convert()
    exit()

print -1

Solution (Python):
n=int(raw_input())
s=raw_input()
state=[['W','S'],['S','W'],['W','W'],['S','S']]
for now in state:
    for i in xrange(1,n):
        if s[i]=="o":
            if now[i]=="S":
                now.append(now[i-1])
            else:
                if now[i-1]=="S":
                    now.append("W")
                else:
                    now.append("S")
        else:
            if now[i]=="W":
                now.append(now[i-1])
            else:
                if now[i-1]=="S":
                    now.append("W")
                else:
                    now.append("S")
    ok=False
    if now[0]==now[n]:
        if s[0]=="o":
            if now[0]=="S":
                if now[1]==now[n-1]:
                    ok=True
            else:
                if now[1]!=now[n-1]:
                    ok=True
        else:
            if now[0]=="W":
                if now[1]==now[n-1]:
                    ok=True
            else:
                if now[1]!=now[n-1]:
                    ok=True
    if ok:
        print "".join(now[0:n])
        exit()
print -1

Solution (Python):
def solve(n, a):
    honest = [0] * n
    for i0 in range(2):
        for i1 in range(2):
            honest[0] = i0
            honest[1] = i1
            for i in range(1, n-1):
                if honest[i]:
                    if a[i] == 'o':
                        honest[i+1] = honest[i-1]
                    if a[i] == 'x':
                        honest[i+1] = 1 - honest[i-1]
                if not honest[i]:
                    if a[i] == 'o':
                        honest[i+1] = 1 - honest[i-1]
                    if a[i] == 'x':
                        honest[i+1] = honest[i-1]
            ok = True
            if honest[0]:
                if honest[-1] == honest[1]:
                    ok &= a[0] == 'o'
                else:
                    ok &= a[0] == 'x'
            if not honest[0]:
                if honest[-1] == honest[1]:
                    ok &= a[0] == 'x'
                else:
                    ok &= a[0] == 'o'
            
            

            if honest[-1]:
                if honest[-2] == honest[0]:
                    ok &= a[-1] == 'o'
                else:
                    ok &= a[-1] == 'x'
            if not honest[-1]:
                if honest[-2] == honest[0]:
                    ok &= a[-1] == 'x'
                else:
                    ok &= a[-1] == 'o'

            if ok:
                t = 'WS'
                res = ''.join([t[j] for j in honest])
                
                return res
    return -1

n = int(input())
s = input()

res = solve(n, s)
print(res)

Solution (Python):
def opp(ch):
  if ch == "W": return "S"
  if ch == "S": return "W"
def test(th, nb, ans):
  if th == "S":
    if ans == "o": return nb
    if ans == "x": return opp(nb)
  if th == "W":
    if ans == "x": return nb
    if ans == "o": return opp(nb)
  
n = int(input().strip())
s = list(input())
res_list = [[x, y] for x in "SW" for y in "SW"] 
for ch in s[1:-1]:
  for res in res_list:
    res.append(test(res[-1], res[-2], ch))
    
for res in res_list:
  if test(res[-1], res[-2], s[-1]) == res[0] and test(res[0], res[-1], s[0])  == res[1]:
    print("".join(res))
    break
else:
  print(-1)

Solution (Python):



_ = input()
s = input()


a = [None] * len(s)

def neib(p, q, s):
    if q =="S":
        if s=="o":
            return p
        if s=="x":
            if p=="S":
                return "W"
            else:
                return "S"
    if q=="W":
        if s=="x":  
            if p=="S":
                return "S"
            else:
                return "W"
        if s=="o":
            if p=="S":
                return "W"
            else:
                return "S"


def checkans(p, q, r, s):
    pr = p+r
    if q=="S":
        if pr=="SS" or pr=="WW":
            return s=="o"
        if p != r:
            return s=="x"
    if q=="W":
        if pr=="SS" or pr=="WW":
            return s=="x"
        if p!=r:
            return s=="o"


ans = "-1"
for ini in [("S", "S"), ("S", "W"), ("W", "S"), ("W", "W")]:
    a[0], a[1] = ini
    for i in range(1, len(s)-1):
        a[i+1] = neib(a[i-1], a[i], s[i])
    
    
    c0 = (checkans(a[-2], a[-1], a[0], s[-1]))
    c1 = (checkans(a[-1], a[0], a[1], s[0]) )

    if c0 and c1:
        ans = "".join(a)
        break
print(ans)

Solution (Python):



from itertools import *
import sys

N = int(input())
marks = input()
marks = [ 1 if mark == 'x' else 0 for mark in marks]

for comb in product([0, 1], repeat=2):
    arr = [None for _ in range(N)]
    arr[:2] = comb
    for i in range(2, N):
        arr[i] = arr[i-2] ^ arr[i-1] ^ marks[i-1]
    if (arr[-2] ^ arr[-1] ^ arr[0] == marks[-1]) \
       and (arr[-1] ^ arr[0] ^ arr[1] == marks[0]) \
       and (arr[0] ^ arr[1] ^ arr[2] == marks[1]):
        print(''.join('S' if x == 0 else 'W' for x in arr))
        sys.exit(0)
print(-1)

Solution (Python):
import sys

n = int(raw_input())
s = raw_input()
s += s[0]

first = ['SS', 'SW', 'WS', 'WW']

for f in first:
    ans = f
    for i in [i+1 for i in range(n)]:
        if ans[-1] == 'S':
            if ans[-2] == 'S':
                if s[i] == 'o':
                    ans += 'S'
                else:
                    ans += 'W'
            else:
                if s[i] == 'o':
                    ans += 'W'
                else:
                    ans += 'S'
        else:
            if ans[-2] == 'S':
                if s[i] == 'o':
                    ans += 'W'
                else:
                    ans += 'S'
            else:
                if s[i] == 'o':
                    ans += 'S'
                else:
                    ans += 'W'
    if ans[0] == ans[-2] and ans[1] == ans[-1]:
        print ans[0:n]
        sys.exit(0)

print -1

Solution (Python):
n = int(input())
s = input().rstrip()
def check(is_sheep, s, i, n):
  a = i - 1 if i != 0 else n-1
  b = i + 1 if i != n - 1 else 0
  if (s[i] == 'o') == is_sheep[i]:
    return is_sheep[a] == is_sheep[b]
  else:
    return is_sheep[a] != is_sheep[b]

def solve(n, s):
  
  for x, y in [(True, True), (True, False), (False, True), (False, False)]:
    is_sheep = [None] * n
    is_sheep[0] = x
    is_sheep[1] = y
    for i in range(2, n):
      if is_sheep[i-1]:
        if s[i-1] == 'o':
          is_sheep[i] = is_sheep[i-2]
        else:
          is_sheep[i] = not is_sheep[i-2]
      else:
        if s[i-1] == 'o':
          is_sheep[i] = not is_sheep[i-2]
        else:
          is_sheep[i] = is_sheep[i-2]
    if check(is_sheep, s, 0, n) and check(is_sheep, s, n - 1, n):
      return is_sheep
  return None

result = solve(n, s)

if result:
  print("".join(["S" if b else "W" for b in result]))
else:
  print(-1)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    s = [c == 'o' for c in S()]
    for k in ['SS','SW','WS','WW']:
        r = k
        for i in range(1,n-1):
            t = r[-1]
            t2 = r[-2]
            if (t == 'S' and t2 == 'S' and s[i]) or (
                t == 'S' and t2 == 'W' and not s[i]) or (
                t == 'W' and t2 == 'S' and not s[i]) or (
                t == 'W' and t2 == 'W' and s[i]):
                r += 'S'
            else:
                r += 'W'
        if ((((r[-1] == 'S' and s[-1]) or (r[-1] == 'W' and not s[-1]))  and  r[-2] == r[0]) or (
            ((r[-1] == 'W' and s[-1]) or (r[-1] == 'S' and not s[-1]))  and r[-2] != r[0])) and (
            (((r[0] == 'S' and s[0]) or (r[0] == 'W' and not s[0]))  and  r[-1] == r[1]) or (
            ((r[0] == 'W' and s[0]) or (r[0] == 'S' and not s[0]))  and r[-1] != r[1])):
            return r
    return -1

print(main())

Solution (Python):
from sys import stdin
n = int(stdin.readline())
s = list(stdin.readline().strip())
def chk(x):
    for i in xrange(n):
        ne = (i + 1)%n
        pr = (i + n-1)%n
        if x[i]=='S':
            if s[i]=='o':
                if x[ne]!=x[pr]:
                    return 0
            else:
                if x[ne]==x[pr]:
                    return 0
        else:
            if s[i]=='o':
                if x[ne]==x[pr]:
                    return 0
            else:
                if x[ne]!=x[pr]:
                    return 0
    return 1                
res = '-1'
op  ={}
op['S'] = 'W'
op['W'] = 'S'
def get(ty,u,v):
    if ty == 'S':
        if v=='o':
            return u
        return op[u]
    if v=='x':
        return u
    return op[u]
def gen(u,v):
    cur = ['*'] * n
    cur[0] = u
    cur[1] = v
    cur[-1] = get(u,v,s[0])
    for i in xrange(1,n):
        pr = (n + i-1)%n
        ne = (i + 1)%n
        if cur[ne]=='*':
            cur[ne]= get(cur[pr],cur[i],s[i])
    return cur

arr = [('S','S'),('S','W'),('W','W'),('W','S')]
ans = '-1'
for x,y in arr:
    my = gen(x,y)
    if chk(my)==1:
        ans = ''.join(my)
        break
print ans

Solution (Python):
n = int(raw_input())
s = raw_input()
cases = ["SS", "SW", "WS", "WW"]

def inv(c):
    return "S" if c == "W" else "W"

for i in xrange(2, n + 2):
    for j, case in enumerate(cases):
        p = case[i - 2]
        c = case[i - 1]
        d = s[(i - 1) % n]
        if d == "o":
            if c == "S":
                newcase = case + p
            else:
                newcase = case + inv(p)
        else:
            if c == "S":
                newcase = case + inv(p)
            else:
                newcase = case + p
        cases[j] = newcase

for case in cases:
    if case[-2:] == case[:2]:
        print case[:-2]
        break
else:
    print "-1"

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

def acceptable(ary):
    flag = True
    if ary[0]:
        if s[0] == 'o':
            flag = ary[1] == ary[-1]
        else:
            flag = ary[1] != ary[-1]
    else:
        if s[0] == 'x':
            flag = ary[1] == ary[-1]
        else:
            flag = ary[1] != ary[-1]
    if ary[-1]:
        if s[-1] == 'o':
            flag = flag and ary[0] == ary[-2]
        else:
            flag = flag and ary[0] != ary[-2]
    else:
        if s[-1] == 'x':
            flag = flag and ary[0] == ary[-2]
        else:
            flag = flag and ary[0] != ary[-2]
    return flag

def solve(ary):
    for i in range(1, n-1):
        if ary[i]:
            if s[i] == 'o':
                ary.append(ary[i-1])
            else:
                ary.append(not ary[i-1])
        else:
            if s[i] == 'x':
                ary.append(ary[i-1])
            else:
                ary.append(not ary[i-1])
    return ary

def print_ans(ans):
    print(''.join(['S' if a else 'W' for a in ans]))

for t in ([True, True], [True, False], [False, True], [False, False]):
    ans = solve(t)
    if acceptable(ans):
        print_ans(ans)
        exit()
print(-1)

Solution (Python):
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

N = read()
s = [0 if c == "o" else 1 for c in input()]

ans = [0] * N

for a, b in product([0, 1], [0, 1]):
  ans[0:2] = [a, b]
  for i in range(2, N):
    ans[i] = (ans[i-2] + ans[i-1] + s[i-1]) % 2
  b1 = (ans[N-2] + ans[N-1] + ans[0] + s[N-1]) % 2
  b2 = (ans[N-1] + ans[0] + ans[1] + s[0]) % 2
  if b1 == 0 and b2 == 0:
    print("".join("SW"[ans[i]] for i in range(N)))
    exit()


print(-1)