nice

there should be a separate comments section where all of you orz fanatics can peacefully spam

i am the orz.hahahhaa

Me too

omg TheScrasse round!

I'm excited to finally reach cm after this contest :D

too hot to handle for a newbie:(

I have an opinion about the difficulty of these problems, but some other authors and testers have very different opinions. Overall, let's say we are agnostic.

It's 2 hours and 30 minutes long. The contests page will be updated.

Hopefully tomorrow

yes you will, gl!

Well it means that the problem will have two version: The easy version, which is C1, and the hard version, which is C2(or, in case of Div 1, A1 and A2)

Me too (my another account). Good luck to you~

Wish you the best of luck on your journey, I advise you to see "Arabic competitive programming" channel on YouTube. Mr.Mostafa Saad had published a sheet contains problems classifications and topics. Although the content in Arabic but the sheet has English comment and content. I think you can use any AI tool to translate the videos to get the most of it. Happy codding

Don't worry too much bro. The first three problems are generally implementation or constructive problems. You will hardly find any algorithm specific problem initially. Even very basic algorithm specific problems on, say binary search, appear in ladder D or beyond. I would suggest you to just brush up you C++ STL. Apart from that you can give some div 2 virtual contests to get a better understanding of the problems.

There will be two versions of Div. 2 C / Div. 1. A, each worth 1250/750 points (so if you solve both versions of Div. 2 C, you get up to 2500 points total). The second version is generally harder than the first; usually the two problems are the same but the hard version allows for larger input sizes.

Ufff! I was close..... maybe next time :')

Congrats! :)

Yes! (as far as I know, all codeforces contests are translated in Russian)

You can greedily set the start of the interval to be $$$1$$$. Then just try to extend your interval until you can't anymore.

my solution (still pending test so take a grain of salt)

In a nutshell if we can make the array all positive, then it's easy because you can do something like

for i in range(1, N):
  if arr[i-1] > arr[i]:
    add i-1 to i

The same thing can be said for all negative numbers. You just do it from the end of the array. The operation takes at most N times which is 20.

Now the difficulties come because array can have positive & negative numbers.

Imagine if the array has at least 1 positive number. Then we can double that number quickly by adding it to itself. The worst case is for positive number 1, and double it 5 times so it definitely exceeds 20. The operation here is another N which is 20.

Then we add this number to each number in the array, and we can be sure to have an array of ALL POSITIVE numbers. And you can apply the logic above.

So in general:

if not_has_pos:
  do the negative stack from end of the array (20 operations)
else:
  quickly double the largest positive number until it's > 20 (at most 5 ops)
  use that largest number to add to each of the array number (at most 20 ops)
  do the all positive stack from the beginning of the array (at most 20 ops)

If all numbers are negative, then just take suffix sum.
Else take any positive number and keep adding itself to it till it is less than 20.
Then add that number to all the negative numbers. Now all are non-negative numbers.
Take prefix sum.

Roughly speaking, make all elements either positive or negative (optimize this a bit), and then it's just prefix/suffix sum

if you have all element as postive then just start appling operations from beginning to a[i],a[i-1].similary for all negeative elements apply operations from last. if array contain both positive and negative you can make any positive element > 60 in atmost 6 moves by appling operation to itself then apply operation on each negative element with this element(>60) and then just solve it for all positive case. maximum moves=6+19+19=44

The main strategy is that if all numbers are not negative you can do:

2 1

3 2

4 3

5 4 ...

so in each step every number becomes at least as big as the previous

if all the numbers are not positive its the otherway around:

19 20

18 19

17 18...

You take 19 steps to do that. Now the question is: how to make all the numbers non-negative or non-positive?

If there are >= 13 positive numbers, you can just pick any of them, sum it with itself 5 times (so if the number is 1 it becomes 2, 4, 8, 16 and finally 32) and then sum with all the other negatives, which are at most 7. So you have 5 + 7 + 19 steps <= 31;

If there are >= 13 negative numbers it is similar as above.

If there are less than 13 negative and less than 13 positive numbers, just take the one with larger modulu, sum it with all the at most 12 numbers of the opposite signal and do the first process. You have 12 + 19 steps <= 31

If all element is positive, we take its prefix sum, else if all element is negative, we take suffix sum

Example: 1 4 7 2 8 -> 1 5 12 14 22;

-1 -2 -1 -> -4 -3 -1

Let numNeg is number negative element and numPos is number of positive element. We will convert all positive to negative or convert negative to positive.

I will discuss about first case, the second same.

• First, double biggest positive number until its abs larger than smallest element' abs. Let number operation need for this process is Kpos.
• Second, add this number to all negative number (after that we have a positive array)
• Third, take prefixsum
• Total cost is: numNeg + Kpos + n — 1
• Total cost for other case is: numPos + Kneg + n — 1
• We can proof that either numNeg + Kpos or numPos + Kneg (or both) not larger than 12

for Div 2 C1 you can easily solve it by a greedy approach you are fine with the operations if all numbers are negative, positive or all numbers are 0 then you can easily do it otherwise for 50 operations just spend 5 operations to make any non zero number >abs(20) then add this number to all the numbers to make same parity as it has then simply do like all negative and all positive

but for Div2 C2 the catch was you have to know how many numbers are positive and negative suppose if you have any of these given count of numbers >=13 then the other numbers count will be at max 7 then in this case you just need to again spend 5 moves for any non zero nubmer from the 13 numbers and spend at max 7 more the make the parity same the number of operations inclusive will be 5+7 =12 and rest you can do 19 operations to make it non decreasing otherwise if maximum count of nagatives and positives <13 then just select a largest non negative element from the array and make all the oppositve parities numbers (which can be maximum 12) to same parity it has then do rest 19 operations on making the array non decreasing

you escape specialist, congrats!

continuous subarray from 1 that is factor of n

You need to use the fact that product $$$n$$$ consecutive numbers is divisible by $$$n$$$. So this kinda works

rep(i,2,1e18) {
    if (n%i != 0) {cout << i - 1 << "\n"; return;}
}

I don't know if this is the intended solution. I had just not enough time to code it up, but I think it should work.

Case1) All are zero. Then we're good

Case2) All are non-negative. Then we're good, just submit {2,1} -> {3,2} etc and you get a increasing array in <= 19 operations.

Case3) all are non-positive. Then we're also good, just submit {n-1,n} -> {n-2, n-1} and you get an non-decreasing array.

Case4) There is roughly same number of positive and negative entries (maximum 4 difference in number of negative and positive entries). Then take the element with biggest absolute value and use it to make all entries positive/negative. This takes maximum 12 operations. Afterwards you can do the same as in case2/3. This costs you maximum 19 operations. Together it costs exactly 31 operations maximum.

Case5) A there is much more positives than negatives or vice versa. Then take one element from the group there is most of, and add it to itself until it becomes 32 or larger in absolute value (this takes maximum 5 operations). Then it is bigger than all other entries, and you can use it to make all the other entires negative/positive. But, there is maximum 7 other elements of opposite sign (else we'd be in case 4). This takes maximum 5 + 7 = 12 operations. But, after this we're back in the situation of case 2/3, which we know takes 19 operations to sort. And again 5 + 7 + 19 = 31, so we can exactly do it even in case 5

Yes, it's a shame, they wouldn't hurt me either.

Can't agree more. Internet also gave up on me seeing my iq. Literally fucked up this one

I assume you found the largest $$$r$$$ such that the segment $$$[1, r]$$$ works, right?

There is an easy proof that this works. Consider any range $$$[l, r]$$$. Let $$$m = r - l + 1$$$, the number of integers in this range.

We can notice that within these consecutive $$$m$$$ integers $$$l, l + 1, l + 2, \dots, l + m - 1$$$, exactly one integer is a multiple of $$$m$$$. Within the first consecutive $$$m - 1$$$ integers $$$l, l + 1, l + 2, \dots, l + m - 2$$$, exactly one is a multiple of $$$m - 1$$$ and so on, until the first consecutive $$$1$$$ integers $$$l$$$ (trivially) has exactly one being a multiple of $$$1$$$.

This means that within the original range $$$[l, r]$$$, there is a multiple of each of $$$1, 2, \dots, m$$$ (where $$$m = r - l + 1$$$) and thus, we get that $$$n$$$ is also a multiple of each of $$$1, 2, \dots, m$$$. This way we get a new range $$$[1, m]$$$ which is as long as the original one, but starts at $$$1$$$.

Suppose the answer to the problem (for specific $$$n$$$) is $$$x$$$; this means that there exists some good range $$$[l, l + x - 1]$$$. But as we showed above, the range $$$[1, x]$$$ must then also be good. This proves that we always can find an optimal range by setting $$$l = 1$$$.

oh my god it got skipped im never making this mistake again

https://codeforces.com/contest/1855/submission/216293541 this might help

Hey like to add each other friend on cf? since we r newbie it will be a friendly competition?

i didn't get just one bro ;-;

Wow Hey just saw ur profile ur graph went up so fast. I know u must have prior knowledge in giving contest. sometimes I cant solve even Div 2 A not even approach and solve it quite late. Can u guide me a bit? With a question ladder or what approach should i take? I can solve on leetcode ez and medium but it hard for me in Codeforces

And I liked in div2C division of the task into subtasks

The way i solve it was to check for while(n % i++), when it becomes false, ou can break and print i

It is somewhat easy to assume that the maximum interval is when l = 1. From there, we can simply throw in a while loop to find the first number that doesn't divide n. Then, the answer is that number minus one.

The longest interval is always 1, 2, 3, ...

You can get it just by writing it down. Let's say the longest interval is actually some other, let's say it has 13. Well, the starting interval always has 1. If you add 14 to your interval, you also add 2 to the starting interval. If 12, you also add 3 and 4. So if you increase your chosen interval, the starting one also increases in size (by that number or more). So you only have to check when 1, 2, 3, 4, 5.. fails.

Assuming that the maximum value is greater than the opposite of the minimum value, and when the number of numbers less than 0 is less than or equal to 12, we can add the maximum value to all numbers less than 0, and then make a prefix sum (12+19). Otherwise, we can multiply any number less than 0 by 5 times and add it to all numbers greater than or equal to 0, and then make a suffix sum (5+7+19)

Because there is no clear strategy for an adaptive grader. So, it may punish some specific solutions, but let other solutions ask less queries.

I did it by trying 1s and 2s then doing the same thing. Let's see if it FSTs. In my opinion this problem should have hacks disallowed because even the intended solution doesn't seem to have any proveable expected runtime bounds.

You can see that if you know the range of card unlocked, you can calculate the profit (sum element subtract number element). We will handle case the last unlock operation over n by append $$$n$$$ number $$$0$$$ to array.

We will take a subset for first operation and take all other $$$v$$$ in the range we unlocked. But not all subset valid. Same as knapsack problem, let $$$dp[i][j]$$$ true if there is a valid subset of first $$$i$$$ element and sum is $$$j$$$. First, $$$dp[0][1] = true$$$

$$$dp[i][j] = dp[i-1][j] | dp[i-1][j - a[i]]$$$

But after that we cannot use subset with sum $$$i$$$ to update $$$dp[i+1]$$$ because the condition for us to use $$$a{i+1}$$$ is that previous subset must have sum greater equal to $$$i +1$$$. Just make set $$$dp[i][i] = 0$$$ before go to step $$$i+1$$$

Use bitset to speedup

Same here !!

You can think of another way. What if you already have the maximum absolute number? Then you don't need to do doubling. If all is positive/negative, you only need 19 operations, so you can use your biggest to fix at most 12 elements before doing that. (so you can have 12 positive/negative where the biggest is not at) Suppose then, there is 7 and 13. Then you use your approach of doubling (which is 5 operations) then 5 + 7 + 19 = 31

Actually I think you have to come up with a different C1 Solution to solve C2. (Well, it's only my personal opinion.)

If $$$a \geq 8$$$, then $$$2n - a - 1 \leq 31$$$ is small enough. Then, in case of $$$a \leq 7$$$, we consider getting a negative number with a maximum absolute value. It takes at most $$$5$$$ operations because $$$-1 \times 2^5 = -32 \lt -\lvert 20\rvert$$$ is small enough.

Then Let's add the $$$a$$$ non-negative numbers by the newly generated negative number. Then, respectively, do a suffix sum.

It takes at most $$$(n - 1) + 5 + a = 31$$$ operations too.