Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
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 hereBoolean 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.
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!
