I tried a totally different approach to solve the problem COVID19B and further tried to optimize it, but it couldn’t pass even a single task.
here is the link to my solution…
https://www.codechef.com/viewsolution/37956709
can anyone tell me where I’m lacking?
My solution:
#include<bits/stdc++.h>
#define F first;
#define S second;
#define PB push_back;
#define er erase;
//Done by vaibhavgadag
#define MP make_pair;
#define fastio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
const long long MOD = 1e9 + 7;
const long long INF = 1e9 + 7;
typedef long long int ll;
using namespace std;
int main()
{
fastio;
ll t,n;
cin>>t;
while(t--)
{
cin>>n;
ll arr[n],maxele=-1,minele=INF;
vector<ll>maxi,mini;//for storing index of maximum and min
for(ll i=0;i<n;i++)
{
cin>>arr[i];
if(arr[i]>maxele)
{
maxele=arr[i];
}
if(arr[i]<minele)
{
minele=arr[i];
}
}
//Finding maximum element index and store in maxi vector and minimum element and store in mini vector
//maxi and mini has index of max ele and min ele
vector<ll>arr1;
for(ll i=0;i<n;i++)//1st person
{
set<ll>s;
ll tempmini=INF;
ll tempmax=-1;
s.insert(i);//1st person
//from max to end
for(ll j=i;j<n;j++)
{
if(arr[j]<arr[i])
{
s.insert(j);
}
//noting slow runner
// can be ith element itselg e.g 3 1 2 3,if i==1 rhen min is i==1
if(arr[j]<tempmini)
{
tempmini=arr[j];
}
}
//checking for min value spreading others before max index
for(ll j=0;j<i;j++)
{
if(arr[j]>tempmini)
{
s.insert(j);
}
if(arr[j]>arr[i])
{
s.insert(j);
}
if(arr[j]>tempmax)
{
tempmax=arr[j];
}
}
for(ll j=i+1;j<n;j++)
{
if(arr[j]<tempmax)
{
s.insert(j);
}
}
arr1.push_back(s.size());
}
sort(arr1.begin(),arr1.end());
/*vector<ll>arr2;
for(ll i=0;i<n;i++)
{
set<ll>s1;
ll tempmax=-1;
s1.insert(i);
for(ll j=0;j<i;j++)
{
if(arr[j]>arr[i])
{
s1.insert(j);
}
if(arr[j]>tempmax)
{
tempmax=arr[j];
}
}
for(ll j=i+1;j<n;j++)
{
if(arr[j]<tempmax)
{
s1.insert(j);
}
}
arr2.push_back(s1.size());
}
*/
cout<<arr1[0]<<' '<<arr1[arr1.size()-1]<<endl;
}
return 0;
}Thanks, @vaibhavgadag for responding but, I wanted to know the mistake in my logic/approach to the problem. The above logic/program described by you is well by me too.
Can you explain what you have done ?
Can you please explain your logic?
Share your code so that i can help you in debugging
sir,For the test case 1 3 2 5 answer should be 1 2 ,but ur code says 1 3.Hope this test case helps to figure out. 
you are checking how many infections would current velocity leads to.
while in question its mentioned that other infected people can further spread the virus, you need to check for them too.
My DFS Solution
ll t, n;
map<ll, vector<pair<float, ll>>> g;
set<ll> s;
void dfs(ll node, float time) {
s.insert(node);
for(auto i : g[node]) {
if(!(s.find(i.second) != s.end()) && i.first >= time)
dfs(i.second, i.first);
}
}
int main(){
optimize
test(t) {
ll x;
cin >> n;
vector<ll> arr(n);
for(ll& i : arr) {
cin >> i;
}
for(ll i = 0; i < n; i++) {
ll j = i - 1, k = i + 1;
while(j >= 0) {
if(arr[j] > arr[i])
g[i].push_back({((i - j) * 1.0)/(arr[j] - arr[i]), j});
j--;
}
while(k < n) {
if(arr[k] < arr[i])
g[i].push_back({((k - i) * 1.0)/(arr[i] - arr[k]), k});
k++;
}
}
ll mn = n, mx = 1;
for(ll i = 0; i < n; i++) {
dfs(i , 0.0);
mn = min(mn, (ll)s.size());
mx = max(mx, (ll)s.size());
s.clear();
}
g.clear();
cout << mn << ' ' << mx << '\n';
}
return 0;
}
1 Like
Your code fails on this test case:
1
4
5 0 1 0
Correct output: 3 4
well, here is the description of my approach…
- input N, & Vi 0<=i<=N
- construct a line (y=mx+c) with y=P(t) {position of ith athlete at time t} , m=Vi , and c=initial position of the ith athlete.
- store all such lines in a vector.
- iterate through the vector and count the no. of intersections of ith line with other lines (for which I used cross multiplication to solve 2 linear equations).
- The line with maximum intersections corresponds to the worst-case whereas the line
with minimum intersections corresponds to the best case.
Good thought of doing it with graph approach, really liked your solution. keep it up
Thanks bro, but it isn’t working or lacking somewhere. I’m currently working on it.
you have took n as c in y = mx + c
which means that all line intersect at x = 0, y=c
Thus, if anyone is infected everyone will get infected eventually, which is wrong.
I am not saying that your approach is wrong it just don’t fits best for this problem. i would suggest not to concentrate more on it rather than this try to solve it by adjacency matrix. that would be really fast and easy to implement.
No, c here is the initial position of the athlete.
like for the input…
1
4
1 3 2 5
4 lines will be constructed with equations…
y=x+1
y=3x+2
y=2x+3
y=5x+4
according to my knowledge of the problem, the correct output of this should be 2 4
the best case is given by 2nd athlete who could only infect the 1st athlete. isn’t it ?
Nope,
it will be 4 for 2nd athlete. Try again
couldn’t think that way, can u pls brief it?
I think you are not clearly considering the case when newly infected athlete will start infecting others.
+
while intersection, compare the time or position when an athlete is infected. If a player comes in contact with someone who was infected earlier with someone else, then he also gets infected.
+
remember to take time of infection in float/double
Here is my solution:
https://www.codechef.com/viewsolution/37690498
Share your code
so that i can debug it