Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Balanced Walks CodeChef Solution
Problem -Balanced Walks CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
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];
int Q[MAX_N],head,tail;
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]);
}
head = tail = 0;
memset(type,-1,sizeof(type));
for(int i = 0;i<N;++i){
if(type[i]!=-1) continue;
Q[tail] = i; ++tail;
type[i] = 0;
while(head<tail){
int u = Q[head]; ++head;
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];
int Q[MAX_N],head,tail;
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]);
}
head = tail = 0;
memset(type,-1,sizeof(type));
for(int i = 0;i<N;++i){
if(type[i]!=-1) continue;
Q[tail] = i; ++tail;
type[i] = 0;
while(head<tail){
int u = Q[head]; ++head;
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.io.BufferedReader;
import java.io.InputStreamReader;
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{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
int nCases = Integer.parseInt(buf.readLine());
for (int i = 0; i < nCases; i++) {
// input
int N = Integer.parseInt(buf.readLine());
// permutations
int P[][] = new int[2][N];
parseInts(buf.readLine(), N, P[0]);
parseInts(buf.readLine(), N, P[1]);
// solver
System.out.println(solve(N, P));
}
}
}Balanced Walks CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
tc := readNum(reader)
var buf bytes.Buffer
for tc > 0 {
tc--
n := readNum(reader)
S := readNNums(reader, n)
T := readNNums(reader, n)
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
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func solve(n int, S []int, T []int) string {
g := NewGraph(n, 2*n)
for i := 0; i+1 < n; i += 2 {
g.AddEdge(S[i], S[i+1])
g.AddEdge(S[i+1], S[i])
g.AddEdge(T[i], T[i+1])
g.AddEdge(T[i+1], T[i])
}
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.
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!
