COVID19B - Editorial

[ashutoshd_14]

true bro

[nitinsrt]

Exactly buddy

[cricket_99]

here is the sol. link->CodeChef: Practical coding for everyone
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…

[afmab]

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

[adityanand09]

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

[adityanand09]

use simple bubble sort on the given array

COVID19B - Editorial

There is the simplest solution, which requires no simulation, even it doesn’t require to check that after how much time one athlete will cross another one. You have to simply reverse the given array and sort it in decreasing order. you have to use bubble sort Let’s take an example the speed array is 3 1 4 2. reverse -->2 4 1 3 now let’s say 2 is infected and denote it with “.” i.e. 2. 4 1 3 now we sort step by step like this 4. 2. 1 3 // first swap will infect the athlete having speed…

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

[kim_taehyung]

for me too bro i couldnt solve it

[paracetamol650]

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 ?

[ansh_11]

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";
}

}

[rahul_th]

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

[alei]

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

[misrablemishra]

I saw this solution in the list of successful submissions page: CodeChef: Practical coding for everyone

Can someone explain why this works?

[doomedtodie]

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();	
	}
}

[cricket_99]

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

[berlin_19]

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 : CodeChef: Practical coding for everyone
If there are some corner cases, I’d like to know them please

[misrablemishra]

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

[abhishek_garg]

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

Here is the link to my submission : CodeChef: Practical coding for everyone

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;
}

[arpit92_8]

why 120 is being multiplied in the setters solution?

[arpit92_8]

@alei

for(int i=0;i<n;i++){
  vector<bool>infected(n);
  infected[i]=true;      
  for(auto p:mp){
    bool spread=false;
    for(int x:p.second)spread|=infected[x];
    if(spread){
      for(int x:p.second){
        infected[x]=true;
      }
    }
  }

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

[blank_kami]

Thanks!