Hello Codeforcers!
I am pleased to invite y'all to participate in Codeforces Round 887 (Div. 1) and Codeforces Round 887 (Div. 2), which will start on Jul/23/2023 17:35 (Moscow time). In both divisions, you will be given $$$6$$$ problems and $$$2.5$$$ hours to solve them. The Div. $$$2 $$$ round will be rated for participants with rating below $$$1900$$$, while the Div. $$$1$$$ round will be rated for participants with ratings which are at least $$$1900$$$.
This round was authored and prepared by Benq, emorgan, omeganot, US3RN4M3, me (cry), Ina, nsqrtlog, buffering, ntarsis30, and ArielShehter.
We want to thank the following people for their contributions:
Our amazing coordinator, darkkcyan, for the outstanding coordination despite the 12 hour time zone difference.
The rest of our problemsetting team for being so eager to contribute their own problems and solutions, as well as testing the round: null_awe, oursaco, Apple_Method, wavelets, izhang, Whimpers, mirachael, Cereal2, asdf1234coding, and dutin.
- The rest of our testers for providing the feedback we needed to ensure our round was as enjoyable as possible: gamegame, rqi, penguinhacker, Umi, jonathanirvings, maxwellzen, GusterGoose27, NemanjaSo2005, willy108, EmeraldBlock, _Fake4Fun, eyangch, sum, amoeba3, Mike4235, awesomeguy856, thehunterjames, xiaossr, tgp07, QuangBuiCPP, Olympia, skye_, sayeem2004, ETL, Ask-2005, MorganWyoming, TonightV, jcai972, and ArcticCrusade.
- Alexdat2000 for translating the statements to Russian.
- MikeMirzayanov for the Codeforces and Polygon platforms.
- You for participating!
UPD 1: Score Distribution
Div. $$$2$$$: $$$500 - 1000 - 1500 - 2000 - 2500 - 3500$$$
Div. $$$1$$$: $$$500 - 750 - 1250 - 2000 - 2250 - 3000$$$
UPD 2: Editorial has been posted here
UPD 3: Congratulations to the winners!
Div.1
Div. 2
Good luck! Red panda wishes you all rating inflation!
Art credit to xiaossr
As a problemsetter, I can certify that I did not test in any shape or form
Hello, are you interested in my approach to question c in div2? I feel that the solution to this problem is not quite the same.https://codeforces.com/contest/1853/submission/215254923
would be funny if tourist regains no 1 in a Benq round
I believe that with Benq as the questioner, the "quality" of this contests will not be poor. :D
That's why this will be one of the most beautiful rounds ever
indeed it was beautiful ,as a result i just watched those questions for 2 hrs straight
As a tester, I can confirm that this is a great contest and has great problems, much like another amazing contest by the name of CerealCodes :D
As a tester, I can confirm that I will neither be able to teamsforces or codecode on this round.
As a tester, I can confirm that willy is a god at rinbot and therefore codeforces.
As a problemsetter, I hope you all enjoy the problems (especially mine).
it's a good problem to think about for 3 days after contest
As a tester, I have enjoyed the round and I hope you also enjoy it.
orz NemanjaSo2005
orz NemanjaSo2005
orz NemanjaSo2005
As a tester, I can confirm that this contest is truly one of the contests of all time
He speaks not the truth. He isn't a tester; he is actually a VIP tester.
As a VIP tester, I can confirm the validity of this statement
it has been scientifically proven that if you play genshin impact you will gain rating on this round!!!
Would only watching anime help?
Time to enjoy -167 delta in a div.1 round!
Nice reference :sad: XD
"The Div. 2 round will be rated for participants with rating below 1900 , while the Div. 1 round will be rated for participants with ratings which are at least 1900"
Does this mean that I, as a purple, am forced to participate in Div1 round?
i believe so
yes it's forced
Scared for my first div1 round. Hopefully I can actually solve 2 problems and avoid instant demotion to blue.
Same. Preparing to be in last top 10%-30% participants.
The same.
As a tester, I hope u enjoy the round as much as I did
I'm afraid to participate cz of your handle.
Hoping to become purple. ( Please make this my most memorable contest ever! )
Bless you!
These are our words.
Problems are high quality. Definitely try to participate!
Waiting for another enjoyable round. Best of luck to all contestants.
As a tester I can confirm that this round is just as good as Oshi no Ko chapter 123.
As usual i want to ask any suggested topics for this contest.
Its secret bro. Secrets are more fun <3
As a problemsetter, I can confirm at least one of the problems will feature Ninomae Ina'nis from hololive-EN Myth!
it's only one problem :cry:
wah
Wah!
こんぺこ、こんぺこ、こんぺこ！ホロライブ３期生の兎田ぺこらぺこ！どうも、どうも！
As a tester, I can confirm the problems will be problems.
i hope to be blue this time
Very rare to see this many colors in the author list
Waiting for this!
Hoping for a good div2 round.
as a problemsetter who didnt problemset, i can assure you that this will be a great contest :D
OMG!! Benq is the writer. Sounds Good!
OMG!! Muhammad_Aneeq (aka lota) has replied Sounds Good.
As the president of CerealCodes and a contest organizer, I can assure you that the problems are of high quality (just like CerealCodes problems).
I don’t know who this man is.
omg CerealCodes orz
As a participant i recommend you to participate.
Bad advice, I wish I didn't follow it
Why didn't PurpleCrayon test when Purple Cry is an author?
ofc we asked, but he wanted to participate officially instead.
PurpleCrayon will win IOI 2023!!!
As a tester, I can confirm that this round will not only give you lots of rating but ginormous muscles too :D
Is div.2 also 2.5 hours?
It'll be fixed so that both rounds last the same amount of time.
Am I the only one who noticed this announcement was made 7 weeks ago?
Hi everyone,
We would also like to mention this round was mostly made possible by problemsetters from the CerealCodes initiative!
CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest here.
We are holding our second contest on August 13-15th, with over $1k in prizes for pre-college students and some great raffles for everyone! We invite everyone to also participate in this contest! If you're interested, be sure to join our discord server and check out more info here.
I'm trying to register to CerealCodes but I can't find my country (Turkmenistan) in countries. :(
please solve this problem
Hi, the issue should be fixed :)
the cool thing is that you have sorted the list :)
i also couldn't find Uzbekistan
should we participate in teams or individually? can you provide more information
As a tester, I can confirm that problemsetting might have happened.
As a pupil,hope to become newbie.
So good luck to you!
Benq!This round would be very interesting
hope I can be a candidate master.
as a cyan participant, i hope to be blue after this contest
The round has been fun for me as a tester, and I hope it will be fun for you as well.
Excited to see tourist in round prepared by Benq
Best of luck everyone
I hope everyone can have a good participation experience
IT'S YOUR TIME TO SHINE MR.TOURIST
Do you mean that you will make us cry in this contest :(
will be fun to see if tourist takes back rank 1 in a Benq round
Looks like someone copy paste the same line (•‿•)
The panda looks like Firefox)
As a participant I hope I'll get over this damn pain this round T_T
Hope for color change!
Are you saying Div1 has easier problems?
Based on the score distribution? No, Div1A is the same problem as Div2C, Div1B is the same problem as Div2D etc., the problems are harder. These problems just give less score in Div.1 because the scoring is relative to other problems and usually scoring is started from $$$500$$$ points.
Hello Benq. This is a fellow United States of America Computing Olympaid competitor, and wishes for you to not write any problems in the USACO 2023 December Gold contest. If this is possible, I will certainly be elated. Please consider others emotions before problem setting for the USACO 2023 December Gold contest.
Skill issue
Shut yo skill issue ahh up you spedialist
Shut yo novice starter learner student trainee apprentice probationer recruit newcomer fledging anti-orz ahh up you unrated newbie in the insanely big world of cp.
Upvoted. Thank you, fellow specialist
orz, fellow specialist problem setter and future legendary grandmaster ntarsis30 :orz:
Humongous krill issue indeed, dumberest
Hoping to become a green , also good luck for everyone
I LOVE YOU CRY :) MY BEST FRIEND, THANK YOU FOR PREPARING A CONTEST <3, good luck to all!!!!.
is cry girl or boy?
she is a beautiful girl!
you fool me, i fool you！ Good luck
Red panda is so cute!
It's even a little insulting — authors have all possible colours except green...
Anyway, why there is such a variety — is it some university project or so on?
i hope to be blue this time
Feeling excited to give this contest.
can tourist be 1st?
good luck for all
thx
Wishing orz quietpan a speedy journey to purple!
I have a question, why the problems of Div.2 have higher score than the problems of Div.1?
QaQ
See this comment
Many colors in setter panel
Whoever came up with div2 problems B and C I hope that for the rest of their life they would only get pairs of integers as their birthday presents.
That joke was amazing. Div 2 B was did feel kind of out of place for a Div 2 B though. But the C was a really good problem for its position. But its a common and really frequently used fact that certain sequences grow really fast, at some point youll have to get used to it.
Imagine 1434ing us
the respective number of letters in "I lost the game"
to my cyan color, i will miss you
C>>>>>>>A,B
Disgusting problem b and c
Nightmarish for me..atleast
very strange and hardest contest I have never seen ever...
Don't know what this round's authors were thinking, but I feel like there is a huge gap between A and B. As a div 2 participant I feel like this round would have been a nice round if B would have been C and C would have been D.
ty guys for the another speedforces round
As a wise man once said, "go solve some problems and learn to use binary search'
div2 c>>b and b>>a. Doesn't feel like this is a well balanced contest :(
Both Div 2 B and C, you had to spot very commonly used ideas. It was your fault you dont have the experience. As a wise man once said, "go solve some problems and learn to use binary search'
does the problem ratings depend only on the ratings of the people who solved it or it also depend on the position of problem ??
like consider same problem in div2C and div4H, then comparitivley div2C will have higher solves than div4H
so, if only the ratings of the problem solvers is considered then div4H will have higher rating than div2C.
As a div1 contestant, i gave up A after reading it :(
Yes, We are cry ing :(
ig, there is huge difference between A and B :(
statements are clear thank you for that but problem C is too much hard , C should be D i think
thank you codeforces for realising me that cp is not for me
More then a half div1 contestants gave up after reading Div2C. Sounds like something that shouldn't happen... Hardest div2C... Spent an hour, but still have as few ideas as after i read it for the first time...
can you explain how you did div2 B please
I am author of B. Intended is to brute force over element before N and reconstruct the sequence from the back. Note that Fibonacci grows fast, so sequences must be short (max length is around log(N)).
What was that C, bro?
We actually considered making it C, but since the solution is just brute force, we decided against it.
Since $$$f(i) = f(i - 1) + f(i - 2)$$$ is increasing really fast. If $$$k > 40$$$ (or so) it will be impossible to construct such a sequence.
Otherwise we know, that $$$a_{k - 3} + a_{k - 2} = n$$$, so we can iterate over all possible values of $$$a_{k - 2}$$$ and $$$a_{k - 3}$$$ will be equal to $$$n - a_{k - 2}$$$, $$$a_{k - 4}$$$ will be equal to $$$a_{k - 2} - a_{k - 3}$$$ and so on. If this sequence is non-decreasing and $$$a_0 >= 0$$$ then we add $$$+1$$$ to our counter.
You can notice that $$$n=F_{k-1}*a+F_{k}*b$$$, with $$$F_k$$$ is the $$$k^{th}$$$ Fibonacii number, and $$$a,b$$$ is first two number of our sequence $$$(a <= b)$$$. Now we can easily count all $$$(a,b)$$$. Sorry for my bad English.
Yeah. This is exactly what i Did. One of the best math problem I had solved in a while. Also C is also very very genius problem. Those who are hating C are the ones low IQ people. Smart ones knows who good the problem is.
Just want a honest opinion , Really 7000 plus people were able to solve B , got me into thinking , for a hard time
Yes. It was very easy, If you would have solved around 40 1500 math rated problems. Because in these types of problems generally we fix something. For example --- To build the whole sequence we just need starting A and B right!!!.
So just bruteforce all the values of A and B.
There are bunch of problems in 1400-1500 rating.
The idea is very very well known.
Oh maybe, yeah I haven't done too much problem solving and the first approach I started was to use matrix exponentiation and then use binary search over 1 to n to find a and b possibilities, but were not able to implement properly, thought that O(nlognlogk) solution would be okay, but it was much simpler, tookna long time to realise the constraint of 30 and dp approach. Hope to do well in upcoming contests
Yes Sir.
My approach for getting strong idea for
C:If we have n = 2*1e5, a[i] = i, and k = 1e5, then the answer can be around 2*1e10 ("very big").
Also, we can see a monotonic property that for every number x <= answer, numbers deleted before it is x-1.
Both these facts point to a Binary Search on Answer strategy.
So could you tell your solution?)
I failed to impress Ntarsis moreover i failed to impress myself.
Don't worry, I'm still impressed.
Div1C
Hi, we were just made aware during the contest. Tbh, just unlucky, none of us were aware of the problem, including the 40 testers and coordinator
That's unfortunate, but thank you for doing your best anyway! These problems were really hard but very interesting.
Here as well, but with small k.
How to solve div1C?
Wow I like Constructive and MathForces so much!!!
IMHO Problem B to me was like you either know it or you don't. Like, I can't get a piece of paper and start working on it and finally get an answer, but 7000+ people solving it really got me questioning my existence.
Very surprising considering we found 5 different solutions for B in testing (intended was just brute force).
You don't need to downgrade yourself by comparing yourself with others!.
The idea is very well known. Just study about it, so the next time you see this problem make sure you are the first one to solve among your friends!!!
First time solving d1ABC!
great problems d1C&D!
mathforces
I think this contest is not for div 2 coders
why? I mean ppl around 1300-1500 can solve first three problems
why so many downs? I really stupid & nob, but can still solve first three problems ( i mean pretests )
Bro, you able to solve it doesn't mean everyone solve all three problems
hardest Div2C I've ever seen
We actually had a harder version before lmao. Originally, K<=10^9.
and what is the difference now?
Now, more binary search solutions pass and an alternate implementation in O(k) time also passes.
look in statement $$$k<=10^9$$$
No?
Don't make contests just to Show-off.
Is there anyone who can give some hint on 1C? I have absolutely no idea.
In this problem, you want to cover an array with intervals such that the $$$i$$$-th octopus is covered by $$$a_i \pmod k$$$ intervals (if $$$a_i = k$$$, set it to $$$0$$$). The idea is that you want to process the array from left to right while opening or closing intervals. Opening an interval has a cost of $$$1$$$ while closing an interval is free.
There is also the constraint that you should have a non negative number of currently open intervals.
When you study the quotient of the number of open intervals by $$$k$$$, you can see that :
if $$$a_i < a_{i-1}$$$, you can pay a cost of $$$a_i - a_{i-1}+ k$$$ to increase this quotient by $$$1$$$, or keep it constant for free.
if $$$a_i > a_{i-1}$$$, you can pay a cost of $$$a_i-a_{i-1}$$$ to keep the same quotient, or decrease it by $$$1$$$ for free.
You always want to maintain the quotient by $$$k$$$ non negative
The main idea of the greedy is that we want to decide as late as possible if we open intervals. By default, we choose to close intervals, but when we can't, it means that we had to pay a cost before.
Maintain a priority_queue with the cost you could have paid. When $$$a_i \neq a_{i-1}$$$, push the cost of opening intervals in the priority_queue. If $$$a_i > a_{i-1}$$$, you had to open intervals before to increase the quotient, so you can greedily pop the least cost from the priority_queue and add it to the total cost.
I thought using brute force for the second problem is not good idea
wow. It was really ( i mean really ) interesting contest ( for me, as div2 user). Amazing second & third problems, like, for me, they was hard, but really interesting. Second was on idea mostly ( like not many fibonacchi numbers ) & third was on idea & realization ( as for me i mean )
cry (The author of this blog) really made me cry during the contest.
S/He literally gave the spoiler of the full contest in the handle.
Div.2(x) Div.1.2(√)
Problem B can be easily solved thanks to this post.
So we can iterate over all values of $$$f_1$$$ from $$$0$$$ to $$$n$$$ and check if there exists integer $$$f_2$$$ such that $$$f_2 >= f_1$$$ since we need a non decreasing sequence.
We don't even need to check for $$$k > 30 $$$, as $$$f_{30} > 2 * 10^{5}$$$ . So the answer for all such values of $$$k$$$ will be 0.
Time complexity : $$$O(n)$$$
Div2C was so difficult but once you solve it ,it seems easy.
How did you solve it, Can you share your solution?
can you give a hint, I just got to the point that
max element that will be canceled on last day = max_element + (k — 1) * (max_element — number missed in b/w)
for eg = 1 3 5 7 number missed = (2, 4, 6) = 3 k = 2
max element that will be canceled on last day = 7 + (k — 1) * (7 — 3) = 7 + 2 * 4 = 15
See this — Commrnt
I wrote this solution for Problem C in the Round 887 Div. 2. Could someone help me how can I get this correct. I am getting TLE in the last test case.
Please somebody tell me how to do div2 C and how you came to this conclusion :(
consider the items the first number deletes every round
note that it increases by 1 -> i.e. 1, 2, 3, etc until you reach the position of the second number, then it increases by 2, then 3 when you reach the third number, etc
my code:
Wow, nice observation!! Thanks a lot
can you explain please, couldn't get it.
reasonings of such patterns?
just write out some simple cases
That is all right but any special reasoning happening such pattern.To observe it is a good thing but to analyse and getting to prove side of it is best.I am not to able to convey what i want .But something to prove this observation might help me in what i want.
Can you please kindly explain your solution?
why are you updating curv and cur when curv>a[cur] ?
My intuition was that answer can be a very big number, so we might be able to use Binary Search on Answer. Then the predicate function clicked immediately.
f(x) = Count of numbers deleted before 'x' == x-1
Now how did I calculate f(x) ?
I observed that once we delete some numbers, the "indices move forward". So for a particular 'x', once an index 'i' crosses 'x', deletion of 'ith' smallest element now doesn't affect f(x).
Very unbalanced contest C was very annoying
For Div2 B, I got that we want number of integers in the interval $$$[nx_{k-1},nx_k]$$$ where
Here $f_i$ is $$$i$$$-th fibonacci number with $$$f_1 = 0, f_2 = 1$$$. It can be shown that
with $x_1 = 0$.But when I tried to evaluate this, I was getting TLE on pretest 5; is the way to go?
No, there is a much simpler solution.
While I'm waiting for solution, here is what I wrote in $$$B$$$ and just now noticed, that this is incorrect.
Corner cases: all are $$$0$$$, all are $$$n$$$, there are $$$0$$$ and $$$n$$$.
For simplicity, there is $$$0$$$. It not, do $$$a_i = n - a_i$$$.
Some number are positive, others are negative. Sort all values. Some suffix is positive and has all edges. Let size of suffix be $$$cnt$$$, sum on suffix be $$$s2$$$ and sum on prefix $$$s1$$$. If $$$s2 - s1 = cnt^2$$$, this is correct split position, answer is $$$YES$$$. Now to build it. Look at suffix, let it be $$$a_1, \dots, a_k$$$. Subtract from all of them $$$cnt$$$. Let $$$idx = 1$$$. Take $$$a$$$ values by blocks of same values. For each block put $$$-idx$$$ to front of result vector $$$a_i$$$ times, then put $$$idx+1$$$ to back of result vector size of block times, add $$$idx += 2$$$. At the end append left $$$-n$$$ to front of result vector.
Further steps:
Write stress
See, as it immedeately asserts, investigate test
Cry, write this
About problem $$$A$$$. Well, that looked obvious for me, that I have just to $$$k - 1$$$ times do $$$x = a_x$$$, where $$$a_x$$$ is a vector of non-mentioned numbers.
Though, I think that $$$a_i \le 10^9$$$ does not make sense, and makes implementation move complex without any reasons (I wrote something like scanline, also thought about set::lower_bound, of binary search).
div 2 c Is a good problem to think about for 3 days after contest
Problem B and C were good, amazing contest!!!.
This was hard. Managed to lose only 21 (according to carrot), i'll get purple in the next context.
Also my brain farted a little on B when i tried using diophantine equations or double for to find the coefficients. Anyways the problems are nice, B is a very cool property of fibonacci-like sequences
2*Div 1
I got some inspiration from this task to solve D1A/D2C
GoodBye my chance to become master :( I really have hard time
Hardforces for div2
Nice problems!
Solution for B (if anyone needs):
-> Form the Fibonacci Series up to 200005, call it arr
-> For a Fibonacci Series of length k and last term n, it looks like this:
a, b, b + a, 2b + a, 3b + 2a, 5b + 3a, ....., arr[k — 1] b + arr[k — 2] a
-> The equation is arr[k — 1] * b + arr[k — 2] * a = n
-> Fix the values of a from 0 to n and find if there exists an integral solution b for the equation
-> if exists, ans++
-> One edge case: n is only up to 200000, so k can't be > 200000, if so answer is 0
:
When every problem in the contest seems solvable but you're still not able to solve all :(
I overkilled problem B by doing fast general fibonacci calculation to determine the last element of the sequence in log(k) time by doing fast squaring of matrices for the fibonacci sequence.
Then I bruteforced over all of the first element, binary searching for the second element using my fast_fibo function to see which one is closest to n. If the fast_fibo(i, j, k) == n, then i increase the count
Time complexity: O(n log(n) log(k)) ??? LOL
I was like: "Theres no way this can be a problem B..."
EDIT: Just failed system tests LOL
haha it seems this round has a lot of overkillable problems
people "solve" problems B and C and say they're implementation hell when theres actually a clean 10 line solution for both of them
Yeah, it turned out there are pretty short implementations for C and B, but coming up with that idea is not easy..
I came up with a pretty easy and intuitive solution for div2 B after about an hour.
can you please tell(maybe briefly) about the intuition...
I have just simulated the whole process according to the question. For a given number $$$N$$$ at $$$k$$$ th position, I am brutally checking if it is possible to have some number $$$x$$$ $$$(0 <= x <= N)$$$ at $$$(k - 1)th$$$ position.
Check function is really simple, if we just fix $$$(k - 1)th$$$ number and $$$k$$$ th number in a fibo sequence, we can easily determine that $$$(k - 2)th$$$ number will be the difference of $$$k$$$ th number and $$$(k - 1)th$$$ number. With that we can easily determine if the sequence we are getting by fixing those $$$2$$$ numbers is a valid sequence or not by recursively calling the same function with different values of $$$N$$$ and $$$K$$$. Sequence is Valid if $$$k = 0$$$ and $$$N >= 0$$$ otherwise if $$$N$$$ become negative, the assumed fibo sequence is inValid.
The problems are so hard that very few people are able to solve CDEF in div.2
B felt a little tougher than a usual div2 B, A was perfect
Performed really badly! Don't even feel to give cf contests anymore!
For Div2 B I tried hacking with this solution 215216845 with test case: 1 200000 1000000000 but judge gave me unsuccessful hacking verdict. Can anyone explain why the above mentioned solution won't TLE on this test case. Also the solution got FST on test 21 with TLE verdict.
This was already a pretest
Yes but it runs in O(1e9) which should TLE?
1e9 fairly fast operations isn't too surprising
I lost 100 points for 2 unsuccessful hacks. I later realised in last few seconds that I should have used 1 1000000000 for 200000 times. It might have given me 150 points from my room.
Exactly same thing happened with me , I used it 10 tim s but still passed, i'm still not sure how a O(1e10) solution could pass
Solved B with just brute force, just like what the problem said: Solution
for problem b, the constraints are tricky because the highest Fibonacci term (where in the original Fibonacci sequence the first two terms are min possible ) less than 2 * 10 ^ 5 is the 27th term(0-based) so it's okay to brute force the solution. you know that the last element is n so start from pos n — 1 and try all numbers that you can use from n to 0 and call it x for every x use recursion to build the sequence, if at any pos you can't get a valid value ( positive and less than the next value in sequence ) so this x is invalid
28th term actually but the idea is correct
I edited it, thanks.
very nice problems
div1 A is so hard,but div1 B is too easy.There's also a huge gap between problem B and C.
Opposite for me, I took so long to find the correct observations for div1B/div2D meanwhile I solved div1A/div2C quite easily with binary search
Nice finally some quality stuff!
Just realized after the contest that B could be solved by brute force bcoz Fibonacci series is exponential , great contest overall!
Binary search is really a great thing
a great tool
Congrats to all the top-participants!
I used a mysterious method to pass this problem in C of Div2, with time complexity O(n). Is anyone interested in proving the right thing to do? https://codeforces.com/contest/1853/submission/215254923
I solved Problem C with binary search. I search if we can delete a prefix of numbers 1, 2, 3, ... x using given operations. If we can delete it then we can also delete prefix upto x-1, x-2 and so on.
I have a Question about a problem, in problem D in Div 2, or problem B in Div 1, I sent my code which was graded as a RTE in case 18, I simply changed the variables from long long to int, and magically the problem was an AC. The more I try to explain why this happened, the more confused I am, mostly because I only use 4 arrays of size 2x10^5 and a few extra variables.
I'm sending my submission that got an RTE: RTE code
And my submission that got the AC: AC code
I would thank so much to whoever explains me why this occurred.
Take a look at Ticket 17000 from CF Stress for a counter example.
Ideone Logs
There's clearly an out of bounds access in your code, you just got lucky with your second submission due to how the memory is mapped for int vs long long. It should be easy to find out the troublesome line using the testcase from the above site. If you're still not able to figure it out, I'll share the exact line number later.
Thank you for your feedback.
Why 256MB ML?
Sometimes people ask this question and the answer is often like "Hmm, we didn't intend to accept or reject your solution. We just didn't recognize such a solution, and used the default ML". Today I got MLE in Div1D and I guess this is yet another example of the above story.
This is certainly my mistake, and I won't complain about it to the authors. However, I'd like to ask why is the default ML 256MB, and I'd be happier if it was 1024MB or something. Is there a particular reason for the current value, or it's just that nobody cares?
hi, i prepared div 1d, and indeed there were a lot of things i could do better, i apologize :(
It is like you said, we did not consider raising the ML since all testers' solutions had very little trouble passing under the constraints; all of the solutions that AC pass with minimal memory.
Next time I will try to be more careful, once again, sorry :(. But I do think you raise a good point. A lot of the times blatant MLE can be caught by TLE anyways, and unless the problem is about optimizing memory (which usually isnt fun) there is little point in blocking slightly worse solutions with a valid memory and time complexity. I will try to keep this in mind for the future.
The contest was very difficult as compared to other div 2 contests. Benq OP.
Ratings updated preliminary, it will be recalculated after removing the cheaters.
Happy for becoming pupil :)
disappointed , couldn't solve C
should've swapped c and d in div2
215249497 Hmm, I have O(n) solution for problem D. Can somebody give me a counter test?
Well, it is possible to solve D1B/D2D in $$$\mathcal{O}(n)$$$ using counting sort.
B was actually pretty hard 4 a normal div2 B.
I received a notification from the system indicating that my solution has matched with several individuals. It is unfortunate that this has occurred, as I encountered unusual responses from my Code Blocks IDE yesterday. Consequently, I resorted to using ideone.com, where regrettably, I failed to notice the presence of the global and secret buttons. As a result, it appears that my solution may have been inadvertently leaked. I must emphasize that this is the first time such an incident has transpired for me.
To substantiate my claim, I have attached proof of my utilization of ideone.com in the provided link. Rest assured; I am taking immediate measures to prevent any recurrence of this situation in the future.
I appreciate your understanding and extend my best wishes to you in your coding endeavors.
https://drive.google.com/file/d/1TSNA_sFDnDaBd_3z4FKnpmSn6xmGaLlj/view?usp=sharing
https://youtu.be/9fNJvvqVTpo
The problems B,C and D of div2 was very good learnt a lot, not able to perform well during contest.
try to explain solutions of Problem A,B, C and D in this video
problem A: try to unsort a[i] and a[i+1] for each i.
problem B: try to reach Ax+By=N; where A is kth no of fibonacci series {f[0]=1,f[1]=0}; where B is kth no of fibonacci seires {f[0]=0, f[1]=1}; and find out the no of integer solution of x and y such that x is less then or equal to y;
problem C:- what is the position of x after first day? and then in how many days x will be removed;
problem D:for every i and j (abs(bi)!=abs(bj)) and try to find out number of positive intergers in imbalanced array, and then fill positive intergers one by one and according to need fill negative integers.
I appreciate the video, but please add "(Hindi)" in the title as not a lot of people speak the language.
I solve Div2 C differently. After some day it falls into a pattern. So our task is to find when it falls upon a pattern. Take a look at my code 215241713
Isn't this very similar to simulating deletions and a solution in this comment. And if by a pattern you mean that after some day we are going to start skipping n consecutive numbers for every single one of the remaining days — yes, using brute force you can see that for any arbitrary inputs at some point the smallest remaining number is going to be increasing by n each time after each round of deletions.
Yes. About same .
can anyone explain the solution of div2 c question?
https://www.youtube.com/watch?v=FncWOIFebWA
I haven't copied a single problem but it still gives says skipped it's so bad They plag on approach as well?
Rating of Problem D ?
Great contest as always, the quality questions there. Can someone help me with this, I am able to crack the logic but can't really code out that missing on some test cases like that. How to get good at that.
https://codeforces.com/contest/1853/submission/215420954 Look at my solution for B? Recursive binary search for find the correct FIB(k-1), then two binary search for find the sides(min and max) of correct values FIB(k-1)
seems like it's harder than expected solution
think i can optimize it with queue of pair{l, r} instead recursion
I wasn't able to solve Div2B but I absolutely loved the problem. This was the first time I used bruteforce to generate possible solutions so that I could identify patterns. Discovering that for every sequence where $$$f_k = n$$$ that $$$f_i$$$ increments or decrements with values corresponding to the standard Fibonacci sequence was so cool to me.
Can't wait to upsolve this problem later. Thank you problemsetters!