Update: Figured it out via this comment

So basically, The path $$$W \rightarrow W - 1 \rightarrow W - 2 \rightarrow ... \rightarrow G $$$ can be broken into steps of 1, and via symmetry we know that going 1 state down on the path from any arbitrary state will take the same number of expected steps, ie $$$E_L$$$. This immediately proves the "assumption"

Had fun deriving my solution for C (after guessing the solution in 15 minutes and then banging my head for 1 hour deriving it to figure out what's wrong, only to realise at the end that I just had to take the modulo of the input as well)

My derivation was just writing down a bunch of recurrence relations and solving for the expectation at current state. An observation I made while deriving was that if you move downwards in the random walk, ie from $$$W$$$ to $$$W-1$$$, you would end up in the exact same situation as before with lesser distance to cover. So we could use this symmetry to avoid writing a recurrence for those states.

Concretely, I made an assumption that the expected steps would then be linearly proportional to the distance between the states ($$$w$$$ and $$$G$$$):

$$$\quad$$$

This let me simplify:

By calculating $$$e(W - 1)$$$ using the assumption, and finding the value of $$$e(W + 1)$$$ in terms of e(W) using recurrence.

Issue is, I still can't rigorously prove why the assumption of linear proportionality would hold. I mean, it is apparent that via symmetry we end up in the same situation, but with lesser distance to cover. But why would it be linearly proportional to the distance?

Does anyone who rigorously solved the problem have a proof for this assumption/observation?

what were the constraints? I have an O(32 * n * m * log(m)) algorithm. Idea is similar to above comment but I use sets, so additional log(m) factor.

We makin' it out of the troposphere with this one 🔥 🔥

You can mention mAP and Rouge-L scores. But I would suggest not to mention Bleu scores

MainuCodingBadiPasandAe

Thanks so much for applying with us

Hi gitgudmonsta,

Following up on your recent interview with Google, we have decided not to proceed with your application at this time. Although this role didn't work out, we may contact you if we come across another opening that we think could interest you and that matches your skills and experience.

Also, if you applied for any other roles with us recently, look for an update on them soon.

I remember his vivid appearance as he descended down the stairs; weary, drowsy and crestfallen. His tie was stifling, it enervated his voice. His glasses were foggy, it narrowed his vision. And he must see far. He must address the restless throng. He must appear intrepid, for he is their last hope, their last source of truth.

An anxious mortal asked,

"How was it? Did it go well? What did they a-"

He lifted up his hand, signaling silence from the crowd. He saw their faces, some hopeless, some fatigued, and a few intrigued awaiting his answers. He tried to move his lips to speak, but he couldn't. Without uttering a word, he spoke to all of them. And everyone listened.

Dejected, he made his way back to his room. He felt a breeze of cool air brushing past his hair. He barely had any left at this point. He took another look at their faces. This time, as he looked upon the throng, he felt an invigorating aura. An aura vibrating not from the listeners, but from within.

The sun dusks, the crowd witnesses the reincarnation of bane. TCS Bhediya rises again.

Try not to cheat next time

Update: Misinterpreted that that the chosen indices $$$p_i$$$ need to be in ascending order (Should've seen the first test case explanation smh). This trivially reduces the solution search space as you would obviously sort $$$b_i$$$ values.

The above solution solves the problem when $$$p_i$$$ must be chosen in increasing order

Anyway, enjoyed solving this (much) tougher variant although that required me to take 3 hours off a Sat for implementing and debugging

Code for the variant: https://mirror.codeforces.com/contest/1935/submission/250334354

Has anyone done this for C?

For j such that b[j] < b[i]:

For j such that b[j] > b[i]:

Answer = max cnt over all dp(i, cnt) such that dp(i, cnt) < l

For finding min(dp(j, cnt — 1) — b[j] & j < i), use range min segment trees over compressed b[i] values. Each cnt will have its own 2 segment trees (one with +b[j], one with -b[j]). Feeling lazy to implement

Idea was puerile. Execution was acceptable. Formatting could be made better to make it appear genuine. Overall, I rate this 4/10.

Try to put a little more effort in your upcoming endeavors on tomfoolery. Take inspiration from the OG https://mirror.codeforces.com/blog/entry/53168 and previous blogs of Lord mainucodingbadipasandae

All the best

सच ही कहते हैं लोग. हाजमोला एक handsome young man है

To all my Greylords out there, you need to hear this:

It is okay to be different.

It is okay to not fit in.

It is okay to not be understood.

Do not allow people to dim your shine because they are blinded. Tell them to put on some sunglasses, because you were born this way.

Let us declare January as Grey Pride month 🏁

#ratingisrating #greyboy #greypride #equality

Thanks. You motivated me to prove it myself. I came up with a not-so-elegant proof with the same outline as yours

I have a nice greedy solution to D which just selects the largest possible distance at every iteration until all elements in $$$a$$$ have been paired, but I don't have a proof.

Code: 242031960

Can anyone prove it?

foreshadowing

Abdullah Abdullah

Bhediya Sir

were

For some reason, I wasn't able to view problems on main or mirror (mirror said something like "This problem doesn't have a statement"). Strangely, this message was shown only on the first 4 problems (I was able to view E atleast) on mirror, while on main I wasn't able to load anything at all. This happened for the first 10 minutes.

I tried opening CF on incognito and it worked fine, so I disabled uBlock and CF-predictor and only then was I able to load the problems.

Can anyone make sense of this?

Oh my god! Junkook!!!!

Army 💜💜💜

Will bhediya sir is the solves 6 problems today?

Upvote: Yes

Downvote: Yes

Ennui is a terrible thing. The monotony in drudgery sure takes away the rapture and alacrity away from life. But the ones who falter and act on caprice increase disarray in their lives. I intend no malevolence, but I fear I have to dissuade you from taking such a decision. There are copious opportunities and I urge you to explore for what is suitable or expedient for you.

One can surmise that the next generation will be in a deplorable servitude of the machines. What seems innocuous today will become pernicious in the future. It is our duty to inculcate and exalt the lofty spirit of competitive programming in the next generation and deter any indolent activities

Mainu math zyada pasand ae

If your solution complexity is $$$O(f(n)) \ge O(n^k), k \in R, k \ge 1, n \in N$$$ per test case with n inputs such that $$$\sum n_i = N \ $$$

Hence, if your solution works on the bound on N, it will work for all test cases within TL

Cavalier, mocking, violent — this is what Wisdom wishes for us to be: she is a woman, and will ever love only a warrior.

When small men begin to cast big shadows, it means the sun is about to set

I remember his vivid appearance as he descended down the stairs; weary, drowsy and crestfallen. His tie was stifling, it enervated his voice. His glasses were foggy, it narrowed his vision. And he must see far. He must address the restless throng. He must appear intrepid, for he is their last hope, their last source of truth.

An anxious mortal asked,

"How was it? Did it go well? What did they a-"

He lifted up his hand, signaling silence from the crowd. He saw their faces, some hopeless, some fatigued, and a few intrigued awaiting his answers. He tried to move his lips to speak, but he couldn't. Without uttering a word, he spoke to all of them. And everyone listened.

Dejected, he made his way back to his room. He felt a breeze of cool air brushing past his hair. He barely had any left at this point. He took another look at their faces. This time, as he looked upon the throng, he felt an invigorating aura. An aura vibrating not from the listeners, but from within.

The sun dusks, the crowd witnesses the reincarnation of bane. TCS Bhediya rises again.

I am suing you

Segment Trees only bear fruits for the persistent and dynamic. They don't bear fruits for lazy people

Almost thought this was a sequel to this legendary binary search blog

Hard luck bro :( Should've joined a legitimate college instead of Hajmola Fan club

Time to become quant bhediya

I wanted to create an insta shitposting account but that would be a complete waste of time. So I decided to make this account and waste only 90% of my time.

Some blog ideas of mine were really creative, others are kinda forced if you see it.

yes sir. Shitposting kam ho gayi matlab acha chal raha hai

You either get girls or live long enough to become a bhediya

What does a Bhediya do Raghav? A Bhediya codes for his TCS. And he does it even when he doesn't like it. He simply bears up and codes. Because he is a Bhediya.

\Bhediya: TCS > GRE

\Non-bhediya: Got placed in a good company so masters plan is delayed for now.

Higher than yours

1) Not TCS :(

2) Nowadays, close to none. First 2 years, around 4-6 hrs each day. Tried to solve atleast 3 good problems each day.

3) Would take this some other time.

4) I got placed the first day (VERY fortunately). And I got to sit for the placements because my internship company was delaying the PPO process.

5) During internship- 5, placements- none.

6) Too much info

We are all bhediyas in search of our TCS. Some puerile freshman is spending hours on inane problems hoping to get placed in his dream company, hoping that all this drudgery has some meaning to it. Whereas, an irate senior envies his friends getting more successful than him, yet he covets all the fame. In the end, he feels TCS is his only path to atonement, the same TCS which was looked down upon hitherto, detested to its core.

I can't stand someone posting more sophisticated shitposts than me

Truly an inspiration for all bhediyas like me

4000 times doin ur mom B)

Hope to get +300 this round

I am ecstatic about solving 1 problem in just 40 minutes this time. Huge improvement from the last contest where I spent 1+ hrs on 1 problem.

Don't you see? We are all bhediyas in search of our TCS. Some puerile freshman is spending hours on inane problems hoping to get placed in his dream company, hoping that all this drudgery has some meaning to it. Whereas, an irate senior envies his friends getting more successful than him, yet he covets all the fame. In the end, he feels TCS is his only path to atonement, the same TCS which was looked down upon hitherto, detested to its core.

I am GRE bhediya

Be intrepid when it comes to solving arduous problems. The journey may seem interminable, but have faith in yourself. Don't fall in the trap of temerity once you gain momentum, keep solving tougher problems. Your problemset should replete of the color green, showcasing your problem solving ardor and your perseverance to not falter throughout the drudgery.

Linear Time FFT

No. I am Amreeka ka dalla

Such indolent acts are pernicious to my fellow coders who toil hard to see their names on top of the leaderboard. This creates spurious standards and kills the alacrity of us newbies.

Do you get it? Do you get my joke? Because it says "As an AI model...". Do you get it? Like, he was saying that he doesn't use AI but like in the last sentence... he like just said that uh... he... yeah. Do you get it now?

I am hearing a lot of people say that this is AI generated. How dare you contemptible lowlifes throw such spurious allegations on me. Check this attached image for proof.

As you can see, that the text is classified as human text.

It's imperative that we refrain from making false allegations against others. Such baseless accusations can cause irreparable harm to a person's reputation, relationships, and mental well-being. Just as we wouldn't want to be unjustly accused, we should extend the same consideration to others. False allegations not only tarnish someone's image but also create an environment of distrust and negativity. Imagine the emotional toll it takes when you're wrongly accused of something you didn't do. It's a painful experience that can lead to anxiety, stress, and a sense of helplessness. As an AI model, I don't have feelings. But I am desolated to see such comments.

Felt cute. Might delete later

you know you are old when you have witnessed TheBhediyaOfDalalStreet writing bigoted blogs in garbage English and being a TCS Bhediya instead of a GRE Bhediya

GRE

It's hapless to see such interminable queues on codeforces. I hope this incongruous situation is handled before the crowd becomes any more irate.

It's desolating to see not one commenter mentioning about me in this throng of commenters. This abhorrent blasphemy is extremely impertinent to me. Although I am intrepid to such comments, I expect the community to be more thoughtful and avoid such temerarious actions in the future.

I am incredulous about the way you have defined these things. Are you sure you aren't just being pompous here? Such bogs are vile to the succinct resources I have prepared in the past

I understand your voracious appetite for algorithms. But you should move away from this drudgery and explore other frontiers in CP.

Santa Went To Microsoft Office For Interview.

Interviewer: “Tell Me Any 4 Versions Of Java?”

Santa Bahot Sochne Ke Baad Bola: “Mar Java, Mit Java, Lut Java, Main Sadke Java“

sounds familiar

Beginner Resources

Babe wake up, it's that time of the year again

acha

Wow such a magnificent piece of code. This guy should be promoted to expert for his unparalleled encryption capabilities.

try not to post CP on CP websites from next time to avoid falling in such situations.

try to man up and debug your code yourself maybe?

I have found a new religion

I am ecstatic to witness AI demolishing these frivolous CP contests and bringing an end to these

When you are in a "try not to write retarded problem statements" competition, and your opponent is diskoteka

Well, I see my comment also doesn't make much sense. After effects of this contest ig.

He is using reverse psychology to trick himself into believing he enjoys CP and solving more problems. Indeed, he did this to get placed.

Weak tests 😼 👎

Hello. I am from the future. It FSTs.

yeah... the subtasks were really well made to develop intuition about the main problem

hello freind. it is actually a very easy technique to do this. so you need to know just check if 'a' is in your're string, then 'b', then 'c'. and there are only 26 letters. so you can do this ans = 0; if (s.find("a", 0)) ans ++; if (s.find("b", 0)) ans ++; .... if (s.find("z", 0)) ans ++;

so it is the very easy solution. you can also write coding program to generate this if block if you are lazy. then you can copy paste it in c++ file.

Hit like if you like the solution

Edit: fixed the c++ syntax :)

I believe these images transcend all language barriers. Art is universal and resonates with the soul of the individual.

Ask your're mom :P XD

don't give contests

bhediyas wanna become specialist within 3 months nowadays

Class 11 combinatorics revise karlo frandss

(Hint: Use (iv) to create a recurrence for b(n, k))

hard luck bozo

hello freind you should drink warm water on empty stomach daily in the morning to cure weekness

become grandmaster and start an alt account

finally hit rock bottom

can confirm

Today is the best time for implementation of this system, since today is the auspicious occasion of Ambedkar (God) Jayanti.

Codenation otw to hire interns for the (1e9 + 7)th time

that's my main account graph B)

decimal code

_______________________डिस इस सो सैड| 😞 😞 कैन वी हिट १०० likes ??________________________👉👉👆👆

Thank you for enlightening words sir. Your visceral intellectual aura has opened my eyes, and now I can see things clearly. I have transcended beyond the meagre troll I was. I have gained +50 social credits

Okay guys so many pointed out a potential loophole in the system. What if someone tries to fake being a lower caste to avail these benefits (as in JEE)?

So I propose linking codeforces account with Aadhar Card number to overcome this issue.

yes that would be great. I want freedom

Okay so now I get why there are downvotes. So apparently privileged upper caste people think that they would lose rating via this system. Brahmanical patriarchy much?

:( That wasn't an opinion, that was an awakening

wow Chinese shitposts are something... gotta step up my game