Stress Testing
I decided to write this article after watching the last screencast made by Errichto. To be more precise when he started making stress testing to find counter-test you can check that here. Errichto has a full video called How to test your solution in Competitive Programming, on Linux? I highly recommend you to check it, basically this article is the same but I am extending it to stress test solutions with multiple answers using a written checker, so let’s jump in.
Read more →Autocomplete
Autocomplete
Autocomplete is the feature when an application predicts the complete word, after just typing some prefix of the word. You must have used autocomplete feature a lot in your life in many area like:
- Search engines, Google search engine suggests to you an autocomplete feature when you type some text in the search bar, usually sorted by most trends.
- Emails, as you start writing some prefix of the Email address you will get a list of suggestions.
- Social media, like facebook, linkedin, instagram…
- In source code editors, actually I am using Atom right now and I have used autocomplete for at least 10 times just in the first small part of this article.
Game Theory
Combinatorial Games
The game is said to be Combinatorial if it satisfies the following conditions:
- The game is played between two players, we will call them Alice and Bob.
- The two players alternate playing, Alice plays first.
- We can define two sets \(F_1\) and \(F_2\) of possible moves for each player, these sets are usually finite, based on these two sets we can classify combinatorial games into:
- Combinatorial impartial games this happens when \(F_1 = F_2\), this means both players have the same options of moving from each position.
- Combinatorial partizan games this happens when \(F_1\ne F_2\), this includes games like chess or checkers in which one player moves the white pieces, and the other player moves the black pieces.
- There is an end position of the game, usually called the terminal position. In normal play rule the player making the last move wins the game, in misère play rules the player making the last move loses the game.
- The game always ends after some finite number of moves.
Maximum Independent Set in Bipartite Graphs
Introduction
The title contains a lot of terms that should be explained separately before we start, given an undirected graph \(G = (V, E)\) we define the following terms:
- Independent Set (IS) : Subset of nodes \(U \subseteq V\) with the following propriety: For any two nodes \(u, v \in U\) nodes \(u, v\) are not adjacent ( There is no direct edge between nodes \(u\) and \(v\) ).
- Maximal Independent Set (MIS) : An independent set is maximal if no node can be added to it without violating the independence condition.
- Maximum Independent Set (MaxIS) : An independent set of maximum cardinality.
Monotonic Queue
Motivation Problem
Given \(n \times m\) matrix \((1 \le n, m \le 3*10^3)\) you have to calculate the sum of minimum numbers in all sub-matrices of size \(a\times b\) with top left corners in \((i, j)\) over all \(1 \le i \le n-a+1\) and \(1 \le j \le m-b+1\).
Read more →