PATHETIC - Editorial

editorial
, , , , , ,
80

It’s written that each node can be assigned value upto 2e18 max in the problem statement

81

To generate p1 and p2:

p1=1,p2=1
primes=[2,3,5,...,93,97]
for p in reverse(primes):
    if (p1<p2)
        p1 = p1*p
    else
        p2 = p2*p
82

Thanks. got it. Can you explain the point that how it is concluded that these two generated numbers would be valid ( i.e., each less than 2*10^18).

83

Since we are multiplying each time with the minimum product value, the final product P (for all primes) is roughly balanced over p1 and p2.
For example 1\times100 = 100 but 10\times10=100 is the most balanced distribution.

84

can you share your approach for calculating p1,p2

85

My approach was merging the last 7-8 primes with the first 7/8 primes as p1 .and keeping remaining ones in another set p2 . Thus you obtain 2e18. constraint. As that was the only bottleneck in this problem

86
88

thanks buddy…finally understood it

89

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

}

90

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

92

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

94

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
95

i am in a similar situation

1 Like
96

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 ?

97

Here u can check

Or

u can do in reverse order too , it will work

98

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

99

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
100

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
101

can you explain this please. Thnaks

102

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