<h3>Little Red Riding Hood and Candy Factory</h3>↵
The problem basically asks to check if the integer is even or odd. As integer is very large you can check if last digit is even or odd to decide the ans. If the integer is even than the ans is <b>YES</b> else ans is <b>NO</b>↵
<h3>Little Red Riding Hood and Convolutions</h3><br>↵
Convolution(L) = L1*L2*L3*L4 + L2*L3*L4*L5 + ........<br>↵
Since only allowed values for L[i] is 1 or -1, we can say that the number of terms (L<sub>i</sub>*L<sub>j</sub>*L<sub>k</sub>*L<sub>l</sub>) which evaluates to -1 are equal to number of terms which evaluates to 1. So, if we negate the given list the number of terms which evaluates to -1 or 1 doesn't change and we get another list L' whose Convolution(L') = 0↵
<h3>An Unfair Fair Game</h3><br>↵
Greedy, O(k):<br>↵
Lets start with simple greedy solution. Given n, subtract k, k-1, k-2 from n till the residue of number is between 0 to k. If the residue is non-zero, add the remaining number to the answer set, and report (k — the cardinality of the answer set).<br>↵
Optimizing greedy to just count the cardinality, O(log(k)):<br>↵
Observe that the numbers we are subtracting form a simple AP, {k, k-1, …, k-x}. The sum of this is S(x): k*(k+1)/2 — (k-x-1)*(k-x)/2. This is a strictly decreasing function in the range x = [1, k]. We can do binary search to find the first non-negative value of S(x). Let this value occur at x = z, answer is (k — (z + (s(z) == 0))).<br>↵
Expected complexity : O(log(k))↵
<h3>Graph Sum</h3><br>↵
Editorial will be published laterWe have to support two queries, add a value to a vertex and print the subtree sum.<br>↵
Finding the value:<br>↵
<ul>↵
<li>if m is odd then no. of ways to form m by 2 and 4 is zero.</li>↵
<li>if m is even then no. of ways is equal to the no. of ways of forming m/2(let say R = m/2) by 1 and 2.<br>↵
which is actually SIGMA(i = 0 to R-1) ((R-i-1) Choose (i)) which is fibonacci number Fib(R)</li></ul>↵
↵
Taking last 5 digits is nothing but mod operation with 10<sup>5</sup>. Fib(R) repeats after 150000 when we take mod with 10<sup>5</sup>.<br>↵
Now add the (no. of ways) * m to every vertex in path from v to vertex 1(root). Use HLD to perform the query.<br>↵
Expected Complexity : O(N*log<sup>2</sup>(N))<br>↵
HLD Tutorial : [Tutorial](http://blog.anudeep2011.com/heavy-light-decomposition)↵
<h3>Code Land</h3><br>↵
The problem statement reduces to this:<br>↵
Given an undirected weighted graph and information of weights of every edge. Remove one bridge and add another such that the weight of the graph is maximized.<br>↵
Lets see what the brute force solution for this will be. Lets try adding every edge and removing minimum weight bridge corresponding to that edge. The complexity of this solution will be O(n<sup>3</sup>).<br>↵
Lets see how we can optimize this code.<br>↵
Claim 1: Every bridge of the graph will be in ST.<br>↵
Proof : Let say tree T is a ST of graph but there is an edge e (x, y) which is not in this ST. Now, as e is not in ST than there is no way to go from x to y (By definition of bridge. The bridge is the only way to reach y from x). That means ST is not connected and hence is not ST, Therefore every bridge of the graph has to be in the ST.<Br>↵
Now, we have a ST which contains all the nodes and all the bridges. Lets find the minimum weight bridge between every pair of nodes (n1, n2). Since, now we have a tree there is only one path from any one node to another, we can find this minimum weight bridge between every pair of nodes by doing n dfs.<br>↵
Now, lets try out our original solution. Since, now we know the minimum weight bridge for every pair of node we can do the same solution in O(n<sup>2</sup>).<br>↵
Final running time : O(n<sup>2</sup>)<br>↵
<h3>Range Query</h3><br>↵
To solve this problem we will use MO's algorithm. If we have sorted our queries with MO's. We can than use range query and range update data structures to solve the problem. For any add or remove we need to update [A[i] — k, A[i] + K] and correspondingly we will add and subtract cnt of range [A[i] — k, A[i] + k] from our ans.<br>↵
We need to use BIT rather than Segment tree (I tried with both and there was a huge difference between time taken to generate ans by both codes. I think the reason for this was recursion but not sure. If anyone know the exact reason please comment.).<br>↵
Expected complexity : O(n*sqrt(n)*log(n))<br>↵
Sources for MO's algorithm : [Tutorial](http://blog.anudeep2011.com/mos-algorithm/)<br>↵
↵
If you find any issues with the editorials let us know. Thanks for participating. :)↵
The problem basically asks to check if the integer is even or odd. As integer is very large you can check if last digit is even or odd to decide the ans. If the integer is even than the ans is <b>YES</b> else ans is <b>NO</b>↵
<h3>Little Red Riding Hood and Convolutions</h3><br>↵
Convolution(L) = L1*L2*L3*L4 + L2*L3*L4*L5 + ........<br>↵
Since only allowed values for L[i] is 1 or -1, we can say that the number of terms (L<sub>i</sub>*L<sub>j</sub>*L<sub>k</sub>*L<sub>l</sub>) which evaluates to -1 are equal to number of terms which evaluates to 1. So, if we negate the given list the number of terms which evaluates to -1 or 1 doesn't change and we get another list L' whose Convolution(L') = 0↵
<h3>An Unfair Fair Game</h3><br>↵
Greedy, O(k):<br>↵
Lets start with simple greedy solution. Given n, subtract k, k-1, k-2 from n till the residue of number is between 0 to k. If the residue is non-zero, add the remaining number to the answer set, and report (k — the cardinality of the answer set).<br>↵
Optimizing greedy to just count the cardinality, O(log(k)):<br>↵
Observe that the numbers we are subtracting form a simple AP, {k, k-1, …, k-x}. The sum of this is S(x): k*(k+1)/2 — (k-x-1)*(k-x)/2. This is a strictly decreasing function in the range x = [1, k]. We can do binary search to find the first non-negative value of S(x). Let this value occur at x = z, answer is (k — (z + (s(z) == 0))).<br>↵
Expected complexity : O(log(k))↵
<h3>Graph Sum</h3><br>↵
Finding the value:<br>↵
<ul>↵
<li>if m is odd then no. of ways to form m by 2 and 4 is zero.</li>↵
<li>if m is even then no. of ways is equal to the no. of ways of forming m/2(let say R = m/2) by 1 and 2.<br>↵
which is actually SIGMA(i = 0 to R-1) ((R-i-1) Choose (i)) which is fibonacci number Fib(R)</li></ul>↵
↵
Taking last 5 digits is nothing but mod operation with 10<sup>5</sup>. Fib(R) repeats after 150000 when we take mod with 10<sup>5</sup>.<br>↵
Now add the (no. of ways) * m to every vertex in path from v to vertex 1(root). Use HLD to perform the query.<br>↵
Expected Complexity : O(N*log<sup>2</sup>(N))<br>↵
HLD Tutorial : [Tutorial](http://blog.anudeep2011.com/heavy-light-decomposition)↵
<h3>Code Land</h3><br>↵
The problem statement reduces to this:<br>↵
Given an undirected weighted graph and information of weights of every edge. Remove one bridge and add another such that the weight of the graph is maximized.<br>↵
Lets see what the brute force solution for this will be. Lets try adding every edge and removing minimum weight bridge corresponding to that edge. The complexity of this solution will be O(n<sup>3</sup>).<br>↵
Lets see how we can optimize this code.<br>↵
Claim 1: Every bridge of the graph will be in ST.<br>↵
Proof : Let say tree T is a ST of graph but there is an edge e (x, y) which is not in this ST. Now, as e is not in ST than there is no way to go from x to y (By definition of bridge. The bridge is the only way to reach y from x). That means ST is not connected and hence is not ST, Therefore every bridge of the graph has to be in the ST.<Br>↵
Now, we have a ST which contains all the nodes and all the bridges. Lets find the minimum weight bridge between every pair of nodes (n1, n2). Since, now we have a tree there is only one path from any one node to another, we can find this minimum weight bridge between every pair of nodes by doing n dfs.<br>↵
Now, lets try out our original solution. Since, now we know the minimum weight bridge for every pair of node we can do the same solution in O(n<sup>2</sup>).<br>↵
Final running time : O(n<sup>2</sup>)<br>↵
<h3>Range Query</h3><br>↵
To solve this problem we will use MO's algorithm. If we have sorted our queries with MO's. We can than use range query and range update data structures to solve the problem. For any add or remove we need to update [A[i] — k, A[i] + K] and correspondingly we will add and subtract cnt of range [A[i] — k, A[i] + k] from our ans.<br>↵
We need to use BIT rather than Segment tree (I tried with both and there was a huge difference between time taken to generate ans by both codes. I think the reason for this was recursion but not sure. If anyone know the exact reason please comment.).<br>↵
Expected complexity : O(n*sqrt(n)*log(n))<br>↵
Sources for MO's algorithm : [Tutorial](http://blog.anudeep2011.com/mos-algorithm/)<br>↵
↵
If you find any issues with the editorials let us know. Thanks for participating. :)↵
