Question definition:
Given an array connected end to end(circular fashion). Find if thee is any arrangement of the array elements such that the absolute diff of adjacent elements is always one.
Need help to solve not able to approach it.
Could you specify what kind of complexity you need?
O(N) or O(N^2) ?
Sort the array and check if it equals to a sequence of consecutive integers
This should work in O (n log n) time.
But what if the problem needs to have adjacent difference exactlty equal to one. It won’t always work.
Nope i don’t think that will work
For example take the case
2 3 2 3
According to problem statement this is a yes
but according to your logic this is a no
I think we can create a graph. First we connect all nodes that have value with absolute difference 1 this should be O(N^2)
Then we find the articulation points. If there are no articulation points then the answer is yes otherwise no. Again complexity is O(N^2).
Why do you find articulation points?
I mean if you create a graph with an edge between two nodes i and j if abs(a[i]-a[j])=1, then you will need to find a Hamiltonian Cycle in this graph.
Yes got it.
We don’t need to “find” a Hamiltonian cycle. we just need to check if there is a Hamiltonian cycle. And i think that 0 Articulation point means there is a Hamiltonian Cycle.
So we just run a dfs and find the low link values. If at any point we find an AP we terminate.
If you just need to check for any arrangement, then it would be fine.
I think I read the problem as “find an arrangement”, that’s why I said that we’ll need to “find” a Hamiltonian Cycle.
Then I think it solves the problem in O(n^2), @vraj1994 .
1 Like
I was thinking about the solution for this problem in my sleep and came up with an idea. Currently, it fails for some test cases. Some sort of corrections should (probably) fix my approach, viz:
- Sort the given array
arr. The following steps are applicable to the sorted array. - let
freq[i]denote the frequency of elementiinarr. - Handle the base case, where, after sorting,
arr[i] < (arr[i + 1] - 1)for any 1\le i \lt N impliesNOT POSSIBLEcase. - Now, for the first and last elements of
arr:- If
freq[first] > freq[first + 1]orfreq[last] > freq[last - 1], then there is no possibility (think why).
- If
- For elements other than
firstandlast, we can observe that iffreq[element] > freq[element - 1] + freq[element + 1], there is no such arrangement. - It fails for some other test cases though.
Anyways, if anyone is working on this approach, I am attaching the scripts here.
Bruteforce that is guaranteed to pass, but slow
#include <bits/stdc++.h>
using namespace std;
#define FOR(x, N) for(int x = 0; x < N; x++)
typedef unsigned long long int ull;
typedef long long int ll;
bool is_valid(vector<int>& a) {
const int N = a.size();
for(int i = 0; i < N; i++) {
if(abs(a[i] - a[(i + 1) % N]) != 1) {
return false;
}
}
return true;
}
void solve() {
int N = 0;
cin >> N;
vector<int> A(N);
FOR(i, N) cin >> A[i];
bool flag = false;
do {
if(is_valid(A)) {
flag = true;
break;
}
} while(next_permutation(A.begin(), A.end()));
cout << (flag ? 1 : 0) << '\n';
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 0;
// t++;
if(!t) cin >> t;
FOR(test, t) {
// cout << "Case #" << (test + 1) << ": ";
solve();
}
return 0;
}
Generator I am using
#include <bits/stdc++.h>
using namespace std;
#define TEST 10
#define TEST_CASES true
int randint(int a, int b) {
return a + rand() % (b + 1 - a);
}
void generate() {
int n = randint(2, 10);
printf("%d\n", n);
for(int i = 0; i < n; i++) {
printf("%d ", randint(1, 10));
}
printf("\n");
}
int main(int argc, char* argv[]) {
srand(atoi(argv[1]));
int test_cases = randint(1, TEST);
if(TEST_CASES) {
printf("%d\n", test_cases);
}
for(int test = 0; test < test_cases; test++) {
generate();
}
return 0;
}
Ignore the following if the approach was clear.
(Contains template) My Approach, that fails for some test cases
/*
Author: Chitturi Sai Suman
Powered by: GitHub Copilot
Created: 2021-11-18 06:12:47
Contest: Codechef
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define FOR(x, N) for(int x = 0; x < N; x++)
#define inverse(a, p) power(a, p - 2, p)
typedef unsigned long long int ull;
typedef long long int ll;
const short int dc[] = {1, 0, 0, -1, -1, -1, 1, 1};
const short int dr[] = {0, 1, -1, 0, -1, 1, -1, 1};
const ll shit = ((ll)(998244353));
const ll mod = ((ll)(1e9 + 7));
const ll hell = ((ll)(1e9 + 9));
const ll inf = ((ll)(1e18 + 3));
static inline ll gcd(ll a, ll b) {
for(ll rem = 0; b > 0; rem = a % b, a = b, b = rem);
return a;
}
static inline ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
#define nax 2000003
void pre_compute() {
return;
}
void solve() {
int N = 0;
cin >> N;
vector<int> a(N);
FOR(i, N) cin >> a[i];
sort(a.begin(), a.end());
map<int, int> freq;
FOR(i, N) freq[a[i]]++;
set<int> my_set(a.begin(), a.end());
for(int i = 0; i < N - 1; i++) {
if(abs(a[i] - a[i + 1]) > 1) {
cout << "0" << '\n';
return;
}
}
bool flag = true;
for(int i: my_set) {
if(i == a[0]) {
if(freq[i] != freq[i + 1]) {
flag = false;
break;
}
}
else if(i == a[N - 1]) {
if(freq[i] != freq[i - 1]) {
flag = false;
break;
}
}
else {
if(freq[i] != max(freq[i - 1], freq[i + 1])) {
if(freq[i] < freq[i + 1] + freq[i - 1]) {
flag = false;
break;
}
}
}
}
if(my_set.size() == 3) {
flag = true;
vector<int> b(my_set.begin(), my_set.end());
sort(b.begin(), b.end());
if(freq[b[1]] != freq[b[0]] + freq[b[2]]) {
flag = false;
}
}
if(flag) {
bool have_same = true;
for(int i = 0; i < N; i++) {
if(freq[a[i]] != 1) {
have_same = false;
break;
}
}
// cerr << "have_same: " << have_same << '\n';
if(!have_same) {
cout << "1" << '\n';
return;
}
cout << (a[0] == a[N - 1] - 1 ? "1" : "0") << '\n';
return;
}
cout << "0" << '\n';
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t = 0;
// t++;
if(!t) cin >> t;
pre_compute();
FOR(test, t) {
// cout << "Case #" << (test + 1) << ": ";
solve();
}
return 0;
}
1 Like
Hi can u explain the approach with the below array
0,1,1,1,2,2,0,-1
The nodes and values
0:0
1:1
2:1
3:1
4:2
5:2
6:0
7:-1
Adj List:
0: 1,2,3,7
1:0,4,5,6
2:0,4,5,6
3:0,4,5,6
4:1,2,3
5:1,2,3
6:1,2,3,7
7:0,6
Note it is an undirected graph which may/may not contain cycles.
DFS order
0 1 4 2 5 3 6 7
low link value for all roots is zero (there is an edge from 7 to 0) thus we get a Hamiltonian cycle.
Basically that’s all we need to check. Lowlink value for everything should be zero.
Actually the point about first and last element of array
Should be
freq[first] >= freq[first + 1] or freq[last] >= freq[last - 1], then there is no possibility (think why).
Here also there is greater than equal to sign.
Apart from the two changes i suggested above your solution is brilliant and O(N)
But can you prove that If the all your conditions are false then a Hamiltonian Path definitely exists?
No, you got it wrong. Here’s an example.
[1, 1, 2, 2] \rightarrow [1, 2, 1, 2]. Even if freq[1] == freq[2], you are able to construct valid array. So, we will not get desired output if we check for the condition (freq[first] >= freq[first + 1]). It should be (freq[first] > freq[first + 1]). Similarly, for the last element (freq[last] > freq[last - 1]).
Thanks, but I don’t think it is O(N), it is at least O(N\log{N}) since we should definitely sort the array. I don’t have any proof for this, this is just a Vague idea I could come up with in my sleep 
.
@cubefreak777 is always there to help.
1 Like
Oh yes I never thought of that.