Anyway, interesting problem set although with some difficulties on system test.

Whenever you move along an edge, some numbers are either added to the set of divisors of the current vertex, or removed from it (and the cost of the edge is the number of affected elements). So, ideally you want your path to have length equal to $$$d(x) + d(y) - 2d(gcd(x, y))$$$, where $$$d(i)$$$ is the number of divisors of $$$i$$$.

If you go through $$$gcd(x, y)$$$, then all divisors of $$$x$$$ which are not divisors of $$$y$$$ are removed, then all remaining divisors of $$$d(y)$$$ are added, so the path has length $$$d(x) + d(y) - 2d(gcd(x, y))$$$, which is optimal. But if you don't go through $$$gcd(x, y)$$$, then you either go through one of its divisors (thus removing $$$gcd(x, y)$$$ from the set, so the length is greater than optimal), or go through some number which is neither a divisor of $$$x$$$ nor a divisor of $$$y$$$.

Reformulate the query problem: we have two numbers $$$a$$$ and $$$b$$$ and want to get $$$b$$$ from $$$a$$$. We can do it only by modifying or dividing a by prime number. Every change costs difference between each number divisor's count.

Calculate change's cost

We could represent any number $$$n$$$ like $$$n=p_1^{l_1}p_2^{l_2}...p_n^{l_n}$$$ ($$$l_i$$$ can be 0, it means $$$p_i$$$ isn't a divisor of $$$n$$$)

Count of divisors, let's name it $$$d(n)$$$, it will be $$$d(n)$$$ = $$$(l_1+1)(l_2+1)...(l_n+1)$$$. When we change $$$a$$$ to $$$b$$$ by modifying we waste $$$d(b) - d(a)$$$.

$$$a=p_1^{l_1}p_2^{l_2}...p_i^{l_i}...p_n^{l_n}$$$

$$$b=p_1^{l_1}p_2^{l_2}...p_i^{l_i+1}...p_n^{l_n}$$$

As we have seen, we have modified by $$$p_i$$$. Calculate divisor's difference: $$$d(b) - d(a) = (l_1+1)(l_2+1)...(l_{i-1}+1)(l_{i+1}+1)... (l_n+1) = \frac{d(a)}{(l_i+1)}$$$ For dividing it works in opposite way: we waste $$$d(a) - d(b)$$$.

$$$Observation 1$$$: if we during our changes have modified and divided by some prime number we could not do these two operations.

$$$Proof$$$. Consider changes between these two changes. $$$x➔xq➔x_1q➔...➔x_nq➔x_n$$$, if we delete first and latest operations we have: $$$x➔x_1➔...➔x_n$$$.

Compare costing changes $$$x_iq➔x_{i+1}q$$$ and $$$x_i➔x_{i+1}$$$ by modifying by $$$p≠q$$$.

$$$d(x_{i+1}q)-d(x_iq) = \frac{d(x_iq)}{l+1}$$$

$$$d(x_{i+1})-d(x_i) = \frac{d(x_i)}{l+1}$$$

$$$l$$$ is a power of $$$p$$$ in canonical representation of number $$$x_i$$$ and $$$x_iq$$$, $$$l$$$ is the same because $$$l$$$ only changes if $$$p=q$$$ $$$\frac{d(x_iq)}{l+1} > \frac{d(x_i)}{l+1}$$$, so better do in second way.

$$$Observation 2:$$$ it is better firstly to do dividing by prime numbers, which aren't divisors of $$$b$$$, then do modifying until we get $$$b$$$.

$$$Proof.$$$ Consider the simplest example: $$$a = pc$$$, $$$b=qc$$$, where $$$p$$$ and $$$q$$$ are prime numbers. Notice $$$c = gcd(a,b)$$$. If we firstly modify and then divide our changes will be $$$a➔pcq➔b$$$. We waste $$$2*d(pcq) - d(a) - d(b)$$$.

If we firstly divide and then modify our changes will be $$$a➔c➔b$$$. We waste $$$d(a) + d(b) + 2d(c)$$$.

Subtract second equation from first one:

$$$2d(pcq) - 2d(a) - 2d(b) + 2d(c)$$$

$$$(d(pcq) - d(a)) - (d(b) - d(c))$$$, substitute $$$a=pc$$$ and $$$b=qc$$$

$$$(d(pcq) - d(pc)) - (d(qc) - d(c))$$$

$$$d(pcq) - d(pc) = \frac{d(pc)}{l_q+1}$$$, $$$d(qc) - d(c) = \frac{d(c)}{l_q+1}$$$, where $$$l_q$$$ is a power of $$$q$$$ in canonical representation of number $$$pcq$$$ and $$$qc$$$.

Numbers $$$pc$$$ and $$$c$$$ have same $$$l_q$$$, so $$$d(pcq) - d(pc) - d(qc) + q(c) = \frac{d(pc) - d(c)}{l_q+1}$$$ and it is bigger then zero, so $$$d(a) + d(b) + 2d(c)$$$ is less then $$$2d(pcq) - d(a) - d(b)$$$, so better firstly to divide and then modify.

$$$UPD: $$$

$$$Obseravation3:$$$ if we during our change have divided and modified by some number we could not do these two operations.

$$$Proof.$$$

Consider changes between these two change: $$$xq➔x➔x_1➔...➔x_n➔x_nq$$$. If we detele first and last operations we have: $$$x_q➔x_1q➔x_2q➔...➔x_n➔x_nq$$$. Name them $$$changing$$$ $$$paths$$$.

Using $$$obseravation 2$$$ we know to get optimal $$$changing$$$ $$$path$$$ firstly we do dividing, then do modifying. Our $$$changing$$$ $$$paths$$$ can be represented like:

$$$xq➔x➔x_1➔...➔x_k➔..➔x_n➔x_nq$$$

and $$$x_q➔x_1q➔x_2q➔...➔x_kq➔..➔x_{n}q➔x_nq$$$.

We do only dividing to get $$$x_kq$$$ and $$$x_k$$$ and then only modifying.

Calculate sum of changing costs in first $$$changing$$$ $$$path$$$:

$$$(d(xq)-d(x))+(d(x)-d(x_1))+...+(d(x_{k-1})-d(x_k))+(d(x_{k+1})-d(x_k))+$$$ $$$+...+(d(x_n) -d(x_n-1))+(d(x_nq)-d(x_n))=$$$ $$$\frac{d(x)}{l+1}+\frac{d(x_1)}{l_1+1}+...+\frac{d(x_{k-1})}{l_{k-1}+1}+\frac{2d(x_k)}{l_k+1}+\frac{d(x_{k+1}}{l_{k+1}}+...+\frac{d(x_n-1)}{l_{n-1}}+ \frac{d(x_n)}{l+1}= \frac{d(x)}{l+1}+\frac{d(x_n)}{l+1}+\sum\limits_{i=1}^k\frac{d(x_i)}{l_i+1}+\sum\limits_{i=k}^{n-1}\frac{d(x_i)}{l_i+1}$$$

Notice in first and last fractions the denominator is the same because when we change $$$xq➔x$$$ and $$$x_n➔x_nq$$$ we divide and modify by same prime number $$$q$$$. In general, when we change $$$x_i➔xq_i$$$ or $$$xq_i➔x_i$$$ we waste $$$\frac{d(x_i)}{l+1}$$$.

Calculate sum of chaging costs in second $$$changing$$$ $$$path$$$: $$$(d(xq)-d(x_1q)) +...+(d(x_{k-1}q) - d(x_kq)) + (d(x_{k+1}q) - d(x_kq)) +...+(d(x_nq) -d(x_{n-1}q))=$$$ $$$\sum\limits_{i=1}^k\frac{d(x_iq)}{l_i+1}+\sum\limits_{i=k}^{n-1}\frac{d(x_iq)}{l_i+1}$$$

Subtact first equation from second:

$$$\frac{d(x)}{l+1}+\frac{d(x_n)}{l+1}-(\sum\limits_{i=1}^k\frac{d(x_iq)}{l_i+1}-\sum\limits_{i=1}^k\frac{d(x_i)}{l_i+1})-(\sum\limits_{i=k}^{n-1}\frac{d(x_iq)}{l_i+1}-\sum\limits_{i=k}^{n-1}\frac{d(x_i)}{l_i+1})$$$

Since $$$d(x_iq)-d(x_i)=\frac{d(x_i)}{l+1}$$$, so we get $$$\frac{d(x)}{l+1}+\frac{d(x_n)}{l+1}-\sum\limits_{i=1}^k\frac{d(x_i)}{(l_i+1)(l+1)}-\sum\limits_{i=k}^{n-1}\frac{d(x_i)}{(l_i+1)(l+1)}$$$, by modifying by $$$l+1$$$ we get: $$$d(x)+d(x_n)-\sum\limits_{i=1}^k\frac{d(x_i)}{l_i+1}-\sum\limits_{i=k}^{n-1}\frac{d(x_i)}{l_i+1}$$$

Separately calculate $$$d(x)-\sum\limits_{i=1}^k\frac{d(x_i)}{l_i+1}$$$ and $$$d(x_n)-\sum\limits_{i=k}^{n-1}\frac{d(x_i)}{l_i+1}$$$:

Since $$$d(x_i)-d(x_{i-1}) = \frac{x_i}{l_i+1}$$$, so $$$d(x_i) = \frac{d(x_{i+1})(l_i+2)}{l_i+1}$$$

$$$d(x)-\sum\limits_{i=1}^k\frac{d(x_i)}{l_i+1} = d(x)-\frac{d(x_1)}{l_1+1}-\sum\limits_{i=2}^k\frac{d(x_i)}{l_i+1}=\frac{d(x_1)(l_1+2)}{l_1+1}-\frac{d(x_1)}{l_1+1}-\sum\limits_{i=2}^k\frac{d(x_i)}{l_i+1}=$$$ $$$\frac{d(x_1)(l_i+1)}{l_i+1}$$$-$$$\sum\limits_{i=2}^k\frac{d(x_i)}{l_i+1}=$$$ $$$d(x_1)-\sum\limits_{i=2}^k\frac{d(x_i)}{l_i+1}$$$

If we go on in the end we will get $$$d(x_k)$$$

Similarly we calculate $$$d(x_n)-\sum\limits_{i=k}^{n-1}\frac{d(x_i)}{l_i+1}=$$$ $$$\frac{d(x_n)(l_{n-1}+2)}{l_{n-1}+1}-\frac{d(x_{n-1})}{l_{n-1}+1}-\sum\limits_{i=k}^{n-2}\frac{d(x_i)}{l_i+1}=$$$ $$$d(x_{n-1}-\sum\limits_{i=k}^{n-2}\frac{d(x_i)}{l_{i+1}}$$$ Finally we get $$$d(x_k)$$$

In this way, the total sum will be $$$2d(x_k)$$$, $$$2d(x_k)$$$ is bigger than zero, so first equation is bigger then second one, so it isn't optimal to divide and then modify by some prime number $$$q$$$.

Using first and third observation we know we only have to divide by prime number, which aren't divisors of $$$b$$$, and then do modify by prime numbers, which arent't divisors of $$$a$$$.

Using second observation we know that firstly we do dividing then we do modifying.

As we have seen, $$$changing$$$ $$$path$$$ $$$x➔gcd(x,y)➔y$$$ is only one, which fits the requirements, so it is optimal path.

P.S. I think it could be proved much easier :)

let us look at some examples after doing mindless graphs of N=12,24,44,100,1000,245 we figure out that we go through gcd

use scanf and printf

Submitted your code again Use the fastio commands properly.

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

have a look to my solution https://mirror.codeforces.com/contest/1334/submission/76178087

What I did was calculated the minimum number of bullets required for each position, if started shooting from monster at that position.

Think it that way: It there where no explosions, we would have to fire one shoot per lifepoint. So, we can earn points by usings explosions.

How much can we earn? The maximum earnings per monster is limited as $$$min(a[i], b[i-1])$$$ This is the power of the explosion, or the total life points of the affected monster, whichever is less.

Since the monsters are in a circle, we can kill on after the other, the explosion damage will be maximum possible on every explosion.

But we have to start somewhere in the circle. The monster where we start does not get any demage by an explosion. As the starting point we use the monster where we would earn the least points, this is the one with minimum $$$min(a[i],b[i-1])$$$

I think my solution is pretty neat used a rolling function to brute force for all rotations

int32_t main()
{
    long long t;
    cin >> t;
    while (t--)
    {
        long long n;
        cin >> n;
        vector<long long> ar(n);
        vector<long long> br(n);
        for (long long i = 0; i < n; i ++)
        {
            cin >> ar[i];
            cin >> br[i];
            ar.push_back(ar[i]);
            br.push_back(br[i]);
        }
        long long fans = 1e18;
        long long cur = 0;
        // for initial window
        for (long long i = 0; i < n; i ++)
        {
            if (i == 0)
            {
                cur += ar[i];
            }
            else
            {
                cur += max(0ll, ar[i] &mdash; br[i-1]);
            }
        }
        fans = min(fans, cur);

        long long l = 0, r = n-1;
        while (l < n)
        {
            fans = min(fans, cur);
            // remove lth ans
            cur -= ar[l];
            // remove l+1th ans
            cur -= max(0ll, ar[l+1] - br[l]);
            cur += ar[l+1];
            cur += max(0ll, ar[r+1] - br[r]);
            l ++, r ++;
        }
        cout << fans << "\n";
    }
    return 0;
}

Use ArrayList instead of long[]

Maybe problem in not fast Java io.

Arrays.sort() can get up to n^4 time in weird cases like for nearly sorted raw type arrays (e.g long[]). To combat this, use Long[] or an ArrayList instead when you plan to sort the contents of a long[] array. I guarantee this change will fix your solution.

Hi, I did many of the hacks for B. You are correct. In java, sorting an array of primitives uses quicksort. This can be exploited by creating an anti-quicksort hack to force the sort to run in O(N^2).

Cool!!!)

First try to write the whole lexicographically smallest cycle of the whole graph.

For simplicity I will take a complete graph of size 4: ( the graph below should be bi-directional )

The lexicographically smallest cycle of this graph is:

1 2 1 3 1 4 2 3 2 4 3 4 1

As you can see, there's a pattern here ( 1 2 1 3 1 4 ) ( 2 3 2 4 ) ( 3 4 ) ( 1 ) which can be modeled by this for loop:

for i in 1..n-1
    for j in i+1 .. n
        print(i + " " + j + " ")
print(1)

Still this is O(n^2), to make it O(n) we need the element close enauph to l and complete the pattern and write the element between l and r, to so do we can simplify the search using this observation: in the pattern the first group starts with 1 and it's of size 2*(n-1), the second group starts with 2 and it's of size 2*(n-2) and so on, we can use this fact to loop through i and find and i such that 2*(n-i) is closest to l , then just print the elements between l and r.( don't forgot the 1 at the end).

Suppose n = 5. for now forget about l and r. Then the lexicographically smallest list will be:
1 2 1 3 1 4 1 5 (1-5)
2 3 2 4 2 5 (2-5)
3 4 3 5 (3-5)
4 5 (4-5)
1.

And what if n = 6? If you guess it right, the list will be:
1 2 1 3 1 4 1 5 1 6 (1-6)
2 3 2 4 2 5 2 6 (2-6)
3 4 3 5 3 6 (3-6)
4 5 4 6 (4-6)
5 6 (5-6)
1

Try it with some other graph with different number of vertices. Keep sum of every list above in a prefix array. From there it will be easy to determine where l starts and where r ends.

First of all lets try to construct the lexographically minimum cycle in the graph:

We have to choose a starting node, we will choose node 1 otherwise any other other as starting node makes the cycle lexographically greater than {1 followed by some other nodes}.

For example : {3 followed by some other nodes} > {1 followed by some other nodes}.

Now we have chosen the starting node as node 1. Where should we go now? Given a complete graph you could go to any other node, so we choose 2.

Because again {1 follow by 2 followed by some other nodes} is less than any other possibility.

now we have 1->2, now where? Again choose 1(for similar reasons). so we have 1->2->1.

now we are back at node 1 but now we can not choose to go to node 2 again(edge 1->2 is already traversed once). So we are forced to go to some node j ( j > 2).

Again for similar reasons explained above, you will choose to go to node 3.

1->2->1->3. Where now? from 3 you may go to any other node.

So again go to 1 : 1->2->1->3->1 So if you see the pattern now, then we have :

1->2->1->3->1 ... 1->n-1->1->n Now where? If I go back to 1 then I am trapped because I have already used every outward edge from 1. So I am forced to go to node 2 instead of 1.

1->2->1->3->1 ... 1->n-1->1->n->2->3->2->4->2 ... 2->n-1->2->n

So we get the lexographically smallest cycle as below : {1->2->1->3->1 ... 1->n-1->1}->n->{2->3->2->4->2 ... 2->n-1->2}->n->{3->4->3...->3->n-1->3}->n.....n->{n-1}->n->1.

The thing inside the braces(call it Bi) is simply {i->i+1->i->i+2 and so on} and after that back to node n.

Once done we complete the cycle by traversing the edge n->1.

Now choose in which brace from 1 to N-1 your L falls and generate that brace content to print. Ofcourse L to R may span over more than one braces or no braces at all(last two or L falling right at the end of some brace).

Hope this helps :)

I didn't understand what was your idea, but I think you should have a look at my code. Idea: lets sort our array, if at some position i we have that a[i] + a[i + 1] + ... + a[n — 2] + a[n — 1] >= x * (n — i) then (a[i] + a[i + 1] + ... + a[n — 2] + a[n — 1]) / (n — i) >= x. Thats why all this people are reach. Thats why we want to maximize n — i (minimize i) and loop goes while all people at suffix are reach.

New to EduForces ?

EduForces is one of the following By Defination
-present an easy problem in most complicated possible -reshuffle all opeartions -Arabic forces

They mostly focus on -creating a broken problem from an already existing algoritms -common mistakes commited by people

Do you mean you can write an $$$O(n)$$$ solution or only a part of it?

Cool explanation. Can you take a look at my code.I used dp[i][j] as minimum number of coins required to generate first j elements of array B using only the first i elements of A. Transitions are quiet straight forward. If next element of A is the next required element of B and I am considering that element dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]). If I dont consider the next element ie I want to delete it,dp[i][j+1]=min(dp[i][j+1],dp[i][j]+a[j]) My answer would be dp[m][n]. I dont understand where I am going wrong. https://mirror.codeforces.com/contest/1334/submission/76300349 Thanks in advance:)

Why to use missile when job can be done with knife?

If we remove the monster at a position i before removing the monster at position i-1 then we won't be able to utilize the explosion of the monster at position i-1. And since, we want to maximize the utilisation of explosions so as to reduce the number of bullets used, we remove the monsters in the order they are standing. In this way, only the explosion of the monster removed last will be wasted.

Every vertex of the graph stands for a list of primefactors. Each edge removes or adds one such primefactor depending on direction of traversal.

So, to find the path from one list of primefactor to another one, we need to remove all primefactors which are in the first list but not in the second, and add all primefactors wich are in the second list but not in the first one.

The order of removals and addings simply does not matter.

Resubmit of your code: https://mirror.codeforces.com/contest/1334/submission/76297548

I had the same problem with my solution. I changed all cin to scanf, cout to print. It helped to improve execution time from TLE to 280ms. oh, "ios_base::sync_with_stdio(0);" at the start of main also helped

There is one monster you need to shoot first. This monster will not be affected by the explosion of the previous monster, all other monsters will be affected by the explosion of the previous ones. So you just calculate the monster, for which the explosion will save you the least amount of shots and then simulate the shooting starting from this monster.

Good explanation brother. You deserve more upvotes.

Line 24

i = n-(k+in);

must be i = k+in-n;

even then your solution will exceed time limit

It is possible to solve it using just Segment trees since b1...bn is in increasing order.

Because 'long int' is same as 'int' in 32-bit compilers and CF has a 32-bit compiler. Check this out. You can use 'long long int' for 64-bit integers.

change endl to \n and add fast i/o

check this out https://mirror.codeforces.com/contest/1334/submission/89154507