It was created 14 hours and kept as a draft and now it is made public.

prepared earlier and made private. made public only after the contest

That means either pi belongs to R and qi belongs to L, or pi belongs to L and qi belongs to R. Since this is true for all pi and qi, then the sum of |pi — qi| is the same as the sum of R — L

This might help in much better understanding

In the first WA testcase, the numbers were $$$p=2^4 \times p_1 \times p_2$$$, $$$q=2 \times p_1$$$, where $$$p_1,p_2$$$ are some large primes. Your solution printed $$$2^4 \times p_2$$$, where the correct answer is $$$p_1 \times p_2$$$

Mine WA at 18th T_T Link to solution

Well... It is something between $$$n^2 \log n$$$ and $$$n^4$$$ :) It depends on your $$$T(n)$$$.

It means that it is between $$$O(n^2 \log n)$$$ and $$$O(n^4)$$$ depending on your implementation. I agree, unexplained arbitrary notations should be avoided...

same

I'm still confused with the solution provided above , can you please eloborate it !

Use Fermat's little theorem to find the modular inverse of n! via fast exponentiation.

Basically k / x is congruent to ka (mod m) if m is prime and a=x^(m-2), so you can just find n! mod m and (2n)! mod m, and then use exponentiation to get (n!)^(m-2) mod m. The answer is just (2n)! mod m multiplied with (n!)^(m-2) mod m twice, modulo m the whole thing.

You can use modular inverse and store them like this 97357968. I think it is a good template

https://mathworld.wolfram.com/BinomialCoefficient.html

in this link see the definition of Binomial coefficients for nonnegative integer y. For calculating 2n! use Fermat theorem

Let us consider the following test case

1
3 4
1 3 3
3 2 1

Here, a is sorted in ascending order. And b is sorted in descending order. also, a[0]+b[0] = 4, which is equal to 4, and a[n-1]+b[n-1] = 4, which is equal to 4.

However, a[1]+b[1] = 5, which is greater than 4

cases

1) if p%q!=0, then answer is p itself

2) else we need a largest factor of p such that it is not divisible by q
let's say the prime factorization of p is 2^x*3^y.. and for q as 2^a*3^b.., as p%q==0 then x>=a, y>=b and so on for every prime factor of p.

Now is the trick/move, we can find possible x of p by removing some factor of p from prime factorization of p, for eg. if I remove 2^(x-a+1), you can see that p/2^(x-a+1) is no more divisible by q. That's it you have to try removing different prime's power and the one with maximum p/prime^(x-a+1) is the answer.

Have some patience, it will automatically update in some time.

how did you enable dark mode??

I understood one approach. Here it is:
if $$$p\% q\neq 0$$$ then $$$x=p$$$
else we can represent $$$p$$$ and $$$q$$$ as follows:
$$$p={p_1}^{k_1}*{p_2}^{k_2} \dots {p_y}^{k_y}*{p_{y+1}}^{k_{y+1}} \dots {p_m}^{k_m}$$$
$$$q={p_1}^{l_1}*{p_2}^{l_2} \dots {p_y}^{l_y}$$$ where $$$p_1,p_2 \dots p_m$$$ are prime numbers.
Here $$$k_1 \geq l_1, k_2 \geq l_2, \dots ,k_y \geq l_y$$$ because $$$p\% q=0$$$
Now we have to take some factor of $$$p$$$ such that it is not divisible $$$q$$$. We can do this by taking some prime number power equal to one less than corresponding power in prime factorization of $$$q$$$ or you can say that we have to divide $$$p$$$ by that prime factor until $$$p$$$ is not divisible by $$$q$$$ . We can do this for all prime factors of $$$q$$$ and take the maximum one. Here is my submission

I don't know if it will make more sense or not the way I thought is ,

Let's call the power of a prime number in prime factorization of a number prime count.

if a number(x) has at least one prime count greater than another number(y) than y%x!=0 Suppose , x=2*2*2*2*3

and y=2*2*3*3*3*5

then y/x will be something like (3*3*5)/2 which won't be a integer.

so now for the given two numbers p & q , we need to find a 'x' that where p%x==0 & x%q!=0and we have to make it the biggest. So we start by making x=p (in another way saying taking all the primes in p) then checking for every prime in q can we make the prime count of q greater than that of x. We print which ever gives the largest number.

vector<ll>primes;//all the primes in the prime factorization of q.
for(ll i=0;i<primes.size();i++)
{
    ll x=p;

    while(x%primes[i]==0)
    {
       x/=primes[i];
       if(x%q!=0)
       break;
    }
    
    ans=max(ans,x);

}

so suppose ,

p=2*2*2*2*3

q=2*2*2*3

then x will be =2*2*3

What is a "malaysian knapsack"?

So sad I was not able to see this during contest. Intuition really plays a big factor in that I think. I straight went to calculating combinations.

Think of it this way-> Lets say the array is sorted, then the problem get reduced to choosing a subsequence of n elements, reverse it and then find the "cost". Now try to find which elements will always contribute a negative value ( that is -a[i]) and which will contribute a positive value (that is + a[i])............you will realise that elements from 1....n always contribute a negative value, while elements n+1.....2n contribute a positive value. In the end just multiply the final answer with the number of possible combinations.

yeah... It took me one hour to understand.

same here. QAQ

I came up with a $$$O(N^2)$$$ solution, which I calculated the appearance of each pair $$$(a_i,\ a_{i+1})$$$ (sorted). Wondering if it's possible to reduce it down to $$$O(N)$$$?

Which problem was that?

You didn't sort

Sorry I didn't see in the problem that the arrays are already sorted.

The problem is there are multiple cases in ONE test case, and if you are exiting the input with return (in one solve() iteration) once you found something >=x, the other numbers left in a,b array won't be read, therefore all the following inputs are wrong.

Yeah, I think he also commented the same on the announcement blog.

DSU without path compression can cancel the previous merge. So you can add all the edge between two groups, using DSU to judge whether this group pair is 'bad', then delete the edges and restore the DSU.

You may see the technique using DSU with rollback to check bi-graph in this problem 813F - Bipartite Checking.

Wow thanks <3

Read this to understand the rating system

I can tell you my logic which got accepted. for q, i calculated it's prime factors and their powers (how many times a particular prime no occured) . i stored this in a vector of pairs and then checked whether p is divisible by all prime factors of q or not. if not then p is the ans. else suppose the power of a prime factor of q in p is p1 and in q it is p2. so, i divided p by pow(pf,p1) and multiplied by pow(pf,p2-1). i did this for every factor of q and calculated the maximum number formed out of them. sol link- https://mirror.codeforces.com/contest/1445/submission/97400076

Div2-D is easy once you see that property that the sum is same for all permutations. If not, then not. Additionally the statement was formulated in a way that it was easy to get it wrong concerning the ordering of the two halfs L and R.

Div2-C on the other hand is fairly clear, all that division and things. What else can we do than a prime factorization of the only value where we can do it? Once realized that it is not so hard to use the fatorization to construct ans.

Consider the smallest value in a[], min(a[]). Which one of b[] values would be "the best" to pair with that?

Well, in b[] there is a biggest value, max(b[]). If $$$max(b[])+min(a[]) > x$$$, then there is obviously no solution.

Else it is optimal to "get rid of max(b[])" by using it. Then repeat with the next smallest value in a[]... same again, you will pair it with the then biggest value in b[].

You end sort a[] ascending, and b[] descending, and checking all pairs a[i]+b[i].

Now, I know how to do it in $$$O(n^2 \log n)$$$ time complex and $$$O(n^2)$$$ space complex if $$$f(p, q)$$$ is bilinear.

Just note that if $$$x_i$$$ belong to the left side, then $$$y_i$$$ belong to the right side, and vice verse.

So we only have to consider $$$f_k(p, q) = \sum_{i = 1}^k x_i y_i$$$ with $$$x_k$$$ in the left side and $$$y_k$$$ in the right side.

And the answer with be $$$\displaystyle 2 \sum_{p, q} \sum_{k = 1}^ n f_k(p,q)$$$

In order to compute $$$\displaystyle \sum_{p, q} f_k(p, q)$$$, we only have to computer sum of $$$k$$$-subarry of left and right side. donated by $$$(l_1, \cdots, l_k)$$$ and $$$(r_1, \cdots, r_k)$$$, and then $$$\displaystyle \sum_{p, q} f_k(p, q) = \sum_{i = 1}^k l_i \cdot r_i$$$.

the origin time complex is $$$O(n^3)$$$, but there is a convolution in above computation, so we can solve this problem with time complex $$$O(n^2 \log n)$$$ with the help of NFT.

Division under mod does not work like that.

For better implementation see https://cp-algorithms.com/combinatorics/binomial-coefficients.html

since i + 1 may not divided by ans, since ans = ans % p

sort the origin array $$$a$$$ and then the answer for both case is

time complex $$$O(n^2)$$$