Problem Link:
Author: Niket Agarwal
Tester: Pritish Priyatosh Nayak
Editorialist: Niket Agawal
Difficulty:
Easy - Medium
Prerequisites:
Observation
Problem:
Given an array of integers. Find if there is a possible arrangement such that the sum of no two adjacent elements is equal to K.
Explanation:
Hint 1
What is the maximum number of elements that could be equal to (K) in the array?
Hint 2
What if there are only (i) and (K-i) elements in the array?
Hint 3
You need to keep count of the frequency of elements (A[i]%K)
There were two cases that needed to be checked.
First, if the frequency of element equal to K is greater than (n+1)/2.
If it is greater, then there is no valid permutation where two elements equal to K would not be adjacent to each other. Since, there are at most (n+1)/2 odd positions in an array.
If K is even, the same condition should be checked for K/2, since two adjacent K/2 would sum to K.
If the first condition is false, we move on to check the second condition.
Lets say, we only have two different elements i and K-i in the array. Then, in no case can we form a permutation that they won’t be adjacent to each other, i.e., they will be adjacent to each other and will sum to K.
These are the only two cases which needed to be checked for a “NO” answer.
If the array passes these two conditions, then there will always be a permutation such that a “YES” answer exists.
Remember to take care of modulus of negative numbers.
Go through the solutions for a better understanding.
Solutions:
Setter's/Editorialist's Solution
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
public static void process()throws IOException
{
int n=ni();
int k=ni();
int[]A=nai(n);
int[]freq=new int[k];
for(int i=0;i<n;i++)
{
int temp=A[i]%k;
if(temp<0)
temp=k+temp;
freq[temp]++;
}
int flag=0;
if(freq[0]>(n+1)/2)
flag=1;
if(k%2==0 && freq[k/2]>(n+1)/2)
flag=1;
for(int i=1;i<=k/2;i++)
{
if(i==k/2 && k%2==0)
break;
if(freq[i]>0 && freq[k-i]>0 && freq[i]+freq[k-i]==n)
flag=1;
}
if(flag==1)
pn("NO");
else pn("YES");
}
static AnotherReader sc;
static PrintWriter out;
public static void main(String[]args)throws IOException
{
boolean oj =true;
if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
int t=1;
t=ni();
while(t-->0) {process();}
out.flush();out.close();
}
static long mod=(long)1e9+7l;
static void pn(Object o){out.println(o);}
static void p(Object o){out.print(o);}
static void pni(Object o){out.println(o);out.flush();}
static int ni()throws IOException{return sc.nextInt();}
static long nl()throws IOException{return sc.nextLong();}
static double nd()throws IOException{return sc.nextDouble();}
static String nln()throws IOException{return sc.nextLine();}
static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
static class AnotherReader{BufferedReader br; StringTokenizer st;
AnotherReader()throws FileNotFoundException{
br=new BufferedReader(new InputStreamReader(System.in));}
AnotherReader(int a)throws FileNotFoundException{
br = new BufferedReader(new FileReader("input.txt"));}
String next()throws IOException{
while (st == null || !st.hasMoreElements()) {try{
st = new StringTokenizer(br.readLine());}
catch (IOException e){ e.printStackTrace(); }}
return st.nextToken(); } int nextInt() throws IOException{
return Integer.parseInt(next());}
long nextLong() throws IOException
{return Long.parseLong(next());}
double nextDouble()throws IOException { return Double.parseDouble(next()); }
String nextLine() throws IOException{ String str = ""; try{
str = br.readLine();} catch (IOException e){
e.printStackTrace();} return str;}}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define repr(i,x,y) for(int i=x;i>=y;i--)
#define int long long
#define pb push_back
#define ff first
#define ss second
#define sz(x) ((int)x.size())
#define all(x) begin(x), end(x)
#define asserti(x,l,r) assert( (x) >= (l) && (x) <= (r))
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<pair<int,int>>;
constexpr int mod = 1000000007;
constexpr int N = 2e8 + 5;
constexpr int inf = 1e18 , eps = 1e-6;
int sumn=0;
void Onigiri()
{
int n,k;
cin>>n>>k;
sumn+=n;
asserti(sumn,1,1e6);
asserti(n,1,1e6);
asserti(k,2,1e6);
int hsh[k]={0},a[n];
rep(i,0,n){
cin>>a[i];
asserti(abs(a[i]),0,1e6);
hsh[(a[i]%k+k)%k]++;
}
for(int m=0;m<=k/2;m++){
if(hsh[m]<=0||hsh[(k-m)%k]<=0)continue;
if(m*2==k||m==0){
if(n-hsh[m]<hsh[m]-1){cout<<"NO";return;}
}
else if(n-hsh[m]-hsh[k-m]==0){cout<<"NO";return;}
}
cout<<"YES";
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifdef Zoro
freopen("/home/pritish/Competitive/in", "r", stdin);
freopen("/home/pritish/Competitive/out", "w", stdout);
#endif
int t=1;
cin>>t;
asserti(t,1,10);
while(t--)
{Onigiri();cout<<"\n";}
cerr<<"\n"<<(float)clock()/CLOCKS_PER_SEC*1000<<" ms"<<endl;
return 0;
}