# CSUBS - Editorial

Setter: Mohan Gorai
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

Simple

None

# PROBLEM

Given an array A of length N and an integer K, Chef writes down the sum of all subarrays of length K in A. Chef writes only distinct values. You want to find the minimum number of changes you need to make to array A, such that Chef writes only one value.

# QUICK EXPLANATION

• We need to make the sum of all K-length subarrays equal, which implies A_i = A_{i+K} for all valid i.
• We can split the elements into groups such that all values in the group should be equal.
• For each group, we find the most frequent element (to minimize operations) and replace all other elements in the group with the element found.

# EXPLANATION

Let’s try an example first

Considering array `a b c d e g h` where a, b, c, d, e, f and g represent elements of array, and say K = 3.

There are five subarrays of length 3, with sums (a+b+c), (b+c+d), (c+d+e), (d+e+f) and (e+f+g). We need all these values equal.

Let’s compare adjacent pairs. (a+b+c) = (b+c+d) \implies a = d, (b+c+d) = (c+d+e) \implies b = e. We can get c= f and d = g.

Hence, a, d, g are all equal, b and e are equal and c and f are equal.

Claim: Formally, by considering subarray A[x:(x+K-1)] and subarray A[x+1, x+K], we can see that for unique value of K-length subarray sums, we need A_i = A_{i+K} to hold for all valid i.

Hence, we can divide the elements into groups, so that all elements in groups, after all operations are applied, become equal.

There would be K groups, i-th group containing elements at position p such that p \bmod K = i. Each group can be processed independently of each other, and the number of operations for each group shall be added to the answer.

Each group contains some values, and we want to change values such that after changes, all values in the group are equal. Since we want to minimize operations, we find the most frequent element in the group and replace all other values with the most frequent element. Since we picked the element with the highest frequency, say F, in a group of size S, we need S-F operations only. Frequencies in a group can be stored in a map.

Summing over all groups, we get the minimum number of operations.

# TIME COMPLEXITY

The time complexity is O(N) or O(N*log(N)) per test case depending upon implementation.

# SOLUTIONS

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

int minChange(int arr[], int n, int k)
{
int ans = 0;
for (int i = 0; i < k; i++)
{
map<int, int> mp;
int count = 0;
for (int j = i; j < n; j += k)
{
mp[arr[j]]++;
count = max(count, mp[arr[j]]);
}
ans += count;
}
return n - ans;
}

int main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
int arr[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
cout << minChange(arr, n, k)<<endl;
}
return 0;
}
``````
Tester's Solution
``````#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);

assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
//assert(false);
}
}
}

string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../CSUBS_0.in", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int sumN = 0;
forn(tc, T)
{

vector<int> A(N);
vector<map<int,int>> R(K);
forn(i, N)
{
if (i + 1 < N)
else
R[i % K][A[i]]++;
}
int res = 0;
for (const auto& ri : R)
{
int mx = 0, su =0;
for (const auto& mp : ri)
{
if (mp.second > mx)
mx = mp.second;
su += mp.second;
}
res += su - mx;
}
printf("%d\n", res);
sumN += N;
assert(sumN <= 500'000);
}

assert(getchar() == -1);
return 0;
}
``````
Editorialist's Solution
``````import java.util.*;
import java.io.*;
class CSUBS{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), K = ni();
int[] A = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
int ans = 0;
for(int i = 0; i< K; i++){
HashMap<Integer, Integer> freq = new HashMap<>();
int count = 0;
for(int j = i; j< N; j += K){
freq.put(A[j], freq.getOrDefault(A[j], 0)+1);
count++;
}
int max = 0;
for(int x:freq.values())max = Math.max(max, x);
ans += count-max;
}
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CSUBS().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
``````

Feel free to share your approach. Suggestions are welcomed as always. 6 Likes

Am I the only one who assumed this is a DP problem?
Nice problems btw.

6 Likes

same here.

instead of count if i take n-k+1 in the editorialist solution , it gives wrong ans why?. As total number of subarrays would be equal to n-k+1 and so the total number of integers at a particular position in the subarray. Please tell me whats wrong in the logic.

the variable ‘ans’ stores no. of elements which are NOT modified, no elements which will modify is equal to ‘n-ans’

Total number of integers at a particular position in a subarray would be k right and not n-k+1
n-k+1 is the no. of subarrays.
count will always be less than or equal to k

Please can someone tell me what’s wrong with my python code

``````tc  = int(input())
from collections import Counter

for _ in range(tc):
n,k = map(int,input().split())
a = list(map(int,input().split()))
inisum = sum(a[:k])
c=0
for x in range(1,n-(k-1)):
if a[x-1]==a[x+k-1]:
continue
else:
a[x+k-1]=a[x-1]
c+=1
print(c)

thanks!``````