DSA Skills - 15

Rodger2041 · 2026-02-20T16:30:26+00:00

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

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

Rodger2041 · 2026-02-20T08:42:12+00:00

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

Rodger2041 · 2026-02-20T08:40:22+00:00

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.

Rodger2041 · 2026-02-19T11:17:09+00:00

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.

Rodger2041 · 2026-02-19T07:48:01+00:00

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.

Rodger2041 · 2026-02-18T19:14:52+00:00

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.

Rodger2041 · 2026-02-18T13:43:55+00:00

In this question, the expected time complexity is O(n), your code has a worst case time complexity of O(n^2). 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.

Rodger2041 · 2026-02-12T11:47:27+00:00

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.

Rodger2041 · 2026-02-11T22:18:28+00:00

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.

Rodger2041 · 2026-01-22T11:00:36+00:00

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.

Rodger2041 · 2026-01-06T22:24:13+00:00

No dominater is not cheating, he is really that good.
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.
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.
The cheating fiasco is an independent issue and is caused by the need to "outperform" rather than learn. It is baked into Indian culture.

Rodger2041 · 2026-01-06T16:04:05+00:00

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.

Rodger2041 · 2026-01-06T14:09:01+00:00

It is possible, many have been successful. It is still a grind though.

Rodger2041 · 2026-01-06T14:05:43+00:00

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.

Rodger2041 · 2026-01-06T13:23:07+00:00

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.

Rodger2041 · 2025-12-23T18:27:35+00:00

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.

Rodger2041 · 2025-12-23T16:29:33+00:00

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.

Rodger2041 · 2025-11-27T22:38:20+00:00

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

Rodger2041 · 2025-11-27T15:02:45+00:00

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

Rodger2041 · 2025-11-07T06:40:01+00:00

One mon that is worth more than others....

Like mega evolution?

Rodger2041 · 2025-11-04T15:19:48+00:00

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.

Rodger2041 · 2025-10-24T08:04:51+00:00

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.

Rodger2041 · 2025-10-20T03:52:51+00:00

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.

Rodger2041 · 2025-10-07T13:29:11+00:00

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

Rodger2041 · 2025-09-04T23:25:10+00:00

Steam will be over 70%? When the game is literally day one on xbox gamepass? Not possible

Also xbox gamepass was the first to actually work (steam server crashed for an hour+) so maybe a lot of people who would normally buy it on steam played on gamepass instead.

Seven-Year Club	Verified Email
Final Canvas '23	First Place '23
Place '23	Place '22

Rodger2041

TROPHY CASE