PATHETIC - Editorial

editorial
, , , , , ,
73

Diversity of solutions is indeed a good thing, maybe in the future this could be highlighted with an “alternate solutions” section in the editorial which gives a one-paragraph explanation of other solutions.

1 Like
75

Is it written somewhere in original problem statement that product has to be less then 2e18 ?

77

Can anyone explain how to generate those two numbers Pa and Pb?

79

can you explain why this works? :frowning:
why should we iterate from backward?

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…