Mike4235's blog

By Mike4235, 3 years ago, In English

Hello, Codeforces!

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:

Scoring distribution:

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
1 ksun48 exxqfu
2 jiangly KanaArima
3 gyh20 BERNARB.01
4 maroonrk until3am
5 Um_nik FCAI-CU
tourist

Also congratulations to ksun48 and Golovanov399 on (re)gaining the Legendary Grandmaster title!

UPD: Editorial

  • Vote: I like it
  • +439
  • Vote: I do not like it

| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

As a blue tester, the best contest I have ever seen!

Wishing everyone a positive delta.

»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

hi

»
3 years ago, hide # |
 
Vote: I like it -33 Vote: I do not like it

As a tester, I think this round is great

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

henlo

»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

omg Vietnamese contest!

»
3 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

bachdrip

»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

da. god

»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

Who is Mike4235?

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +134 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +36 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it -22 Vote: I do not like it

        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.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      void solve() {
          string name="thenymphsofdelphi";
          string heorshe="he/she";
          name=" "+name;
          cout<<"Since"<<name<<" is the paragon of human virtue without equal past or present, "<<heorshe<<" is most resplendent in love, tributes and accolades. Waking or sleeping, I must not forget"<<name<<"’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"<<name<<"? For the blind, "<<heorshe<<" is their vision. For the deaf, "<<heorshe<<" is their music. For the mute, "<<heorshe<<" is their voice. For the anosmic, "<<heorshe<<" is their aroma. For the numb, "<<heorshe<<" is their feeling. For the atrophied, "<<heorshe<<" is their muscle. For the starved, "<<heorshe<<" is their sustenance. For the thirsty, "<<heorshe<<" is their water. For the exhausted, "<<heorshe<<" is their energy. For the depressed, "<<heorshe<<" is their happiness. For the disillusioned, "<<heorshe<<" is their hope. For the pessimistic, "<<heorshe<<" is their optimism. For the disadvantaged, "<<heorshe<<" is their champion. For the marginalized, "<<heorshe<<" is their justice. For the oppressed, "<<heorshe<<" is their salvation. For the righteous, "<<heorshe<<" is their symbol. For the enlightened, "<<heorshe<<" is their muse. For the erudite, "<<heorshe<<" is their education. If"<<name<<" speaks, I listen. If"<<name<<" questions, I answer. If"<<name<<" orders, I obey. If"<<name<<" opines, I agree. If"<<name<<" fears, I assure. If"<<name<<" hopes, I dream. If"<<name<<" is happy, I am jubilant. If"<<name<<" is angry, I am apoplectic. If"<<name<<" is sad, I am disconsolate."<<name<<" is my ideal,"<<name<<" is my romance,"<<name<<" is my passion."<<name<<" is my strength,"<<name<<" is my compass,"<<name<<" is my destination."<<name<<" is my language,"<<name<<" is my culture,"<<name<<" is my religion."<<name<<" is my ocean,"<<name<<" is my mountain,"<<name<<" is my sky,"<<name<<" is my air,"<<name<<" is my sun,"<<name<<" is my moon,"<<name<<" is my world."<<name<<" is history,"<<name<<" is present,"<<name<<" is future. If"<<name<<" has a million fans, I am one of them. If"<<name<<" has a thousand fans, I am one of them. If"<<name<<" has a hundred fans, I am one of them. If"<<name<<" has ten fans, I am one of them. If"<<name<<" has only one fan, that is me. If"<<name<<" has no fans, I no longer exist. If the whole universe is for"<<name<<", then I am for the whole universe. If the whole universe is against"<<name<<", then I am against the whole universe. I will love, cherish, and protect"<<name<<" until my very last breath; my successors will love, cherish and protect"<<name<<" until their very last breath."<<endl;
      //take if anyone need ╰(*´︶`*)╯
      }   
      
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

free rating

»
3 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

I hope that the authors have prepared a well-written editorial

»
3 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

as a tester fan, how so orz shiv_codegen ?

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +16 Vote: I do not like it

Div. 1, Div. 2
Div. 1 & 2

»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

As a tester, I regret having tested this round. It's so good that I half-wished I had chosen to participate officially.

»
3 years ago, hide # |
 
Vote: I like it +29 Vote: I do not like it

Damn, div 0?

»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

It is sad that not a single tester have cat in his/her avatar ⚫⁔⚫.

»
3 years ago, hide # |
Rev. 3  
Vote: I like it +72 Vote: I do not like it

When an anti-Codeforces writer writes a Codeforces Round

»
3 years ago, hide # |
Rev. 3  
Vote: I like it +1 Vote: I do not like it
»
3 years ago, hide # |
 
Vote: I like it -11 Vote: I do not like it

The Scoring Distribution of Div2 seems perfect!

All the best, everyone for the round. Hope you get delta +

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Mike4235 I am really motivated to see your consistency.I noticed your graph, you have worked hard to come up from the very beginning.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

ABCD1 gang?

»
3 years ago, hide # |
Rev. 3  
Vote: I like it 0 Vote: I do not like it

?

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Would D1 be too easy? It supposed to be 1500-1600?

»
3 years ago, hide # |
Rev. 2  
Vote: I like it -36 Vote: I do not like it

this is gonna be my first contest! wahoo!

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

this is gonna be my first contest! wahoo!

»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Is the score distribution related to the difficulty rating of the problems?

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

My first div 0 , so exited )

»
3 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

era of Div. 0 rounds?

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

thx for that cool round)

»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

speedforces

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +25 Vote: I do not like it

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...

»
3 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +19 Vote: I do not like it

    MikeMirzayanov Please look into this matter. Really frustrating as these types of server error almost doubles the rank during initial period of contest.

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +6 Vote: I do not like it

    same thing happened with me. After submitting for problem B, site became unresponsive and my submission was not showing in the mirror site

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +7 Vote: I do not like it

    It seems that the solution to this problem is very simple: ignore exactly the same submits by the testing system

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +22 Vote: I do not like it

      All solutions mentioned here are actually different (probably equivalent but the files are not equal). For submissions of i_pranavmehta 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.

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        Rev. 2  
        Vote: I like it 0 Vote: I do not like 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.

        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it +5 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
            Rev. 2  
            Vote: I like it +19 Vote: I do not like it

            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

          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
             
            Vote: I like it +17 Vote: I do not like it

            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.

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        Rev. 2  
        Vote: I like it +1 Vote: I do not like it

        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!

        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
             
            Vote: I like it +1 Vote: I do not like it

            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.

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Speedforces

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

whooo ! what's problem D ??? Any hint plzz ?

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, hide # |
 
Vote: I like it +36 Vote: I do not like it

Why cant we have a balanced problemset?

»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

How to optimize in D1B2?

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    hi Adi bhai ( @ adityagamer )

    If you explain me D1B1, I will explain you D1B2 :P

    • »
      »
      »
      3 years ago, hide # ^ |
      Rev. 2  
      Vote: I like it +1 Vote: I do not like it

      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

»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

for the 2nd time in CF, got WA because I forgot to MOD THE ANSWER... feeling very angry on myself..

»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

woohoo div0.5 round

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Could anyone please tell me what i am doing wrong in D1 div2?

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

Again D is way too difficult than C.

»
3 years ago, hide # |
 
Vote: I like it +36 Vote: I do not like it

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

»
3 years ago, hide # |
Rev. 3  
Vote: I like it 0 Vote: I do not like it

how to solve div2 c?

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    Sort both the arrays. If at any $$$i$$$, $$$a_i \lt = 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$$$.

»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it -7 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +15 Vote: I do not like it

      I did consider that and I couldn't solve it :/

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        Rev. 2  
        Vote: I like it 0 Vote: I do not like 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

»
3 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/contest/1828/submission/205901157

Can somebody help me in Div 2 C? My solution didn't pass pretest 3. (I hope my logic is correct) .

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    You should take mod inside the last loop itself, otherwise the answer may overflow.

    final = (final*ans [i])%MOD

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +11 Vote: I do not like it

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.

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it +22 Vote: I do not like it

    $$$D2$$$ can also be solved using stack. For every index $$$i$$$ you need to find no of pairs $$$(j,k) j \lt i \lt k $$$ such that $$$max [j,i] \lt min [i+1,k] $$$. Can be solved using monotonic stack. (No need for seg tree)

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +25 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it +32 Vote: I do not like it

        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 $$$ \gt 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$$$.

        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          You actually don't need a monotonic stack, you can simply add considered positions in a different set, similarly to unconsidered ones.

          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
             
            Vote: I like it +10 Vote: I do not like it

            Thanks!! Wow, I got your reply! I'm a big fan of your video editorials. They are really informative! Keep up the good work :)

        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          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).

      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        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)

»
3 years ago, hide # |
Rev. 3  
Vote: I like it +34 Vote: I do not like it

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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +18 Vote: I do not like it

    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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Good contest, normal i can only solve Div2 A and B but in this contest i can solve C

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +2 Vote: I do not like it

    Well, for the same reason it's bad : )

    Have never seen 6K+ accepted in D2C myself

»
3 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

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 ****

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

why is the time limit 1 second for d1b2 i TLE with concise n log n solution because i used sets

»
3 years ago, hide # |
 
Vote: I like it +43 Vote: I do not like it

Loved the contest so much! Every problem was so pleasant to solve, and most importantly — no math :)

»
3 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

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.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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?

»
3 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

why is this submission stuck in 'running'?

»
3 years ago, hide # |
Rev. 4  
Vote: I like it 0 Vote: I do not like it

problem C: (DIV 2) Test Case 1: Why the answer is 32 ? Why not factorial 6 * 32 ??

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    can you elaborate on why 6 factorial should come?

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

»
3 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

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 :(

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +25 Vote: I do not like it

    That's why easier and harder versions is bad

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    I thought D was simpler than both :)

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    B2 was pretty hard for B, yeah.

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    B was simple imo.

    • »
      »
      »
      3 years ago, hide # ^ |
      Rev. 2  
      Vote: I like it +12 Vote: I do not like it

      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)

      • »
        »
        »
        »
        3 years ago, hide # ^ |
        Rev. 2  
        Vote: I like it +1 Vote: I do not like it

        I mean it's solution is very simple. At least mine: simple binsearch with sparse table

        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it +2 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
             
            Vote: I like it +1 Vote: I do not like it

            Ok i understand your point. I could solve it in contest tho

          • »
            »
            »
            »
            »
            »
            3 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it

            How did you solve it?

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, hide # ^ |
               
              Vote: I like it +1 Vote: I do not like 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, hide # ^ |
                 
                Vote: I like it 0 Vote: I do not like it

                Nice solution!

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, hide # ^ |
                Rev. 2  
                Vote: I like it 0 Vote: I do not like it

                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).

»
3 years ago, hide # |
Rev. 2  
Vote: I like it +6 Vote: I do not like it

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.

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    True, I got TLE on system testing on test case 9 :(

  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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://mirror.codeforces.com/blog/entry/113785

    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +19 Vote: I do not like it

      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.

»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Sortforces

»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

D1 got TLE on systests for O(n^2 log n) solution in Python.

75th -> 1393rd

Ouch

»
3 years ago, hide # |
Rev. 2  
Vote: I like it 0 Vote: I do not like it

..

»
3 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

Finally CM after 3 years. Love CP

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In D1B:

why the answer is 6 in this case?

4 2 1 4 3

  • »
    »
    3 years ago, hide # ^ |
    Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 **

»
3 years ago, hide # |
Rev. 13  
Vote: I like it +50 Vote: I do not like it

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.

»
3 years ago, hide # |
 
Vote: I like it +145 Vote: I do not like it

Give me my +1 rating point, please.

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I solved one more problem than before, but I only gained a few points. I suspect this round was a Div. 3.

»
3 years ago, hide # |
 
Vote: I like it +47 Vote: I do not like it

Also congratulations to ksun48 and Golovanov399 on (re)gaining the Legendary Grandmaster title!

Thank you!

»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

My O(n²logn) in D1 works in 1201 ms in gym https://mirror.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

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
»
3 years ago, hide # |
Rev. 2  
Vote: I like it +41 Vote: I do not like it

Hello, here is a video tutorial/editorial with solutions to these problems: D2B, D2C/D1A, D2D1/D1B1, D2D2/D1B2, D2E/D1C:

https://youtube.com/watch?v=VwY7QzStMk4

»
3 years ago, hide # |
Rev. 2  
Vote: I like it -8 Vote: I do not like it

thanks

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I got this message from system about code similarity

Attention!

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://mirror.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.

»
3 years ago, hide # |
Rev. 11  
Vote: I like it +29 Vote: I do not like it

6th place in Div. 2: am I joke to you?

»
3 years ago, hide # |
Rev. 2  
Vote: I like it -26 Vote: I do not like it

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.

»
3 years ago, hide # |
Rev. 6  
Vote: I like it 0 Vote: I do not like it

Mike4235 MikeMirzayanov

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.

//////////////
int n;
cin >> n;
loop(i,1,n){ 
  print_(2*i); 
}
newL;
/////////////

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://mirror.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 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Waiting for the editorials……^_^

»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem F is fantastic