304 North Cardinal St.
Dorchester Center, MA 02124

# Balanced Walks CodeChef Solution

## Balanced Walks CodeChef Solution in C++17

``````#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAX_N 20000
int main(){
int T,N,p1[MAX_N],p2[MAX_N],type[MAX_N];
vector<int> L[MAX_N];
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i = 0;i<N;++i) L[i].clear();
for(int i = 0;i<N;++i) scanf("%d",&p1[i]);
for(int i = 0;i<N;++i) scanf("%d",&p2[i]);
for(int i = 0;i+1<N;i += 2){
L[p1[i]].push_back(p1[i+1]);
L[p1[i+1]].push_back(p1[i]);
L[p2[i]].push_back(p2[i+1]);
L[p2[i+1]].push_back(p2[i]);
}
memset(type,-1,sizeof(type));
for(int i = 0;i<N;++i){
if(type[i]!=-1) continue;
Q[tail] = i; ++tail;
type[i] = 0;
for(int i = L[u].size()-1;i>=0;--i){
int v = L[u][i];
if(type[v]!=-1) continue;

type[v] = 1-type[u];
Q[tail] = v; ++tail;
}
}
}
for(int i = 0;i<N;++i){
if(type[i]==0) putchar('A');
else putchar('B');
}
putchar('\n');
}
return 0;
}``````

## Balanced Walks CodeChef Solution in C++14

``````#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define MAX_N 20000

int main(){
int T,N,p1[MAX_N],p2[MAX_N],type[MAX_N];
vector<int> L[MAX_N];

scanf("%d",&T);

while(T--){
scanf("%d",&N);
for(int i = 0;i<N;++i) L[i].clear();

for(int i = 0;i<N;++i) scanf("%d",&p1[i]);
for(int i = 0;i<N;++i) scanf("%d",&p2[i]);

for(int i = 0;i+1<N;i += 2){
L[p1[i]].push_back(p1[i+1]);
L[p1[i+1]].push_back(p1[i]);

L[p2[i]].push_back(p2[i+1]);
L[p2[i+1]].push_back(p2[i]);
}

memset(type,-1,sizeof(type));

for(int i = 0;i<N;++i){
if(type[i]!=-1) continue;

Q[tail] = i; ++tail;
type[i] = 0;

for(int i = L[u].size()-1;i>=0;--i){
int v = L[u][i];
if(type[v]!=-1) continue;

type[v] = 1-type[u];
Q[tail] = v; ++tail;
}
}
}

for(int i = 0;i<N;++i){
if(type[i]==0) putchar('A');
else putchar('B');
}
putchar('\n');
}
return 0;
}``````

## Balanced Walks CodeChef Solution in C

``````#include <stdio.h>
#include <memory.h>
int n, z[4][20100];
char x[20100];
void losen(int i, char e)
{
if(i>=n||x[i]!=0||!e)
return;
x[i]=e;
losen((z[2][i]&1)?z[0][z[2][i]+1]:z[0][z[2][i]-1],e==65?66:65);
losen((z[3][i]&1)?z[1][z[3][i]+1]:z[1][z[3][i]-1],e==65?66:65);
}
int main()
{
int fall, i;
for(scanf("%d",&fall); fall--; printf("%s\n",x))
{
for(scanf("%d",&n),memset(x,0,sizeof(x)),(z[0][n+(i=1)]=z[1][n+1]=n); i++<=n; scanf("%d",&z[0][i-1]), z[2][z[0][i-1]]=i-1);
for(i=1; i++<=n; scanf("%d",&z[1][i-1]), z[3][z[1][i-1]]=i-1);
for(i=0; i++<n; losen(i-1,(!x[i-1])?65:0));
}
return 0;
}``````

## Balanced Walks CodeChef Solution in JAVA

``````
import java.util.StringTokenizer;

public class Main {

public static void parseInts(String s, int nInt, int data[]){
StringTokenizer tok = new StringTokenizer(s, " ");
for(int i=0; i<nInt; i++)
data[i] = Integer.parseInt(tok.nextToken());
}

public static void setColor(int i, int newColor, int[] color, int[][] P, int[][] S){
if(color[i] > 0)
return;
color[i] = newColor;
// call setColor recursively
for(int j=0; j<2; j++){
int next = S[j][i] + 1 - 2*(S[j][i] % 2);
if(next == color.length)
continue;
setColor(P[j][next], 3 - newColor, color, P, S);
}
}

public static String solve(int N, int[][] P){
// mapping from sites to position in permutation
int S[][] = new int[2][N];
for(int i=0; i<N; i++)
for(int j=0; j<2; j++){
S[j][P[j][i]] = i;
}
// array that holds the color of each site (1, 2) <-> (A, B), 0 means not visited yet
int color[] = new int[N];
// next sites to visit, there are at most two sites that have to be stored.
int nextSite[] = new int[2];
int nextColor[] = new int[2];
int i,j, next;
for(i=0; i<N; i++){
if(color[i] == 0){ // skip site if it is already colored
color[i] = 1; // minimize lexicographic order when color is arbitrary
// find next sites to visit
for(j=0;j<2;j++){
next = S[j][i] + 1 - 2*(S[j][i] % 2);
if(next < N){ // important for odd number of reachable sites
nextSite[j] = P[j][next];
nextColor[j] = 2;
} else{
nextSite[j] = 0;
}
}
for(j=0; j<2; j++){
int k = j;
// traverse graph
while(color[nextSite[j]] == 0){
k = 1 - k; // switch permutation
color[nextSite[j]] = nextColor[j];
int sk = S[k][nextSite[j]];
next = sk + 1 - 2*(sk % 2);
if(next < N){ // important for odd number of reachable sites
nextSite[j] = P[k][next];
nextColor[j] = 3 - nextColor[j];
} else{
nextSite[j] = 0;
}
}
}

} // if(color[i] == 0)
}

// translate result into String
char[] result = new char[N];
for(i=0; i<N; i++)
if(color[i] == 1)
result[i] = 'A';
else
result[i] = 'B';

return new String(result);
}

public static void main(String[] args) throws Exception{

for (int i = 0; i < nCases; i++) {
// input
// permutations
int P[][] = new int[2][N];
// solver
System.out.println(solve(N, P));
}

}

}``````

## Balanced Walks CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"os"
)

func main() {

var buf bytes.Buffer
for tc > 0 {
tc--
res := solve(n, S, T)
buf.WriteString(res)
buf.WriteByte('\n')
}
fmt.Print(buf.String())
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
return res
}

func solve(n int, S []int, T []int) string {
g := NewGraph(n, 2*n)

for i := 0; i+1 < n; i += 2 {
}

assign := make([]int, n)
for i := 0; i < n; i++ {
assign[i] = -1
}
que := make([]int, n)
var front, end int
for i := 0; i < n; i++ {
if assign[i] >= 0 {
continue
}
assign[i] = 0
que[end] = i
end++
for front < end {
u := que[front]
front++
for j := g.node[u]; j > 0; j = g.next[j] {
v := g.to[j]
if assign[v] < 0 {
assign[v] = 1 - assign[u]
que[end] = v
end++
}
}
}
}

buf := make([]byte, n)

for i := 0; i < n; i++ {
if assign[i] == 0 {
buf[i] = 'A'
} else {
buf[i] = 'B'
}
}
return string(buf)
}

type Graph struct {
node []int
next []int
to   []int
cur  int
}

func NewGraph(n int, e int) *Graph {
g := new(Graph)
g.node = make([]int, n)
g.next = make([]int, e+1)
g.to = make([]int, e+1)
g.cur = 0
return g
}

func (g *Graph) AddEdge(u, v int) {
g.cur++
g.next[g.cur] = g.node[u]
g.node[u] = g.cur
g.to[g.cur] = v
}``````
##### Balanced Walks CodeChef Solution Review:

In our experience, we suggest you solve this Balanced Walks CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Balanced Walks CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Balanced Walks CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!