PATHETIC - Editorial

thanks buddy…finally understood it

@rajarshi_basu @sjshohag @gainullinildar pls help me i wrote a similar solution to editorial but i got WA pls help i can’t figure out the bug

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool prime[101]={0},visited[101]={0};
ll lim=2e18;
void sieve()
{
prime[0]=prime[1]=1;
for(int i=2;i * i<=101;i++)
{
if(prime[i]==0)
{
for(int j=i * i;j<101;j+=i)
{
prime[j]=1;
}
}
}
}
vector < ll > matrix[101],adlist[101];
long long pa=1,pb=1;
ll ans[101];

void dfs(ll i,int h)
{

if(visited[i])
return;
visited[i]=1;

if(h%2)
ans[i]=pa;
else ans[i]=pb;
if(adlist[i].size()>0)
{
    for(int j=0;j<adlist[i].size();j++)
    dfs(adlist[i][j],h+1);
}

}
int main()
{
sieve();

set<ll> primes;
for(ll i=2;i<101;i++)
if(prime[i]==0)
primes.insert(i);
while(primes.size()>2)
{
    ll a=*primes.begin();
    primes.erase(primes.begin());
    auto it=primes.upper_bound(lim/a);
    it--;
    ll b=*it;
    primes.erase(it);
    primes.insert(a*b);
}
auto yo=primes.begin();
pa=*yo;
yo++;
pb=*yo;
ll t,n,u,v;
cin>>t;
while(t--)
{
    cin>>n;
    for(int i=0;i<101;i++)
    {
    matrix[i].clear();adlist[i].clear();
    visited[i]=0;
    }
    
    for(int i=0;i<n-1;i++)
    {
        cin>>u>>v;
        matrix[u].push_back(v);
        matrix[v].push_back(u);
    }
    int parent[n+1]={0};
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<matrix[i].size();j++)
        {
            if(matrix[i][j]!=parent[i])
            {
                parent[matrix[i][j]]=i;
                adlist[i].push_back(matrix[i][j]);
            }
        }
    }
    dfs(1,1);
    
    for(int i=1;i<=n;i++)
    cout<<ans[i]<<' ';cout<<'\n';
}

}

I’ve used two variables which are the product of alternate prime numbers under 100.
Then I made the graph bipartite. And then finally depending on the colour of every node I’m printing either of the two variables. Still I’m getting WA. Can someone help me?
Link to my solution :- WA Solution

if you take product of alternate prime numbers one of the numbers will be greater than 2e18

I improved my solution so that now the value of the two variables satisfy the limits of a[i], p1 = 1167007034667414745, p2 = 1975624735289262486. And I’m still getting WA.
Link to solution :- WA Solution

2 Likes

i am in a similar situation

1 Like

Why do we need to Greedily assign Prime Numbers to p1 and p2 ?
I am getting WA on when I assign p1 and p2 naively like this :
222

What is the reason behind this ?

Here u can check

Or

u can do in reverse order too , it will work

I found my bug. I wasn’t clearing my adjacency list. I can’t believe I forgot it again. :disappointed_relieved: Ughghghghg…

How to calculate the two primes??
I tried it, but with mine calculated p1,p2, I am getting WA

CODE LINK TO CALCULATE TWO PRIMES

1 Like

It is quite easy. Though there could be couple of more ways, but here what I did :

  1. Took all the primes till 100 in a sorted manner.
  2. Product of all prime numbers at every even index stored in a separate variable, and odd indices in a separate variable.
  3. Now there was overflow for ONLY one of them.
  4. So i divided the larger one by 5 and multiplied the other with 5.
  5. Here’s my beautiful java implementation.
  6. Make sure to read the comments from my code to see what were those numbers
1 Like

can you explain this please. Thnaks

So you checked for p1 that it never gets out of bounds. But what for p2?? :face_with_raised_eyebrow:
It does go out of bounds.
Your p1 and p2 are 614889782588491410 and 3749562977351496827
One of them is above the range 2000000000000000000

1 Like

we can take the same value twice

See my earlier comment

Yeah, I got it
Thanks a lot !!

+1

I printed 1170615464648030300 (LCM(1, 2, 3, …, 100) which is less than 2e18) for each node and got WA.
Is it mentioned in the problem that the product of values of nodes in each path can’t exceed 2e18? I can only see that the value of each node can’t exceed 2e18. Can someone please explain?

This is incorrect. Just try dividing this value by 64. The value has overflown long long

1 Like

what if there are 5 nodes in total and length selected is 4 then how to solve this