Блог пользователя k-dx

Автор k-dx, история, 2 года назад, По-английски

Tutorial: Codeforces formatting/markup

When writing my first blog post I grew frustrated because I couldn't find resources on how to format the post and what I can/can't use. So I decided to collect what I know in this blogpost, so this wouldn't be such a problem for other newbies in the future.

This post has been written with my best knowledge. If something is incorrect please let me know!

Table of Contents

  1. Markdown — general formatting
  2. LaTeX (MathJax) — math and other special symbols
  3. Codeforces specific features
  4. Other useful resources
  5. BONUS: Typing $ in your posts

1. Markdown — general formatting

Overview

When you are writing a post or a comment on codeforces, you are writing in a markup language called Markdown. You can learn more about markdown and how it works here. It has its own easy syntax, for example if you want bold text, you should write **bold text** in the editor. You can find links to resources about Markdown provided by the creator of Codeforces MikeMirzayanov in his post here. There are also many materials and Markdown cheatsheets on the internet (https://www.markdownguide.org/basic-syntax/), but beware that Markdown has many flavours meaning something you find online might apply to a different Markdown flavour than Codeforces uses and therefore will not work here. Also if something doesn't work try adding an empty line before and after it. For example, you need an empty line before and after list's items to make a list.

HTML

Because Markdown gets converted into HTML, you can use HTML tags in it. So writing <b>something bold</b> will also get you something bold. You can read more about it here. Beware that from my experience unfortunately not all tags work, I've had problems with <svg>.

Tables

I find it much easier to use https://www.tablesgenerator.com/markdown_tables rather than create tables in Markdown manually.

Code

Short code

To include code in your posts enclose it in triple backtics (```), like so:

```c++
#include <iostream>
using namespace std;

int main () {
   cout << "Hello world!\n";
   return 0;
}
```

You can add your language name after the beginning triple backtics. See c++ above. The above will render as:

#include <iostream>
using namespace std;

int main () {
   cout << "Hello world!\n";
   return 0;
}
Longer code

If your code is long it is good to enclose it in <spoiler></spoiler> tags, like so:

<spoiler summary="My Code">
```c++
#include <iostream>
using namespace std;

int main () {
   cout << "Hello world!\n";
   return 0;
}
```
</spoiler>

This will render as:

My Code

2. LaTeX (MathJax) — math and other special symbols

Overview

To type math on Codeforces we use LaTeX language, which is getting rendered by MathJax (source). In LaTeX, a command is backslash symbol (\) followed by the name of the command. The 'arguments' are inside curly braces. For example, \frac{1}{2} would give us a fraction of 1/2. There are two ways to enter 'math mode' on Codeforces:

inline math mode: the equation will be inline. To use it, put LaTeX code between single $ (dollar signs):
Some text containing math $1 + \frac{1}{2} = \frac{3}{2}$., which renders as:

Some text containing math $$$1 + \frac{1}{2} = \frac{3}{2}$$$.

displayed math mode: the equation will be on a new line and centered. To use it, put LaTeX code between $$ (two dollar signs):
Some text containing math $$1 + \frac{1}{2} = \frac{3}{2}$$., which renders as:

Some text containing math

$$$1 + \frac{1}{2} = \frac{3}{2}$$$

.

Cheatsheet and tutorial

You can find more about LaTeX in MathJax here:

Making your equations bigger

If you type $$\sum_{n=1}^\infty \frac{1}{n^2}$$ you will get this:

$$$\sum_{n=1}^\infty \frac{1}{n^2}$$$

As you can see, the $$$\infty$$$ and $$$n=1$$$ parts are not above and under the sum symbol. We can fix this by adding \displaystyle command at the beginning of math mode (just after $ or $$), like so: $$\displaystyle\sum_{n=1}^\infty \frac{1}{n^2}$$ and we get this:

$$$\displaystyle\sum_{n=1}^\infty \frac{1}{n^2}$$$

Seeing LaTeX source of any equation

You can see the LaTeX source of any equation on Codeforces by right-clicking it and selecting 'Show math as > TeX Commands'. Try it on the equation above! Note that it will not work on older equations, which are rendered as images. More info here.

Finding the name of a symbol

If you don't know the name of a symbol in LaTeX try using https://detexify.kirelabs.org/classify.html, where you can draw it and it will tell you the name! Isn't it cool?

3. Codeforces specific features

Codeforces has some special features to link its entities (users, submissions, problems, etc.). To use them, use the dropdown with the Codeforces icon  in the bar above the editor.

4. Other useful resources

5. BONUS: Typing $ in your posts

If you want to type $ symbol without activating the math mode, you should use HTML escape codes and type &#x24; in your post. This will display as a dollar sign.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +119
  • Проголосовать: не нравится

Автор k-dx, история, 2 года назад, По-английски

Above the blogpost editor I see such information:

Use

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

Автор k-dx, история, 2 года назад, По-английски

Hockey Stick Identity — easy explanation

In this post I explain what Hockey Stick Identity (also reffered to as parallel summing) is, visualize it and present an intuitive 'proof'.

What is Hockey Stick Identity?

For whole numbers $$$n$$$ and $$$r$$$ $$$(n \geq r),$$$

$$$ \displaystyle \sum\limits_{k=r}^{n} \binom{k}{r} = \binom{n+1}{r+1} . $$$

Let's visualize this on the Pascal triangle for $$$n = 6, r = 2$$$. We know that elements on the triangle are results of the binomial coefficient. For example $$$ \binom{6}{2} = 15 $$$ is in $$$\color{blue}{\text{row}}$$$ $$$6$$$, $$$\color{orange}{\text{column}}$$$ $$$2$$$.

Do you see it? It resembles a hockey stick! Hence the name.

$$$ \begin{align}

\color{green}{ \sum\limits_{k=2}^{6} \binom{k}{2} } &= \color{red}{ \binom{6+1}{2+1} } \\ \color{green}{ \binom{2}{2} + \binom{3}{2} + \binom{4}{2} + \binom{5}{2} + \binom{6}{2} } &= \color{red}{ \binom{7}{3} } \\ \color{green}{ 1 + 3 + 6 + 10 + 15 } &= \color{red}{ 35 } \end{align} $$$

'Proof'

Idea for this part has been very kindly suggested by my friend hugo4CF.

Let's say we have $$$n + 1 = 7$$$ letters $$$(A, B, C, D, E, F, G)$$$ and we want to count all possible sets of $$$r + 1 = 3$$$ letters from it. The answer to this is obviously $$$\displaystyle \binom{7}{3} = 35$$$. That is the right side of our equation. But we can count it differently. Let's put our letters in a row (the order doesn't matter), e. g.: $$$(E, G, A, D, F, B, C)$$$. Now for each $$$k \in \lbrace r, r + 1, \dots, n \rbrace = \lbrace 2, 3, 4, 5, 6 \rbrace$$$ we will take the $$$\color{magenta}{k+1}$$$-st letter and choose the remaining $$$r = 2$$$ letters from the first $$$k$$$ letters. Let's visualize it:

k row of letters result
2 ($$$\underbrace{\textbf{E, G}}_{\binom{2}{2}}, \color{magenta}{\textbf{A}}$$$, D, F, B, C) $$$\displaystyle\color{green}{\binom{2}{2}}$$$
3 ($$$\underbrace{\textbf{E, G, A}}_{\binom{3}{2}}, \color{magenta}{\textbf{D}}$$$, F, B, C) $$$\displaystyle\color{green}{\binom{3}{2}}$$$
4 ($$$\underbrace{\textbf{E, G, A, D}}_{\binom{4}{2}}, \color{magenta}{\textbf{F}}$$$, B, C) $$$\displaystyle\color{green}{\binom{4}{2}}$$$
5 ($$$\underbrace{\textbf{E, G, A, D, F}}_{\binom{5}{2}}, \color{magenta}{\textbf{B}}$$$, C) $$$\displaystyle\color{green}{\binom{5}{2}}$$$
6 ($$$\underbrace{\textbf{E, G, A, D, F, B}}_{\binom{6}{2}}, \color{magenta}{\textbf{C}}$$$) $$$\displaystyle\color{green}{\binom{6}{2}}$$$

This way we get our left side of the equation.

Application

This identity is used in problem 660E - Different Subsets For All Tuples. Leave a comment if you know other problems for it.

In practice

Naturally, if we want to calculate the binomial, we can for example use the formula $$$ \displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!} $$$ and do the division using modulo-inverse.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +74
  • Проголосовать: не нравится