for that you gotta be active on cf, if you solve some q and enter some contests, you will start seeing other people's solution.

[deleted]

cuz youre unrated

Because you are not the trust peaple (

You need to take part in more contests

WA

WA

WA

WA

WA

perhaps next time

As a megumin picture holder...

As a anime lover...

What do you mean by "hard" exactly?

It is if you read it correctly. I did not.

I don't think so

The Editorial will be published soon.

Idea for F : w(a * b) = w(a) + w(b) — w(gcd(a, b)). So you can fix the gcd and the sum, then its just implementation which i couldnt do in 50 mins lol

$$$\omega(a \cdot b) = \omega(a) + \omega(b) - \omega(gcd(a, b))$$$

For every $$$gcd$$$ for every sum of $$$s = \omega(a_i) + \omega(a_j)$$$ calculate the number of pairs of indices $$$i \lt j$$$ such that $$$gcd(a_i, a_j) = gcd$$$ and sum of their omegas is $$$s$$$. This can be done with a convolution which name I don't know but it's basic.

Then just calculate the answer with the first formula

I couldnt solve it during the contest.

but this is what I was thinking: use w(a * b) = w(a) + w(b) — w(gcd(a, b)). sieving and saving the omega values before hand for upto 2*10^5. I found that 2*3*5*7*11*13*17*19 = 9699690 so all the values for numbers < 2*10^5 should be below 8. Which means 8c2 there are only 28 possible pairs so we pre-calculate w as well for all possible pairs

The only thing I was stuck at is how to add this w^k for all i,j i<j without n^2.

You can solve for each $$$x$$$ how many $$$\omega(a_i, a_j)=x$$$ there are, and then use this to solve the $$$k$$$ power thing.

If there are odd number of odds and a non-zero number of evens then generate upto the maximum possible and then the next elements follow result[i] = result[i-2] but if there are an even number of odds, same thing follows but result[n-1] = 0

After putting max odd number and all evens, if the remaining count is odd, you can sacrifice the smallest even number for another odd number.

You have n coins, |E| of them will be even. For 1 <= k <= n, generally you have two overreaching cases:

• Case 1: 1 <= k <= |E|+1: As you correctly put it, largest odd, then k-1 largest evens.

• Case 2: |E|+2 <= k <= n:

|O|=k-|E|, if |O|%2==0, then if either |E|==0 or |O| = n-|E|, then your max is 0; otherwise, the max is the second to last value you had in the Case 1 cases. If |O|%2 == 1, then your max is the largest in the Case 1 cases.

Most likely you missed the case when k=n

If the no. of odd numbers is even, the final score is always 0

So, bro, you are all correct except one condition, here:

if (en) { ans[i] = temp[m — 2]; }else { ans[i] = 0; }

So, when en = 0, you say ans[i] = 0, but there are cases where you can select sequence of just odd values and get, odds[0] instead of 0. Hope that makes sense!

If all the numbers are odd, then what ?

but what if not enough evens ?? we need to exhaust some odds in the front

kinda a big hint but you can first do all paths of lenght==2 and then do a topological sort on another graph that only has an original x->y edge when value[x]< value[y] I will let you figure out the dp part

I used DP on edges. Worked for me LOL

Try to think with dp idea. We can go from u to v, if we are starting simple path from u, or if a[pr[u]] + a[u] = a[v]. That means we can sort nodes by their value. Then if we fix u and v (u have edge to v), we can take the nodes which have direct edge to u and their value is equal to a[v] — a[u]. So for u we need store values by pair<weight of pr[u], u> as dp. Feel free to ask more details :)

other than the two-edge paths, you can always process the nodes in the order of the values.