# CHCBOX - Editorial

Author: Anik Sarker
Tester: Raja Vardhan Reddy
Editorialist: William Lin

Simple

# PROBLEM:

Given an array W with even length N, find the number of cyclic shifts of this array X such that the first half of X does not contain the maximum element.

# QUICK EXPLANATION:

Find the maximum element, then find the maximal ranges between pairs of maximum elements. A range with length l adds \max(l-\frac{N}{2}+1, 0) to the answer.

# EXPLANATION:

Assume that the range is circular, so W_{n+i}=W_i. The first half of array X is its subarray X[0, \frac{N}{2}-1]. If we shift W to the left by K to form X (a right cyclic shift by K is also a left cyclic shift by N-K), then X[0, \frac{N}{2}-1] is W[K, K+\frac{N}{2}-1].

Thus, we’ve reduced the problem to counting the number of 0\le K < N such that W[K, K+\frac{N}{2}-1] does not contain the maximum element. In other words, we want the number of circular subarrays of length \frac{N}{2} in W which don’t contain the maximum element.

Notice that the elements with maximum value in W separate W into several subarrays which don’t contain the maximum element. Let the set of such subarrays be S. For example, if W=[1, 7, 2, 3, 7, 4, 7, 3, 2, 3, 1, 1, 2, 2], S consists of W[2, 3], W[5, 5], and W[7, 14] (the last subarray wraps around to the beginning).

A subarray of length \frac{N}{2} has to be completely contained in one of the subarrays in S. Otherwise, the subarray would contain the maximum element.

We can solve for each subarray in S independently. Supposed the subarray has length l. How many subarrays of length \frac{N}{2} can we fit in it?

If l<\frac{N}{2}, obviously we can’t fit any subarrays of length \frac{N}{2}. Then, we can notice a pattern. If l=\frac{N}{2}, we can fit 1, if l=\frac{N}{2}+1, we can fit 2, and so on. In general, we can fit \max(l-\frac{N}{2}+1, 0) subarrays of length \frac{N}{2}.

Thus, the solution is to find the subarrays in S and evaluate the formula for each of the subarrays.

# SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int a[maxn];

int main(){
int t;
scanf("%d", &t);

for(int cs=1; cs<=t; cs++){
int n;
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);

int Max = 0;
for(int i=1; i<=n; i++) Max = max(Max, a[i]);

vector<int> pos;
for(int i=1; i<=n; i++) if(a[i] == Max) pos.push_back(i);
pos.push_back(pos[0] + n);

int ans = 0;
int sz = n / 2;
for(int i=1; i<pos.size(); i++) ans += max(0, pos[i] - pos[i-1] - sz);

printf("%d\n", ans);
}
}

Tester's Solution
//raja1999

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);

int A[112345],cnt[212345];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
//t=1;
while(t--){
int n,i,c=0,maxi=0,ans=0;
cin>>n;
rep(i,n){
cin>>A[i];
maxi=max(maxi,A[i]);
}
f(i,1,n+1){
cnt[i]=0;
}
rep(i,n){
if(A[i]==maxi){
c++;
if(i<n/2){
cnt[1+i]++;
cnt[1+n/2+i]--;
}
else{
cnt[1]++;
cnt[1+i-n/2]--;
cnt[1+i]++;
}
}
}
f(i,1,n+1){
cnt[i]=i>0?cnt[i-1]+cnt[i]:cnt[i];
if(cnt[i]==c){
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

const int mxN=1e5;
int n, w[mxN];

void solve() {
//input
cin >> n;
for(int i=0; i<n; ++i)
cin >> w[i];

//find max
int mx=0;
for(int i=0; i<n; ++i)
mx=max(w[i], mx);

//find length of subarrays in S
vector<int> v;
for(int i=0, j=0; i<n; i=j) {
if(w[i]==mx) {
++j;
continue;
}
for(; j<n&&w[j]^mx; ++j);
v.push_back(j-i);
}
//first and last subarrays might be connected
if(w[0]^mx&&w[n-1]^mx) {
v[0]+=v.back();
v.pop_back();
}

int ans=0;
for(int vi : v)
ans+=max(vi-n/2+1, 0);
cout << ans << "\n";
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);

int t;
cin >> t;
while(t--)
solve();
}


Please give me suggestions if anything is unclear so that I can improve. Thanks

11 Likes

Can you look at solution and tell why i am getting wa
My logic is that 2 indexes matters first and last i:e smalles and biggest indexes of max value
of arr
now with this 3 cases possible
case 1
both are < n/2

case 2
max is >n/2 while other is <n/2
case 3 both are >n/2
now if both are n/2 ans is:- n-maxindex+1
for case2 ans =n-maxindex-(difference of index of max and min)
for case 1 its n/2-differerece of index

4 Likes

i did it using segTree

can someone explain in simple c++

1 Like

What if all chocolates have the same sweetness?
Consider the test case:
6
1 1 1 1 1 1
Will the output be 0 or it be 6?
I submitted with output 6(got an AC) while others with output 0 (got an AC too)
So the question : Is it even possible that sweetness can be same for all the chocolates?
My Solution : https://www.codechef.com/viewsolution/30654986

1 Like

Problem had weak test cases I think so
https://www.codechef.com/viewsolution/30671225
Fails the following test case:
1
4
2 1 1 2
Expected op:
1
Actual op:
0

Yet the problem was given AC

12 Likes

Exactly

Why my solution get TLE?
my submission: https://www.codechef.com/viewsolution/30671229

https://www.codechef.com/viewsolution/30670772

@rajatrc1705 my program is giving output 1 on your given test case but actual ans is 0 so my submission got WA what to do for this?any one help

SOLVED
How can i create circular array and count the number of elements that lies between two maximum elements?
if is very confusing
for example
elements- 1 2 2 1 2 1
index-------0 1 2 3 4 5
max element=2
between index 1 and 2
between index 2 and 4
between index 4 and 1(4,5,0,1)
if i use circular linked list it will become complicated.

https://www.codechef.com/viewsolution/30674585
In the following code segment, why is the commented if accessed even when the condition is failing. Getting WA due to that reason!!

I am not able to figure why i am getting WA in this?
Please someone help whats the problem or you can give test cases too!
Thanks!!

you can refer my solution ,if any doubts u can ask me

#include <bits/stdc++.h>
# define ll  int
using namespace std;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,i,j,k;
cin>>n;
ll a[n],mx=0,c[n]={0};
for(i=0;i<n;i++)
{
cin>>a[i];
mx=max(mx,a[i]);
}

for(i=0;i<n;i++)
{
if(a[i]==mx)
c[i]=1;
}
ll x=0,y=0,f=0,ans=0;
for(i=0;i<n;i++)
{
if(f==0)
{
if(c[i]==0)
x++;
}
if(f==1)
{
if(c[i]==0)
y++;
}

if(i==n-1 && c[i]==0)
{
ans+=max(((x+y)-(n/2)+1),0);
}

if(c[i]==1)
{
f=1;
if(y!=0)
ans+=max((y-(n/2)+1),0);
y=0;
}

}
cout<<ans<<"\n";
}
return 0;
}
3 Likes

Explain me this @tmwilliamlin

for _ in range(int(input())):
n=int(input())
l=list(map(int,input().split()))
x=l.index(max(l))
y=n-l[::-1].index(max(l))-1
if y-x > n//2:
print(0)
else:
print(n//2-(y-x))


why this works (solution of other person) , he considers only first and last index of max value. ?

I feel the solution here is so overkill

Can’t we just use a hash map and store the count of elements and as we move, remove the element a[n/2-1], a[n/2-2],… and add a[n-1], a[n-2]… and keep continuing like that. And after each check if the hash[max] is zero or not.

Here, the Max element will be 1. Also, like it is said in the editorial, the difference or gap between any two maximums will be 0, thus the answer will be 0.
Also, if you think about it, the chef wants to avoid the sweet with maximum sweetness, and here all the sweets have max sweetness, so the answer is fairly evident.

1 Like