mzhang2021 / cp-blog Goto Github PK

View Code? Open in Web Editor NEW

10.0 1.0 2.0 52.71 MB

License: MIT License

HTML 18.23% Ruby 0.29% SCSS 20.07% CSS 8.16% JavaScript 53.26%

cp-blog's People

Contributors

Stargazers

Watchers

Forkers

shahjalalshohag mdfarhansadiq

cp-blog's Issues

cp-blog/update/

September 2022 Update | Yet Another Competitive Programming Blog

Hey everyone, it’s been too long since I last took the time to sit down and write a blog post. There’s a multitude of reasons why I haven’t written anything lately. Mainly, once college started, any time to devote to CP instantly evaporated thanks to classes, clubs, and socializing. But also, I just didn’t have anything to write. Typically, when I write a blog post, I write with some topic or intent in mind, usually to educate or as an opinion piece. I’ve started a number of drafts for my next article but have tentatively scrapped all of them, simply because I realized midway that I either didn’t have too much to say or I didn’t feel qualified enough to write on the subj

https://mzhang2021.github.io/cp-blog/update/

cp-blog/segtree-merging/

Segment Tree Merging | Yet Another Competitive Programming Blog

Segment tree merging often serves as an alternative to small-to-large while also cutting an extra log factor, or can be used for “directed” merging (i.e. the merging is not symmetric w.r.t. both sets). The extent to which this technique can be applied is actually quite extensive, and a lot of it is not documented in English (the only English resource I’ve found is this cf post), so I hope to bridge the gap with this post.

https://mzhang2021.github.io/cp-blog/segtree-merging/

cp-blog/reflection/

Self Reflection and What's Next? | Yet Another Competitive Programming Blog

It’s been a month since my last major milestone in CP, and high time for some self reflection. There are two major CP competitions I competed in this month: Facebook Hacker Cup, and Kotlin Heroes 8.

https://mzhang2021.github.io/cp-blog/reflection/

cp-blog/divide-and-conquer/

Applications of Divide and Conquer | Yet Another Competitive Programming Blog

Divide and conquer (D&Q for short) is a common and powerful problem solving paradigm in the world of algorithms. There are numerous well-known examples such as merge sort and fast Fourier transform, and in this article I will cover some (maybe less common) applications of D&Q that are more specific to competitive programming. The sections progress from simple to complex, so more experienced competitors can skip to a later section of the article.

https://mzhang2021.github.io/cp-blog/divide-and-conquer/

cp-blog/how-to-read/

How to Understand Hard Tutorials | Yet Another Competitive Programming Blog

Hooray, it’s my first post of October, meaning I’ve kept this blog running for at least a month!

https://mzhang2021.github.io/cp-blog/how-to-read/

cp-blog/library/

Maintaining a CP Library | Yet Another Competitive Programming Blog

I love maintaining a competitive programming library. You get to implement things attuned to your own personal style, and it’s super satisfying when you use something from your library to successfully pass a problem. There’s also just something satisfying about working on a project over a long period of time, and having it grow and evolve alongside your CP journey. I started my library 3 years ago1 in high school, and it’s come a long way since then. And so now, I write this article so that I can plug my library explain how I design my implementations and how they integrate into my setup. If you check the stats for my Github repo, it was created in February 2020, but that was only the date wh

https://mzhang2021.github.io/cp-blog/library/

cp-blog/first-ever-regionals/

My First Ever ICPC Regionals Experience! | Yet Another Competitive Programming Blog

This past weekend, I attended my first ever ICPC regionals! It was an incredibly fun and enlightening experience for me, so I’d like to share with you some takeaways I had.

https://mzhang2021.github.io/cp-blog/first-ever-regionals/

cp-blog/historic-segtree/

Historic Information on Segment Trees | Yet Another Competitive Programming Blog

It’s been a while, but I’m back with some more estoric knowledge! Historic information is a concept I’ve only seen briefly mentioned in this tutorial on segment tree beats, and the section only covers one example of it, so I’ll cover some more examples in this article.

https://mzhang2021.github.io/cp-blog/historic-segtree/

cp-blog/long-challenge/

Long Challenges are Awesome | Yet Another Competitive Programming Blog

Short contests are fun, although not without its fair share of frustrating moments. Have you ever come so close to solving a problem, but ran out of time? If only you had 10 extra minutes! Or have you ever “bricked” on a problem? That is, you come across a problem that should be within your rating range and easily solved, but you just can’t think of the trick needed to solve it? This has happened to me many times, with the most recent example being Global Round 15. I could not think of how to get past the naive $\mathcal O(n^2)$ solution for problem B for the longest time, and I had to skip that problem to do the other ones first in order to save my performance.

https://mzhang2021.github.io/cp-blog/long-challenge/

cp-blog/berlekamp-massey/

Trivialize Linear Recurrence Problems with Berlekamp-Massey! | Yet Another Competitive Programming Blog

Berlekamp-Massey is a powerful tool that can knock out almost all linear recurrence problems, but it’s often explained in the context of BCH decoding in many online tutorials, making it difficult to understand in a more general sense. There’s TLE’s Codeforces blog, which contains all the core concepts of the algorithm but is a bit terse in my opinion. There’s also Massey’s paper, which is more on the mathematically rigorous side, and I have incorporated some of Massey’s proofs into the proof section of this article. The goal of this article is to explain Berlekamp-Massey using my intuition/understanding of it.

https://mzhang2021.github.io/cp-blog/berlekamp-massey/

cp-blog/transition/

Transition Then State | Yet Another Competitive Programming Blog

When we think about the classic model for dynamic programming, typically we think about first enumerating the state, and then enumerating the transitions from that state. But sometimes that perspective doesn’t yield itself to a sufficiently fast solution. Let’s look at some examples.

https://mzhang2021.github.io/cp-blog/transition/

cp-blog/perspective/

A Shift in Perspective | Yet Another Competitive Programming Blog

I’ve seen numerous problems recently where the solution comes from a shift in perspective, and I’ve found them amusing enough to write a whole blog around this topic. I wouldn’t consider this a technique but rather just an explanation of visual intuition for problem solving.

https://mzhang2021.github.io/cp-blog/perspective/

cp-blog/first-post/

First Post | Yet Another Competitive Programming Blog

Welcome to my blog! I go by smax on Codeforces and most other competitive programming sites, and this is a fun personal project for me that I’ve always wanted to do. On this blog, I’ll post articles about techniques, tricks, opinions, or pretty much anything remotely related to CP. Do check it out if you’re interested. This site is powered by Jekyll and the “Mediumish” theme, so if you like how the site looks be sure to check those out.

https://mzhang2021.github.io/cp-blog/first-post/

cp-blog/gss/

Solutions to SPOJ GSS Series | Yet Another Competitive Programming Blog

SPOJ has a series of problems with problem codes GSS1, GSS2, …, GSS8. The problems are intended as educational range query problems, and while they are a bit outdated, they can still be interesting to work through and think about. I highly recommend thinking about each problem on your own before looking at the editorial. Also, don’t feel the need to go in order, because they are definitely not ordered by difficulty. Finally, while I might include snippets of code for clarity of explanation, writing the full code for each problem will be left as an exercise to the reader :)

https://mzhang2021.github.io/cp-blog/gss/

cp-blog/difficulty/

What Makes a Problem Hard? | Yet Another Competitive Programming Blog

Just go to the comment section of any announcement blog for a contest, and you’ll likely see a comment like “A < C < B” or “E was much easier than D.” Or look at any leaderboard, and there’s always at least a few contestants who solve the problems out of order or skip some problem. Problem difficulty is a very subjective thing, and it’s always near impossible to create a set of problems such that A is strictly easier than B, which is strictly easier than C, and so on. Why is that the case, and what makes a problem difficult?

https://mzhang2021.github.io/cp-blog/difficulty/

cp-blog/nac/

2022 ICPC North American Championship | Yet Another Competitive Programming Blog

Yay the blog has been revived!

https://mzhang2021.github.io/cp-blog/nac/