reflecting on why i suck at algorithms

27 Nov 2022 stream-of-consciousness competitive-programming

kaguya sama in moron mode pointing out a segfault

https://en.m.wikipedia.org/wiki/Trout_tickling

In the news

大阪府の18歳以下全員に米10キロを配布へ　他の食料品も選択可
 https://www.theguardian.com/business/2022/nov/29/alibaba-founder-jack-ma-hiding-out-in-tokyo-reports-say

Alibaba founder Jack Ma living in Tokyo since China’s tech crackdown (paywalled)

The Toad is dead.

P/ECE, a Japanese handheld cum PDA. The grandaddy of the Playdate.

https://aquaplus.jp/piece/spec.html

insanity is doing the same thing over etc.

i've decided to try using anki for competitive programming / leetcode / math / etc.

i consider myself to be smack in the middle of the pack when it comes to pattern-matching.

i can solve CF 1600-1700 level / AtCoder Beginner Contest D DP problems if they're framed a particular way.

as some folks point out:

https://senrigan.io/blog/chasing-10x-leveraging-a-poor-memory-in-software-engineering/

I wanted to be a good, hell, great software engineer. But my work was mediocre. Even worse, I was trying. My ass was in that chair twelve hours a day, six days a week trying to write beautiful Python code. I was constantly looking up documentation and sucked into the internet's rabbit-hole of distractions. I was a try-hard failure.

https://sive.rs/srs

I’m an intermediate programmer. I didn’t go to school for it. I just learned by necessity because I started a website that just kept growing and growing, and I couldn’t afford to hire a programmer, so I picked up a few books on PHP, SQL, Linux, and Apache, learned just enough to make it work, then used that little knowledge for years.

But later, when I worked along side a real programmer, I was blown away by his vocabulary! All of these commands and functions just flowing effortlessly out of his fingers. We were using the same language, but he had memorized so much of it, that I felt like a child next to a university professor. I really wanted to get that kind of fluency.

It made me think about how much I’ve learned then immediately forgotten, over the years. I read books or articles about some useful feature, try it once, but then I get distracted, forget about it, and go about my normal way of doing things.

I wanted to deeply memorize the commands and techniques of the language, and not forget them, so that they stay at the forefront of my mind whenever I need them.

i often see people debating the value of rote memorization versus conceptual understanding and i suppose it's a case of por que no los dos?

for instance, there are people who spend half, or even most of their lives in another country and speak with imperfect grammar because there's no real impetus to perfect their grammar if they're already 80-90% of the way there and can eke out a living and make themselves understood

comp. prog. is fundamentally different, however, since you have "banks of knowledge" on various different levels, and your recall must be 100% accurate to AC a given question. just regurgitating, say, BFS or DFS will not teach you how to keep track of visited nodes and prune the search tree. And even then, there are a ton of microdecisions you have to make; if, say, log(nodes you can visit) fits into an unsigned int; then perhaps it's time to use a bitset to keep track of the subset of nodes you've already visited. And you better remember how binary arithmetic works, so you can test if you're visited all the nodes!

so i feel like spaced repetition can, at the very least, reinforce these habits of quickly narrowing down the "approach space".

to put it another way, i feel like my fluid iq is decent enough / not the bottleneck because there are multiple instances where i've modified somewhat tricky algorithms despite only having seen it before < 10 times, in the middle of a contest (e.g. Rabin Karp.)

what frustrates me the most is when i see problems like these and i bark up the entirely wrong tree or i had no chance of getting the solution in the first place.

https://leetcode.com/contest/weekly-contest-318/problems/minimum-total-distance-traveled/

The constraints are small, less than 100 robots and factories.
i supposed bruteforce would work.
the "statefulness" of everything misled me, because they framed it as "a factory can only repair n robots, and once you set a robot in motion, it cannot stop", etc.
i went off the wrong track and wondered if it could be some sort of binary search on the total distance moved, thus a greedy problem
i would have thought about DP if they framed it as "you have to decide which factory, any given robot is going to be assigned to"
i'd still have gone wrong because it never occurred to me that the 3rd dimension to memoize would have been the remaining capacity (or number of robots already assigned to that factory), i.e. (robot_i, factory_j, k)

as you can see, i've ventured well into "i don't know what i don't know" territory. i guess the only thing left to do is to improve my crystallized intelligence...

my personal goal is to become orange in codeforces. i don't know if i will, but i really do hope i get there some day...

navelgazing

i don't go around saying this irl, but i didn't have a rigorous education. like at all. i've neeted for 6-7 years in total. i got into a very mediocre school by the skin of my teeth and pure luck, not a literal diploma mill, but, i do not recall having ever written a proof even once

... aside from that one DSA class with this question where a sequence was given and i had to prove that that it was O(n^3); i threw everything i knew about induction and stuff out the window, and i managed to express the sequence in such a way that it was a sum_i=1^n( a degree 2 polynomial ), and for good measure i wrote some nonsense about the famous 1 + 2 + 3 + ... + n makes a triangle which is half the area of n^2, so this applies in 3D too...

i got a 92% on that test.

the professor was rumored to be strict, having earned his chops from one of the Universités, but by his grace he gave me very decent marks whenever i managed to demonstrate, in competitive programming terms, having grokked the problem instead of cheesing it, even if the implementation was wonky. to avoid favoritism he did a few name-blind assignments and he later confided in me that he could usually guess which assignment was mine (maybe because of the formatting, kek) and wouldn't mind if i did, say, enumerating subsets with bitmasks instead of backtracking if that day's topic was recursion "because you seem to already know recursion whenever you talk about recurrence relations in class, so keep that in mind"

if my assumption is correct, he was equally lenient towards 2 other students. both of who went on to make it in 'murica. and honestly, i should hurry up and make it, before he kicks the bucket.

i've never done calc, linalg or even upper high school level combinatorics in a formal setting, not even the binomial theorem.

heapsort was theorized about, but not implemented. Dijkstra and A* search were worked through by hand, but not implemented. divide and conquer was briefly covered, but there was absolutely no mention of dynamic programming. such was the state of how watered down it was.

my progression and current contest rating appears to be roughly in line with https://leetcode.com/lichuan199010/

she has solved well over 1600 problems and learns by categorizing them in greater detail.

To gain the most out of practice, I believe the key is to compare and contrast.

Some of the questions I can remember very well. Some of them I do not. I think the key is to practice on the best questions. I wrote LRU, Calculator III, and skyline at least 5-6 times at different time points because they are very generalizable to help solving other questions, and are examples of how to solve hard questions. Good luck! I heard what you said, and I also forget about some questions. After a few months, some questions looks brandnew to me.

https://codeforces.com/blog/entry/23054?#comment-295186

I solved 1000+ problem there (on POJ) about 5 years ago

people with math degrees obliterate the competition once they get the hang of the language.

https://codeforces.com/profile/kclee2172
https://leetcode.com/kcsquared/
https://flykiller.github.io/codeforces problems/

alright, that's enough navelgazing.

tougenkyou

reflecting on why i suck at algorithms

In the news

insanity is doing the same thing over etc.

navelgazing

links

reflecting on why i suck at algorithms

In the news #

insanity is doing the same thing over etc. #

navelgazing #

links #

In the news

insanity is doing the same thing over etc.

navelgazing

links