\chapter{Various}

\section{Intervals}
	\kactlimport{IntervalContainer.h}
	\kactlimport{IntervalCover.h}
	\kactlimport{ConstantIntervals.h}

\section{Misc. algorithms}
	\kactlimport{TernarySearch.h}
	\kactlimport{LIS.h}
	\kactlimport{FastKnapsack.h}

\section{Dynamic programming}
	\kactlimport{KnuthDP.h}
	\kactlimport{DivideAndConquerDP.h}

\section{Debugging tricks}
	\begin{itemize}
		\item \verb@signal(SIGSEGV, [](int) { _Exit(0); });@ converts segfaults into Wrong Answers.
			Similarly one can catch SIGABRT (assertion failures) and SIGFPE (zero divisions).
			\verb@_GLIBCXX_DEBUG@ failures generate SIGABRT (or SIGSEGV on gcc 5.4.0 apparently).
		\item \verb@feenableexcept(29);@ kills the program on NaNs (\texttt 1), 0-divs (\texttt 4), infinities (\texttt 8) and denormals (\texttt{16}).
	\end{itemize}

\section{Optimization tricks}
	\verb@__builtin_ia32_ldmxcsr(40896);@ disables denormals (which make floats 20x slower near their minimum value).
	\subsection{Bit hacks}
		\begin{itemize}
			\item \verb@x & -x@ is the least bit in \texttt{x}.
			\item \verb@for (int x = m; x; ) { --x &= m; ... }@ loops over all subset masks of \texttt{m} (except \texttt{m} itself).
			\item \verb@c = x&-x, r = x+c; (((r^x) >> 2)/c) | r@ is the next number after \texttt{x} with the same number of bits set.
			\item \verb@rep(b,0,K) rep(i,0,(1 << K))@ \\ \verb@  if (i & 1 << b) D[i] += D[i^(1 << b)];@ computes all sums of subsets.
		\end{itemize}
	\subsection{Pragmas}
		\begin{itemize}
			\item \lstinline{#pragma GCC optimize ("Ofast")} will make GCC auto-vectorize loops and optimizes floating points better.
			\item \lstinline{#pragma GCC target ("avx2")} can double performance of vectorized code, but causes crashes on old machines.
			\item \lstinline{#pragma GCC optimize ("trapv")} kills the program on integer overflows (but is really slow).
		\end{itemize}
	\kactlimport{FastMod.h}
	\kactlimport{FastInput.h}
	\kactlimport{BumpAllocator.h}
	\kactlimport{SmallPtr.h}
	\kactlimport{BumpAllocatorSTL.h}
	% \kactlimport{Unrolling.h}
	\kactlimport{SIMD.h}
