CSUBS - Editorial


Contest Division 1
Contest Division 2
Contest Division 3

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






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.


  • 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.


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.


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


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

#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;
	    if ('0' <= g && g <= '9') {
		    x *= 10;
		    x += g - '0';
		    if (cnt == 0) {
			    fi = g - '0';
		    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 {

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

int main(int argc, char** argv) 
#ifdef HOME
	    freopen("../CSUBS_0.in", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    int T = readIntLn(1, 1000);
    int sumN = 0;
    forn(tc, T)
	    int N = readIntSp(1, 100'000);
	    int K = readIntLn(1, N);

	    vector<int> A(N);
	    vector<map<int,int>> R(K);
	    forn(i, N)
		    if (i + 1 < N)
			    A[i] = readIntSp(1, 100'000);
			    A[i] = readIntLn(1, 100'000);
		    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{
    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);
            int max = 0;
            for(int x:freq.values())max = Math.max(max, x);
            ans += count-max;
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
    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());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));

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

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

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:


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


why is the answer is (n-ans) instead of ans?

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])
    for x in range(1,n-(k-1)):
        if a[x-1]==a[x+k-1]: