PATHETIC - Editorial

editorial
, , , , , ,
69

Thanq so much for the quick reply :smile:

1 Like
70

See Observation 5

1 Like
71

I actually like a constructive problem if it can be solved in multiple ways because not everyone thinks in the same way. You may notice that this contest have 3 constructive problems and all of them have multiple solutions.

3 Likes
72

Whatā€™s the problem with this approach : For all nodes , calculate distance from all the leaf nodes to this node then the node value is simply the lcm of all these distances .
code : CodeChef: Practical coding for everyone

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