ECJN206-Editorial

PROBLEM LINK:

Practice

Author: Akash Kumar Bhagat
Tester: Sandeep Singh,Arnab Chanda
Editorialist: Akash Kumar Bhagat

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Graph Traversal, Breadth-First-Search, Depth-First-Search

PROBLEM:

You are given a network of people related or came into contact with each other after the lockdown was imposed. You have 2 characters(which may or may not be the part of the network) and one of them has recently tested positive of Covid-19. Your task is to find whether there is a possibility of the other person getting infected or not(Supposing each and everyone who directly or indirectly came into contact with the infected person may be infected).

EXPLANATION:

Given the name of the infected person, we have to check whether there is a chance of the other person getting infected or not. We could analyse the network/graph of people who came into contact with each other, and traverse the network from the infected person (if he/she is present in the network) and check whether we encounter the other person on our way or not.

We may use any graph traversal technique either BFS or DFS and will get the desired result. In case the infected person id not in the graph, that means no one in the network came into contact with the infected person hence all other people including the other person is safe.

SOLUTIONS:

Python 3.7
def chk(graph,javed,mohan):
    q=[javed]
    visited={};boo=False
    for i in graph.keys():
        visited[i]=False
    visited[j]=True
    while(len(q)>0):
        v=q[0];q.pop(0)
        if(v==mohan):
            return True
        for i in graph[v]:
            if(not visited[i]):
                visited[i]=True
                q.append(i)
    return False
                
for _ in range(int(input())):
    n,j,m=input().split();n=int(n)
    dic={}
    dic[j]=[];dic[m]=[]
    for i in range(n):
        a,b=input().split()
        #print(a,b)
        if(a in dic.keys()):    dic[a].append(b)
        else:   dic[a]=[b]
 
 
        if(b in dic.keys()):    dic[b].append(a)
        else:   dic[b]=[a]
    #print(dic)
    ans="Quarantine" if(chk(dic,j,m)) else "Stay Home, Stay Safe"
    print(ans)

CPP
#include <bits/stdc++.h>
#define ll long long int
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define scanarr(a,b,c) for( i=b;i<c;i++)cin>>a[i]
#define showarr(a,b,c) for( i=b;i<c;i++)cout<<a[i]<<' '
#define ln cout<<'\n'
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define mod 1000000007
#define MAX 100005
using namespace std;
class dsu {
 public:
  vector <int> p;
  int n;
 
  dsu(int _n) : n(_n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
  }
 
  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }
 
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      return true;
    }
    return false;
  }
};
////////////////////////////////////////////////////////////////CODE STARTS HERE////////////////////////////////////////////////////////////////
 
 
vector <string> ans = {"Stay Home, Stay Safe", "Quarantine"};
unordered_map<string, int> mp;
 
 
void solve(){
 
  int n, i, j;
  string x, y, a, b;
  mp.clear();
  set <string> st;
 
  cin >> n >> x >> y;
  st.insert(x);
  st.insert(y);
  
  vector<pair<string, string>> joins;
 
  for(i = 0 ; i < n; i++){
 
      cin >> a >> b;
      st.insert(a); st.insert(b);
      joins.push_back({a, b});
  }
  dsu dd = dsu(st.size() + 10);
 
  int cnt = 1;
 
  for(auto x : st)
    mp[x] = cnt++;
 
  for(auto x : joins)
    bool ok = dd.unite(mp[x.first], mp[x.second]);
  
 
  cout << ans[dd.get(mp[x]) == dd.get(mp[y])] << endl;
 
    
}
int main(){
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif
 
    int t;
    cin >> t;
    while(t--)
        solve();
} 
3 Likes

I’m getting WA with DSU approach.
Solution
@akay_99 @arnie8991 @sandeep1103

Why WA with DSU approach ?
My Solution https://www.codechef.com/viewsolution/34849392
@akay_99 @sandeep1103 @arnie8991 Can you please tell which case I am missing

@akay_99 Can you explain the logic behind the need to check for the condition X == Y in the problem? I had multiple WA submissions because of that.

1 Like

I left the contest after 2 - 3 WAs. The question clearly says that “There are two friends in our story namely Jawed and Mohan.” @akay_99 Why will one assume X == Y after this?

@ahambrahmasmi sorry for the inconvenience you guys had for DSU.

This was because the X and Y are being chosen randomly hence there was a chance that X==Y.

Edit: we have corrected the test cases. extremely sorry for the trouble caused to you guys

2 Likes

That’s not fair. You should rejudge it. I was able to solve 8 problems, got multiple WAs on this one.
submission

@akay_99 You could have done some thing like:

while(X == Y)
        Y = random_string();
1 Like

My solution using dsu
https://www.codechef.com/viewsolution/34846493

Wow I wasted my time on this question thinking I was wrong. But its just testcases were wrong. Well played.

My submission

All the DSU Solutions are rejudged and the rank-list is updated.
Really sorry for the inconvenience :no_mouth:

3 Likes

Huge respect for rejudge. Btw in rankings submission was changed but total penalty and rank didn’t.

1 Like