Quick-sort: Video tutorial, pseudo-code (and in-place sorting)
We want to sort an array with n elements. Quick-sort does this by breaking up the array into non-overlapping segments, sorting them separately and then combining the results.
For instance, suppose we have a box with slips of paper with numbers between 100 and 300 to be sorted. We could first separate the slips into two bunches: those with values below 200 and those with values above 200. We can sort these bunches separately. Since all the values in the second bunch are larger than those in the first bunch, we can combine them easily into a single sorted bunch. (See Sorting | Online Study Material - IARCS for a great resource on this.)
Rijndael is a family of block ciphers developed by Belgian cryptographers Vincent Rijmen and Joen Daemen. It was submitted as an entry to the National Institute of Standards and Technology's (NIST) competition to select an Advanced Encryption Standard (AES) to replace Data Encryption Standard (DES). In 2001, Rijndael won the competition and the 128, 192, and 256-bit versions of Rijndael were officially selected as the Advanced Encryption Standard.
The three variants of AES are based on different key sizes (128, 192, and 256 bits). In this article, we will focus on the 128-bit version of the AES key schedule, which provides sufficient background to understand the 192 and 256 bit variants as well. At the end, we'll include a note the other variants, and how they differ from the 128-bit version.
Encryption with AES
The encryption phase of AES can be broken into three...
Motivation: Given an array of N integers. You have to answer some queries in form (l, r, k). To answer this query you have to print the number of integers less than k in the sub-array array[l .... r].
You should be able to solve the problem in O(log^2 n) per query at least. How? You can use Merge Sort Trees.
Now what is a Merge Sort Tree? Merge Sort Tree is actually a Segment Tree but each node contains a vector. If the range of the node is [l,r] then the vector will contain the elements of array[l...r] but in sorted order.
To solve the above problem we can make a Merge Sort Tree first and go into relevant segments and binary search on the vector that was stored in those nodes to count how many numbers are less than k. This will give O(log^2 n).
I think O(nlog^2 n ) is not an acceptable time limit for this problem. It is only meant to be solved in O(nlog n). I tried writing it using merge sort tree but was getting TLE even with fast io. You can solve it using BIT or persistent segment tree in nlogn time.
Motivation problem: We have a tree consisting of n(<=10^5) nodes. We will consider the tree nodes indexed from 1 to n. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue. The distance between two tree nodes v and u is the number of edges in the shortest path between v and u. We need to learn how to quickly execute queries of two types:
paint a specified blue node in red;
calculate which red node is the closest to the given one and print the shortest distance to the closest red node.
Your task is to write a program which will execute the described queries.
Comments: It does seem like RMQ(Range Minimum/Maximum but on trees. Of course these can be solved using segment trees(Heavy Light Decomposition). But there is a technique which can be used to solved these kind of problems with the same time complexity but shorte...