I hope there are no ugly geometry problems(like in Educational Round 87).

BTW glhf xD

Hey MikeMirzayanov, I have got TLE on D whereas i have used O(NlogN) Solution. When i resubmitted it after final standing it got accepted. Solution from contest — https://mirror.codeforces.com/contest/1366/submission/83442824 Solution After contest -https://mirror.codeforces.com/contest/1366/submission/83505708 They both are same solution.. Kindly look at the issue and try to resolve if possible

Video Tutorial for Problem A,B,C,D

A sad meme :)

I think the announcement was not there on the Home page earlier.

I quit .

I'm guessing Harbour.Space University signed a contract with Mike for publicity. As part of the contract, 2 contests per month must be held sporting the uni's name. Since this is a long term contract, Mike needed a reliable team of people to hold these (easier than finding a new team for each contest).

And one more thing they all are from same institution Saratov state U.

Afraid of timelimited on 2 3 4 5 6 7 8 9 10.。。

It had only been 50 minutes since the blog was made public. Wait for few hours, I know my true redditers won't let you feel bored

But every time the codeforces community writes a div2-only contest, somewhere in the world 3000 people with a rating of 2100+ are sad :)

Because Asishgup got a huge amount of upvote in his blogs while posting about contests.

Because Ashishgup is Indian.

Your text to link here... Have a look at this. Contribution is moreover dynamic and not static.

It's interesting that people downvoted this comment, including me.

Deleted.

because they promote some particular university every time

I think the contests were Ashishgup were great, but saying they are just on another level is too much. Today's contest was great too, I loved C today. And other problems were great too.

This meme is previously posted by Nieb_Hasan_077 here

I'll comeback soon don't worry

I can hear this meme.

Educational = MultipleTestForces

Yes, just submit working solutions, then everthing will be fine. But do not talk to anybody while contest about the problems.

lol it looks like it's actually more efficient. Pigeoncopter

Any examples?

But there were almost no if-else and casework in today's A and B.

which website?

test every prime factor (if the prime fac divides multiple times go mult all of them in p^n) and its reciprocal, one of them should always work if there is a solution. i'm not sure if you can do that for every single prime factor (and thus auto break the loop saving time) but i didnt want to take any chances. reason this works is because one number will have all the prime factors and one number will have none, if the 2nd is 100% coprime then when u add the second to first theres absolutely 0 chance of it being mod p, however its possible that its mod a different prime so thats why i tested every prime (it ran within the time constrants since primes under sqrt(10^7) was like 400 or something)

First observation is that d1 and d2 are co-prime (or else (d1, d2) would divide a). Second observation is that if (d1 + d2, a) = x then x divides a (obviously). So, there shoudln't be any divisor x of a such that x|d1 and x|d2. From here it's obvious how to solve: get number x2 = a / x1 so that (x1, x2)=1 and if there are no such solutions, then there is no solution

if ai have only 1 prime divisor, then -1

if a[i]%2=0 then a[i]=2^k * x, so pair (x,2) alway true

if a[i]%2=1 then a[i]=p1^x1*p2^x2*.... which (pi<p2<...) then pair(p1,p2) alway true

TRY TO PROVE THEM !

Using seive you can find the spf(smallest prime factor) array for all numbers till 10^7.

Then to query a number num, divide num by spf[num] till num isn't divisible by spf[num].

if num==1 answer doesn't exist, otherwise answer is (spf[num], num)

.

A simple solution I came up with was as follows: Consider all primes $$$p_1, p_2, ..., p_k$$$ which divide $$$n$$$, with $$$k \ge 2$$$. Then we consider $$$a = p_1 + p_2 p_3 ... p_k$$$. Suppose $$$gcd(a, n) > 1$$$. Then at least one prime which divides $$$n$$$ also divides $$$a$$$, however this is a contradiction (fun fact: note that the same argument can be used in a proof of the infinitude of primes). Now if $$$k < 2$$$, note that there is no solution.

To implement this, we can do the following: using the sieve of Eratosthenes, find the product of all primes which divide $$$n$$$, and call it $$$f[n]$$$. Also keep storing the smallest prime divisor of $$$n$$$, say $$$g[n]$$$, then your answer will be $$$(g[n], f[n]/g[n])$$$ if it exists.

It is clear that gcd(d1, d2) = 1 otherwise gcd(d1+d2, a) !=1 Let p be the smallest prime which divides a. Then, a = XY where Y is the largest number such that Y%p !=0 If Y=1: we are sure that there can't be 2 divisiors>1 such that gcd(d1+d2, a)=1 So in this case answer is (-1, -1) Now we will prove with (d1, d2) = (X, Y) we are done. Proof: Note the following 2 identities 1. gcd(a,b) = gcd(a,a+b) 2. if gcd(a,b)=1 and gcd(a,c) = 1 then gcd(a,bc)= 1 Now note that gcd(X,Y) = 1 This implies gcd(X+Y, X) = gcd(X+Y, Y) = 1 By (2) It is clear that gcd(X+Y, XY) = gcd(X+Y, a). Hence, find p, then find Y by dividing a_i by p until you get a_i%p!=0. X = a_i/ Y If Y = 1 your answer is (- 1, -1) else (X,Y)

Simple Approach

For an $$$even$$$ number, answer will be $$$($$$ $$$2$$$, Product of remaining odd prime factors $$$)$$$

For an $$$odd$$$ number, answer will be $$$($$$ $$$1st$$$ Smallest prime factor, $$$2nd$$$ Smallest Prime factor $$$)$$$

And obviously, first, you need to check whether alteast $$$2$$$ distinct prime factors for a number exists or not. if not answer will be $$$($$$ $$$-1$$$, $$$-1$$$ $$$)$$$

Proof

For an $$$odd$$$ number,

Consider an example $$$ai$$$ = $$$105$$$ $$$( 3 * 5 * 7 )$$$. Ans is $$$(3, 5)$$$.

$$$3$$$ is $$$1st$$$ smallest prime factor and $$$5$$$ is $$$2nd$$$ smallest prime factor of $$$105$$$.

Let $$$x = d1 + d2 = 3 + 5 = 8$$$.

$$$g = gcd(x, 105)$$$ and obviously $$$g$$$ can't be $$$3$$$ or $$$5$$$. So $$$g$$$ should be greater than $$$5$$$, which is not possible. (why? Let $$$x' = g * e$$$ , $$$e$$$ is even number, $$$e$$$ must be aleast $$$2$$$. You can see $$$x' > x$$$ if $$$g > 5$$$, which is not possible.So $$$g$$$ has to be $$$1$$$.

For an $$$even$$$ number,

Consider an example $$$ai$$$ = $$$210$$$ $$$( 2 * 3 * 5 * 7 )$$$. Ans is $$$(2, 105)$$$.

$$$105 = 3 * 5 * 7$$$ (Product of remaining odd prime factors).

You can see $$$d1 = 2$$$ and $$$d2 = 105$$$, now forget about $$$d1$$$ and ask a question from yourself. What is the minimum $$$y$$$, I should add to $$$d2$$$ such that $$$g = gcd(d2 + y, ai) > 1$$$. And you will find you need to add smallest prime odd factor, for this case it is $$$3$$$ but we are adding just $$$2$$$ ($$$d1 = 2$$$, hence the answer).

83434115
Consider the cases where the number x is odd or even.

If x is even:

1. If x is a power of 2, then no solution exists
2. Otherwise, there exists some odd factor k > 1 and gcd(2+k, x) = 1

If x is odd:

Check for every factor k < sqrt(x) if gcd(x/k + k, x) = 1
Motivation: If x/k and k are coprime, then they would be the solution

Otherwise, no solution exists

https://mirror.codeforces.com/contest/1366/submission/83472749 we just need to find 2 factor which are coprime to each other

I initialized the min as I always do with MOD. And yup, WA4.

increases by different constants in O(n) ranges. its not same constant always.

This might give you the idea where it fails :

Input :

4 3 1000000000

1 2 1

2 3 100000

1 4 99999

Here you will be getting maximum answer by repeating the edge 99999. But there comes a time when 100000 will dominate.

Let $$$f[u][k]$$$ denote the maximum weight path ending at $$$u$$$ using exactly $$$k$$$ edges. You can compute it for all $$$1 \leq k \leq m$$$ via $$$\mathcal O(nm)$$$ DP. Consider a long path using $$$x > m$$$ edges. It will always arrive at some node $$$u$$$ using some $$$k$$$ edges and repeatedly traverse the maximum weight edge adjacent to $$$u$$$ (let's call it $$$\text{max}_u$$$) the rest $$$x-k$$$ times. So the answer for $$$x$$$ is the maximum of $$$f[u][k] + (x-k)\text{max}_u = \text{max}_u x + f[u][k]- \text{max}_uk$$$ over all $$$1\leq u\leq n$$$ and $$$1\leq k \leq m$$$. Interpret this quantity as a line $$$y=mx+c$$$ and compute the lower hull for all of $$$\mathcal O(n)$$$ such lines. Now each line can give you the maximum answer for some range $$$[l,r]$$$ of values $$$x$$$. You can use binary search to find this range and add the contribution using some standard formula.

Here's my AC 83474415 submission.

1. First part handles case $$$k \le n$$$ (dp)

2. second part handles $$$n+1 \le k \le q$$$ (convex hull of $$$mx_i * (k-n) + dp_i$$$).

Complexity is $$$O(n*m + n*n) = O(n*m)$$$ (you could probably solve second part in $$$O(n*log(n))$$$).

In my point of view, it's a straightforward application of prime factorization.

Could you please explain your approach?