ELWINTER - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Voicu Mihai
Tester: Manan Grover
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy

PREREQUISITES:

BFS, Graphs

PROBLEM:

You are given a connected graph with N nodes and M edges. You are given Q queries of the following types:

  • 𝟷 u: Given node u(1\le u \le N), set the state of the node u to frozen.
  • 𝟸 𝚝: Given t, let t units of time pass by
  • 𝟹 𝚟: Given node v (1 \le v \le N), answer if node v is currently frozen.

Initially, no node is frozen.
The graph has the following property:

  • If, at time T, a node u is frozen, then, at time (T+1), all neighbours of u become frozen.

For each query of type 3, answer whether the node is currently frozen.

EXPLANATION:

Let us first see that the graph is connected, hence if you look at the 2^{nd} type of the query then you can realize that the if the any node is frozen at time x then the whole graph will get frozen at x+N-1 seconds at maximum because of the only single reason that the graph is connected.

Hence you need not to be afraid of such large constraints for the second query. Now as the problem says you need to do that and it’s a simple BFS.

While writing the editorial I remembered the analogy used by CP algorithms to explain BFS when I was new to BFS. I will paste that analogy and you will find it interesting as it’s what our question says:

“The algorithm can be understood as a fire spreading on the graph: at the zeroth step only the source s is on fire. At each step, the fire burning at each vertex spreads to all of its neighbors. In one iteration of the algorithm, the “ring of fire” is expanded in width by one unit (hence the name of the algorithm).”

They used this analogy to explain BFS and here are we our question is this analogy isn’t that. Hence we will be using BFS for the same. Now let’s see how we will be dealing with the queries.

  • 1^{st} type of Query.

    For this type of query you will be given a node which we want you to froze that. If the node is already frozen sorry for the query, you can forgave us. But if its not frozen just froze that and add to the queue.

  • 2^{nd} type of Query.

    For this type of query, as we told you need to perform the bfs till the current time to the given time. But remember you after a certain interval of time every node will get frozen and you can stop performing bfs after that and can simply ignore these type of queries from then.

  • 3^{rd} type of Query.

    For this type of query please check if the node is frozen and let us know. Thanks for your help.

TIME COMPLEXITY:

O(Q + N + M)

SOLUTIONS:

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

const int nmax = 3e5 + 5;

vector<int> g[nmax];

int frozen[nmax];
queue<pair<int,int> > que; // I used this to ensure that timelimits won't be against the use of the std::queue, although I know it is preffered to hand-write the queue

int currenttime;

static void timepass() {
  while(!que.empty()) {
    int t, x;
    tie(t, x) = que.front();
    if(t > currenttime) 
      break;
    que.pop();
    for(auto y : g[x]) {
      if(frozen[y])
        continue;
      que.push({t + 1, y});
      frozen[y] = 1;
    }
  }
  currenttime++;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  for(int i = 0,x, y; i < m; i++) {
    cin >> x >> y;
    --x;
    --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }  
  for(int i = 0; i < q; i++) {
    int t, x;
    cin >> t >> x;
    if(t == 1) {
      --x;
      if(frozen[x] == 0)
        frozen[x] = 1, que.push({currenttime, x});
    }
    if(t == 2) {
      x = min(n + 1, x + currenttime);
      while(currenttime < x)
        timepass();
    }
    if(t == 3) {
      --x;
      cout << (frozen[x]? "YES\n" : "NO\n");
    }
  }
  return 0;
}

Tester
#include <bits/stdc++.h>
using namespace std;
void sim(priority_queue<pair<int, int>> &pq, int vis[], int t, vector<int> gr[]){
  while(pq.size()){
    int x = -pq.top().first;
    int y = pq.top().second;
    if(x > t){
      break;
    }
    pq.pop();
    if(vis[y] != -1){
      continue;
    }
    vis[y] = x;
    for(int i = 0; i < gr[y].size(); i++){
      pq.push({-x - 1, gr[y][i]});
    }
  }
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int n, m, q;
  cin>>n>>m>>q;
  vector<int> gr[n + 1];
  for(int i = 0; i < m; i++){
    int u, v;
    cin>>u>>v;
    gr[u].push_back(v);
    gr[v].push_back(u);
  }
  int vis[n + 1];
  memset(vis, -1, sizeof(vis));
  priority_queue<pair<int, int>> pq;
  int t = 0;
  bool f = false;
  while(q--){
    int x, y;
    cin>>x>>y;
    if(x == 1){
      pq.push({-t, y});
    }
    if(x == 2){
      t += y;
    }
    if(x == 3){
      sim(pq, vis, t, gr);
      if(vis[y] == -1){
        cout<<"NO\n";
      }else{
        cout<<"YES\n";
      }
    }
  }
  return 0;
}
3 Likes

I was getting TLE on 2 cases. Maybe I am wrong but in my case also it will be Q+M+N. can anyone tell me when it will exceed the time limit.

Update : I found the issue, one line issue in case of q==1 :pleading_face:

import heapq
from collections import deque

def bfs(graph,visited, vc, timer,frozen):
    q = deque(frozen)
    empty = deque([])
    # print(q,timer,empty,frozen,visited)
    while(timer > 0):
        while(q):
            vnode = q.popleft()
            for i in graph[vnode]:
                if(not visited[i]):
                    vc -=1
                    empty.append(i)
                    visited[i] = True
                if(vc <= 0):
                    break
            if(vc <= 0):
                break
            # print(q,timer,empty,frozen,visited)
        q = empty
        empty = deque([])
        if(vc <= 0):
            break
        timer -= 1
    
    frozen = list(q)
    return [frozen,vc]

n,m,q = map(int,input().split())
graph = {}
x = 10000000000000
visited = [False for i in range(n+1)]
vc = n
mini = [x for i in range(n+1)]
frozen = []
for i in range(1,n+1):
    graph[i] = []

for _ in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for _ in range(q):
    qu,val = map(int,input().split())
    if(qu == 1):
        if(not visited[val]):
            visited[val] = True
            frozen.append(val)
    elif(qu == 2):
        if(vc >0):
            timer = val
            resVal = bfs(graph,visited,vc,timer,frozen)
            frozen = resVal[0]
            vc = resVal[1]
    else:
        print("YES" if visited[val] else "NO")

my wrong submission using djikstras like algo
I didn’t realise simple bfs would do the job…During contest i was trying to solve this problem offline by creating an array “time_to_freeze” which stores the earliest time every node gets frozen and then using this information i will say a node x at time t is frozen if t >= time_of_freeze[x] else node x is not frozen
To create the time_of_freeze array , I thought this problem as a graph with a additional node (lets call it super node) and super node has weighted edge with nodes present in query 1 with weight as the time at which it appears in query 1 and all other edges in graph have weight = 1.Now basically we have to do djikstras to get the “time_to_freeze” array (which is the smallest dist from super node in the new assumed graph)

But I am getting wrong answer…Can some point out where am I wrong??

1 Like

this is my solution : Link

My Logic is similar to yours , kind of multisource bfs , but if u see my implementation I had to use a temporary queue so I was thinking the test cases were weak.
@cherry0697 can u please confirm about the weak tcs

This question had very tight time limits.
My code didn’t work in Java but same code with syntax modifications worked in C++.

2 Likes

I used almost same approach but gave TLE in JAVA.
link
I did not see even one Accepted JAVA solution

1 Like

I was trying to do the same thing , got WA. Turns out the original problem is pretty straightforward.

Here is my simple approach -
I have initialized a vector of length n for storing 1 if the node is frozen and 0 if the node is not frozen and initialized with zeroes.
With the passing of each second of time, I do the following -

  1. I iterate through all the nodes and check if they are frozen or not
  2. For the nodes, which are not frozen, I start checking the neighbors of those nodes (simply iterating over the adjacency list of that node), and if I find a neighbor, which is marked, I put this node in the mark vector and break, thus moving to the next node.
  3. I have a mark vector that is initialized every second, which stores which nodes to mark after this second, as marking nodes directly in between seconds would be a problem.
  4. After iterating through all the nodes, I mark all the nodes in the mark vector as this second has now ended.
  5. now during the iteration of nodes, I keep a count to check whether all the nodes are already marked or not, and if all the nodes are already marked, there is no use of repeating this process for further coming seconds, and I use a global variable(like a flag, you can say), to break out to stop this process for further seconds.
    My Submission Link - Solution: 60869964 | CodeChef
/* 
add a check here if all the nodes are visited or not. 
if all are visited then you don't have to run this loop.
*/
                    while (x-->0){
                        int size=frozen.size();
                        if(size==0)
                            break ;
                        while (size-->0){
                            int val = frozen.poll();
                            while (graph[val].size()>0){
                                int topVal=graph[val].poll();
                                isFrozen[topVal]=true;
                                frozen.add(topVal);
                            }
                        }
                    }

I am getting WA in Test Case 11 and 15 whats 's the problem ,can anyone help

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define Time cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define vi vector<int>
#define onesbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define sp(x, y) fixed << setprecision(y) << x
#define w(x)  int x;cin >> x;while (x--)
#define tk(x) int x;cin >> x;
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
#define debug(x) cerr<< #x <<" ";_print(x);cerr<<endl;
#else
#define debug(x)
#endif
template <class T> void _print(T t){cerr<<t;}
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(vector < vector <T> > v){cerr<<"[\n";for(int l=0;l<v.size();l++){{for(int k=0;k<v[l].size();k++)cerr<<v[l][k]<<" ";}cerr<<"\n";}cerr<<"]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
class gcd{public:int g,t;};
int modularInverse(int a,int m){int z=(a%m+m)%m; return z; }
gcd extended_euclidean(int a,int b,int t1,int t2){ if(b==0){ gcd x; x.g=a; x.t=t1; return x; }int t=t1-t2*(int)(a/b);return extended_euclidean(b,a%b,t2,t);}

vector<int>v[300003];

void dfs(vector<bool>&affNeighbourNode,int node,int i,int d,vector<bool>&state,vector<int>&temp){
    if(i>=d) {
        temp.pb(node);
        return;
    }
    for(auto x:v[node]){
        if(state[x]==0){
            state[x]=1;
            dfs(affNeighbourNode,x,i+1,d,state,temp);
        }
    }
    affNeighbourNode[node]=1;
}

int32_t main(){
fast


#ifndef ONLINE_JUDGE


    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);


#endif


int n,m,q;
cin>>n>>m>>q;

vector<bool>state(n+1,0);
vector<int>affecNode;
vector<bool>affNeighbourNode(n+1,0);
for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    v[x].push_back(y);
    v[y].push_back(x);
}



for(int i=0;i<q;i++){
    int type,x;
    cin>>type>>x;
    if(type==1){
        if(affNeighbourNode[x]==0){
            affecNode.push_back(x);
        }
        state[x]=1;
    }
    else if(type==2){

        vector<int>temp;
            for(auto z:affecNode){
                if(affNeighbourNode[z]==1) continue;
                else
                dfs(affNeighbourNode,z,0,x,state,temp);
        }
        
        affecNode.clear();
        affecNode=temp;
    }
    else{
        if(state[x]==1) cout<<"YES\n";
        else 
        cout<<"NO\n";
    }
    debug(state);
}

return 0;
}

Can anyone help me out like what i am doing wrong
my approach is simple I am using multi source bfs and marking all the nodes minimum time required by them to be frozen. for all the queries which needs to be answered i will check if the node was frozen before the curTime.I am storing the values of node(which needs to be answered) and curTime in req vector.After performing multi source bfs i am checking whethther i node is frozen or not and printing answer.(I am getting lot of wa please help me out below is my submission )
https://www.codechef.com/viewsolution/60885227

1 Like

If all nodes are visited then size will be zero just in next loop. So it will run just 1 extra time.

Can anyone tell me what is the difference between these 2 if-statements?

image
Submission link: Solution: 60885645 | CodeChef

image
Submission link: Solution: 60885670 | CodeChef

I am getting ac on first and wa on the second one… don’t know why

In the first snippet, you’re checking only the type of query inside if. But in the second snippet, you’re also checking another condition !popped[x - 1]. This will impact the flow of control. Consider a case where t == 1 is true but !popped[x - 1] is false. In this case, the control will not enter both if and else if. Instead, it will enter else which is not what we want. You should also make sure that the control enters else only when t = 3.

1 Like

Oh fml, thanks for pointing it out, I really overlooked it during contest, and got 6-7 wa because of that xD

1 Like

in the video editorial , i have noticed that they are using two queues: qq and q. Can anyone explain why can’t we use just one of them ?

I have some doubts

  1. what exactly is the purpose of priority queue pq? and why are we pushing -t as its first element instead of pushing t simply

  2. why do we need the condition of x> t in the sim function? I can’t understand how it is working

Was it guaranteed that no two u, v will be the same in input? no.
I did this problem by just using two unordered sets instead of a queue but I have used a map to ensure distinct u,v pair (gives tle). After removing that map solution gets ac.

Can someone give the wrong test case for my solution? @admin
Link: Solution: 60910450 | CodeChef

It is passing all the test cases except two. My approach is very different, so I want to know where is the mistake in my solution.

@suman_18733097 Please let me know the wrong test case. I am not able to get why using the dfs approach is wrong.

The solution is pretty cool. Faster and cleaner than what I was doing.