Box of Chocolates Codechef Solution: Chef just got a box of chocolates as his birthday gift. The box contains NN chocolates in a row (numbered 11 through NN), where NN is even. For each valid ii, the ii-th chocolate has a sweetness value WiWi.
Chef wants to eat all the chocolates in the first half of the box and leave all chocolates in the second half uneaten. Since he does not like chocolates that are too sweet, he will be unhappy if at least one of the chocolates he eats has the maximum sweetness among all the chocolates in the box.
A right cyclic shift by kk chocolates (0≤k<N0≤k<N) consists of moving the last kk chocolates in the row to the beginning in the same order and moving each of the remaining N−kN−k chocolates kk places to the right. Before eating the first half of the chocolates, Chef wants to perform some right cyclic shift in such a way that he will not be unhappy after eating them. Find the number of ways to do this, i.e. the number of valid integers kk such that if Chef performs the right cyclic shift by kk chocolates and then eats the first half of the chocolates in the box, he does not become unhappy.
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of each test case contains a single integer NN.
- The second line contains NN space-separated integers W1,W2,…,WNW1,W2,…,WN.
Output
For each test case, print a single line containing one integer ― the number of shifts for which Chef does not become unhappy.
Constraints
- 1≤T≤51≤T≤5
- 1≤N≤1051≤N≤105
- NN is even
- 1≤Wi≤1051≤Wi≤105 for each valid ii
Sample Input 1
2 6 1 1 2 1 1 1 6 1 1 2 1 1 2
Sample Output 1
3
Explanation
Example case 1: The three valid right shifts and the contents of the box for these shifts are:
- shift by k=1k=1: (1,1,1,2,1,1)(1,1,1,2,1,1)
- shift by k=2k=2: (1,1,1,1,2,1)(1,1,1,1,2,1)
- shift by k=3k=3: (1,1,1,1,1,2)
Box of Chocolates CodeChef Solution in JAVA
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
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
int n;
n=sc.nextInt();
int ar[]=new int[n+1];
int i=0,j=0;
int max1=Integer.MIN_VALUE;
for(i=0;i<n;i++)
{
ar[i]=sc.nextInt();
max1=Math.max(max1,ar[i]);
}
int sizes[] = new int[n+1];
int count=0;
// int j=0;
for(i=1;i<=n;i++){
if(ar[i] != max1){
count++;
}
else{
sizes[j++]=count;
count=0;
}
}
if(count != 0){
sizes[0]=count+sizes[0];
}
int res = 0;
for( i=0;i<j;i++){
res += Math.max(sizes[i]-n/2+1,0);
}
System.out.println(res);
}
}
}
Box of Chocolates CodeChef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
vector <int> w(n);
for(int i = 0; i < n; i++) cin >> w[i];
int max_ele=INT_MIN;
for(int i = 0; i < n; i++) {
max_ele=max(max_ele, w[i]);
}
vector<int> v;
for(int i=0, j = 0; i < n; i=j){
if(max_ele==w[i]){
++j;
continue;
}
for(;j<n&&max_ele^w[j];++j);
v.push_back(j-i);
}
// if first and last are connected then
if(max_ele^w[0]&&max_ele^w[n-1]) {
v[0]+=v.back();
v.pop_back();
}
int ans=0;
for(int i: v){
ans+=max(0, i-n/2+1);
}
cout << ans << endl;
}
return 0 ;
}Box of Chocolates CodeChef Solution in Python
for i in range(int(input())):
n=int(input())
l1=list(map(int,input().split()))
x=l1.index(max(l1))
y=n-l1[::-1].index(max(l1))-1
if y-x>n//2:
print(0)
else:
print(n//2-(y-x))Disclaimer: The above Problem (Box of Chocolates) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.