CHCBOX - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

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

DIFFICULTY:

Simple

PREREQUISITES:

Ad-hoc

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 comment(linker, "/stack:200000000")
//#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();
	}

	//calculate answer
	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 :slight_smile:

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 :stuck_out_tongue:

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

can anyone please help me why i am getting WA.
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.

The correct answer is 1.

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!!

Solution-https://www.codechef.com/viewsolution/30670670

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 :sweat:

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

Thanks @tri123 for your reply!

Can you please once see my code whats the issue?

Yes it will work as he is considering the smallest and the greatest index of max element and there can be only one or none valid subarray, if there is a valid subarray then such valid subarray is only one ,other subarray will not be valid as it results in l<n/2.
So valid subarray will have l==n/2 or l>n/2 and in this case the answer is l-(n/2)+1