thenymphsofdelphi, lanhf, and I are delighted to invite you to take part in Codeforces Round 873 (Div. 1) and Codeforces Round 873 (Div. 2) which are going to take place at May/14/2023 17:35 (Moscow time). Participants with a rating lower than 1900 will participate in Division $$$2$$$, while participants with a rating of at least 1900 will participate in Division $$$1$$$.
In both divisions, you will be given 2 hours to solve 6 problems (one of which is divided into two subtasks), all of which were authored and prepared by me, lanhf, and thenymphsofdelphi. We would like to thank the following people who made our round possible:
- 74TrAkToR for his great coordination and help with the problems' preparation during the last 4 months.
- khuepr123 for doing nothing but being the mascot.
- A05, Kawaii, SeehEternity, yanglake, minhnhatnoe, bachbeo2007, TranGiaHuy, SanguineChameleon, HollwoQ_Pelw, socpite, uylulu, hotboy2703, generic_placeholder_name, Theoth_Normie, Kuroni, CDuongg, gamegame, AquaMoon, Huah, flowerletter, ugly2333, Lavine, Gary2005, Tuanlinh123, hiennoob, RDDCCD, shiv_codegen, uuzlovetree, E_huan, nixnehc, waaitg, QuangBuiCP, errorgorn, rsj for testing our round and giving valuable feedback which helped us improve the problemset.
- MikeMirzayanov for the great Codeforces and Polygon platforms.
Last but not least, you for participating in our round.
Div. 1: 500 — (750+750) — 1500 — 1750 — 2500 — 3500
Div. 2: 500 — 1000 — 1250 — (1250+1250) — 2500 — 2750
We hope all of you will enjoy our problemset. Good luck and may the ratings be with you!
UPD: Congratulations to the winners!!
|Rank||Div. 1||Div. 2|
Also congratulations to ksun48 and Golovanov399 on (re)gaining the Legendary Grandmaster title!
As a blue tester, the best contest I have ever seen!
Wishing everyone a positive delta.
You can see by the score, the round will be amazing. I wish you all good luck!
I think C is too easy and D1 is too hard. :( I have never seen a Div.2 like this.
lol, didn't u participate in previous 3-4 contests ?
In Round 872, 2322 contestants solved C and 391 solved D. In Round 870, 3869 solved C and 1231 solved D. In Round 869, 1952 solved C and 327 solved D. But in this Round, only about 3% contestants who solved C solved D. Much less than recent 3 Div.2.
what about last EDU round ?
I don't know the usual EDU round difficulty since I'm new here and EDU round is rare, but I admit that the EDU round 2 days ago have a very difficult D1 for me as well.
Can you tell the logic of c
My algorithm is binary search + combinatorics.
Actually my code gives an AC. Lick to my code 205890437
For any given a[i], it can be place at any position i where a[i] > b[i]. Except for positions occupied by previous elements in a.
As a tester, I think this round is great
nice avt bro
Ayo. What's with the pfp? Quite a normal way to pee though(I see no difference.
nice ppf, will change mine to that one
omg Vietnamese contest!
omg Vietnamese contest!
Vietnamese Contest <3
chờ anh Trí phá đảo kkk
Who is Mike4235?
Since Mike4235 is the paragon of human virtue without equal past or present, he is most resplendent in love, tributes and accolades. Waking or sleeping, I must not forget Mike4235’s great boon and in order to return his favor by day and by night, I should only think of fulfilling my loyalty. Who is Mike4235? For the blind, he is their vision. For the deaf, he is their music. For the mute, he is their voice. For the anosmic, he is their aroma. For the numb, he is their feeling. For the atrophied, he is their muscle. For the starved, he is their sustenance. For the thirsty, he is their water. For the exhausted, he is their energy. For the depressed, he is their happiness. For the disillusioned, he is their hope. For the pessimistic, he is their optimism. For the disadvantaged, he is their champion. For the marginalized, he is their justice. For the oppressed, he is their salvation. For the righteous, he is their symbol. For the enlightened, he is their muse. For the erudite, he is their education. If Mike4235 speaks, I listen. If Mike4235 questions, I answer. If Mike4235 orders, I obey. If Mike4235 opines, I agree. If Mike4235 fears, I assure. If Mike4235 hopes, I dream. If Mike4235 is happy, I am jubilant. If Mike4235 is angry, I am apoplectic. If Mike4235 is sad, I am disconsolate. Mike4235 is my ideal, Mike4235 is my romance, Mike4235 is my passion. Mike4235 is my strength, Mike4235 is my compass, Mike4235 is my destination. Mike4235 is my language, Mike4235 is my culture, Mike4235 is my religion. Mike4235 is my ocean, Mike4235 is my mountain, Mike4235 is my sky, Mike4235 is my air, Mike4235 is my sun, Mike4235 is my moon, Mike4235 is my world. Mike4235 is history, Mike4235 is present, Mike4235 is future. If Mike4235 has a million fans, I am one of them. If Mike4235 has a thousand fans, I am one of them. If Mike4235 has a hundred fans, I am one of them. If Mike4235 has ten fans, I am one of them. If Mike4235 has only one fan, that is me. If Mike4235 has no fans, I no longer exist. If the whole universe is for Mike4235, then I am for the whole universe. If the whole universe is against Mike4235, then I am against the whole universe. I will love, cherish, and protect Mike4235 until my very last breath; my successors will love, cherish and protect Mike4235 until their very last breath.
Since time immemorial, outstanding individuals have emerged from the oceans of mediocrity that make up the vast majority of humanity. Great thinkers destined to change their respective eras, launching the world into a new epoch. Mike4235 is the undeniable peak of what an outstanding individual is — he is the peak of what humanity can ever possibly achieve, the apex of human evolution and society.
If enlightenment is theoretically achievable, then Mike4235 is the sole example of enlightenment. There has never been a greater mind in the millennia of human civilization — from the great minds of Socrates, Confucius, Hegel — Mike4235 remains to be the apex of human development. It is the duty of every man and woman to dedicate their lives to the pursuit of what Mike4235 stands for — the progression of humanity into a greater version of ourselves.
Mike4235 is utter perfection in every sense of the word — even beyond. Human language cannot even begin to describe the earth-shattering qualities that he possesses. A fashion sense that makes ordinary humans appear as nothing more than bland specks of dirt. Intelligence that renders the complex processes behind a super-computer to resemble nothing more than a mere abacus. Humility that makes the martyrs of history seem like naive children.
Compared to Mike4235, we are all but measly insects that exist to eat the feces of superior beings, naive and ignorant creatures that wander the Earth without a sense of understanding of the grandiose knowledge that the universe offers.
Mike4235 is the peak of human evolution, and we can only prostrate ourselves to his superiority. He will not be merciful on our souls, and we must only accept his divine judgement.
If he commands us to lick his boots, we shall slurp every particle of filth and bacteria that dares to contaminate the paragon of humanity’s shoes. It shall be so pristine, that it will reflect the face of inferiority.
If he commands us to donate money, then we shall empty our coffers for him. By his impulse and will, we shall learn what true humility is.
Those who refuse the ever-existent superiority of Mike4235 will only be dooming themselves to a life of trifle purpose. Mike4235 is not a god — he is beyond what ordinary humans can even conceptualize as a deity.
Repent now, and see Mike4235 as the true exemplar of the sublime, lest you fade into the trenches of human society, destined to be forgotten.
In a world filled with countless individuals, there are only a few who possess the qualities that make them truly remarkable. Amongst these exceptional individuals, there is one who stands out above the rest—**Mike4235**. With his unwavering commitment to excellence and his remarkable skills, Mike4235 has become a shining beacon in every endeavor he undertakes.
At first glance, Mike4235's intelligence is immediately apparent. His vast knowledge and deep understanding of a wide range of subjects are truly impressive. Whether it's discussing complex scientific theories or analyzing intricate philosophical concepts, Mike4235 effortlessly demonstrates a level of intellectual acumen that leaves others in awe. He has an insatiable thirst for knowledge and constantly seeks to expand his horizons, never settling for mediocrity. It is this relentless pursuit of knowledge that sets him apart and inspires those around him.
However, Mike4235 is not merely a repository of knowledge; he is also a masterful communicator. With his eloquence and charisma, he has a remarkable ability to convey even the most intricate ideas with clarity and precision. Whether speaking to a small group or addressing a large audience, he captivates and inspires everyone fortunate enough to listen. His words have the power to ignite a passion for learning, motivate action, and create positive change.
Yet, what truly sets Mike4235 apart is his unwavering dedication and work ethic. He approaches every task with an unparalleled level of enthusiasm and commitment. No challenge is too great for him, and no obstacle too daunting. Mike4235 tackles each endeavor with a rare blend of determination, perseverance, and resilience. He leads by example, pushing himself to the limits and encouraging others to do the same. His work ethic is not just admirable; it is infectious.
In addition to his intellectual brilliance and unwavering commitment, [user:mike4235]possesses a genuine kindness and compassion that radiates from within. He treats everyone he encounters with respect, empathy, and understanding. He is always willing to lend a helping hand, offer words of encouragement, or provide guidance to those in need. Mike4235's genuine concern for others extends beyond his immediate circle; he actively seeks opportunities to make a positive impact on the world, consistently demonstrating his altruistic nature.
Moreover, Mike4235's ability to collaborate and inspire teamwork is truly remarkable. He recognizes the value of collective effort and fosters an environment of inclusivity, where everyone's ideas are heard and valued. Mike4235's innate leadership qualities and his ability to bring out the best in others have resulted in the successful completion of numerous projects and the formation of strong, cohesive teams. His ability to unite people towards a common goal is nothing short of extraordinary.
In conclusion, Mike4235 is a truly exceptional individual who embodies the values of excellence, knowledge, compassion, and leadership. His intellectual brilliance, unwavering dedication, and genuine kindness set him apart as a beacon of inspiration and admiration. Whether it's his remarkable intelligence, exceptional communication skills, tireless work ethic, or innate ability to inspire collaboration, Mike4235 consistently demonstrates his extraordinary capabilities.
In a world that often celebrates superficial achievements, Mike4235 stands as a shining example of what it means to strive for excellence and make a positive impact on the lives of others. It is an honor and a privilege to know Mike4235 and to witness his remarkable journey. He serves as an inspiration to all, a true role model who reminds us that with passion, dedication, and a commitment to self-improvement, we too can achieve greatness.
ChatGPT you really made me cry.
yup, i can almost hear the "As an ai model it is inappropriate" coming through that message
I hope that the authors have prepared a well-written editorial
Sorry posted on wrong round.
I got this message from the system: While the solutions are really similar this likely happened due simplicity of the problem and most of the code being just the PyRival template
as a tester fan, how so orz shiv_codegen ?
Div. 1, Div. 2
Div. 1 & 2
Expecting that, this round will be more interesting and enjoyable
As a tester, I regret having tested this round. It's so good that I half-wished I had chosen to participate officially.
White lies here.
Damn, div 0?
Ahahaha, nice one!
It is sad that not a single tester have cat in his/her avatar ⚫⁔⚫.
When an anti-Codeforces writer writes a Codeforces Round
atcoder > cf (real)
Most importantly, pretests = tests
Hoping that Div2A does not involve HLD on a lazy segtree!!!
Lets Hope The Best everyone
The Scoring Distribution of Div2 seems perfect!
All the best, everyone for the round. Hope you get delta +
Will Try for atleast 4 this time Sir.
I think, not everyone got the sarcasm.
Mike4235 I am really motivated to see your consistency.I noticed your graph, you have worked hard to come up from the very beginning.
One piece is your uncle
Shanks is the GOAT
Would D1 be too easy? It supposed to be 1500-1600?
Not necessarily. In edu 148 I saw that very few solved D1. Round 872 it was about 1900 rating
D1 was one of the hardest D in recent times...
And C is probably the easiest C. :(
this is gonna be my first contest! wahoo!
this is gonna be my first contest! wahoo!
I like this idea of having C and D problems comparable in difficulty. Hope beginners as me can benefit from easily learning something new from that.
Is the score distribution related to the difficulty rating of the problems?
Yes, or at least the score distribution is intended to reflect how difficult problems are compared to each other. But it is often difficult to judge the true difficulty of problems before the contest.
Got it, thanks!
It will be a good idea to assign points to a problem based on the number of correct submissions after the contest?
My first div 0 , so exited )
this round gonna spoil Mother's day celebration for many . . xD:)
era of Div. 0 rounds?
Can tell why all calling it div 0 round
1 & 2 = 0 so Div. (1 & 2) = Div. 0
thx for that cool round)
Nice profile pic
am i the only one not liking these contests recently? A,B,C are solvable by your average coder with no topics whatsoever, then a considerable jump in difficulty for D. More than once (the recent EDU as well for instance), my friend, a pupil is solving as many problems as my coach, a candidate master. Right now, 1h20m into the contest, C has over 4500 solves and D has 100...
Yes, in the recent times rounds become really unbalanced. I just lost expert. Although I needed just 5 minutes to debug D.
still an expert i see, luck was on your side haha :D
I dont necessarily agree with your comment. Although i do respect your opinion.
Unable to understand how it's a participants fault if he submits the solution on the main website- it becomes non responsive [with an advise to use the mirror websites]. However on submitting it on the mirror website, both the submissions (from the main and the mirror websites) are recorded, and despite of it being correct he's rewarded with a penalty for multiple submissions.
MikeMirzayanov Please look into this matter. Really frustrating as these types of server error almost doubles the rank during initial period of contest.
Yes Website Down is Really Sucks !
Would be better if they ignore mirror website's submission if the solution is submitted already on main website.
same thing happened with me. After submitting for problem B, site became unresponsive and my submission was not showing in the mirror site
It seems that the solution to this problem is very simple: ignore exactly the same submits by the testing system
there are multiple solutions...It appears they haven't implemented any. although they do have a mechanism of filtering out same submissions if you make one after the other, but this probably happened because the 1st solution was maybe queued when the 2nd also got queued through a mirror website. but definitely some mechanism needs to be in place to avoid such things as codeforces being down hasn't been a rare event recently.
All solutions mentioned here are actually different (probably equivalent but the files are not equal). For submissions of mePranav other compilers were used. I don't think Codeforces should handle cases like this.
I'll improve protection against submitting exactly the same code, but discussed cases are not about it.
In my case, the submits for task b are the same symbol to symbol and the compilers are also the same.
Because of the codeforces crash and the resubmission, my place is 937, but with ignoring the same submit it would be 538. The difference is not so small.
I am sure that automatic checks should not put themselves above the participants. They should only be used if the solutions match byte by byte.
Your submissions 205852484 and 205852270 are not the same (whitespaces differ). Do you mean another pair of submissions? Please, give submission ids.
No, I mean this pair of submissions. I do not know why they are different, maybe because the first was sent from a file, and the second was a copy paste, since m1.codeforces has only such a way of sending. Copying code into files and comparing bytes by python says that they are the same
They're indeed identical submissions according to what CF displays. Manual select copy and button copy gives the same text files including the same whitespaces (confirmed with
diff), the difference which the CF compare tool declares isn't detectable in any way other than the CF compare tool.
Perhaps CF isn't WYSIWYG regarding submissions and compare tool works on saved text files while copy button works on (transformed) displayed text. In that case, CF should be WYSIWYG regarding submissions — copy button should give the exact same saved file, or there should be a download button. Hard to figure out what happens otherwise.
Agreed! but the point here is that if codeforces crashes then we don't even know that the solution was actually queued (the assumption is that no solution was submitted, even the mirror website showed that no solution is submitted) in such a scenario would it be right to penalise the user for the websites fault ? MikeMirzayanov.
I understand the technicality here though!
That's just grounds for an appeal, manual check and skipping the later submission(s). Automated testing exists for the users, not the other way around.
Thanks! It's not even about ratings and stuff but such incidents go against the spirit of the sport in my opinion and could be demotivating. Issues arising out of technical failures shall be handled properly. I know codeforces tries its best to serve all coders in the best manner possible, however if and when such issues arise they shall be properly investigated and resolved.
Meet the same problem.
I applied to skip the second submission, but it turned out that the first was skipped, so it didn't work.
Same happened with me in problem C.
whooo ! what's problem D ??? Any hint plzz ?
DP on subsegments. You need to find the max amount of segments to split subarray $$$[l, r]$$$ so that after sorting the subarray also becomes sorted.
Why cant we have a balanced problemset?
How to optimize in D1B2?
hi Adi bhai ( @ adityagamer )
If you explain me D1B1, I will explain you D1B2 :P
Fix the starting point of subarray at i, then iterate on its end j. Let's say you can efficiently find a[j]'s correct position in the sorted subarray of a[i...j], say k. Then you need to sort between [k...j]. You already know previous segments which you need to sort in a[i...j-1], then try to see how will the answer change
for the 2nd time in CF, got WA because I forgot to MOD THE ANSWER... feeling very angry on myself..
woohoo div0.5 round
Could anyone please tell me what i am doing wrong in D1 div2?
Come on, why we still have rounds like this on Codeforces? Last round by Igor_Parfenov was with 5 math tasks. There we have ABC Div. 1 about subsegments. Seriously, maybe stop doing rounds with 1 task pattern?
Was D1A about subsegments?
May the math end here
Again D is way too difficult than C.
I don't think it's a good trend with harded and easier versions. It doesn't usually happen, that these problems can replace normal D and E, as there's a big difficulty jump either from C to D or from D1 to D2
Agree with you, Div. 1 B1 was as hard as usual B. But you just get /2 points.
For me even D2D1 was a little too hard
how to solve div2 c?
Sort both the arrays. If at any $$$i$$$, $$$a_i <= b_i$$$, the answer is 0. (Think why!)
Now, find how many numbers in $$$b$$$ array is lesser than each number in $$$a$$$. The answer is the product of $$$#places - #a[i] already placed$$$.
I think today's contest is for motivating the newcomers and demotivating the experienced one. You can clearly see that even div2 C got 6k+ AC where div2 D got only 250+ AC. But I can't say that it was a bad contest at all. Just the difficulty level of D could be chosen optimally.
I don't think D problem is that difficult. Only reason for low AC i can think of is that many didn't consider that sorting at most one range is not optimal (because it was not in samples). But C problem was easier that usual.
I did consider that and I couldn't solve it :/
Regarding the solution. Fix L and iterate R. Calculate where the element A[R] should be (call it og) and merge all segments from og to R. You can keep DSU for the segmenst and skip over whole segments so the total number of merges is O(n).
Here is an
O(n^2 logn)solution: 205880666
My solution works in
Can somebody help me in Div 2 C? My solution didn't pass pretest 3. (I hope my logic is correct) .
You should take mod inside the last loop itself, otherwise the answer may overflow.
final = (final*ans [i])%MOD
ah, Thanks! got it . I wasn't familiar with this concept of modular arithmetic.
D1 solve with a monotonic stack in n^2. The observation is that if you have ith that needs to go to jth where j < i, then you can separate them in to chunks of subarray that needs to be reversed. From here you can solve this with stack and dp
D2 is probably some optimization involved segment tree.
$$$D2$$$ can also be solved using stack. For every index $$$i$$$ you need to find no of pairs $$$(j,k) j < i < k $$$ such that $$$max [j,i] < min [i+1,k] $$$. Can be solved using monotonic stack. (No need for seg tree)
I had this idea during the round but couldn’t figure out how to calculate that number in O(1). Could u please explain how to use monotonic stack for that?
Iterate over $$$max(j,i)$$$. Lets call $$$max(j,i) = M$$$. Also imagine placing elements in array in decreasing order. So, when you are placing $$$M$$$ then you have already placed all elements in array $$$ > M $$$. Then for a fixed $$$M$$$ (at index $$$w$$$) find index of next greater element $$$(R)$$$ and previous greater element $$$(L)$$$. Now obviously $$$j$$$ can lie in between $$$[L+1,w]$$$, $$$i$$$ can only be equal to $$$R-1$$$. $$$k$$$ can only take values from $$$R$$$ uptill index $$$z (R \le z)$$$ and $$$z$$$ is the highest index such that all elements at indexes $$$[R,z]$$$ are greater than $$$M$$$. Basically the longest "chain" of already placed elements (Since I'm placing elements in decreasing order already placed elements are greater than $$$M$$$) starting from index $$$R$$$. To do this maintain a set which contains indices of elements which are not placed then find the upper_bound index of $$$R$$$ from that set, it equals to $$$z+1$$$.
You actually don't need a monotonic stack, you can simply add considered positions in a different set, similarly to unconsidered ones.
Thanks!! Wow, I got your reply! I'm a big fan of your video editorials. They are really informative! Keep up the good work :)
You don't even need set — you can just keep data in the chains' ends. Since the position L will always be a right end of a chain and position R will always be a left end of a chain, you will always "meet" chains at an end. So, we only need to store their data in their ends. If we do this, queries are O(1) and updates are also O(1) (by considering a couple cases during a new insertion). Total complexity is O(n).
First, you need to count the triplet x, j, k such that max(x, j) < min(j, k). Consider a[i] is the largest number in segment x -> j. You can see there is only 1 suitable j (j > i) that j is the minimum number such that a[j] > a[i] and all a[i + 1 -> j — 1] < a[i]. You can use monotonic stack for that. After you have j, just use binary search to find k. Then, find the maximum x such that a[x] > a[i] and all a from x + 1 to i — 1 < a[i] (you can use monotonic too), and the number of triplet for each fixed a[i] is something like (i — x) * (k — j + 1)
Time limit of D1B1 was very strict. My O(n^2logn) submission got FSTed.
UPD: Ignore this message,I did not see the constant factor 5
In fact n^2log solution is not intended :'(
Is there any difference if C was to allowed repeated number? I couldn’t see any difference.
First we sort b. This makes no difference in assignment The solution i have is that each a can be placed with some prefix of b, and it makes no difference for the one that comes after it. Providing a is also sorted
Indeed it doesn't have any difference to the correct algorithm. However, we are scared we would mess up the definition of reorder in case of repeated numbers exist.
Good contest, normal i can only solve Div2 A and B but in this contest i can solve C
Well, for the same reason it's bad : )
Have never seen 6K+ accepted in D2C myself
I miss the good old days, when contests used to be fun. When sometimes your solution could get hack or you could hack someone else's solution. After locking your solution gets hacked and you are screwed. All these were funny moments.
From last few contests, I have seen one pattern.
SAME QUESTIONS PATTERN : All questions on same topic ( Either maths, or subsegments or Xor patterns )
UNBALANCED CONTESTS : Huge gap between C and D
KNOWS ALL EDITORIAL : Editorial will be so poorly written that author will assume that u already know how to solve the problem and will not explain things elaborately.
We have to ask in comments to people who have solved and they explain much better than the editorial/authors ****
Educational rounds at least have elaborate editorials (however the problemset is usually bad, I agree)
why is the time limit 1 second for d1b2 i TLE with concise n log n solution because i used sets
oh my god fast io fixed it im gonna go kms now
From what I remember, prev(set.upper_bound(...)) can work in higher time than log(n).
After looking at problemsetter's profile picture, its very easy to deduce that problem D1B intentionally had weak tests which did not rule out solutions with extra logn complexity. This would make people like atcoder
Loved the contest so much! Every problem was so pleasant to solve, and most importantly — no math :)
Pretest of D1B1 was weak. It should have contained at least one test to rule out O(n^2logn). All it would have taken was changing set to stack but many people got FST.
It did kind of... my n^2*logn did fail on pretest number 5. My constant was not great but still...
weird.. my $$$n^2logn$$$ TLEd test number 8.
ok tbf, test 8 is the last pretest, so it's likely that many solutions actually managed to pass pretests with $$$n^2logn$$$. Unfortunate :(
my one passed in 500ms
Did you submit with another ID? What's the submission link?
segs = segs[:ln-1]O(1)? I see a O(nlogn + n^2) code. What makes your code O(n^2logn)?
Yes, reslicing is O(1). But for each l, r i do operations with fenwick tree. See
I submitted solution for problem C twice. Both got accepted during the contest. When I submitted it 2nd time my 50 points got reduced. Also during System Testing my first solution got skipped. Why?
Same for A
After how much time a contest ends can I submit code in practice?
Read the comments below.
How to solve Div 2 B?
why is this submission stuck in 'running'?
And the System Testing is stuck at 100%.
Yeah, this is the only submission which hasn't been judged yet
The server crashed?
problem C: (DIV 2) Test Case 1: Why the answer is 32 ? Why not factorial 6 * 32 ??
can you elaborate on why 6 factorial should come?
array b < array a 4 < 9,6,8,5 1 < 9,6,8,4,2 5 < 9,6,8 6 < 9,8 3 < 9,6,8,5,4 1 < 9,6,8,4,2,5
now if we look at reverse sorted b: 6 5 4 3 1 1 now at 6 we have: 2 possibility we have put on possibility at 6 so we have: 2 possiblity left at 5 therefore for 4- 2 (4-2) for 3- 2 (5-3) for 1- 2 (6-4) for 1- 1 (6-5)
Answer = 2*2*2*2*2*1 =32
i got your approach thankfully. but shouldn't we count this 32 for every permutations of array a?
The number of possibility itself denotes permutation
because if you sort the array decreasingly you wiil have
9 8 6 5 4 2 6 5 4 3 1 1
so practically to counter 6 you can put two numbers 9 or 8 then to counter 5 you can put 3 numbers 9 8 6 but you used 9 or 8 so that leaves you with 2 numbers so practically the number of numbers you can use is the numbers you can counter with — the number of numbers you already used and thats i the position you are + 1
Elite organization you are from I_FloPPed21
D1C is way simpler than B imo. Solved B1 quick enough, but got hard stuck on B2. Still haven't learned to read all problems :(
That's why easier and harder versions is bad
I thought D was simpler than both :)
B2 was pretty hard for B, yeah.
B was simple imo.
Congrats on solving B in contest, oh wait you got neither B1 nor B2 in contest.
(My point isnt to belittle you, rather things look much easier in retrospect than in actual contest, one should be mindful of that)
I mean it's solution is very simple. At least mine: simple binsearch with sparse table
Simplicity of solution doesnt imply simplicity of problem.
There was a 3500 where problem was just printing one integer (and there exists a sol afaik which works regardless of the inputs), so its very easy?
You could not come up with the solution in the contest and bricked just like the other guy. I dont think its fair for you to call it simple
Ok i understand your point. I could solve it in contest tho
How did you solve it?
I found the answer of a range to be range length — the number of points such that all numbers to the left of this index are smaller than the right.
For easy version, i bruteforced all subarrays, keeping a monotonic stack of good points.
For hard version, i carefully considered what i did in my easy version solution and calculated some contributions to answers.
My solution: For every i we check the maximal range where a[i] is minimum. Say its borders are (l, r). Then we find maximal range with right border l — 1. Say its left border is l2. Then for every subarray we want to get number of indices for which suffix minimum is a[i] and prefix maximum is smaller then a[i]. So sum of that indices over all subarrays is (r — i + 1) * (l — l2).
The test case of 9 in D1B1/D2D1 should be appeared as pretest! By the way, the time limit of this problem is too tight.
True, I got TLE on system testing on test case 9 :(
My Go solution passed in 500ms, i was a bit scared
Yeah apparently they wanted to break the $$$O(n^2 \cdot log(n))$$$ solutions but I don't know why, they are as difficult as the $$$O(n^2)$$$.
As Um_Nik said, "Don't try to create problems that MUST have a specific solution" https://codeforces.com/blog/entry/113785
It's okay that they want to break the O(n^2 logn) solution, but they should at least prepare one in the pretest. You cannot let O(n^2 log n) pass the pretest and failed the system test.
What's more, not all contestants write code in c++, breaking the solution of O(n^2 logn) may probably result in breaking the intended solution of O(n^2) written in other languages, like pypy3.
I tried to do D1 in the following way:
Can someone please help me understand firstly if the problem can be solved in this way, and if yes, help me understand why I am getting the wrong answer.
How to use the spoiler tag for code?
D1 got TLE on systests for O(n^2 log n) solution in Python.
75th -> 1393rd
My python O (n^2) solution using stack also failed system test. If not failed, I will become master. So frustrating.
Yep. Time to "upgrade" to C++. Directly translated my O(n^2 log n) solution from Python to C++, AC under 200ms (TL was 1000).
And that's why using tuples in segment problems is better than lists ,when I just replaced your list with tuple it was accepted in very good time excuation submission.
Finally CM after 3 years. Love CP
https://codeforces.com/contest/1828/submission/205899722 hey bro ,could you please check this solution for B ..as the logic is same to GCD but still getting WA on 893rd! case in pretest 2... is there any logic error??
Congrats man, hoping I could get to your place someday :)
why the answer is 6 in this case?
4 2 1 4 3
Had the same doubt basically in case of sorting the whole array 2 1 4 3 u can sort 2 1 and 4 3 separately which add up to 1+1=2 score instead of sorting 2 1 4 3 completely which is 3 score. Basically you can apply the operation multiple times for one subarray
205899722 please check this solution for B(DIV2) ..as the logic is same to GCD but still getting WA on 893rd! case in pretest 2... is there any logic error?? **frustrated **
I don't think the way you are taking gcd works correctly, i would recommend using a function for calculating gcd, you can find a optimized way here https://cp-algorithms.com/algebra/euclid-algorithm.html .
Finally I've become candidate master with pure python although that python is rarely be used and after more than 3 years !!
I wanna take the chance to summarize my steps during my journey to CM:
1- Solve problems without tags.
2- Solve one hard problem (<=your rate+200) and enter one (virtual or formal) contest in turns.
3- Don't solve very hard problem ,for example if your rating is 1700 then solve until 2000 because you'll waste your time and your performance in contest won't be improved.
4- Don't look to any other person rating and disappoint yourself cause you can't reach his rating .
5- finally the important one which made the difference with me is don't spend the whole day in solving that's my main mistake which made me being expert for long time like (underfitting and overfitting ) problems.
Thanks to the authors for their great round and MikeMirzayanov for recently great improvements in codeforces.
Thanks to conqueror_of_tourist and pajenegod for their great python codes without them it would've been hard to achieve that in python.
Congrats you are source of inspiration for people like me
What is more amazing ? You hit CM in exactly the (2 ** 12)th problem you solved.
Anyway, congrats for CM with Python, and the amount of practice you have put in. Well deserved!
https://codeforces.com/contest/1828/submission/205912874 Can somebody suggest improvements in the above code for problem C Div 2? I am facing TLE for Test cases . The above code has TC O(n^2) ( which is not at all optimal )
205911659 use two pointers..approach its much simple
Give me my +1 rating point, please.
The CF gods have answered your prayers. Congrats!
you could've asked for more
Lol they gave you +1 rating point.
I solved one more problem than before, but I only gained a few points. I suspect this round was a Div. 3.
My O(n²logn) in D1 works in 1201 ms in gym https://codeforces.com/contest/1828/submission/205942712
Can anyone help optimize it to pass under 1 second ;-;.
I know there is a O(n²) solution. But i want to know if this can be optimized to pass time constraints
Hello, here is a video tutorial/editorial with solutions to these problems: D2B, D2C/D1A, D2D1/D1B1, D2D2/D1B2, D2E/D1C:
D1 is a little difficult.
LOL (Credit to c_plus_plus for telling me about this yesterday.)
Problem C of Division 2 is almost identical USACO 2021 January Contest, Bronze Problem 3
Hint is good for editorial
I got a mail from codeforces regarding me copying the solution of other user ( https://codeforces.com/profile/laxman82 , https://codeforces.com/contest/1828/submission/205878246 , https://codeforces.com/contest/1828/submission/205879339 ). This mail is correct but I have a reason. The other user is my elder brother who seldom does competitive programming, however on that day we both were giving contest. In the midst of the contest my system hanged(it happens often because it's old with 4GB RAM with old mechanical hard disk) however I was still solving the problems and when my code was ready I became excited and submitted it from my brother's system , however later I realized that I had submitted it mistakenly through my brother's account , after which I logged in from my account and submitted the code again.
This is evident from the fact that he uses C++ for coding while I do it in Python 3 , this was the first submission in python through his account.
I agree that it is violation of codeforces policy and I heartfully apologize for doing the same, however it was done unknowingly. I am a young guy and interested in coding and any negative delta would be very painful for me. I had no intention of plagiarism and violating the rules of conduct and I assure you that this was my first and last time of violating the official policy( whether done knowingly or unknowingly). Please forgive me this time , I sincerely apologize for my mistake.
Yes, I also beg for forgiveness for this inadvertent error not done purposefully or with a thought of plagiarism. I promise that same will not be repeated at any cost in future
I got this message from system about code similarity
Your solution 205856289 for the problem 1828B significantly coincides with solutions prathampekamwar/205856289, Shining_M00N/205883173. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
Well, the solution match is not perfect and given the triviality of the problem, this much similarity should be allowed. I don't even know the Shining_MOON user account, the given way I took input is quite similar to the way I always take my inputs. I always use this to take input for different test cases. int t; cin>>t; while(t--) Also, the remaining code is just taking input into an array and then the use of abs function could be seen as coincidence, since there are so many people giving contests. Also we have used different gcd functions, I used gcd while the other user used __gcd, also our variable names differ.
All in all the solution is too trivial and small that it could easily have been a coincidental match. I hope that this won't count as a violation, since there might be some time in future where I might get banned due to coincidence as a repeated violation. I have just searched gcd function on internet and that is different in both codes, so I can't give some proof but this code is so trivial that I don't think that this should be counted as violation.
Thanks to whomever it may concern.
6th place in Div. 2: am I joke to you?
Meanwhile tourist: no me
Unintentionally my solution of NahidRiaj/205884480 is coincidence to solution of riaj_1/205883451 .We are friend and we solved problems after discuss with each other then make solutions and submit them in this round. We were not copied each other code but our codes maximum coincide to each other. We shared our logic to each other. I don't know how our code implementation of this problems were almost same. Please pardon me . I will never do this type of mistake in future . Please don't block my account. Next time I will solve every problem without discussion to anyone. One things that my friend is new in CF community . He wants to learn about coding that's why I discuss logic with him. Next time I will tell him logic after contest.
you cannot discuss problems during contest. move on.
Yeah.It's my fault.And I hope in future I'll concern about it.Thanks for your reply.
I want to address an issue regarding the similarity between my code and that of my friend's in this contest. We both used the same template, which contributed to the resemblance. Additionally, the main code was concise and simple, leading to similar implementations. Plagiarism was never the intention. Below is the main code now anyone can write this code that is just coincidence please roll back my rating if possible.
Attention! Your solution 205846628 for the problem 1828A significantly coincides with solutions daemon_targ/205845714, __Shubham__Jaiswal__/205846628. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
3 people using the same template and submitting the exact same code down to the whitespaces?
Okay now i can understand my fault
Waiting for the editorials……^_^
Problem F is fantastic