PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Mohan Gorai
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
Simple
PREREQUISITES
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) {
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
if(IsDebuggerPresent())
{
freopen("../CSUBS_0.in", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
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);
else
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{
//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;
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);
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());}
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()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 