Author: fighternan
Reduce Time Complexity in DP
Posted on
Summary In this post, I will introduce some DP problems. It might not be difficult at the first glance. However, the optimal solution might have lower complexity if one carefully defines the state or uses some other techniques while transferring states. OJ Details LC 1027. Longest Arithmetic Sequence It is not difficult to get the…
State Compression DP
Posted on
Summary State compression is a common technique in some DP problems when number of states are limited and each state consists of bits, where each bit has specific physical meaning. OJ Details LC 1349. Maximum Students Taking Exam Difficulty: 6 points. We could use bit manipulation and state compression DP. For each row, when a…
Built-in C++ String Functions
Posted on
This post contains some useful functions in the standard library which simplify your codes regarding string processing. std::rotate* Performs a left rotation on a range of elements. Specifically, std::rotate swaps the elements in the range [first, last) in such a way that the element n_first becomes the first element of the new range and n_first…
Linear Recurrence Relation & Binary Exponentiation & DP Counting
Posted on
Summary In this post, I will introduce a common technique in some DP counting problems: binary exponentiation. Typically, in these problems, you will be given a number n and you are asked to return the number of valid combinations. You need to figure out the initial state and the transform function between states. The problems…
Hard-to-Detect DP
Posted on
Summary In this post, I will introduce some problems that seem difficult. But once we think of them in another way, they will become DP problems in linear structures or intervals, which are not difficult to solve. OJ Details LC 1049. Last Stone Weight II Think of it in this way: we divide the numbers into…
Pure Greedy
Posted on
Summary In this post, I will introduce some problems which could solved by pure greedy technique. “Pure” means no other techniques are needed in this category of problems. Actually greedy can be combined by other techniques like DP. Note that usually greedy will be faster than Pure Dynamic Programming. But in case one could not…
Binary Search the Result
Posted on
Summary In this post, I will introduce some problems which could binary search the best result. The problems in this category usually ask for a best value. The value could fall into the range of [min, max]. Another important property is that if the value at the middle is not achievable, we could eliminate a…
Subarray & DP
Posted on
Summary In this post, I will introduce some problems related to subarray and dynamic programming. The most important thing in subarray is that it is continuous. So usually one dimension of the DP will be chosen as “a subarray starting at index i”. Then we need a separate loop for it to choose the best…
Palindrome & DP
Posted on
Summary In this post, I will introduce some problems related to palindrome and dynamic programming. A palindrome has a property that, if we add two equal characters in both side of it, it is still a palindrome. OJ Details LC 1278 Palindrome Partitioning III Difficulty: 6-7 points Given a string s containing lowercase letters and an integer k….
Merge Sort
Posted on
Summary In this post, I will introduce some problems using the merge sort technique. These problems often ask, for an element at index , how many are there which satisfies a formula. OJ Details The Master Theorem If is of complexity , then is of complexity So in these problems, a key point…
DP in Linear Structures & Real Result
Posted on
Summary Some problems require returning real result not just a number. To do this, a good method is that we create another table to store the optimal choices we made on each state. To return any optimal result, the choice table will be as large as the alg table. The result can we achieved by…
Divisors & Factors
Posted on
Summary In this post, I will introduce some common techniques related to divisors and factors. Details Number of Divisors GCD
KMP
Posted on
Summary In this post, I will introduce some problems related to KMP. OJ Details Pi is the length of the longest prefix of substring , such that this prefix is also the suffix of . Note that this prefix excludes itself. By the definition, we have . For example, we have, Please refer…
Pure Bit Manipulation
Posted on
Summary In this post, I will introduce problems related to bit manipulation. Before that, you may want to learn the std::bitset<> class template. Detials LC 1386. Cinema Seat Allocation The problem is not difficult. But it is tricky to write a clean code. The hint is that all valid patterns can be presented by the…
Monotonic Queue (Pure)
Posted on
Summary I will introduce some pure Monotonic Queue problems in this post. Details Sword to Offers Problem 59 Max Queue Mantain a special queue so that you can do max_value, push_back, and pop_front in amortized O(1) time. LC 456. 132 Pattern It is not difficult to get an O(n^2) or even an O(nlogn) solution: we…
Segment Tree
Posted on
Summary In this post, I will introduce several templates for the Segment Tree. Compared to the binary index tree, segment tree is easy to understand, though the codes are longer. I will not introduce 2D Segment Tree in this post. Some OJ problems are listed below. LC 1157: query range majority; update single node; LC…
DP in Intervals (Dynamic)
Posted on
Summary Some problems in this category has something dynamic. Like several elements merge into one element or eliminate one element with the a cost related to its neighbors. The key point of these problems is think backward: think about how the last element is formed. Details Minimum Cost to Merge Stones I There are N…
Date
Posted on
Summary In this post, I will introduce some problems related to date. Details Is Leap Year Days of the Year Days from 1900 Days Between Dates
Compute Capabilities and Thoughputs on NVIDIA’s GPUs
Posted on
Summary In this post, I will introduce the thoughputs and compute capabilities on NVIDIA’s GPUs. The post doesn’t contain hardware details. Conclusion It might be a common sense that half precision floats will run faster on GPUs, like this post by Intel. However, it is a different story on NVIDIA’s GPUs. For example, you may…
Scoping and Friends in Nested Classes
Posted on
Summary In this post, I will introduce the scoping in nested classes and how friend classes work here. Conclusion The rules are, As any member of its outer class, nested classes have access to all names (private, protected, etc) to which the outer class has access; however, outer classes have no special access to inner…
Custom Deleters of Shared & Unique Pointer
Posted on
Summary In this post, I will introduce custom deleters when using C++ std::shared_ptr and std::unique_ptr. Conclusion Use the following snippets. Note the fourth case, where a unique_ptr with custom deleter will not pass the deleter to the shared_ptr when using release(). class OldThing { public: ~OldThing() { if (allocated_) { std::cout << "MEMORY LEAK!" <<…
Edge Cases of Namespace Pollution
Posted on
Summary In the previous post, I introduced the rules of using directives (using namespace std) and using declarations (using std::vector). Generally speaking, the rules are good if there is no confliction, in which two using-declarations are the same. As a quick recap, using directives are forbidden. Since this directive makes all names from a namespace…
Containerized WordPress, Migration, and SSL
Posted on
Summary The world witnessed the popularity of containerized applications. Docker provides good isolation and is of good portability. It also could be the basic item in a distributed system. In this post, I introduced how to create a WordPress site in docker; how to migration WordPress; how to make the site secure via SSL; how…
How to debug Async Kernels or APIs in CUDA
Posted on
Summary In this post, I will introduce how to debug async kernels or async APIs in CUDA. The async operations will not block CPU codes. When we check the return type of the functions calls, it may be SUCCESS but there are bugs like "illegal memory access". On the other hand, when we find the…
Sync and Async in CUDA
Posted on
Summary In this post, I will introduce the Sync and Async behaviors in CUDA. Conclusion The followings are handy codes testing the behaviors of CPU and streams. Details There are two aspects, kernels and streams. 1. Kernels Some of my conclusions are, All kernels will return immediately no matter we use the default stream or…
AddressSanitizer
Posted on
Summary In this post, I will introduce a useful tool called AddressSanitizer. The motivation of it is that I have a debate with one of my colleagues about whether it is necessary to detect memory leaks in small projects. I was the one who persists to avoid memory issues though the program is small and…
Include Syntax
Posted on
Summary In this post, I will introduce the different between #include "file" and #include <file> in C++. Conclusion #include <file> This variant is used for system header files. It searches for a file named file in a standard list of system directories. You can prepend directories to this list with the -I option. #include "file"…
Git Large File Storage
Posted on
Summary In the post, I will introduce a common usage of large file storage in Git together with a tool bfg. Background Say one day you found an engineer in your team accidentally commit a binary file (for example a shared library) to the remote repository. He argued the file must be accessible in the…
In-Class Initialization Errors
Posted on
Summary In this post, I will introduce some common compiling errors I used to see related to in-class initialization: Error: in-class initialization of static data member xxx of non-literal type; Error: ISO C++ forbids in-class initialization of non-const static member xxx; Conclusion As usual, I present the correct ways to do in-class initialization at the…
Include Guard V.S. #pragma once
Posted on
Summary In this post, I will introduce the difference between include guard and #pragma directives in C++. Conclusion As usual, I will present the conclusion first. Include guard is the standard way to prevent multiple inclusion of the same header; #pragma directive is not required by C++ standard but now widely supported by most of…
How to Install Kubernetes and Enable Dashboard
Posted on
Summary In this post, I will introduce how to create a single control-node Kubernetes cluster with version v1.15.x and enable an accessible dashboard. With this post, you can easily deploy a cluster from scratch for testing. Details Before we start, note that there are problems like single node failure and security, which makes the deployment…
Ways to Overload Default Order in C++’s STL
Posted on
Summary In this post, I will introduce some methods to overload the default order in C++’s STL. Please refer to my other post if you are not familiar with Ordered Containers in C++. This post is a helpful reference when solving coding challenges. Conclusion You are giving a sequence of pairs, {{5, “five”}, {1, “one”},…
Thread Pool in C++
Posted on
Summary In this post, I will introduce how to build a simple thread pool in C++. Conclusion The codes are from here. The thread pool only uses thread, mutex, and condition_variable. #include <thread> #include <mutex> #include <condition_variable> class ThreadPool; // our worker thread objects class Worker { public: Worker(ThreadPool &s) : pool(s) { } void…
Mutex in C++ and Java
Posted on
Summary In this post, I will introduce the correct way to use mutex in C++, compared to Java. Conclusion Try not to use std::mutex directly. Use std::unique_lock, std::lock_guard, or std::scoped_lock (since C++17) to manage locking in a more exception-safe manner. Undefined behaviors will happen if a). A mutex is destroyed while still owned by any…
Github-Synchronized, Markdown-based, and Auth-Enabled Wiki System
Posted on
Summary In this post, I will introduce how to set up a personal Wiki system with the following features, Github-Synchronized: All pages are synchronized on Github; Markdown-based: All pages can be written in Markdown; Auth-Enabled: Visitors can view and admins can view/edit. Conclusion I provide a ready-to-use Docker image. sudo docker run \ -v ${PWD}:/home/wiki_repo…
DependencyManagement and Dependencies in Maven
Posted on
Summary In this post, I will introduce the key difference between Maven’s <dependencyManagement> and <dependencies>. Conclusion In pom inheritance, artifacts specified <dependencies> will ALWAYS be included as a dependency of the child module(s). However, artifacts specified in <dependencyManagement> will only be included if child modules explicitly specify them in <dependencies>. <dependencyManagement> is good for centralized…
Generics in Java Compared to C++ Templates
Posted on
Summary In this post, I will introduce Generic in Java. The post may be useful when you are working with Java with prior knowledge of C++. Context The context is that I want to define an AbstractBaseClass which is a top-level abstract class but different subclasses require different types of arguments for some member functions….
Profile Applications in CUDA
Posted on
Summary In this post, I will introduce how to use the tool nvprof to profile your CUDA applications. Details It is a good practice to dive deeper to see how much time each kernel or each CUDA runtime API takes when you want to optimize your applications. Intuition It is not good to use any…
Virtual Functions, Constructors, and Destructors
Posted on
Summary In this post, I will introduce rules related to constructors and destructors of classes which has virtual functions. Conclusions Golden Rule 1: Define a virtual destructor immediately Golden Rule 2: Do not invoke virtual functions from constructors or destructors Details In C++, Virtual functions allow for the choice of member function calls to be…
Override vs Overload
Posted on
Summary In this post, I will introduce function override and function overload in C++, which are introduced by polymorphism in object oriented programming. Conclusion Overload Function overloadding achieves at compile time. It provides multiple definitions of the function by changing signature. Changing signatures includes changing number of parameters, change datatype of parameters. Note that return…
Class Template Definition and Declaration
Posted on
Summary In this post. I will introduce class templates in C++. Especially, how do we declare a template which generates classes and how do we write definitions in separate source files. I will also dive deeper to present how class templates are compiled. Conclusion As usual, I present the conclusions first.Say the customer will use…
Install CUDA 10.1 and Driver 418
Posted on
Summary In this post, I will introduce how to install the newest CUDA and corresponding Nvidia driver in Ubuntu 16.04. Details I want to use CUDA for neural network inference. But after I compile the executable files and run, it tells me driver not compatible with this version of CUDA. I have GTX 1060 and…
Install SSL Certificate and Change To HTTPS
Posted on
Summary In this post, I will introduce how to install the SSL certificate for WordPress. Conclusion I did some research and tried different methods. Now I will provide the simplest ways. Apply for an SSL certificate; Download the certificate and sent it to the server; Do the following command: sudo yum install mod_ssl; Add a…
Update PHP for WordPress on CentOS
Posted on
Summary In this post, I will introduce how to update PHP for WordPress. Conclusion As usual, I present the following snippets first. sudo yum remove php-common mod_php php-cli sudo yum install epel-release sudo yum install http://rpms.remirepo.net/enterprise/remi-release-7.rpm sudo yum install yum-utils sudo yum-config-manager –enable remi-php72 sudo yum install php php-mysql –y sudo systemctl restart httpd Details…
A Generic Project Structure in C++
Posted on
Summary In this post, I will introduce a generic structure for C++ projects. Details A clean structure is the basis of a clean project. I simplify the full version and present a simpler but useful structure here. 1. bin: The output executables. 2. build: This folder contains all object files. 3. docs: Any notes, like…
Git Snippets
Posted on
Summary In this post, I will introduce some useful snippets related to Git. I will update this post from time to time. Details Rename Local Branches Say you want to rename the branch old-name to new-name locally. git checkout old-name git branch -m new-name # -m: move/rename a branch and its reflog Rename Local &…
Brief Introduction to Functors
Posted on
Summary In this post, I will introduce function objects, also known as functors. Conclusion I provid the following snippets as a quick reference. See meeting-rooms-II for the problem details. /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int…
Allocate Memory in Constructors and Destructors
Posted on
Summary In this post, I will introduce the way to define a class which contains memory allocation. I will focus on constructors and destructors in this post. Conclusion I present the conclusion first as usual: whenever the implementation of a class involves dynamically allocated memory, the class should explicitly define: a destructor which frees the…
Remote Desktop Application
Posted on
Summary In this post, I will introduce a solution for remote desktop control. It is totally free and has great performance. Note: It seems Google Chrome Remote Desktop does not support gdm. But I am quite sure it works if you use lightdm which is also the default display manager in Ubuntu. Conclusion As usual,…
Namespace and Using
Posted on
Summary In this post, I will introduce how to use "using" in C++, in other words, how to use an existing namespace. Conclusion As usual, I present the conclusion first. The followings are recommended ways which minimize name collision possibilities and maximize code clarity and writing convenience. See this post as well. For Headers Do…