Boolean Game CodeChef Solution

Problem -Boolean Game 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.

Boolean Game CodeChef Solution in C++17

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define DEBUG(x) cout<<'>'<<#x<<':'<<x<<endl
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORC(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define dd long double
#define all(x) x.begin(),x.end()

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m,k;
        cin>>n>>m>>k;
        vector<ll> g(n+1) ;
        REP(i,n){
            cin>>g[i+1];
        }
        vector<vector<pair<ll,ll>>> arr(n+1);
        REP(i,m){
            ll u,v,d;
            cin>>u>>v>>d;
            arr[u].pb(mp(i,d));
            arr[v].pb(mp(i,d));
        }
        vector<vector<pair<ll,ll>>> dp(n+1);
        dp[0].pb(mp(0,0));
        
        for(ll i=1;i<=n;i++)
        {
            vector<pair<ll,ll>> temp;
            temp.insert(temp.end(),all(dp[i-1]));
            ll curr=0,mask=0;
            set<ll> open;
            for(ll j=i;j>=1;j--)
            {
                curr+=g[j];
                mask^=1LL<<j;
                for(auto & [idx,w]:arr[j]){
                    if(open.count(idx)){
                        curr+=w;
                    }
                    else
                    {
                        open.insert(idx);
                    }
                }
                if(j>1){
                    for(auto & [val,old_mask]:dp[j-2]){
                        temp.pb(mp(val+curr,mask^old_mask));
                    }
                }
                else{
                    temp.pb(mp(curr,mask));
                }
                
            }
            sort(all(temp));
            reverse(all(temp));
            set<ll> sel;
            ll filled =0;
            for(ll j=0;j<temp.size() && filled<k ;j++)
            {
                if(sel.count(temp[j].ss)) continue;
                dp[i].pb(temp[j]);
                filled++;
                sel.insert(temp[j].ss); 
            }
        }
        for(ll i=0;i<k;i++)
        {
            cout<<dp[n][i].ff<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Boolean Game CodeChef Solution in C++14

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define DEBUG(x) cout<<'>'<<#x<<':'<<x<<endl
#define REP(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORC(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define dd long double
#define all(x) x.begin(),x.end()

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--)
    {
        ll n,m,k;
        cin>>n>>m>>k;
        vector<ll> g(n+1) ;
        REP(i,n){
            cin>>g[i+1];
        }
        vector<vector<pair<ll,ll>>> arr(n+1);
        REP(i,m){
            ll u,v,d;
            cin>>u>>v>>d;
            arr[u].pb(mp(i,d));
            arr[v].pb(mp(i,d));
        }
        vector<vector<pair<ll,ll>>> dp(n+1);
        dp[0].pb(mp(0,0));
        
        for(ll i=1;i<=n;i++)
        {
            vector<pair<ll,ll>> temp;
            temp.insert(temp.end(),all(dp[i-1]));
            ll curr=0,mask=0;
            set<ll> open;
            for(ll j=i;j>=1;j--)
            {
                curr+=g[j];
                mask^=1LL<<j;
                for(auto & [idx,w]:arr[j]){
                    if(open.count(idx)){
                        curr+=w;
                    }
                    else
                    {
                        open.insert(idx);
                    }
                }
                if(j>1){
                    for(auto & [val,old_mask]:dp[j-2]){
                        temp.pb(mp(val+curr,mask^old_mask));
                    }
                }
                else{
                    temp.pb(mp(curr,mask));
                }
                
            }
            sort(all(temp));
            reverse(all(temp));
            set<ll> sel;
            ll filled =0;
            for(ll j=0;j<temp.size() && filled<k ;j++)
            {
                if(sel.count(temp[j].ss)) continue;
                dp[i].pb(temp[j]);
                filled++;
                sel.insert(temp[j].ss); 
            }
        }
        for(ll i=0;i<k;i++)
        {
            cout<<dp[n][i].ff<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Boolean Game CodeChef Solution in PYTH 3

# cook your dish here
from sys import stdin
input = stdin.readline

def answer():

    dp = [[] for i in range(n + 1)]
    dp[0].append(0)

    for i in range(1 , n + 1):
        
        dp[i].extend(dp[i - 1])
        
        for j in range(i , 0 , -1):

            x = 0
            for l in range(j , i + 1):

                for r in range(l , i + 1):

                    x += value[l][r]

            if(j == 1):
                dp[i].append(x)

            else:
                for val in dp[j - 2]:
                    
                    dp[i].append(val + x)
        

        dp[i].sort(reverse = True)
        while(len(dp[i]) > k):
            dp[i].pop()
                
    return dp[n]


for T in range(int(input())):

    n , m , k = map(int,input().split())

    g = list(map(int,input().split()))

    value = [[0 for i in range(n + 1)] for j in range(n + 1)]


    for i in range(m):

        x , y , val = map(int,input().split())
        value[x][y] = val

    for i in range(n):
        value[i + 1][i + 1] = g[i]
    
    print(*answer())

# cook your dish here

Boolean Game CodeChef Solution in JAVA

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    static void addCost(PriorityQueue<Long> queue,long arr[],long cost)
    {
        for(int i=0;i<arr.length;i++)
        queue.offer(cost+arr[i]);
    }
    static HashMap<Integer,ArrayList<int[]>> start;
    static HashMap<Integer,long[]> dp;
    static  long[] takeOnes(int curr,int n,int k,int interval[])
    {
        if(curr>n)
            return new long[]{0};
        
        long cost=0;
        if(dp.containsKey(curr))
            return dp.get(curr);
        PriorityQueue<Long> queue=new PriorityQueue<Long>((a,b)->{
            if(b>a)
                return 1;
            return -1;    
        });
        
        //only zero
        addCost(queue,takeOnes(curr+1,n,k,interval),cost);

        int left=curr,right=curr;

        while(right+1<=n)
        {
            if(start.containsKey(right))
            {
                for(int neigh[]:start.get(right))
                        if(neigh[0]>=left)
                            cost+=neigh[1];
            }
            cost+=interval[right];
            addCost(queue,takeOnes(right+2,n,k,interval),cost);
            right++;
        }
        if(start.containsKey(right))
        {
            for(int neigh[]:start.get(right))
                if(neigh[0]>=left)
                    cost+=neigh[1];
        }
        cost+=interval[right];
        addCost(queue,takeOnes(right+1,n,k,interval),cost);
        
        int size=(queue.size()<k)?queue.size():k;
        long res[]=new long[size];
        int i=0;
        while(size>0){
            res[i++]=queue.poll();
            size--;
        }
        
        dp.put(curr,res);
        return res;
    }
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
    
		 
		Scanner scan=new Scanner(System.in);
		int t=scan.nextInt();
		for(int r=0;r<t;r++)
		{
		    int n=scan.nextInt();
		    int m=scan.nextInt();
		    int k=scan.nextInt();
		    int interval[]=new int[n+1];
		    start=new HashMap<Integer,ArrayList<int[]>>();
		    for(int i=1;i<=n;i++){
		        interval[i]=scan.nextInt();
		        
		    }
		    dp=new HashMap<Integer,long[]>();
		    for(int i=0;i<m;i++)
		    {
		        int u=scan.nextInt();
		        int v=scan.nextInt();
		        int cost=scan.nextInt();
		        if(!start.containsKey(v))
		            start.put(v,new ArrayList<int[]>());
		        start.get(v).add(new int[]{u,cost});      
		    }
		    long res[]=takeOnes(1,n,k,interval);
		    for(int i=0;i<res.length-1;i++)
		        System.out.print(res[i]+" ");
		    System.out.println(res[res.length-1]);      
		   
		}
    }
   
	
	
}

Boolean Game CodeChef Solution in PYPY 3

from sys import stdin
input = stdin.readline

def answer():

    dp = [[] for i in range(n + 1)]
    dp[0].append(0)

    for i in range(1 , n + 1):
        
        dp[i].extend(dp[i - 1])
        
        for j in range(i , 0 , -1):

            x = 0
            for l in range(j , i + 1):

                for r in range(l , i + 1):

                    x += value[l][r]

            if(j == 1):
                dp[i].append(x)

            else:
                for val in dp[j - 2]:
                    
                    dp[i].append(val + x)
        

        dp[i].sort(reverse = True)
        while(len(dp[i]) > k):
            dp[i].pop()
                
    return dp[n]


for T in range(int(input())):

    n , m , k = map(int,input().split())

    g = list(map(int,input().split()))

    value = [[0 for i in range(n + 1)] for j in range(n + 1)]


    for i in range(m):

        x , y , val = map(int,input().split())
        value[x][y] = val

    for i in range(n):
        value[i + 1][i + 1] = g[i]
    
    print(*answer())

Boolean Game CodeChef Solution in GO

package main

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

func main() {
	reader := bufio.NewReader(os.Stdin)

	var buf bytes.Buffer

	tc := readNum(reader)

	for tc > 0 {
		tc--
		n, m, k := readThreeNums(reader)
		G := readNNums(reader, n)
		L := make([][]int, m)
		for i := 0; i < m; i++ {
			L[i] = readNNums(reader, 3)
		}
		res := solve(k, G, L)
		for i := 0; i < len(res); i++ {
			buf.WriteString(fmt.Sprintf("%d ", res[i]))
		}
		buf.WriteByte('\n')
	}
	fmt.Print(buf.String())
}

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 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 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 solve(K int, G []int, L [][]int) []int64 {
	n := len(G)
	cc := make([]int, n+1)
	for _, l := range L {
		cc[l[1]]++
	}
	reward := make([][]Pair, n+1)
	for i := 0; i <= n; i++ {
		reward[i] = make([]Pair, 0, cc[i])
	}

	for _, l := range L {
		u, v, d := l[0], l[1], l[2]
		reward[v] = append(reward[v], Pair{u, d})
	}

	for i := 0; i <= n; i++ {
		sort.Sort(Pairs(reward[i]))
	}
	dp := make([][][]int64, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([][]int64, n+1)
		for j := 0; j <= n; j++ {
			dp[i][j] = make([]int64, 0, K)
		}
	}
	push := func(i, j int, v int64) {
		dp[i][j] = append(dp[i][j], v)
	}

	push(0, 0, 0)
	// dp[i][j] = j < i, 且x[j] = 0, x[j+1...i] 为1时的最大集合
	for i := 1; i <= n; i++ {
		tmp := int64(G[i-1])
		for _, r := range reward[i] {
			// 所有以i结尾的线段的收益
			tmp += int64(r.se)
		}
		var p int
		for j := 0; j < i; j++ {
			for p < len(reward[i]) && reward[i][p].fi <= j {
				tmp -= int64(reward[i][p].se)
				p++
			}
			for _, r := range dp[i-1][j] {
				push(i, j, tmp+r)
			}
		}
		// if set i is zero, dp[i][j] = dp[i-1][j]
		for j := 0; j < i; j++ {
			for _, r := range dp[i-1][j] {
				push(i, i, r)
			}
		}
		sort.Sort(Int64Gt(dp[i][i]))
		dp[i][i] = dp[i][i][:min(len(dp[i][i]), K)]
	}
	res := make([]int64, 0, K)

	for j := 0; j <= n; j++ {
		for _, r := range dp[n][j] {
			res = append(res, r)
		}
	}
	sort.Sort(Int64Gt(res))
	return res[:min(len(res), K)]
}

type Pair struct {
	fi, se int
}

type Pairs []Pair

func (ps Pairs) Len() int {
	return len(ps)
}

func (ps Pairs) Less(i, j int) bool {
	return ps[i].fi < ps[j].fi
}

func (ps Pairs) Swap(i, j int) {
	ps[i], ps[j] = ps[j], ps[i]
}

type Int64Gt []int64

func (this Int64Gt) Len() int {
	return len(this)
}

func (this Int64Gt) Less(i, j int) bool {
	return this[i] > this[j]
}

func (this Int64Gt) Swap(i, j int) {
	this[i], this[j] = this[j], this[i]
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}
Boolean Game CodeChef Solution Review:

In our experience, we suggest you solve this Boolean Game 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 Boolean Game CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Boolean Game 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 *