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.

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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *