Hello as title, any math topic suggestions that have few resources on, and are not too hard (i.e. it's explainable in one blog, perhaps with high-school maths knowledge)? IMO my previous blogs on maths (lagrange interpolation and linear modulo inversions) are pretty pog and received decent feedback, and I think (not to boast or anything) I am a good explainer? So I want to contribute with my grade 10 maths knowledge and also practice my english and writing skills in general.
It's free too for the lazy people out there, so you save your time and get your credit while I get my contribution points. Win-win condition (win for the cf readers too).
tldr please read blog title and reply thx
I would really like a rigorous explanation of the Nim-grundy numbers. I have not studied that topic precisely because there isn't a rigorous source. So if you can write up an article with proofs for everything (I mean everything in game theory which is used in CP), I would like that.
Ah fuck I knew it.
Sure, it might take a while as I go through my notes while redoing Project Euler once again (essentially) :) but probably doable.
Thanks for the suggestion!
I wrote a blog talking about Nim and Grundy numbers here: https://mirror.codeforces.com/blog/entry/66040
I intend to maintain this blog and keep improving its quality over the years, so if there's anything you find lacking, I would love to be able to address it.
Oops, but you can see that I already commented my concerns on your blog some months ago.
After several replies, I thought that you were missing my point, and that you had no idea what I was trying to ask.
So I would like grhkm here to try and post a more proof-based treatment of the topic. In fact, this topic seemed so hand-wavy to me that it gave me PTSD and also I am scared of any game-theory problem now, thinking Oh no, what if it is that unrigorous Sprague-Grundy theorem now. Game problems were in the past one of my favorite topics so I would like grhkm to perform some therapy and restore my love for game problems!!
Would you consider this article to be rigorous enough?
No, and I have already said why in Shisuko's blog.
I'm not sure which part is handwavy? Things don't need mathematical formulations and numbers and symbols to be considered rigorous. I mean, we're in CS/comp-prog. Most proofs here are argumentative rather than numerical.
I showed the proof for Grundy numbers working in a specific example, then pointed out how all the same arguments I made also worked given any directed graph. That's a very common and valid stylistic choice in math writing.
how about combinatorics?
What can I talk about hmm... min/max inclusion-exclusion formula (for expected values)? Burnside's (lmao)? Catalan's (I really have to learn this)?
I will keep this in mind, but specific might help~
burnside would be great, like some hard recursion based on burnside lemma. or even if you suggest me some questions to solve that would be also fine for me.
Burnside's lemma has caused me confusion in the past, although I think I'm more comfortable with it now.
Or really, anything related to graph theory would be great (maybe Hall's marriage theorem or counting labeled teres).
Thanks for being so open to ideas! :)
i mean a good idea might be creating a syllabus of links and good resources of the math subjects you think are Necessary for CP that will be really appreciated
if you cant i think a general and easy explanation of the applications of matrix exponentiation in calculating some recursive algorithms(like fibonacci) in (log n) time complexity will be helpful(i know some blogs exist on this topic but they seem a little bit to complicated:( )
For matrix exponentiation, Errichto has a good video on it and corresponding problems.
thanks
sorry i will do more research before commenting from now on