JAG - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Kumar Angesh Singh
Tester: Anay Karnik
Editorialist: Mohan Abhyas

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given an undirected graph with N nodes (numbered 1 through N). For each valid i, the i-th node has a weight W_i. Also, for each pair of nodes i and j, there is an edge connecting these nodes if j - i \neq W_j - W_i.

Find the number of connected components in this graph.

Hint:

Hint

j - i \neq W_j - W_i can be rewritten as W_i - i \neq W_j - j.

EXPLANATION:

Let’s say W_i^1 = W_i - i. There is an edge between node i and node j if W_i^1 \neq W_j^1.

Case 1 All W_i^1 are equal

All W_i^1 are equal => no edges exist => no of connected components = N

Case 2 All W_i^1 are not equal

All W_i^1 are not equal => there exist i and j such that W_i^1 \neq W_j^1 => i and j are connected by edge. Consider any node k, it will be connected to atleast one of i, j(W_k^1 = W_i^1 => W_k^1 \neq W_j^1).
i, j are connected and every other node is connected to one of them => it is a connected graph => no of connected components = 1

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(Nlog(N)) per testcase as per the implementation.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int w[n];
        for(int i=0;i<n;i++){
            cin>>w[i];
        }
        bool flag=1;
        for(int i=1;i<n;i++){
            if(w[0]!=w[i]-i){
                flag=0;
                break;
            }
        }
        if(flag==0){
            cout<<"1\n";
        }
        else{
            cout<<n<<'\n';
        }
    }
    return 0;
}
Tester's Solution
#include <iostream>
#include <set>

#define int long long

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int t;
  std::cin >> t;

  while(t--) {
    int n;
    std::cin >> n;

    std::set<int> set;
    for(int i = 0; i < n; i++) {
      int x;
      std::cin >> x;
      set.insert(x-i);
    }

    if(set.size() == 1)
      std::cout << n << std::endl;
    else
      std::cout << 1 << std::endl;
  }

  return 0;
}
3 Likes

Please update Test cases

Testers and setters I need you to look into weak testcases
issue for this problem.

1 Like

Anyways, changes to the problem test cases post the contest cannot be done. We just have to ignore as we did earlier.

How are we certain that only 2 cases will come ? There could be a case of W ={3,2,1,4,6} , here set will neither be == n nor be 1.

1 Like

Why the answer will not be 1 ?

Given Weights = [3, 2, 1, 4, 6]

W_i - i = [2, 0, -2, 0, 1]

So, there is an edge between the following pairs of vertices

(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 3)
(2, 5)
...

As you can see, the whole graph is connected and forms a single component. So, the answer for this test case is 1.

1 Like

oh shit , I confused myself, thanks

1 Like