matthewsamuel95 / acm-icpc-algorithms Goto Github PK
View Code? Open in Web Editor NEWAlgorithms used in Competitive Programming
Algorithms used in Competitive Programming
- Dijkstra
- Kruskal
- Prims
- Topological Sort
- Floyd Warshall
- Dial’s
- Johnson’s
- Tarjan’s
Example { 2, 5, 3, 7, 11, 8, 10, 13, 6 }
Length of Longest Increasing Subsequence is 6
Time Complexity:
O(N log N)
Additional resources:
https://www.youtube.com/watch?v=S9oUiVYEq7E
Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false. For example, if the given array is {12, 3, 4, 1, 6, 9} and given sum is 24, then there is a triplet (12, 3 and 9) present in array whose sum is 24.
where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.
For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)
Given an array of integers, find any one combination of four elements in the array whose sum is equal to a given value X.
For example, if the given array is {10, 2, 3, 4, 5, 9, 7, 8} and X = 23, then your function should print “3 5 7 8” (3 + 5 + 7 + 8 = 23).
Put code in Hashing
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Given an integer x, find square root of it. If x is not a perfect square, then return floor(√x).
Examples:
Input: x = 4
Output: 2
Input: x = 11
Output: 3
Bubble Sort Algorithm in Java
Write a function that, for a given no n, finds a number p which is greater than or equal to n and is a smallest power of 2.
Input : n = 17
Output : 32
Input : n = 32
Output : 32
Input : mat[][] = { {0, 0, 1, 1},
{0, 1, 1, 0},
{1, 1, 1, 0},
{1, 0, 0, 1} }
Output : 8 sq. units
(Top, left): (0, 0)
(Bottom, right): (3, 1)
Input : mat[][] = { {0, 0, 1, 1},
{0, 1, 1, 1} }
Output : 6 sq. units
Time Complexity : O(Row x Col)
Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false. For example, if the given array is {12, 3, 4, 1, 6, 9} and given sum is 24, then there is a triplet (12, 3 and 9) present in array whose sum is 24.
Put the code in Hashing/3_Sum/{ur file}
greedy seems to be a concept, sorting algorithms into their usage should be better 😄
Selection of Random Number from stream of numbers
The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.
Given two strings S and T, find length of the shortest subsequence in S which is not a subsequence in T. If no such subsequence is possible, return -1. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. A string of length n has 2^n different possible subsequences.
Input : S = “babab” T = “babba”
Output : 3
The subsequence “aab” of length 3 is
present in S but not in T.
Input : S = “abb” T = “abab”
Output : -1
There is no subsequence that is present
in S but not in T.
Algorithm should have
Time complexity : O(mn^2)
Space Complexity : O(mn)
Determine whether a given graph contains Hamiltonian Cycle or not. If it contains, then print the path. Following are the input and output of the required function.
Implement pow(x, n), which calculates x raised to the power n (x^n).
Examples
Input: 2, -2
Output : 0.25
Input: 2.00000, 10
Output: 1024.00000
Push code to Math/Power/{ur file}
The problem is to count all the possible paths from top left to bottom right of a mXm matrix with the constraints that from each cell you can either move only to right or down
Example
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
one of the basic dp problem is maximum sum increasing subsequence it will be good to include this
please write a gitignore that at least considers for .pyc and a.out and others
Write a function that calculates and returns log_2 n . For example, if n = 64, then your function should return 6
Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
Example 1: Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Explanation: "i" and "love" are the two most frequent words. Note that "i" comes before "love" due to a lower alphabetical order.
Example 2: Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 Output: ["the", "is", "sunny", "day"] Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.
Edmond-Karp's
Dinic's
provided an integral number print all its factors which when multiplied gives the original number
Given two arrays, find length of the longest common increasing subsequence [LCIS] and print one of such sequences (multiple sequences may exist)
Suppose we consider two arrays –
arr1[] = {3, 4, 9, 1} and
arr2[] = {5, 3, 8, 9, 10, 2, 1}
The answer would be {3, 9} as this is the longest common subsequence which is increasing also.
Example
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Place code in String subfolder
Given an expression string exp , write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[“,”]” are correct in exp. For example, the program should print true for exp = “[()]{}{()()}” and false for exp = “[(])”
Given a value V, if we want to make change for V cents, and we have infinite supply of each of C = { C1, C2, .. , Cm} valued coins, what is the minimum number of coins to make the change?
Input: coins[] = {25, 10, 5}, V = 30
Output: Minimum 2 coins required
We can use one coin of 25 cents and one of 5 cents
Input: coins[] = {9, 6, 5, 1}, V = 11
Output: Minimum 2 coins required
We can use one coin of 6 cents and 1 coin of 5 cents
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of edits (operations) required to convert ‘str1’ into ‘str2’.
Insert
Remove
Replace
All of the above operations are of equal cost.
Input: str1 = "geek", str2 = "gesek"
Output: 1
We can convert str1 into str2 by inserting a 's'.
Input: str1 = "cat", str2 = "cut"
Output: 1
We can convert str1 into str2 by replacing 'a' with 'u'.
Input: str1 = "sunday", str2 = "saturday"
Output: 3
Last three and first characters are same. We basically
need to convert "un" to "atur". This can be done using
below three operations.
Replace 'n' with 'r', insert t, insert a
Give instructions how to follow the file structure and create a pull request
You can follow this solution in C++, using HashMap to get O(n) solution.
`#include < map >
using namespace std;
class Solution {
public:
vector twoSum(vector &numbers, int target) {
int len = numbers.size();
map<int, int> r;
vector rr;
for (int i = 0; i < len; i ++) {
if (r.find(numbers[i]) == r.end()) { // if not exist
r[numbers[i]] = i; // add it to the map
}
int j, num = target - numbers[i];
if ((r.find(num) != r.end()) && ((j = r[num]) < i)) {
rr.push_back(j + 1);
rr.push_back(i + 1);
return rr;
}
}
return rr;
}
};`
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Implement pow(x, n), which calculates x raised to the power n (x^n).
Examples
Input: 2.00000, 10
Output: 1024.00000
Well i use this sites and files to learn more about Competitive Programming:
-Training Camp
-Competitive Programming 3
-Algorithms
-UVA Online Judge
-Codeforces
-Sphere Online Judge
-ACM ICPC Live Archive
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.
Input: n = 5
Output: Sum of digits in numbers from 1 to 5 = 15
Input: n = 12
Output: Sum of digits in numbers from 1 to 12 = 51
Input: n = 328
Output: Sum of digits in numbers from 1 to 328 = 3241
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.