Several solutions for this contest.
Author: appledorem
Suffix Automaton Review & Study Note
Suffix Automaton Study Note This is a review & note for studying suffix automaton. What is a Suffix Automaton? In computer science, a suffix automaton is the smallest partial deterministic finite automaton that recognizes the set of suffixes of a given string(computer_science). The above definition is a short excerpt from Wikipedia about suffix automaton. From the definiton of deterministic finite automaton, we let […]
String Problems: KMP & Manacher Algorithms
A brief introduction to KMP and manacher algorithm.
Reading Note: Introductory Combinatorics 2
Chapter 3: Pigeonhole Principle This is a reading note of Introductory Combinatorics by Richard A. Brualdi. The following aspects are ones that are most important within this chapter: Simple Version of Pigeonhole Principle Application of Simple Pigeonhole Principle Enhanced Version of Pigeonhole Principle Applications of Enhanced Pigeonhole Principle Ramsey Theorem Simple Version of Pigeonhole Principle […]
Reading Note: Introductory Combinatorics 1
[latexpage] Chapter 2: Permutation and Combination This is a reading note of Introductory Combinatorics by Richard A. Brualdi. There are several important aspects within this chapter that I will include in this. Four Basic Counting Principle Permutation & Combination within Single Set Permutation & Combination within Multiple Sets Finite Possibility Introduction to Set We define […]
Codeforces Educational Round46
Last Update: July, 2018 First time post a codeforces contest. Don’t know how to do the last one.. emm… Save this for later Since this is only a Div 2, so I won’t include much explanation(took me centuries to finish). Typesetting is to0 hard… A: Just do it #include <iostream> #include <cstring> #include <string> […]
BZOJ3036: The Destiny of the LEON
Problem Description: There are N nodes and M directed roads with weight in an acyclic graph. At each node, there is a probability of 1 / K to go to each next node, where K number of roads that are connected to current node. Starting at 1, calculate the total expectancy distance to go to […]
BZOJ2442: Mowing the Lawn[USACO2011 Open]
Problem Description: Mowing the Lawn [Neal Wu, 2008] After winning the annual town competition for best lawn a year ago,Farmer John has grown lazy; he has not mowed the lawn since thenand thus his lawn has become unruly. However, the competition isonce again coming soon, and FJ would like to get his lawn intotiptop shape […]
BZOJ 1692: Best Cow Line [USACO 2007 Dec]
Problem Description: FJ is about to take his N (1 <= N <= 30,000) cows to the annual “Farmer of the Year” competition. In this contest every farmer arranges his cows in a line and herds them past the judges. The contest organizers adopted a new registration scheme this year: simply register the initial letter […]
AtCoder Regular 099E: Independence
Problem Description: https://arc099.contest.atcoder.jp/tasks/arc099_c This problem is one that requires thoughts on complement graph. The official editorial has done a pretty good job in explanation. Step: Convert into complement graph -> Find characteristic of this graph -> Bipartite graph -> Convert back -> Find minimum roads -> DP #include <iostream> #include <cstring> #include <string> #include <vector> #include […]