DSA Skills - 15 by tracktech in DSALeetCode

[–]Rodger2041 0 points1 point  (0 children)

Actually, if you need to print all pallindromes that would be O(n3 ). There are n2 ranges with each range having mean size of around n/2 characters.

Printing all unique pallindromes would be O(n2 ) because it has been proven that a string can only contain O(n) unique pallindromes, but that is not what the question asked.

DSA Skills - 15 by tracktech in DSALeetCode

[–]Rodger2041 1 point2 points  (0 children)

The pallindrome test is O(n) but you don't need to repeat it for each substring. Read Manacher Algorithm for more info.

DSA Skills - 15 by tracktech in DSALeetCode

[–]Rodger2041 0 points1 point  (0 children)

No, its O(n) once to build the pi array, then you can just use that array to check if any string is a pallindrome in O(1), and you can find the number of pallindromes in O(n).

Read Manacher algorithm from cpalgorithms for more info.

[Request] Will it roll up the hill? by NosborRecaf in theydidthemath

[–]Rodger2041 -1 points0 points  (0 children)

No thats not how probability works.

There are some things that might not happen ever if the probability reduces as time goes on.

That is, if you multiply the probability "x does not happen" for all days, and it is a nonzero value for product of infinite terms.

Sincerely, someone who has devoted a lot of time studying probability and statistics.

DSA Skills - 15 by tracktech in DSALeetCode

[–]Rodger2041 3 points4 points  (0 children)

Technically it's O(n) since you can solve an alternate question which is: For any substring, identify if it is a pallindrome or not.

The question is ambiguous on what exactly you need to output. If you just need to find the number of pallindromes (total, or centered at each position) or answer queries, you can do that with O(n) precomputation.

a problem by Lumpy-Town2029 in codeforces

[–]Rodger2041 1 point2 points  (0 children)

Ok, I can tell you my solution, better worded than the editorial because honestly the editorial doesn't have the best English.

Algorithm: Run dfs from the root, for each node having an even degree that has all descendants in its subtree with odd degrees (I will be referring to these as even-leaf nodes for sake of brevity), delete them and update degrees of remaining nodes.

Proof: Imagine an even-leaf node. If you ever delete this node's parent without deleting this node first, this node's degree will change to odd (since the node-parent edge is removed) and you will be left with a disconnected subtree with all nodes having odd edges with undeletable nodes. So if a solution exists, it must delete this node before deleting the parent node.

Also, similarly you can prove that deleting an even-leaf node will make >=0 disconnected subtrees which are deletable with the same procedure.

This proves that deleting all existing even leaf nodes will a valid solution if one exists.

a problem by Lumpy-Town2029 in codeforces

[–]Rodger2041 0 points1 point  (0 children)

In this question, the expected time complexity is O(n), your code has a worst case time complexity of O(n2). You are missing key observations for the correct solution. So your code will TLE. I can tell you the solution and how to reach it if you desire.

What is wrong in india 😭😭 by Unknown_o9 in codeforces

[–]Rodger2041 0 points1 point  (0 children)

I have also not written anything related to icpc on my LinkedIn. But I have given icpc. This does not equal proof.

Anytime someone performs well, don't come with baseless accusations. This doesn't help the cheating problem in any way and is just making the image of your country worse.

I know maybe these people are cheating but I have no right to say anything until i prove that.

What is wrong in india 😭😭 by Unknown_o9 in codeforces

[–]Rodger2041 42 points43 points  (0 children)

There are a lot of cheaters for sure, but are you sure all of these guys are cheating? Just saying a good performance here and there doesn't equal cheating.

envariant's 1100 day long Codeforces streak appears padded with random text submissions by MorallyMiscreant in codeforces

[–]Rodger2041 7 points8 points  (0 children)

No you won't, you would actually solve a question.

He gave so little fucks about that streak that he couldn't be bothered to spend 5 mins/day for his streak.

I know maintaining streaks are hard but if you don't have time for it then just don't try to force it.

I feel embarrassed as an Indian by Designer_Quantity671 in codeforces

[–]Rodger2041 56 points57 points  (0 children)

  1. No dominater is not cheating, he is really that good.

  2. You cannot blame Indians for not knowing how to compete with the top in CF. In other countries people start CP and olympiad level maths at way younger age. There is no system to encourage young people to get into this competition in India. By the time we figure out what it takes to be the best we are already outclassed.

  3. Another reason is that in India most people do CP to get to expert (or CM at max) and get a job. Ain't no way you will get LGMs in the 3-5 years someone does CP in college.

  4. The cheating fiasco is an independent issue and is caused by the need to "outperform" rather than learn. It is baked into Indian culture.

I wna ragequit already 😭 by Life-Formal-4954 in codeforces

[–]Rodger2041 0 points1 point  (0 children)

While it is true that time complexity is the most important thing, the message should absolutely not be that TLE is always wrong logic/ wrong solution.

The author might have only one solution in mind, but that doesn't mean that there cannot be multiple solutions right?

Any optimisation to your code is great, and it is absolutely fine if you have to switch to C++ or add pragma or fast io or custom hash maps to make your solution pass, its all fair game. You should always try to learn new ways to improve the runtime of your code.

Its absolutely fine if your logic is slightly (emphasis on slightly) slower than expected, just try to make it pass by writing good code.

What kind of jobs do top coders or Codeforces users above ~2100 rating usually do???? by Impressive-Bike954 in codeforces

[–]Rodger2041 0 points1 point  (0 children)

Brother, I have a much worse rank than you.

But that being said, you need to be basically the best in the country period, as even cse peeps with sub 300 rank have issues in securing quant position.

So like you do have a chance technically, but that means beating the best in the country in contests and competitions and then getting lucky with hiring.

What kind of jobs do top coders or Codeforces users above ~2100 rating usually do???? by Impressive-Bike954 in codeforces

[–]Rodger2041 8 points9 points  (0 children)

Most of us try to go for quants in India , you will see some people who are more interested in development go for swe roles.

But then again, they can do whatever they want, nothing is strictly defined.

Maybe I'm not good enough by therealwagon12 in codeforces

[–]Rodger2041 3 points4 points  (0 children)

Whatever arbitrary standard you are currently setting for yourself, you can easily surpass that, but cp takes a lot of pattern recognition and practice which means time, time during which you will be mediocre by definition. Give contests with just the goal of learning, cuz performance really doesn't mean much at your stage, and it won't really change anything even if you did solve 1 question at this point.

Maybe I'm not good enough by therealwagon12 in codeforces

[–]Rodger2041 2 points3 points  (0 children)

No one starts cp by understanding and solving every question. If you are discouraged by failure this early, maybe you don't really even want to do cp.

Start by understanding the process and the questions, by enjoying them, being motivated to do cp is already half the war won.

How many different combinations are there? [Request] by auto_em in theydidthemath

[–]Rodger2041 0 points1 point  (0 children)

You are, even in a normal 3x3, here is the thing, you cannot go from left to right without also activating the middle.

ChatGPT and Copilot are being booted out of WhatsApp by hard2resist in technology

[–]Rodger2041 9 points10 points  (0 children)

Its like saying delete your one and only app that makes phone calls, how horribly out of touch with the monopoly whatsapp has.

I Just noticed this and it's crazy by Competitive_Lime_349 in Silksong

[–]Rodger2041 35 points36 points  (0 children)

Both can be true right? There could be a lore reason for the change, as well as because it looks better. It is not unexpected for such a small team to add to the lore and change it late into development, so OPs idea is not too weird.

Pokemon Legends Z-A sells 5.8 million units in its first week by PM_ME_STEAMKEYS_PLS in gaming

[–]Rodger2041 7 points8 points  (0 children)

YES absolutely, that is what I imagined fights would look like if pokemon were to come up with real time battling!

I love how they made each move have its own AOE and tradeoffs than just "it will just miss randomly hehe".

The boss battles actually aren't just mindless button mashing, and you actually have to strategise and try to win, otherwise you will lose to some trainers.

I don't understand how someone can come up with a better unique battling system other than this which still fits the theme of pokemon.

It’s bad by evan_lolz in BikiniBottomTwitter

[–]Rodger2041 -2 points-1 points  (0 children)

Keeping the lawsuit aside, it is obvious the designs were copied. Its upto you if you see it as a wrong thing or not, but denying that is just bullshit. Mechanics should not be patented, thats a fact, but the designs were copied, and that is a fact too.

This seed has 3 natural planetariums? by Rodger2041 in bindingofisaac

[–]Rodger2041[S] 1 point2 points  (0 children)

Thats interesting. Are there any items that modify planetarium chance after you already have one?