Introduction and Proof Lemma: $gcd(a - n, n) = gcd(a, n)$. Proof: Let $g = gcd(a, n)$, therefore from the definition of gcd, $g$ is the largest number which divides both $a$ and $n$. Now, as $g|a$ and $g|n$ therefore $g|(a-n)$. Now to be sure that $g$ is the largest such number, let’s assume there exist another $d$ such that it is the largest one rather than $g$ that is $d > g$, in this case $d|n$ and $d|(a-n)$.…

What is a category? Category is simply some objects, with some morphisms arising from one object and pointing to another (this can be same object too). Such that, There exists an indentity morphism for all objects. For every two morphisms of the type $m_1: A \mapsto B$ and $m_2: B \mapsto C$ there exists a morphism $m: A \mapsto C$ which is called composition of $m_1$ and $m_2$. And this composition is associative.…

Monoid A monoid is a really simple concept which consists of a pair of set of objects $S$ and a binary operator $\cdot$ defined on them, such that There exists an identity ($id \in S$) such that $a \cdot id = id \cdot a = a$ for all $a \in S$ The binary operator $\cdot$ is associative i.e. $a \cdot (b \cdot c) = (a \cdot b) \cdot c$ for all $a, b, c \in S$ Interesting note: Klesli Category can also be seen as a monoid with it’s morphisms as objects.…

Let’s say you are given two numbers $a$, $n$ and you have to compute $a^n$. Algorithm Naive Approach: $O(n)$ The easiest approach to do this, if one knows how to use “for” loops or implement it (if it is not implemented already) in any given programming language is just a single $O(n)$ iteration. Below is a sample implementation in C++. int a, n; // a, n can be initialized either by taking input or // by assigning hardcoded values a = 3, n = 4 let's say // expo initialized to 1 as it is the multiplicative identity int expo = 1; for (int i = 0; i < n; ++i) { expo = expo * a; } // now expo == a^n : true Note Here, the data type is “int”, assuming the value of $expo = a^n$ comes under the constraint of “int”.…

Github & Git Resource: https://www.youtube.com/watch?v=Pp08lcCOwd8 Github — Distributed Version Control System Central | * --> * --> * ---> * ---> (*) |(Final Node) | \ / * ----> * --> * --> * (Distributed) Merge Some commands git init git status git remove –cached — To unstage git restore — to get back previously commited file git commit -a (short git add + commit) git push origin [branch name] — send branch name to origin (in this case - website) git merge [branch-name] — merge to current branch git pull origin [branch-name] git branch -D branch-name —> To delete Pushing code to local repositry Add stuff → git add .…

Introduction Protocol to communicate with other nodes (secure shell) Other examples of protocol are HTTP, HTTPS, FTP, … (each one have some port of their own) like 22 for SSH, 21 for FTP Traffic is encrypted <3 The server must have SSHD server (Open SSH Daemon) — for listening to the requests > ssh [username]@[IP Address] Authentication Methods Password SSH keys — can be used with git Host Generate SSH key & Commands > ssh-keygen [-T rsa] ~/.…

Piano’s Fifth Axiom This blog covers the proof of Piano’s Fifth Axiom using set theoretic definitions which are being used to develop Piano’s Axioms. Axiom: If $n$ and $w$ are in $\omega$, and if $n^{+} = m^{+}$ then $n = m$. To prove the given axiom, we need to first go through two propositions, Proposition 1. No natural number is a subset of any of it’s elements. Proof 1: Consider the set $S$ with the given properties, now as $0 = \emptyset$, therefore no elements in $0$ exists hence $0$ is not a subset of any of it’s elements or $0 \in S$.…

Maximum Independent Set in Bipartite Graphs Kőnig’s line coloring theorem: In any bipartite graph, the number of edges in a Maximum matching equals the number of vertices in a minimum vertex cover. The complement of a minimum vertex cover in any graph is the maximum independent set. Related Problem: F. Bicolored Segments New Technique : Flow over segment - instead of connecting all the nodes in a contiguous segment, a segment tree can be employed to connect $O(\log{}n)$ nodes (of a segment) rather than $O(n)$ nodes.…

830C-Bamboo Partition It turns out the possible values of $answer$ is of the type $\lfloor\frac{x}{y}\rfloor$, and we need some way to iterate through these values which are $O(\sqrt{n})$. This can be done with some neat trick. for(LL i = 1; i <= K; i++){ LL possible = (K/i); i = K/possible; } Link to Proof Link to Code …

1043F-Make It One Solved it using binary search over $1$ to $N$. But it wasnt necessary as it can be seen that if the gcd of some subset is $1$ where $ A_i \leq 300,000 $, then the size of that subset can be maximum $7$ (so bruteforce over $1$ to $7$ would have worked). Proof: It’s $7$ because if we take small primes greedily and making their gcd not equal to $1$, then after $8^{th}$ element, it would exceed $300,000$.…