Skip to content

Instantly share code, notes, and snippets.

View OmarBazaraa's full-sized avatar

Omar Bazaraa OmarBazaraa

View GitHub Profile
@OmarBazaraa
OmarBazaraa / problem_c.cpp
Created September 8, 2019 12:47
C. Crusher’s Code
#include <bits/stdc++.h>
using namespace std;
const int N = 8, M = (1 << 24) + 100;
int n;
double memo[M];
void compress(vector<int>& a) {
@OmarBazaraa
OmarBazaraa / problem_h.cpp
Last active September 8, 2019 10:51
H. Holodeck Hacking
#include <bits/stdc++.h>
using namespace std;
long long dp[20][2][2];
string s;
long long solve(int idx = 0, int carry = 0, int needCarry = 0) {
if (idx * 2 == (int) s.size())
return needCarry == carry;
@OmarBazaraa
OmarBazaraa / extendedEuclid.cpp
Created January 30, 2019 21:24
Extended Euclid Method
// Returns the Bezout's coefficients of the smallest positive linear combination of a and b
// using the extended Euclidean algorithm.
// (i.e. GCD(a, b) = s.a + t.b).
// O(GCD(a, b)) = O(log(n))
pair<int, int> extendedEuclid(int a, int b) {
/* PROOF:
------
gcd(a, b) = s.a + t.b -->(1)
= gcd(b, a mod b) = s'.b + t'.(a mod b), a mod b = a - q.b, q = floor(a/b)
@OmarBazaraa
OmarBazaraa / main.cpp
Last active September 21, 2018 14:27
SPOJ - SFLIP- Segment Flip
/**
* The problem can be solved greedly with the help of segment tree or other data strucutres.
*
* The idea is to find the segment with the minimum total sum, then flip (negate) it.
* We keep doing so for k times, or until all the values in the array become non-negative.
*
* One key observation about this problem is that it does not matter whether
* the segments are overlapping or not.
*
* I used segment tree in order to find and flip segments quickly.
@OmarBazaraa
OmarBazaraa / main.cpp
Last active September 12, 2018 19:18
CodeChef - CHSIGN - Change the Signs
/**
* I used DP to solve this problem.
* I try to minimize the the sum of the sequence, so I do the following for every element:
* 1. Just leave it positive as is.
* 2. Negate it if possible and go to the next valid position (i.e. the position where another negation can occur).
*
* Why linear iterations in {@function next} will not result in TLE ?!
* Because in order to iterating in the while loop we need every element is greater than or equal the sum of all the previous
* elements. Such sequence will be with length of at most log2(10^9).
*/
@OmarBazaraa
OmarBazaraa / main.cpp
Created September 12, 2018 11:40
SPOJ - INCDSEQ - Distinct Increasing Subsequences
#include <bits/stdc++.h>
using namespace std;
const int N = 100100, K = 55, MOD = 5000000;
int n, k, a[N], BIT[K][N];
int val, tmp, cnt, id;
map<int, int> mp;
int fix(int x) {
@OmarBazaraa
OmarBazaraa / main.cpp
Created September 11, 2018 22:14
SPOJ - INCSEQ - Increasing Subsequences Problem
#include <bits/stdc++.h>
using namespace std;
const int N = 100100, K = 55, MOD = 5000000;
int n, k, a[N], BIT[K][N];
void update(int tid, int idx, int val) {
while (idx < N) {
BIT[tid][idx] = (BIT[tid][idx] + val) % MOD;
@OmarBazaraa
OmarBazaraa / main.cpp
Created September 9, 2018 14:17
HackerRank Sum of all Distances Problem
#include <bits/stdc++.h>
using namespace std;
typedef long long Long;
const int N = 100100, M = 200200;
int T, n, u, v, w;
int edgeId;
int head[N], cnt[N], nxt[M], to[M], weight[M];
@OmarBazaraa
OmarBazaraa / src.cpp
Last active September 1, 2018 11:16
Spiral matrix traversal
#include <bits/stdc++.h>
using namespace std;
const int N = 101;
// Direction arrays in spiral order { Right, Down, Left, Up }
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
int n, m, a[N][N];
@OmarBazaraa
OmarBazaraa / main.cpp
Created August 10, 2018 17:20
UVA 1238 - Free Parentheses
#include <bits/stdc++.h>
using namespace std;
const int N = 33, M = N * 105;
int n, a[N];
char sign[N];
bool vis[N][M * 2][N];
string s;
set<int> st;