In this HackerRank Chocolate Game problem solution, Laurel and Hardy have N piles of chocolates with each pile containing some number of chocolates. The piles are arranged from left to right in a non-decreasing order based on the number of chocolates in each pile. They play the following game.
For every continuous subsequence of chocolate piles (at least 2 piles form a subsequence), Laurel and Hardy will play the game on this subsequence of chocolate piles, Laurel plays first, and they play in turn. In one move, the player can choose one of the piles and remove at least one chocolate from it, but the non-decreasing order of the chocolate piles must be maintained. The last person to make a valid move wins.
How many continuous subsequences of chocolate piles will Laurel win if both of them play optimally? The number of chocolates of each pile will be recovered after the game ends for each subsequence.
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the chocolateGame function below.
#
def chocolateGame(arr):
#
# Write your code here.
#
from collections import defaultdict
prefixes = (defaultdict(int), defaultdict(int))
iter_arr = iter(arr)
loses = 0
prev = next(iter_arr)
curr_xor = [prev, 0]
it = 1
prefixes[0][0] = 1
prefixes[1][0] = 1
prefixes[0][prev] = 1
for i in iter_arr:
curr_xor[it] ^= (i - prev)
loses += prefixes[it][curr_xor[it]]
prefixes[it][curr_xor[it]] += 1
prefixes[it][curr_xor[it] ^ i] += 1
it = not it
prev = i
n = len(arr)
return n * (n - 1) // 2 - loses
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
arr_count = int(input())
arr = list(map(int, input().rstrip().split()))
result = chocolateGame(arr)
fptr.write(str(result) + '\n')
fptr.close()Problem solution in Java.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the chocolateGame function below.
*/
static long chocolateGame(int[] arr) {
long result = (arr.length - 1L)*arr.length/2;
Map<Integer, Integer> sums = new HashMap<>();
sums.put(0, 1);
int sum = 0;
for (int i = arr.length - 2; i >= 0; i -= 2) {
int x = sum ^ arr[i + 1];
sum ^= arr[i + 1] - arr[i];
int a = sums.getOrDefault(x, 0);
int b = sums.getOrDefault(sum, 0);
sums.put(sum, b + 1);
result -= a + b;
}
if (arr.length % 2 == 1) {
sum ^= arr[0];
result -= sums.getOrDefault(sum, 0);
}
sums = new HashMap<>();
sums.put(0, 1);
sum = 0;
for (int i = arr.length - 3; i >= 0; i -= 2) {
int x = sum ^ arr[i + 1];
sum ^= arr[i + 1] - arr[i];
int a = sums.getOrDefault(x, 0);
int b = sums.getOrDefault(sum, 0);
sums.put(sum, b + 1);
result -= a + b;
}
if (arr.length % 2 == 0) {
sum ^= arr[0];
result -= sums.getOrDefault(sum, 0);
}
return result;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int arrCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
int[] arr = new int[arrCount];
String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
for (int arrItr = 0; arrItr < arrCount; arrItr++) {
int arrItem = Integer.parseInt(arrItems[arrItr]);
arr[arrItr] = arrItem;
}
long result = chocolateGame(arr);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}Problem solution in C++.
#include <stdio.h>
#include <map>
using namespace std;
int pile[100005];
map<int, int> wins[2];
int main()
{
int N;
int grundy[2]={0,0};
scanf("%d", &N);
for(int i=0; i < N; ++i)
scanf("%d", pile+i);
long long ans=0;
for(int i=0; i < N; ++i){
int x;
if(i)
x=pile[i]-pile[i-1];
else
x=pile[i];
grundy[i%2]^=x;
++wins[i%2][grundy[i%2]^pile[i]];
ans += wins[i%2][grundy[i%2]];
++wins[(i+1)%2][grundy[(i+1)%2]];
}
long long n=N;
printf("%lld\n", (n*(n-1))/2-ans);
return 0;
}
Problem solution in C.
#include <stdio.h>
#include <stdlib.h>
void sort_a(int*a,int *c,int size,int*new_size);
void merge(int*a,int*left,int*right,int *c,int*c_left,int*c_right,int left_size, int right_size,int*new_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
int main()
{
int n,evensize,oddsize,sort_evensize,sort_oddsize,i,j,t;
int *d,*dd,*dseven,*dsodd,*sort_even,*sort_odd,*c_even,*c_odd,**even_table,**odd_table;
long long ans=0;
scanf("%d",&n);
d=(int*)malloc(n*sizeof(int));
dd=(int*)malloc((n-1)*sizeof(int));
evensize=oddsize=(n-1)/2;
evensize+=(n-1)%2;
dseven=(int*)malloc(evensize*sizeof(int));
dsodd=(int*)malloc(oddsize*sizeof(int));
sort_even=(int*)malloc(evensize*sizeof(int));
sort_odd=(int*)malloc(oddsize*sizeof(int));
c_even=(int*)malloc(evensize*sizeof(int));
c_odd=(int*)malloc(oddsize*sizeof(int));
for(i=0;i<n;i++)
scanf("%d",d+i);
for(i=0;i<n-1;i++)
{
dd[i]=d[i+1]-d[i];
if(!i)
dseven[i/2]=dd[i];
else if(i==1)
dsodd[i/2]=dd[i];
else if(i%2)
dsodd[i/2]=dsodd[i/2-1]^dd[i];
else
dseven[i/2]=dseven[i/2-1]^dd[i];
}
for(i=0;i<evensize;i++)
{
sort_even[i]=dseven[i];
c_even[i]=1;
}
for(i=0;i<oddsize;i++)
{
sort_odd[i]=dsodd[i];
c_odd[i]=1;
}
sort_a(sort_even,c_even,evensize,&sort_evensize);
sort_a(sort_odd,c_odd,oddsize,&sort_oddsize);
even_table=(int**)malloc(sort_evensize*sizeof(int*));
for(i=0;i<sort_evensize;i++){
even_table[i]=(int*)malloc((c_even[i]+1)*sizeof(int));
even_table[i][0]=0;
}
odd_table=(int**)malloc(sort_oddsize*sizeof(int*));
for(i=0;i<sort_oddsize;i++){
odd_table[i]=(int*)malloc((c_odd[i]+1)*sizeof(int));
odd_table[i][0]=0;
}
for(i=0;i<evensize;i++){
j=get_i(sort_even,dseven[i],sort_evensize);
even_table[j][++even_table[j][0]]=i;
}
for(i=0;i<oddsize;i++){
j=get_i(sort_odd,dsodd[i],sort_oddsize);
odd_table[j][++odd_table[j][0]]=i;
}
for(i=0;i<n-1;i++)
if(i%2){
t=d[i]^dseven[(i-1)/2];
j=get_i(sort_even,t,sort_evensize);
if(j>=0 && j<sort_evensize && sort_even[j]==t)
{
t=get_i(even_table[j]+1,(i+1)/2,even_table[j][0]);
ans+=even_table[j][0]-t;
}
t=0;
if(i!=1)
t^=dsodd[(i-2)/2];
j=get_i(sort_odd,t,sort_oddsize);
if(j>=0 && j<sort_oddsize && sort_odd[j]==t)
{
t=get_i(odd_table[j]+1,i/2,odd_table[j][0]);
ans+=odd_table[j][0]-t;
}
}
else{
t=d[i];
if(i)
t^=dsodd[(i-1)/2];
j=get_i(sort_odd,t,sort_oddsize);
if(j>=0 && j<sort_oddsize && sort_odd[j]==t)
{
t=get_i(odd_table[j]+1,i/2,odd_table[j][0]);
ans+=odd_table[j][0]-t;
}
t=0;
if(i)
t^=dseven[(i-1)/2];
j=get_i(sort_even,t,sort_evensize);
if(j>=0 && j<sort_evensize && sort_even[j]==t)
{
t=get_i(even_table[j]+1,i/2,even_table[j][0]);
ans+=even_table[j][0]-t;
}
}
ans=((long long)n)*(n-1)/2-ans;
printf("%lld",ans);
return 0;
}
void sort_a(int*a,int *c,int size,int*new_size)
{
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int *left,*right,*c_left,*c_right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
c_left=(int*)malloc(m*sizeof(int));
c_right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left[i]=a[i];
c_left[i]=c[i];
}
for(i=0;i<size-m;i++)
{
right[i]=a[i+m];
c_right[i]=c[i+m];
}
int new_l_size=0,new_r_size=0;
sort_a(left,c_left,m,&new_l_size);
sort_a(right,c_right,size-m,&new_r_size);
merge(a,left,right,c,c_left,c_right,new_l_size,new_r_size,new_size);
free(left);
free(right);
free(c_left);
free(c_right);
return;
}
void merge(int*a,int*left,int*right,int *c,int*c_left,int*c_right,int left_size, int right_size,int*new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
c[index] = c_right[j];
a[index++] = right[j];
j++;
} else if (j == right_size)
{
c[index] = c_left[i];
a[index++] = left[i];
i++;
} else if (left[i] <= right[j])
{
c[index] = c_left[i];
a[index++] = left[i];
i++;
} else {
c[index] = c_right[j];
a[index++] = right[j];
j++;
}
if(index>1&&a[index-2]==a[index-1])
{
index--;
c[index-1]+=c[index];
}
}
(*new_size)=index;
return;
}
int get_i(int*a,int num,int size)
{
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size)
{
return a[(size-1)>>1];
}
0 Comments