From cbce9826a617bcb9f44bb74c7b6a88a7d6c5c42e Mon Sep 17 00:00:00 2001 From: Benjamin Qi Date: Mon, 20 Jul 2020 19:17:40 -0400 Subject: complete search w/ recursion --- content/2_Bronze/Complete_Rec.mdx | 159 ++++++++++++++++++++++++++++++++++++ content/2_Bronze/Gen_Perm.mdx | 126 ---------------------------- content/2_Bronze/Intro_Complete.mdx | 33 +++----- content/3_Silver/Unordered.mdx | 3 +- content/ordering.ts | 2 +- 5 files changed, 173 insertions(+), 150 deletions(-) create mode 100644 content/2_Bronze/Complete_Rec.mdx delete mode 100644 content/2_Bronze/Gen_Perm.mdx diff --git a/content/2_Bronze/Complete_Rec.mdx b/content/2_Bronze/Complete_Rec.mdx new file mode 100644 index 0000000..3dd1aa9 --- /dev/null +++ b/content/2_Bronze/Complete_Rec.mdx @@ -0,0 +1,159 @@ +--- +id: complete-rec +title: "Complete Search with Recursion" +author: Darren Yao, Sam Zhang +description: "Includes generating subsets and permutations." +frequency: 2 +prerequisites: + - intro-complete +--- + +import { Problem } from "../models"; + +export const problems = { + subset: [ + new Problem("CSES", "Apple Division", "1623", "Intro|Very Easy", false, ["Recursion", "Subsets"], "all $2^n$ subsets"), + ], + permSam: [ + new Problem("CSES", "Creating Strings I", "1622", "Intro|Easy", false, [], "all perms of string"), + ], + ex: [ + new Problem("Bronze", "Photoshoot", "988", "Normal", false, [], ""), + ], + back: [ + new Problem("CSES", "Chessboard and Queens", "1624", "Normal", false, [], "Recursively backtrack. See CSES book for more details."), + new Problem("CSES", "Grid Paths", "1625", "Insane", false, [], "Recursively backtrack. See CSES book for more details."), + ], + gen: [ + new Problem("Bronze", "Back & Forth", "857", "Hard", false, [], "exponential time going through all possibilities"), // 99.63 + new Problem("Bronze", "Livestock Lineup", "965", "Hard", false, ["permutations"], ""), // 91.95 + ], +}; + +## Generating Subsets + + + + + + + +## Generating Permutations + + + + + + + +
+ +A **permutation** is a reordering of a list of elements. Some problems will ask for an ordering of elements that satisfies certain conditions. In these problems, if $N \leq 10$, we can probably iterate through all permutations and check each permutation for validity. For a list of $N$ elements, there are $N!$ ways to permute them, and generally we'll need to read through each permutation once to check its validity, for a time complexity of $O(N \cdot N!)$. + + + + + +### Lexicographical Order + +This term is mentioned quite frequently: + + + +Think about how are words ordered in a dictionary. (In fact, this is where the term "lexicographical" comes from.) + +In dictionaries, you will see that words beginning with the letter 'a' appears at the very beginning, followed by words beginning with 'b', and so on. If two words have the same starting letter, the second letter is used to compare them; if both the first and second letters are the same, then use the third letter to compare them, and so on until we either reach a letter that is different, or we reach the end of some word (in this case, the shorter word goes first). + +Permutations can be placed into lexicographical order in almost the same way. We first group permutations by their first element; if the first element of two permutations are equal, then we compare them by the second element; if the second element is also equal, then we compare by the third element, and so on. + +For example, the permutations of 3 elements, in lexicographical order, are + +$$ +[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. +$$ + +Notice that the list starts with permutations beginning with 1 (just like a dictionary that starts with words beginning with 'a'), followed by those beginning with 2 and those beginning with 3. Within the same starting element, the second element is used to make comparisions. + +Generally, unless you are specifically asked to find the lexicographically smallest/largest solution, you do not need to worry about whether permutations are being generated in lexicographical order. However, the idea of lexicographical order does appear quite often in programming contest problems, and in a variety of contexts, so it is strongly recommended that you familiarize yourself with its definition. + +### Checking Permutations in Lexicographical Order + +What's going to be in the `check` function depends on the problem, but it should verify whether the current permutation satisfies the constraints given in the problem. + + + + + +#### Method 1 + +($O(N\cdot N!)$ code) + + + +#### Method 2 + + + + + +Alternatively, we can just use the [`next_permutation()`](https://en.cppreference.com/w/cpp/algorithm/next_permutation) function. This function takes in a range and modifies it to the next greater permutation. If there is no greater permutation, it returns false. To iterate through all permutations, place it inside a `do-while` loop. We are using a `do-while` loop here instead of a typical `while` loop because a `while` loop would modify the smallest permutation before we got a chance to process it. + +```cpp +do { + check(v); // process or check the current permutation for validity +} while(next_permutation(v.begin(), v.end())); +``` + +Each call to `next_permutation` makes a constant number of swaps on average if we go through all $N!$ permutations of size $N$. + + + + + +```java +import java.util.*; + +public class Test { + static boolean[] used; + static ArrayList cur = new ArrayList(); + static int n; + static void gen() { + if (cur.size() == n) { + check(cur); // check current permutation for validity, or print it, etc. + return; + } + for (int i = 0; i < n; ++i) if (!used[i]) { + used[i] = true; cur.add(i+1); + gen(); + used[i] = false; cur.remove(cur.size()-1); + } + } + static void genPerm(int _n) { + n = _n; used = new boolean[n]; + gen(); + } + public static void main(String[] Args) { + genPerm(5); + } +} +``` + + + + + +## Backtracking + + + + + + + +No (current) bronze problem should require pruning ... + +## Problems + + + + \ No newline at end of file diff --git a/content/2_Bronze/Gen_Perm.mdx b/content/2_Bronze/Gen_Perm.mdx deleted file mode 100644 index 239b389..0000000 --- a/content/2_Bronze/Gen_Perm.mdx +++ /dev/null @@ -1,126 +0,0 @@ ---- -id: gen-perm -title: "Generating Permutations" -author: Darren Yao, Sam Zhang -description: "Methods to generate all permutations of an array, a common technique associated with complete search." -frequency: 1 -prerequisites: - - intro-complete ---- - -import { Problem } from "../models"; - -export const problems = { - permSam: [ - new Problem("CSES", "Creating Strings I", "1622", "Intro|Easy", false, [], "all perms of string"), - ], - ex: [ - new Problem("Bronze", "Photoshoot", "988", "Normal", false, [], ""), - ], - perm: [ - new Problem("CSES", "Chessboard and Queens", "1624", "Normal", false, [], "Recursively backtrack. See CSES book for more details."), - new Problem("Bronze", "Livestock Lineup", "965", "Hard", false, ["permutations"], ""), // 91.95 - ] -}; - - - -
- -A **permutation** is a reordering of a list of elements. Some problems will ask for an ordering of elements that satisfies certain conditions. In these problems, if $N \leq 10$, we can probably iterate through all permutations and check each permutation for validity. For a list of $N$ elements, there are $N!$ ways to permute them, and generally we'll need to read through each permutation once to check its validity, for a time complexity of $O(N \cdot N!)$. - - - - - -## Lexicographical Order - -This term is mentioned quite frequently: - - - -Think about how are words ordered in a dictionary. (In fact, this is where the term "lexicographical" comes from.) - -In dictionaries, you will see that words beginning with the letter 'a' appears at the very beginning, followed by words beginning with 'b', and so on. If two words have the same starting letter, the second letter is used to compare them; if both the first and second letters are the same, then use the third letter to compare them, and so on until we either reach a letter that is different, or we reach the end of some word (in this case, the shorter word goes first). - -Permutations can be placed into lexicographical order in almost the same way. We first group permutations by their first element; if the first element of two permutations are equal, then we compare them by the second element; if the second element is also equal, then we compare by the third element, and so on. - -For example, the permutations of 3 elements, in lexicographical order, are - -$$ -[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. -$$ - -Notice that the list starts with permutations beginning with 1 (just like a dictionary that starts with words beginning with 'a'), followed by those beginning with 2 and those beginning with 3. Within the same starting element, the second element is used to make comparisions. - -Generally, unless you are specifically asked to find the lexicographically smallest/largest solution, you do not need to worry about whether permutations are being generated in lexicographical order. However, the idea of lexicographical order does appear quite often in programming contest problems, and in a variety of contexts, so it is strongly recommended that you familiarize yourself with its definition. - -## Checking Permutations in Lexicographical Order - -What's going to be in the `check` function depends on the problem, but it should verify whether the current permutation satisfies the constraints given in the problem. - - - - - -### Method 1 - -($O(N\cdot N!)$ code) - - - -### Method 2 - - - - - -Alternatively, we can just use the [`next_permutation()`](https://en.cppreference.com/w/cpp/algorithm/next_permutation) function. This function takes in a range and modifies it to the next greater permutation. If there is no greater permutation, it returns false. To iterate through all permutations, place it inside a `do-while` loop. We are using a `do-while` loop here instead of a typical `while` loop because a `while` loop would modify the smallest permutation before we got a chance to process it. - -```cpp -do { - check(v); // process or check the current permutation for validity -} while(next_permutation(v.begin(), v.end())); -``` - -Each call to `next_permutation` makes a constant number of swaps on average if we go through all $N!$ permutations of size $N$. - - - - - -```java -import java.util.*; - -public class Test { - static boolean[] used; - static ArrayList cur = new ArrayList(); - static int n; - static void gen() { - if (cur.size() == n) { - check(cur); // check current permutation for validity, or print it, etc. - return; - } - for (int i = 0; i < n; ++i) if (!used[i]) { - used[i] = true; cur.add(i+1); - gen(); - used[i] = false; cur.remove(cur.size()-1); - } - } - static void genPerm(int _n) { - n = _n; used = new boolean[n]; - gen(); - } - public static void main(String[] Args) { - genPerm(5); - } -} -``` - - - - - -### Problems - - \ No newline at end of file diff --git a/content/2_Bronze/Intro_Complete.mdx b/content/2_Bronze/Intro_Complete.mdx index 0fc3dee..8b21022 100644 --- a/content/2_Bronze/Intro_Complete.mdx +++ b/content/2_Bronze/Intro_Complete.mdx @@ -9,31 +9,26 @@ frequency: 4 import { Problem } from "../models"; export const problems = { - easier: [ - new Problem("CSES", "Apple Division", "1623", "Intro|Very Easy", false, ["Recursion"], "all $2^n$ subsets"), + probs: [ new Problem("Bronze", "Diamond Collector", "639", "Easy", false, ["Nested Loop"], "fix the min"), // 99.9 new Problem("Bronze", "Milk Pails", "615", "Easy", false, ["Nested Loop"], "Hint: Fix the number of first-type operations you perform."), // 99.71 - new Problem("Bronze", "Bovine Genomics", "736", "Easy", false, ["Nested Loop"], ""), // 99.73 - new Problem("Bronze", "Cow Gymnastics", "963", "Easy", false, ["Nested Loop"], "Hint: Brute force over all possible pairs."), // 99.93 - new Problem("Bronze", "Where Am I?", "964", "Easy", false, [], "Hint: Brute force over all possible substrings."), // 99.48 - new Problem("Bronze", "Triangles", "1011", "Easy", false, [], "loop over the possible right angles"), // 98.02 - ], - harder: [ + new Problem("Bronze", "Bovine Genomics", "736", "Normal", false, ["Nested Loop"], ""), // 99.73 + new Problem("Bronze", "Cow Gymnastics", "963", "Normal", false, ["Nested Loop"], "Hint: Brute force over all possible pairs."), // 99.93 + new Problem("Bronze", "Where Am I?", "964", "Normal", false, [], "Hint: Brute force over all possible substrings."), // 99.48 + new Problem("Bronze", "Triangles", "1011", "Normal", false, [], "loop over the possible right angles"), // 98.02 new Problem("Bronze", "Lifeguards", "784", "Normal", false, [], "Hint: Try removing each lifeguard one at a time."), // 98.76 - new Problem("Bronze", "Photoshoot", "988", "Normal", false, [], "Hint: Figure out what exactly you're complete searching."), // 98.45 - new Problem("Bronze", "Back & Forth", "857", "Hard", false, [], "exponential time going through all possibilities"), // 99.63 - new Problem("Bronze", "Field Reduction", "641", "Hard", false, [], "Hint: For this problem, you can't do a full complete search; you have to do a reduced search."), // 91.75 new Problem("Bronze", "Circle Cross", "712", "Hard", false, [], "For every pair, check if they cross (draw small cases to figure out how). Be careful about overcounting."), // 89.6 - new Problem("Silver", "Bovine Genomics", "739", "Hard", false, [], "Brute force every substring and check if they explain spottiness."), new Problem("Bronze", "Load Balancing", "617", "Very Hard", false, [], ""), // 82.79 new Problem("Bronze", "Bull in a China Shop", "640", "Very Hard", false, [], "lots of WA on this one"), // 47.38 - new Problem("Silver", "Field Reduction", "642", "Very Hard", false, [], ""), ], }; + + + + - module is based off this - + module is based off this
@@ -111,10 +106,4 @@ A couple notes: ## Problems -### Easier - - - -### Harder - - \ No newline at end of file + diff --git a/content/3_Silver/Unordered.mdx b/content/3_Silver/Unordered.mdx index f530ad8..4983dc3 100644 --- a/content/3_Silver/Unordered.mdx +++ b/content/3_Silver/Unordered.mdx @@ -20,7 +20,8 @@ export const problems = { standard: [ new Problem("CSES", "Sum of Two Values", "1640", "Easy", false, [], "Brute force one value by going through a[], then check if the other exists."), new Problem("Bronze", "Where Am I?", "964", "Easy", false, [], "Store all substrings in a map of , and then find the longest length such that no substring of that length appears twice."), - new Problem("Silver", "Cities & States", "667", "Hard", false, [], "Store two maps of counts for the first two letters of a city and state code, then iterate over the cities and use the maps to efficently query for the corresponding counts."), + new Problem("Silver", "Bovine Genomics", "739", "Easy", false, [], ""), + new Problem("Silver", "Cities & States", "667", "Normal", false, [], "Store two maps of counts for the first two letters of a city and state code, then iterate over the cities and use the maps to efficently query for the corresponding counts."), ], }; diff --git a/content/ordering.ts b/content/ordering.ts index 625eb67..c0edfbc 100644 --- a/content/ordering.ts +++ b/content/ordering.ts @@ -79,7 +79,7 @@ const MODULE_ORDERING: {[key in SectionID]: Chapter[]} = { description: "Solving bronze problems by checking all possible cases in the solution space.", items: [ "intro-complete", - "gen-perm" + "complete-rec", ] }, { -- cgit v1.2.3-70-g09d2