Yeah

As a not tester, I gave you contribution

Negative contribution given boy....

Good luck!

try flareon color

Best of Luck!

Delta will +500.

all the best!!!

OMG Blue Round

Hope not by negative delta.

Ку плэчере <3

I relate!

Div 3 is the best opportunity to reach expert

Sure you will be expert.

gay

really be an expert.thank you all.

True. They always have interesting problems.

Go to the contest section Codeforces page. Find round 834 and register before the contest

nice performance

Congratulations!

I used a greedy idea:

However, I haven't proved this idea in the contest, so I'm not sure about the systests. If someone else who have proved it can mention it here, then it would be helpful.

I used a Maximum Segment Tree.

• Initialize int[] answer of length n which will store our final permutation. On every odd position(0 based indexing) fill the elements of int[] b. Because we want minimum number to be in front position, so it makes sense to keep the maximum element on the second position.
• Now we have filled half of answer array. Now we iterate integers from n to 1 and check if its not present in answer, find the right_most element in answers array which is less than this current number. So we can safely place this number on left hand side of the found number. Now delete this number. This type of operations can be done by segment trees.

My solution is not clean as wrote in hurry in contest and its a newbie's code. My AC 181520850

If you are a braindead grey (like me) and never thought to solve the problem backward, you can also binary search on a lazy add/min segtree.

https://codeforces.me/contest/1759/submission/181510473

Solution for G:

From $$$i=n/2 \space to \space1$$$,for each $$$b[i]$$$,find $$$max(x)(x<b[i],x≠b[j])$$$ .

Proof:

Note $$$X=max(x)(x<b[i],x≠b[j])$$$.

Consider $$$"... Y\space b[j] ... X\space b[i] ..."$$$ and $$$"... X \space b[j] ... Y\space b[i] ..."$$$.Because $$$X$$$ is the largest number less than $$$b[i]$$$,we get $$$X>Y$$$,the former has a smaller lexicographical order.

You can consider cases like: a == b then answer is 0 distance between a and b is >= x then answer is 1 distance between a and l or a and r is more then x and then distance from that end is more then x ( to the b ) then the answer is 2 and the last case is to make the deistance to one of the endpoints equal to at least x, and this just adds 1 to the previous case, so the answer is 3 in the last case, if you can't do that than the answer is -1

Check if ans==0

If possible use 1 step, else

if possible go to left or right end, then to b, else

if possible go to left end then right end, or to right end then left end, then to b.

else not possible.

Me the same. I wasted too much time in D and then found out E was much easier to figure out. But it was too late... :(

I am not sure what is your code doing. But i found a test case:

1
513943340 921893439

Brute Force Output: 
256971670000000000

Obtained Output: 
462549006000000000

My estimation would be $$$1300$$$.

My solution for D:

k zeros at the end of a number means that this number can be represented as 10^k*a, where a is some number. 10 = 2 * 5, therefore, in the answer we need to maximize the number of pairs {2, 5}

1) Decompose n into prime factors and count the number of 2 (let it be q2) and 5 (let it be q5). If q5 > q2, then we need to add q5 - q2 twos in the price increase coefficient. If q2 > q5, then q2 — q5 fives. If q2 == q5, it means that we cannot "collect" tens from two numbers and add a zero to the end of the answer.

2) After that, I started picking up a number from [1; m]. We need as many 10 as possible in the answer multipliers, so I multiply the number (2 or 5) that I lacked to create pairs with multipliers of the number n, abs(q5 - q2) times by itself. tmp = (q5 > q2 ? 2 : 5)^abs(q5 - q2)

3) Then, I need to maximize the quantity of 10 at answer and, if there is solutions with the same number of zeros, need to get maximum. So we can increase tmp variable. To increase the number of tens, you need a number that can be represented as 10^k * a. This is easy to do if you take a digit of the highest digit and add to it (the length of the number - 1) zeros. For example, when m = 21345, you need to take 20000. So we have to do something like this:

r = m // tmp
t = int(str(r)[0] + (len(str(r)) - 1) * '0')
tmp *= t

4) When working with the tmp variable, it is necessary not to forget that it cannot be more than m, so it is necessary to set conditions that tmp <= m everywhere you are increasing tmp.

The answer is n * tmp or n * m if there isn't solutions with zeros at the end.

When you are multiplying it's crossing the limit for integers. Try with long integers

What you are facing is integer overflow, try using 64-bit integers.

That is something you will often have to care about.

Observation 1. The maximum answer is $$$p-1$$$, One case where this happens is where the number is a single digit.

Observation 2. A full carry across one or several digits happens only once at most.

Now think of it like this. How many steps do we need when our number is 0? That's $$$p-1$$$. Now, how many steps do we need when we have a few more digits existing in the number, smaller than the last digit? Might be smaller than that, but we may still have to run a full cycle. For this reason, we manage two variables, $$$\mathbf{pp}$$$ and $$$\mathbf{pk}$$$. $$$\mathbf{pp}$$$ is the smallest number connected as a continuous group with $$$p$$$, $$$\mathbf{pk}$$$ is the same but it is for the last digit. These two variables serve as boundaries. To be precise, $$$\mathbf{pp}$$$ serves as the boundary before the carry, $$$\mathbf{pk}$$$ serves as a boundary after the carry. So, you should be very well able to case-work with $$$\mathbf{pk}$$$ on whether we need a carry or not. Now the rest is just implementing the carry, and fiddling with these two variables (and the last digit).

Solution for F:

Note $$$k=a[n]$$$,consider $$$k->k+1->...$$$

Case1:

$$$k->k+1->...->p-t$$$

In this case, there is no carry bit.$$$0,1,..,k-1$$$ must appear in $$$a[]$$$.

$$$p-t$$$ is the largest number that does not appear in $$$a[]$$$.

Case2:

$$$k->k+1->...->p-1->0->...->k-t$$$

In this case, you should recalculate $$$a[]$$$(consider carry bit),note it as $$$b[]$$$.

$$$k-t$$$ is the largest number that does not appear in $$$a[]$$$ and $$$b[]$$$.

coooooool!

jiangly's algorithm: the greatest element of an array is always the last element.

Just find out how many 2 and 5 you get from m and (1<=x<=n) if(x==1) answer will be m*n; otherwise m*x;

As the humanoid can gain more health as it consumes an astronaut, you should iterate until you cannot consume an astronaut anymore instead of binary search the position at the beginning. After that you will drink a potion then try again that strategy. There are 3 ways to drink potion (2,2,3), (3,2,2) and (2,3,2) so just try all of them.

I figured it out, I thought the original permutation's size can't be over 50, but the problem statement never actually said that, only the found elements can't be more than 50

Agree 100%, nitin sir orz

Use blue first.

Sir, what about Sneh_Patel_0701 he has cheated in previous rounds too. But didn't get caught. Now he is going to become expert. Is there any punishment for them?

you missed else after your last elif

can u explain little more how exactly u getting logic to finding k?

Hi, @djay24 What's your intuition behind (m / k) .?? like, you used k = (11/5)*k, why are you doing so, can you explain.?

Thanks in advance.

What is your state? I had an iterative dp where $$$dp[i][j][k]$$$ denoted the max cost achievable till index $$$i$$$ if you take $$$j$$$ green potions and $$$k$$$ blue potions in total. While transitioning, I tried to take $$$l$$$ green potions and $$$m$$$ green potions in the $$$ith$$$ step. If the cost achievable without taking these $$$l$$$ potions and $$$m$$$ blue potions was greater than $$$a[i]$$$ then I greedily add $$$a[i]/2$$$ to my answer and then multiply by 2 and 3 on the basis of how many $$$l$$$ potions and how many $$$m$$$ potions I took.

Submission

hello！can i get some help please

Arrays.sort uses a dual-pivot quicksort algorithm. Unfortunately, its worst case time complexity is $$$O(n^2)$$$.

Dont worry,Mike will ban them

you only have the following options:

1. if a is already at b -> answer is 0
2. if difference between a and b is >= x -> answer is 1
3. from a go to l (if possible), then to b (if possible) -> answer is 2
4. from a go to r (if possible), then to b (if possible) -> answer is 2
5. from a go to l (if possible), then go to r (if possible), then to b (if possible) -> answer is 3
6. from a go to r (if possible), then go to l (if possible), then to b (if possible) -> answer is 3
7. if none of the above is possible, then answer is -1, otherwise it is the minimum of all the cases

for steps 3-6, we chose either l or r and not any other temperature because its always efficient to use an operation go to the farthest possible index.

i wasn't able to solve F without implicit segment tree with lazy propagation and binary search on it(got MLE 2 times xd)

The contest doesn't even show in my contest tab. What is the reason for that? Can someone please clear up the confusion?

< 1600

Oh, it's already updated but I didn't noticed it because it shows "unrated". Why?