PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Jeevan Jyot Singh, Nishank Suresh
Editorialist: Abhinav Sharma
DIFFICULTY:
2934
PREREQUISITES:
Greedy Algorithms, Maths
PROBLEM:
Chef has an array A of length N.
He calls an index i (1 \leq i \leq N) good if there exists some j \neq i such that A_i = A_j.
Chef can perform the following operation at most once:
- Choose any subsequence of the array A and add any positive integer to all the elements of the chosen subsequence.
Determine the maximum number of good indices Chef can get.
EXPLANATION:
Let freq[i] denote the number of occurrence of i in array A. Suppose we choose an integer d to be added in the operation. Using this operation a number x can be converted y only if y-x = d. So, let us divide the numbers in the range [1,1000] into d sequences of form [i, i+d, i+2*d,..] for all i in the range [1,d].
Now consider frequency array of each of these d sequences i.e., F_i = [freq[i], freq[i+d], freq[i+2*d]...]. We can add any elements of F_i to answer if it’s value is more than 1, i.e. there are more than one occurrence of the element corresponding to that frequency. So, we will try to make each of values in F_i not equal to 1. Also, the above operation can be considered as subtracting some value z at index j (z \le F_i[j]) and adding z at index i+1.
Consider all the subarray X of F_i, such that there are no elements equal to 0 in it and its length is maximum possible. Following cases occur-
- Length of X is even, i.e. X = [x_1,x_2,..,x_{2k}]. In this case we can simply add all values of X to the answer. This is because we can convert the X array into [0, x_1+x_2,....,0,x_{(2k-1)}+x_{2k}] using the above operation. We can see that each of the elements of X is not equal to 1.
- Length of X is odd and atleast one element in X is greater than 1. Let x_j > 1 , then we can think of X as [x_1,x_2,...,x_j-1,1,..]. So, now the length of X is even an using the first case, we can add all values of X to the answer.
- Length of X is odd and all the values in X are equal to 1. In this case, we can simply not consider the x_1, and we are left with an array of even length and using the first case, we can simply add all values of X except 1 to the answer. It can be proved that we cannot make all the indices good in this case.
Finally, we can iterate over values of d from 1 to 1000 and answer will be the maximum number of good indices over all the values of d.
TIME COMPLEXITY:
O(N*max(A_i)) for each test case.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
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){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
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,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
int sum_n = 0, sum_m = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 998244353;
void solve(){
int n = readIntLn(2,1000);
int freq[1001] = {0};
int x;
vector<int> a;
rep(i,n){
if(i<n-1) x = readIntSp(1,1000);
else x = readIntLn(1,1000);
a.pb(x);
freq[x]++;
}
sort(a.begin(), a.end());
int ans = 0;
rep(i,1001) if(freq[i]>1) ans+=freq[i];
bool z[1001] = {0};
rep_a(d,1,1000){
int tmp = 0;
for(auto i:a){
if(z[i]) continue;
int cnt = 0, sum = 0, grt1 = 0;
for(int j=i; j<=1000+d; j+=d){
if(j<=1000 && freq[j]) z[j]=1;
if(j>1000 || freq[j]==0){
if(cnt%2==1 && !grt1) tmp += sum-1;
else tmp += sum;
cnt=sum=grt1=0;
}
else{
cnt++;
sum+=freq[j];
if(freq[j]>1) grt1=1;
}
}
}
for(auto i:a) z[i] = 0;
ans = max(ans, tmp);
}
cout<<ans<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1,500);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
assert(sum_n<=2000);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Tester 1 solution
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
freq = [0]*1001
for x in a:
freq[x] += 1
ans = 0
for d in range(1, 1001):
cur = 0
mark = [0]*1001
for x in a:
if mark[x] == 1:
continue
ptr = x
tot = 0
mx = 0
while ptr <= 1000:
if freq[ptr] == 0:
break
mark[ptr] = 1
tot += freq[ptr]
mx = max(mx, freq[ptr])
ptr += d
if mx > 1 or tot%2 == 0:
cur += tot
else:
cur += tot-1
ans = max(ans, cur)
print(ans)
Tester 2 solution
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(...)
#endif
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const long long INF = 5000;
// -------------------- Input Checker Start --------------------
long long readInt(long long l, long long r, char endd)
{
long long x = 0;
int cnt = 0, 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)
{
if(is_neg)
x = -x;
if(!(l <= x && x <= r))
{
cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
assert(false);
}
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 readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }
vector<int> readVectorInt(int n, long long l, long long r)
{
vector<int> a(n);
for(int i = 0; i < n - 1; i++)
a[i] = readIntSp(l, r);
a[n - 1] = readIntLn(l, r);
return a;
}
// -------------------- Input Checker End --------------------
const int N = 1005;
int sumN = 0;
int temp[N], freq[N];
array<int, 2> dp[N];
int get_answer(int n)
{
// dp[i][0] = maximum answer till ith index such that I did not transfer anything from (i - 1)th index to ith index
// dp[i][1] = maximum answer till ith index such that I made a non zero transfer from (i - 1)th index to ith index
if(temp[0] > 1)
dp[0][0] = dp[0][1] = temp[0];
else
dp[0][0] = dp[0][1] = 0;
for(int i = 1; i < n; i++)
{
dp[i] = {0, 0};
int value = temp[i] > 1 ? temp[i] : 0;
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + value;
if(temp[i - 1] == 0)
dp[i][1] = -INF;
else
{
if(i - 2 >= 0)
dp[i][1] += max(dp[i - 2][0], dp[i - 2][1]);
dp[i][1] += (temp[i] + temp[i - 1] > 1 ? temp[i] + temp[i - 1] : 0);
}
if(temp[i - 1] > 1 and temp[i] > 0)
dp[i][1] = max(dp[i][1], dp[i - 1][1] + temp[i]);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
void solve()
{
int n = readIntLn(2, 1000);
vector<int> a = readVectorInt(n, 1, 1000);
sumN += n;
int mx = *max_element(a.begin(), a.end());
for(int i = 0; i <= mx; i++)
freq[i] = 0;
for(int x: a)
freq[x]++;
int ans = 0;
for(int x = 1; x <= mx; x++)
{
int cur = 0;
for(int i = 1; i <= x; i++)
{
int idx = 0;
for(int j = i; j <= mx; j += x)
{
temp[idx++] = freq[j];
}
cur += get_answer(idx);
}
ans = max(ans, cur);
}
cout << ans << endl;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T = readIntLn(1, 500);
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
assert(sumN <= 2000);
readEOF();
return 0;
}