COVID19B - Editorial

true bro

Exactly buddy

here is the sol. link->https://www.codechef.com/viewsolution/37558233
bascially here 1 to node n are 1 to n numbered athletes & in the adjacency matrix i have stored the time when i’th & j’th player will meet…
Then calling DFS using i’th palyer as root node(1<=i<=n) & i’th palyer can only infect j th player if their time meeting is +ve & greater than equal to the time when i’th palyer was infected & only that j’th player is responsible for speading infection to others also…

2 Likes

i did dfs too.So first task is to form a graph where weighted edges represent time at which the nodes contact,so we start from each and infect all that are in direct contact with initial node and for all other nodes check if time of contact for the next edge is more if its more we explore that node else we continue to other nodes.
I think a visual explanation would be easier to uderstand

1 Like

yes you are absolutely right, it can be solved without reversing the array

use simple bubble sort on the given array

you don’t need to reverse the array (sorry for that)

for me too bro i couldnt solve it

i will never ever , ever ever forget this q , took me 5 days to implement . @alei is it possible if you could give the 2nd subtask ?

1 Like

Can anyone help me find why my code did’t clear the subtask 2 ??

#include
#include <bits/stdc++.h>
#include
#include
#include
#define ll long long int
#define mp make_pair
#define pb push_back
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t,n,no,i,j,count,k,c,z,nu,a;
cin>>t;
while(t–)
{
vector<pair<ll,int>>v;
vectorv1;
cin>>nu;
while(nu–)
{
cin>>no;
v.pb(mp(no,0));
}
n=v.size();
for(i=0;i<n;i++)
{ count=0;
for(z=0;z<n;z++)
v[z].second=0;

        v[i].second=1;
        
        for(j=i+1;j<n;j++)
        {
            if(v[i].first>v[j].first)
            v[j].second=1;
        }
        
        for(k=i-1;k>=0;k--)
        {
                if(v[k].first>v[i].first)
                { 
                v[k].second=1;
                for(c=i+1;c<n;c++)
                {
                    if(v[k].first>v[c].first&&v[c].second==0)
                    v[c].second=1;
                }
                }
                
                else if(v[k].first<v[i].first)
                { 
                for(c=i+1;c<n;c++)
                {
                    if(v[k].first>v[c].first&&v[c].second==1)
                    v[k].second=1;
                }
                }
        }
        for(a=0;a<n;a++)
        {
            if(v[a].second==1)
            count++;
        }
        v1.pb(count);
    }
    sort(v1.begin(),v1.end());
    cout<<v1.front()<<" "<<v1.back()<<"\n";
}

}

After the slower to the right are infected they can in turn infect the ones slower on the left but greater than the infected

you mean input data? Since constraints are small, it contains all possible sequences.

I saw this solution in the list of successful submissions page: https://www.codechef.com/viewsolution/37620727

Can someone explain why this works?

This is the solution i came up with

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

typedef long long Int;
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define sz(s) (int)(s).size()
#define pb push_back
#define mp make_pairS
#define F first
#define endl "\n"
#define S second
const int inf = 1000000000;
const int MOD = 1000000007;

void solve()
{
    Int n;cin>>n;
	Int a[n];
	Int temp;
	FOR(i,0,n)cin>>a[i];
	Int minans=0,maxans=0;
	Int count[n]={0};
	FOR(i,0,n){
	    count[i]=1;
	    temp=*min_element(a+i, a+n);
	    FOR(j,0,i)
			if(a[j]>temp)
			    count[i]++;
		temp=*max_element(a, a+i+1);
		FOR(j,i+1,n)
	        if(temp>a[j])
			    count[i]++;

	}
	sort(count,count+n);
	minans=count[0];
	maxans=count[n-1];
	cout<<minans<<" "<<maxans<<endl;
}  

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	fastio;
	Int t=1;
	cin>>t;
	while(t--){
		solve();	
	}
}

yes , I observed & thinking how is it accepted , as per my observation it should give wrong ans. :thinking: but it’s working :sweat_smile:

1 Like

I need some help debugging my code , couldn’t get the second task correct
I used an adj matrix to store time and check if there is contact.
then i used a for loop which runs for every racer and stores in a queue the racers he will infect
then i run another for loop , to check if any other racers will be infected via indirect contact
(e.g 1 infects 2, then 2 infects 3)
here is a link to my solution : https://www.codechef.com/viewsolution/37901824
If there are some corner cases, I’d like to know them please

Yeah I can’t seem to prove why this should work? Very neatly writtencode and looks like an elegant approach

Can anyone help me find why my code doesn’t work?

Here is the link to my submission : https://www.codechef.com/viewsolution/37927673

Code -

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

int solve(vector<vector<double>> meeting, int infected, double time)
{
    int count=1;
    for(int i=0; i<meeting.size(); i++)
    {
        if(meeting[infected][i] > time)
        {
            double check=meeting[infected][i];
            for(int j=0; j<meeting.size(); j++) 
            {   
                meeting[j][i]=-1;
            }
            count = count + solve(meeting, i, check);
        }
    }
    return count;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>> t;
    for(int i=0; i<t; i++)
    {
        //INPUT
        int n;
        cin >> n;
        vector<int> v(n);
        for(int i=0; i<n; i++) 
        {
            cin>>v[i];
        }

        //WORKING
        int lowest=INT_MAX;
        int highest=INT_MIN;
        
        vector<vector<double>> meeting(n, vector<double> (n, -1));
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==j || v[i]==v[j]) continue;
                double temp = ((double)(j-i) / (double)(v[i]-v[j]));
                if(temp >= 0)
                {
                    meeting[i][j] = temp;
                }
            }
        }

        for(int i=0; i<n; i++)
        {
            int ans=solve(meeting, i, 0);
            lowest=min(lowest, ans);
            highest=max(highest, ans);
        }
        

        //OUTPUT
        cout<<lowest<<" "<<highest<<"\n";
        
    }
    return 0;
}


why 120 is being multiplied in the setters solution?

can pls someone explain this code ?
using vectors and pairs in map is difficult to undersatnd.

Thanks!