Ciao, Codeforces! We're glad to invite you to take part in Codeforces Round 889 (Div. 1) and Codeforces Round 889 (Div. 2), which will start on Jul/29/2023 17:35 (Moscow time). You will be given 6 problems and 2 hours and 30 minutes to solve them in both divisions.
- One of the problems will be divided into two subtasks.
- One of the problems will be interactive, so please read the guide for interactive problems if you are not familiar with it.
The problems were authored and prepared by akifpatel, dario2994, Kaey and me.
We would like to thank
- dario2994 for his energetic coordination;
- Alexdat2000 for Russian translation;
- Vladithur, errorgorn for VIP testing;
- ALeonidou, antontrygubO_o, buffering, cry, emorgan, jamesbamber, MatteoArcari, MrBrionix, MyK_00L, pwned, zamong_juice for testing;
- MikeMirzayanov for creating Codeforces and Polygon.
Score distribution:
- Div. 1: $$$(750 + 750) - 1500 - 1500 - 2000 - 2750 - 3250$$$
- Div. 2: $$$500 - 1000 - (1250 + 1250) - 2500 - 2500 - 3000$$$
We hope you'll like the problemset!
Update 1: the editorial is out.
Update 2: congratulations to the winners!
Winners and first solves
nice
nice
ok
Feels inferior to Genshin Impact :(
Please don't metion Genshin Impact, or I think u r op too.
orz
there should be a separate comments section where all of you orz fanatics can peacefully spam
WeaponizedAutist What does "orz" mean?
detailed explanation
So this is like the other way to say "Thank you"?
More like it's the other way to show your respect.
Seems like a really tough div1 from B's points
omg TheScrasse round!
omg TheScrasse round!
omg TheScrasse round!
can i join spam chain
As a tester, I had a lot of fun testing this round and I hope you enjoy the problems as much as I did. Good luck and have fun!
Finally a Div 1 :D. I can learn how to unmaster now.
I'm excited to finally reach cm after this contest :D
lol
as a tester i can confirm not even the fire emoji can express how hot the problems are
Offering equal scores for three problems is a bit unusual--are those problems ordered by the authors' impression of their difficulty, or are the authors completely agnostic regarding the relative difficulty of D1 ABC?
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.
first time to see div1 abc have the same score. really cool
How long is the round actually? It says 2h30 in the announcement but 2h in the contests page.
It's 2 hours and 30 minutes long. The contests page will be updated.
When can I get positive delta in a div.1 round?????
Hopefully tomorrow
Deleted. Good luck to all participants!
Hello, I'm a newbie and I'm a little confused. Will I gain any ratings on profile from this round or not?
yes you will, gl!
orz
I hope it will be contest with interesting problems.
Break through oneself
Please be a good round
Why score distribution is 1250+1250 does that ques will have two part
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)
Total 2500 points for Div2. C? Sounds like it will be very tough for it’s place.
hopefully to be expert after this contest
Me too (my another account). Good luck to you~
thanks, good luck to you too
Thanks for this round and good luck for everyone :) !
I'm excited for this. :pray:
what does (1250 + 1250) or (750 + 750) mean?
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.
oh okay I got it. thank you) and if I solve only one version, then I get 1250 pts, right?
Correct.
If you solve C2 the same code is usually correct for C1
This may or may not be true. That's why they specifically mention about it at the start of problem statement.
Can anyone tell me, what will be the topics for this contest?
One of the problems will be interactive. :)
Hoping to reach blue..
Let's see if I reach specialist after this round.
Ufff! I was close..... maybe next time :')
Hope to become CM :)
Congrats! :)
Thanks! :)
Ciao.
is round translated on russian?
Yes! (as far as I know, all codeforces contests are translated in Russian)
But not well translated.
Hope to increase rating
Maybe too hard?
2hr 30min felt kind of humiliating tbh
lol
What the heck was Div 2B ! lol
You can greedily set the start of the interval to be $$$1$$$. Then just try to extend your interval until you can't anymore.
Until you get
Time limit exceeded
*No, you won't because the loop will iterate at most 43 times since $$$\mathrm{lcm}(1, 2, \dotsc, 43) = 9\,419\,588\,158\,802\,421\,600$$$ which is more than $$$10^{18}$$$.
can anyone share the intution of C, i thought about adding twice of one element to other element in a certain way would make this pair sorted.. i add twice of element greater in absolute value to element smaller in absolute value like 6 -3 i add (6 * 2) to -3 to make it 9 but couldn't get ahead of this..
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
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:
how to solve D2C?
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.
This won't work for C2
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.
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
Those who can't solve C.Try to think of prefix sum.
how to solve Div2 . B?
continuous subarray from 1 that is factor of n
but is not it o(n)? could you show me your code?
It looks like it's $$$O(n)$$$ but it actually isn't because the smallest $$$x$$$ when $$$lcm(1, 2, 3, ..., x-1, x)$$$ $$$>$$$ $$$10^{18}$$$ is very small.
no number can have factors from 1 to n except 1 and 2. so the time complexity would be O(k) where factorial(l)<=n and k=max(l).
You need to use the fact that product $$$n$$$ consecutive numbers is divisible by $$$n$$$. So this kinda works
How to solve div 2C
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
https://mirror.codeforces.com/contest/1855/submission/216345178
I submitted it and it worked :/. I had it ready 30 seconds after competition was over. that sucks. but it at least shows the logic described above works.
Proof by AC is the best strategy for this contest
I just need 5 more operation on Div2 C2.
Yes, it's a shame, they wouldn't hurt me either.
trash round
Problem Div1A/Div2C is just telling me: you are a fool with low IQ.
Can't agree more. Internet also gave up on me seeing my iq. Literally fucked up this one
I have no idea why my Div2.B AC'ed, lmao
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$$$.
My solution is a lot dumber actually. I checked from 1 to some r, and I just took a rough estimation of max r possible for the time constraint, lol.
How do I learn to prove my solutions? I came up with the solution of taking the largest r such that the segment [1,r] works, purely through intuition, but failed to prove it mathematically.
can I check something because I has C1 pass pretests at 1.04 but C2 pass at 1.26 and I decided to submit the C2 solution in C1 and my C1 is now recorded as +2 and 1.26 instead of +1 and 1.04. Will this change back when system testing is done or did I make a mistake?
oh my god it got skipped im never making this mistake again
Really interesting problems,thank you!
problems are amazing thanku everyone , i dont know why i am getting wa2 on div2/c
For div1E I simply assumed that there's some answer that uses some number of 1, some number of 2 and numbers > 30. Did anyone actually prove their solution for this problem?
Suspicious submissions in C1 problem (Div.2), almost around 1500 solution in last 10 min. I mean some people could have solved the problem but 1500 is pretty odd and many of them havent even solved 2nd?
interesting 1a-hard but hardly implementation :(
u may know a word in Chinese, niu-bi, which means "wonderful", "strong". Now I think it's suitable to the problem A2 in div.1. So fantastic the Constructive Problem is.
Maybe it's atypical (for me) that C is divided into two subtasks, but all in all a good round. if I had more will to start working D...
And I liked in div2C division of the task into subtasks
can someone share how to solve div 2B .Please
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.
Too hard for me. Although I was lucky enough to solve 1A, there were too many penalties.
That 32 operations in Div2C2 :(
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)
rainboy didn't solve 2F, sad.
big difference between 31 and 50. Interesting problem
IF I FAIL SYSTESTS ON D
Why Div1D non adaptive?
Because there is no clear strategy for an adaptive grader. So, it may punish some specific solutions, but let other solutions ask less queries.
So no elegant randomized solution :(
The intended solution is not randomized. There are some randomized solutions that ask more queries than the intended solution (but still less than 2000), so we decided to let them pass.
How to do 1E? I tried putting some number of 1s, and then filling the rest with >30 by taking nCr greedily, (I try with all possible numbers of 1) but based on my runs, I can only do <70 for most at best.
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.
did you do the coinchange subproblem greedily? (i cant see of a fast way to do that part fast, so I just do greedy)
Yes, I ordered the ways of reaching values [0, 29] with the 1s and 2s then greedily used them.
How to solve D1B?
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
Thanks
My best approach for div2 C2 could do it in <= 35 steps, could not make it till <= 31 till the end :(. I will check number of positive and negative elements, and those who have majority, I will make all the elements with same parity of parity of majority element.
Let's say positive numbers > negative numbers. Then I will make maximum positive number > 20, this will take 5 operations. Now I will add this positive element to remaining at max 10 negative elements this will take 10 operations. Now I will take prefix sum so at max 20 operations. 5 + 10 + 20 == 35.
Same if negative numbers > postive numbers. Is this correct approach?
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.)
Try to find a position with the maximum absolute value among all numbers. Let's call it $$$x$$$.
Assume it's positive. If not, just simply reverse the whole array and turn all numbers into their opposite numbers.
Let's say we have $$$a$$$ non-negative numbers.
Then, add all the $$$n - a$$$ negative numbers by $$$x$$$. Finally do a prefix sum.
It takes $$$(n - 1) + (n - a) = 2n - a - 1$$$ operations.
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.
How to solve div2D?
Can you share your strategy and story under so unusual score distribution?
I guess A2 is too puzzle for me, so read B&C and move on to B and solve it.
After that, read D&E (and at this time I notice that I'm good at this kind of E), work C, and luckily I can solve it.
Now, it's time to weigh up A2(750) vs E(2750). I take a few minutes for A2 and can't solve it, so I decide to say goodbye to A2.
Then I tackled on E and at last, I won
PT passed ! (hope it won't FST)Yooooooooooo!!! It passed the systest!!!!!!Last minute I think A2 again, but I dropped it finally :(
That's all of my story. Skipping A2 is the most important decision for me during the contest.
Here is the story you asked:
Initially div2C was only one, with $$$36$$$ queries. Then, in this order, div2E and div2D.
Testers complained about the gap between div2B and div2E (which was in div2D position at that time).
Since coming up with new problems is hard, we decided to split div2C in two subtask: one clearly easier and one clearly harder.
Some more testers' feedback arrived and we decided to swap div2E and div2D.
Testers felt like solving div2C1+C2 was as has as the following problems.
Since different people had different opinions on the relative difficulty of the problems, we decided to go for the score distribution div2C=div2D=div2E.
Taking into account that before the round one has limited information, it seems to have been a reasonable call.
I would be really interested to see what the solve statistics would look like under a different ordering of the problems; I think that the difficulty ordering is highly subjective, and the order in the round may be the main reason that e.g. A2 has more solves than B. Too bad it isn't possible to give A, B, and C to each contestant in a random order...
(fwiw, my personal difficulty ordering is A1 < B <= C < A2, but I think I tend to perform best on tasks like C. I think C is probably harder than B if you're being objective, and likely harder than A2.)
Re: the original question, my strategy going in was to read A and immediately type A1 if it seemed free and either A2 seemed time-consuming or I was pretty sure the A2 solution would involve direct modification of the code for A1. I didn't want to spend time on A1 separately otherwise because the points I'd gain from solving A1 a few minutes faster would be outweighed by the points I'd lose from being a few minutes slower to the later tasks. After assessing and possibly solving part or all of A, I planned to read B and C, attempt one based on solve statistics, and go from there.
In-contest, I figured out A1 pretty much instantly and decided to think about A2 rather than typing A1. Luckily, I figured out the trick for A2 not too long afterwards for a quick AC. I attempted B before reading C because after I finished A2, I saw that B had several solves and C had none. After finishing up B and C fairly quickly, I moved on to D and E. At the time both problems were unsolved, and because E was worth far more points than D I assumed that D would be much easier. Thus, I solved D before reading E and finished E up afterwards. (In retrospect, it would have been a bit better to do E first, but ah well--not the end of the world.)
https://atcoder.jp/contests/abc081/tasks/arc086_b
I think Div. 2 C1 is equal to this problem I solved a few weeks ago, but I still got a lot of WA on pretest 2. Can anyone help me? The following two submissions are almost the same.
https://mirror.codeforces.com/contest/1855/submission/216291552
https://atcoder.jp/contests/abc081/submissions/42020794
Take a look at Ticket 17015 from CF Stress for a counter example.
Thanks. The conclusion is that Atcoder testcases at that time were too weak. So sad.
AC sol with assert: https://atcoder.jp/contests/abc081/submissions/44090544
why i found a same problem (div2 C and div1 A) in https://atcoder.jp/contests/arc086/tasks/arc086_b
-120 by CF Predictor
It's a coincidence, sorry. It also happened in the last educational round. In both cases, the statement was short and many people can come up with such statements independently.
Fun fact: I also solved that AtCoder problem more than 2 years ago, but completely forgot about it.
It is same as easier version but not harder so I think it is fine.
No matter how hard they are, I love short and precise statements like this round. Hopefully next rounds's will be short just like this.
Thank you for this round! I solved D1ABC and (if no FST) I should be getting back to GM, yay. And honestly, I loved all of the problems I solved.
I think A had a nice idea; first subtask is simple, but second one requires you to act differently in different cases, and the operations are just barely enough (at least in my solution).
When I looked at B, it was quite obivous (to me) that the answer was to use bitsets. The details weren't difficult but they also weren't trivial; it was fun thinking about the solution (even though I got 2 WA, sad).
Problem C was beautiful! I love probability questions, they usually require some nice observations (and math, which I also like). Btw, why were the constraints $$$m \le 500$$$? I think most people found the $$$O(m^2)$$$ answer explained in the editorial using linearity of expectation, was there some other solution you also wanted to pass (editorial doesn't mention anything)?
And also, I have to thank you for short and clear problem statements. You didn't include any unnescessary stories in the statements. And the stories you did include weren't annoying, but they made sense in the setting of the problems. I think they were good.
Overall, I think this was an amazing round, at least on the Div.1 side of things. It seems like the problems might've been a little difficult, especially for Div.2, but I can't say anything about Div.2. I definitely enjoyed participating, and I would love to see more rounds from you guys!
Thanks! :)
The intended solution in problem C is quadratic, but some contestants wrote a cubic solution, and we didn't want to cut it off.
fstforces xd
week pretest
how to solve C2 in Div2?
Getting Div2. C2 accepted is a proof in itself, you can't get that problem AC without a proof.
I mean how to solve it
Just think about making whole array either positive or negative in at most $$$12$$$ operations, rest $$$19$$$ operations can be used to make array non-decreasing.
Making array non-decreasing in $$$19$$$ operations is quite trivial if the array is either completely positive or negative. To make the array either positive or negative in at most $$$12$$$ operations, consider the absolute maximum from the array, if number of elements of opposite signs are $$$\leq$$$ $$$12$$$, you can use the absolute maximum element to change their signs in $$$\leq$$$ $$$12$$$ operations. Otherwise, if there are $$$\gt 12$$$ elements of the opposite signs which means there are $$$\leq 7$$$ elements of same sign. What you can do in that case is take any element of the opposite sign and perform the given operation on the same element at most $$$5$$$ times making it absolute maximum of the array, rest $$$7$$$ operations can be used to change the sign of left elements, since there are only at most $$$7$$$ elements of other sign.
+123 -111 +202 in last 3 contests. My ratings are on a roller coaster.
Great contest, I love it.
I enjoyed the contest.
1A2 tests are a little weak, I just hacked my own solution.
Sorry but I don't like E because my solution (no-proof-at-all heuristic) passed...
Suffering with success
same
HELP — Why does 216311224 gives wrong answer for Div2C/Div1A.
Tests in D are poor. My (and if I'm not mistaken for example tourist's) submissions are incorrect. I find a segment of length $$$k$$$ on the cycle, and then I do rounds with parameters like $$$k$$$ and $$$2k$$$ and if $$$4k \geq n$$$ I hope that it's enough, but it isn't. If something is attached to the cycle at the beginning of the first segment, I won't find it.
Trying to hack these solutions I get unexpected verdict, but there's something worse. tourist's submission won't even work if there is a path of length 499 attached to the cycle made only of the first vertex (or I messed something up), but hacking says that the hack is incorrect. My solution solves it correctly, so I guess there is no such test, but I think that it means that the model solution might be wrong?
UPD: Nevermind here, it works on codeforces, but it somehow behaves this way on my machine, so most likely I've messed something up.
UPD2: Ok, I get it now, he's tricky, he's correct on this test :P
One of the testers' solution is wrong. The official solution works correctly on that test.
This round feels more like atcoder. Not my favorite style but problems were still interesting.
https://mirror.codeforces.com/contest/1855/submission/216345919
why am i getting memory limit exceeded?
I had the same problem. Try using long long.
no still getting mle
It seems as though you haven't considered the case in which all elements are not positive (<= 0). This means your loop that increases each element either keeps adding nothing or subtracting, and also adding that "operation" to a vector, so you get MLE before TLE.
Cheaters:
number 1
number 2
Got c*cked by edge case of all negatives during contest for C2 and thus couldn't solve it in time (would have been a real rating boost). I had 1h+ to implement... GG
Accepted solution: https://mirror.codeforces.com/contest/1855/submission/216347323
Cheaters part 2:
link 1
link 2
Div2 C2: who are getting WA on test 2 try this:
1 20 -1 20 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 20
I got WA cause i misplaced i with j in 1 place
Video Editorial for problem A,B,C1 and C2;
https://youtu.be/_BIHuCbGRlQ
The ratings in Div1 are updated, but not in Div2? Is it because of more participants in Div2?
can someone please explain div2B solution interval [l,r] contains at least one multiple of x for each 1≤x≤r−l+1
Consider some value of $$$x$$$, say $$$x = 5$$$. Let's look at the multiples of $$$5$$$:
$$$1, 2, 3, 4, \underline{5}, 6, 7, 8, 9, \underline{10}, 11, 12, 13, 14, \underline{15}, \dots$$$
Notice that if we take any $$$5$$$ consecutive integers, exactly one of them will be a multiple of $$$5$$$:
$$$[1, 2, 3, 4, \underline{5}]$$$
$$$[2, 3, 4, \underline{5}, 6]$$$
$$$[3, 4, \underline{5}, 6, 7]$$$
$$$[4, \underline{5}, 6, 7, 8]$$$
$$$[\underline{5}, 6, 7, 8, 9]$$$
$$$[6, 7, 8, 9, \underline{10}]$$$
and so on.
This is true in general: if we take $$$x$$$ consecutive integers, exactly one of them will be a multiple of $$$x$$$.
Notice that a range $$$[l, r]$$$ contains $$$r - l + 1$$$ consecutive integers. This means that the range $$$[l, r]$$$ contains a multiple of $$$r - l + 1$$$. But the range also contains a smaller subrange $$$[l, r - 1]$$$ with length $$$r - l$$$; this range must contain a multiple of $$$r - l$$$, and so on. Since the range $$$[l, r]$$$ contains smaller subranges for all lengths between $$$1$$$ and $$$r - l + 1$$$, it must contain a multiple of every integer $$$1, 2, 3, \dots, r - l + 1$$$.
Turned cyan today.:)
Hello!
I participated in this contest after registering when the contest started, and I started maybe around 30-40 minutes late. I solved two problems. But I don't see any rating change. It says the contest was unrated.
Please help me understand the situation.
It will take a while for the system to update rating. P/s : at the time I commented, both div1 and div2 got updated
I like E very much! I think that such problems check creativity, but what's important, it's elegant. I'd probably set lower limit on m, so it'd be easier to prove that the solution is correct on all the cases (with a code of course, not on paper).
I hate E very much! The intended solution doesn't have any proved (expected time) bound for the given constraints, so we can't be sure that it actually solves all possible inputs that are within the constraints or not. Even if you prove that it solves them by running it over all possible inputs, that's ugly af and the process of "solving" it is more like solving the cases that were set and hoping that the case that's bad for your solution isn't in the systest instead of solving the problem by itself (since during the contest it's not efficient to spend minutes to hours verifying that your construction works for all cases). In that type of problem, you should at least disallow hacks and make pretests the same as the systest (which seems to be the case here) since it's not inconceavable that the expected solution gets hacked.
I think that both your feedback and Radewoosh's one are valuable (and also hos.lyric, I read it only now). Thank you! This kind of discussions need to happen in the community. If anyone else has an opinion, please share it, it can have an effect on future problem sets!
I will make some comments partially related to tfg's comment.
There is a strong (enough for me) intuition which suggests why the official solution shall be fast enough on all inputs. This is not a proof, but is better than nothing. In particular I would not bet my hand that the official solution works on all $$$m\le 10^{10}$$$ but I am absolutely certain that some simple variation of it (like just changing the seed or changing a $$$5$$$ with a $$$6$$$) does.
It is possible to check the correctness over all inputs in a reasonable amount of time (but this was not done).
The main reason why I lowered the constraint from $$$m\le 10^{10}$$$ to $$$m\le 10^{11}$$$ is that I was scared. Is this a good thing to do in general? No. Am I regretting it? No.
Pretests = Tests in E. Exactly for the reasons you mention. Not allowing hacks seems a good idea for the next time. (it would not have changed anything this time)
I am very sad to see "We don't know any provably correct solution" in the editorial. Now the problem is not only of my taste but also incomplete.
Where to pose these kind of problems? Some suggestions.
Well, it wouldn't be a surprise for you that I hate this problem (and maybe every problem Petr feels like he could have come up with ).
Actually, I hate it maybe even more than the usual problems of this type. I knew (or rather expected) that I can't prove anything on paper, and I have to try some things and see if they work. Literally the first thing I implement is the
eval
function. Then I play with some parameters, look at the outputs and... it doesn't look like it's working! Not for me. There are big gaps between the values I get asdp[60]
, by an order of magnitude bigger thandp[29]
which I would have to use to fill the gap. So I abandon the problem thinking "maybe I tried the wrong thing" (which happened to me several times while solving problems actually set by Petr, so I'm kinda used to not seeing what is strongly suggested by intuition to everybody else). I go and solve D, and only have 15 minutes left. With nothing better to do and nothing to lose I implement restoring the answer in my abandoned code for E and submit. My reaction. I genuinely hoped that it would fail systests because otherwise I don't get why this problem exists. The limitations are big enough so you can't run the solution on all tests (even though I guess my solution is better suited for that than the model one, since I do the precalculation once and then solving for one $$$m$$$ is relatively fast, but it still would take hours to run on $$$10^{10}$$$ values of $$$m$$$). It doesn't even look like it's working (to me). I literally got accepted with the code that was written an hour before submit and abandoned because I didn't think it works.I don't know what to take from it. I understand that I'm on the extreme end of the "do I believe in miracles" spectrum. I can't say that it is a bad problem. I'm not a person for whom this problem is meant to be enjoyable.
I'm neutral towards E very much! I haven't read the problem.
Tell me how you figured out Div2B. 1. Find out the solution logically (roughly know the reasoning or proof) 2. Printing and observing and guessing
1
my perform was so bad for this contest, i got MLE like 6 time just because a silly mistakes. Very good problem btw :D
Didn't know that bitset can pass 1e5, while A2 getting fst... this feels so bad [:cry:]
Thank you for the round! I love each of Div.1 ABCD.
A1 is the same as ARC086B, but this is not an issue. (that's why I had first solve :D
I am not a fan of 1E: I think at least hacks should be disabled for this kind of unproved/unverified problem (and maybe specify that pretests = tests).
Great probset btw!!
O(n^2/w) for n=10^5,,, so it is an acceptable complexity...?
$$$w$$$ can be as large as $$$256$$$ on Codeforces.
wow, that surprises me. Now it is a reasonable solution for me, thx.
How 2E?
Why do I have lower initial score, higher rank, but obtain fewer score than others? hxsj: 1213 + 176 = 1389 rank:912 dxh074: 1291 + 182 = 1473 rank:916
here is the reason. https://mirror.codeforces.com/blog/entry/77890
ok,thanks.
Please debug my submission https://mirror.codeforces.com/contest/1855/submission/216449340 I am getting Memory limit exceeded on test 2 again & again...
Fixed Solution.. Made changes in "if and else if" conditions.. added >= and <= . Work out the test case I gave and you'll be able to figure it out.
MikeMirzayanov
I've received a message from system that
It seems like a coincidence, but both Imdie and me are completely innocent. We haven't cheated or violated any rule in the contest. We even didn't know each other then.
It's been about one year since my last OI contest where I got an NOI silver medal. I participated in the CF contest only for fun and had no motive to cheat. And it's also impossible for me to copy others' code during a contest.
Imdie and all my friends can verify what I said above. I hope the violation record can be revoked and I can get my rating added.
why my submission is TLE? https://mirror.codeforces.com/contest/1855/problem/B Problem B : My submission : 244680296