Skip to content

Instantly share code, notes, and snippets.

View Jangwa's full-sized avatar

Amar Jyoti kachari Jangwa

View GitHub Profile
@Jangwa
Jangwa / LIS "Length"O(nLog(n) ).cpp
Last active August 29, 2015 13:55
Longest Increasing Sub sequence "Length" O(nLog(n) )
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
int a,num[120000],n,ans[120000],sz;
int main(){
while (scanf("%d",&n) == 1){
@Jangwa
Jangwa / Segment Tree Lazy Propagation.cpp
Last active August 29, 2015 13:55
Lazy Propagation means that you only update what you actually need to, when you need to. For example, if we have a segment tree that covers the range 1-20. If we update segment [1,20], we update only the value of the root node of the tree and set a flag on it's children [1,10] and [11,20] to let them know that they need to be updated. Next, if w…
#include<iostream>
#include<algorithm>
using namespace std;
#include<string.h>
#include<math.h>
#define N 20
#define MAX (1+(1<<6)) // Why? :D
#define inf 0x7fffffff
@Jangwa
Jangwa / 2D BIT.cpp
Created January 29, 2014 16:15
2D BIT BIT can be used as a multi-dimensional data structure. Suppose you have a plane with dots (with non-negative coordinates). You make three queries: set dot at (x , y) remove dot from (x , y) count number of dots in rectangle (0 , 0), (x , y) - where (0 , 0) if down-left corner, (x , y) is up-right corner and sides are parallel to x-axis an…
void update(int x , int y , int val){
while (x <= max_x){
updatey(x , y , val);
// this function should update array tree[x]
x += (x & -x);
}
}
void updatey(int x , int y , int val){
while (y <= max_y){
@Jangwa
Jangwa / Binary Indexed Tree.cpp
Last active September 24, 2015 13:17
Notation BIT - Binary Indexed Tree MaxVal - maximum value which will have non-zero frequency f[i] - frequency of value with index i, i = 1 .. MaxVal c[i] - cumulative frequency for index i (f[1] + f[2] + ... + f[i]) tree[i] - sum of frequencies stored in BIT with index i (latter will be described what index means); sometimes we will write tree f…
Isolating the last digit
NOTE: Instead of "the last non-zero digit," it will write only "the last digit."
There are times when we need to get just the last digit from a binary number, so we need an efficient way to do that. Let num be the integer whose last digit we want to isolate. In binary notation num can be represented as a1b, where a represents binary digits before the last digit and b represents zeroes after the last digit.
Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. b consists of all zeroes, so b¯ consists of all ones. Finally we have
-num = (a1b)¯ + 1 = a¯0b¯ + 1 = a¯0(0...0)¯ + 1 = a¯0(1...1) + 1 = a¯1(0...0) = a¯1b.
Now, we can easily isolate the last digit, using bitwise operator AND (in C++, Java it is &) with num and -num:
a1b
@Jangwa
Jangwa / Fast Input.cpp
Created January 29, 2014 13:25
These two are functions that will help you to take input in fast. If you use this to function to take input, execution time decrease dramatically. Without locking the memory inputs are read to buffer so its very fast
#define getcx getchar_unlocked
inline void inp( int &n )//fast input function
{
n=0;
int ch=getcx();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
while( ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
n=n*sign;
@Jangwa
Jangwa / nCr With MOD.cpp
Last active July 12, 2020 13:31
For larger factorials you can either write big factorial library or use a language like Python. The time complexity is O(n). If we have to calcuate nCr mod p(where p is a prime), we can calculate factorial mod p and then use modular inverse to find nCr mod p. If we have to find nCr mod m(where m is not prime), we can factorize m into primes and …
#include<iostream>
using namespace std;
#include<vector>
/* This function calculates (a^b)%MOD */
long long pow(int a, int b, int MOD)
{
long long x=1,y=a;
while(b > 0)
{
@Jangwa
Jangwa / RANGE QUERY with Sparse Table (ST) algorithm.cpp
Created January 28, 2014 16:25
RANGE QUERY with Sparse Table (ST) algorithm
RANGE QUERY
Given a (big) array r[0..n-1], and a lot of queries of certain type. We may want to pre-process the data so that each
query can be performed fast. In this section, we use T (f, g) to denote the running time for an algorithm is O(f(n))
for pre-processing, and O(g(n)) for each query.
If the queries are of type getsum(a, b), which asks the sum of all the elements between a and b, inclusive,
we have a T (n, 1) algorithm: Compute s[i] to be the sum from r[0] to r[i-1], inclusive, then getsum(a,b) simply
returns s[b+1]-s[a].
@Jangwa
Jangwa / KMP.cpp
Last active January 4, 2016 19:49
KMP
The Naive pattern searching algorithm doesn’t work well in cases where we see many matching characters followed by
a mismatching character. Following are some examples.
txt[] = "AAAAAAAAAAAAAAAAAB"
txt[] = "ABABABCABABABCABABABC"
lps[i] = the longest proper prefix of pat[0..i] Searching Algorithm:Preprocessing Algorithm:
if (pattern[0] == '\0') /* Construct the lookup table */ /* Perform the search */ free(T);
pat[] = "AAAAB"
@Jangwa
Jangwa / Josephus Problem.cpp
Last active January 4, 2016 19:49
Question - There are n persons numbered from 0 to n - 1 standing in a circle. The person number K, counting from the person number 0, is executed. After that the person number k of the remaining persons is executed, counting from the person after the last executed one. The process continues until only one person is left. This person is a survivo…
Iterative version
int jos(int K,int N)
{
int r =0;
for(int i=1;i<=N;i++)
{