##Statistics↵
Total Users/Teams who have made a submission: **754**↵
↵
Total Submissions: **4212**↵
↵
Number of distinct users/teams with correct submissions: **498**↵
↵
[Contest Link]( https://www.codechef.com/DIBZ2016)↵
↵
[Feedback form](http://goo.gl/forms/cMY4KZLEJV)↵
↵
↵
---↵
↵
↵
↵
##Winners↵
<li>Rank 1: [user:Sumeet.Varma,2016-01-31]</li>↵
<li>Rank 2: [user:amankedia1994,2016-01-31]</li>↵
<li>Rank 3: [user:PrashantM,2016-01-31]</li>↵
↵
---↵
↵
↵
↵
↵
##Shil and RasenShuriken↵
(setter: [user:_shil,2016-01-31])<br>↵
Total number of pairs such that their product is even. Count total number of odd numbers = x.<br> ↵
Product of two numbers is odd if the both numbers are odd.<br>↵
↵
Ans = **N*(N-1)/2 — x*(x-1)/2**↵
↵
---↵
↵
↵
##Shil Loves Exclusive Or↵
↵
(setter: [user:_shil,2016-01-31])<br>↵
Use the fact that Xor of 2x and 2x+1 is 1.<br>↵
Therefore xor of 1 to 4n+3 is 0.<br>↵
You can derive the appropriate answer from the following results <br>↵
F(4n+3) = 0 <br>↵
F(4n) = 4n <br>↵
F(4n+1) = 4n ^ (4n+1) = 1<br> ↵
F(4n+2) = (4n+2)^1<br>↵
↵
↵
---↵
↵
↵
↵
##Utkarsh and Random Trees↵
↵
(setter: [user:usaxena95,2016-01-31]) ↵
**Dp[i]** = expected distance of node i from root. ↵
**Dp[i] = 1 + 0.5*(Dp[i-1] + Dp[i-2])** ↵
Also an observation is that the height of the tree is equal to the distance of node N from 1. ↵
Therefore ans = **Dp[N]**. ↵
Complexity **O(N + T)** ↵
↵
This is invalid if problem is to randomly take one of last 3 nodes as parent of i. So **Dp[i] = 1 + (Dp[i-1] + Dp[i-2] + Dp[i-3]) / 3** remains analogous. But expected height is not same as **Dp[N]**.↵
↵
↵
---↵
↵
##Same Old Matrix Problem↵
↵
(setter: [user:aditya1495,2016-01-31]) ↵
↵
Solving this problem required considering some cases. ↵
↵
First we will generate 2 DP Tables:↵
↵
1.) dp[i][j] = Maximum money I can collect, moving only right or down and travelling from (1, 1) to (i, j). ↵
2.) rdp[i][j] = Maximum money I can collect, moving from (i, j) to (N, M).↵
↵
We can solve the problem using above two DP tables and splitting the possible scenarios in 6 different cases.↵
↵
Let variable RES store your answer. Initialise RES with dp[N][M], as you are sure to make this profit without any change in direction.↵
↵
Consider the following images for clarity:.↵
↵
Red arrow is the move obtained by paying P dollars. Two green arrows indicate moves before and after the move with red arrow. Which one is taken before and which one is after can easily be understood.↵
↵
**Case 1:**↵
↵
[↵
↵
Ans: dp[i][j] + A[i &mdashinus; 1][j + 1] + rdp[i][j + 1] &mdashinus; P↵
↵
**Case 2:**↵
↵
[↵
↵
Ans: rdp[i &mdashinus; 1][j + 2] + dp[i][j] + A[i][j + 1] + A[i &mdashinus; 1][j + 1] &mdashinus; P↵
↵
**Case 3:**↵
↵
[↵
↵
Ans: dp[i][j] + A[i + 1][j &mdashinus; 1] + rdp[i + 1][j] &mdashinus; P↵
↵
**Case 4:**↵
↵
[↵
↵
Ans: rdp[i + 2][j &mdashinus; 1] + dp[i][j] + A[i + 1][j &mdashinus; 1] + A[i + 1][j] &mdashinus; P↵
↵
**Case 5:**↵
↵
[↵
↵
Ans: dp[i][j] + rdp[i + 1][j] + A[i][j + 1] &mdashinus; P↵
↵
**Case 6:**↵
↵
[↵
↵
Ans: dp[i][j] + rdp[i][j + 1] + A[i + 1][j] &mdashinus; P↵
↵
Take maximum of RES with Ans for all valid cells (i, j) for all valid cases.↵
↵
Note: Don't forget that you cannot move out of grid. So make sure thatA, dp**A**, **dp**, and **rdp** values exist for required positions before processing a case. Also since money in cell can be negative, make sure that you initialize dp**dp** and **rdp** with -−INF. Many code made this mistake and got a penalty.↵
↵
---↵
↵
##Utkarsh and Sub Array Sum↵
↵
(setter: [user:usaxena95,2016-01-31])↵
How to calculate F(A) efficiently ? Lets consider the **i<sup>th</sup>** bit. Let the number of elements in **A** who has **i<sup>th</sup>** bit **ON** be **x**. Number of elements whose **i<sup>th</sup>** bit is **OFF** be **y** = N-x. Xor of a sequence of bits is 1 if the total number of 1's are odd. Number of sub sequences whose xor sum has **i<sup>th</sup>** bit **ON** = number of sub sequences having odd number of **1**.↵
↵
This can calculated by combinatorics = (Take any number of 0's)*(take odd number of 1's) = (2<sup>x</sup>)*(<sup>y</sup>C<sub>1</sub> + <sup>y</sup>C<sub>3</sub> + <sup>y</sup>C<sub>5</sub> +..+) = (2<sup>x</sup>) * (2<sup>y-1</sup>) = 2<sup>x+y-1</sup> = 2<sup>N-1</sup>. We add this to answer if **y ≥ 1**. Which means that add 2<sup>N-1</sup> to ans if OR of i<sup>th</sup> bits of A is 1 (i.e. **y ≥ 1**)↵
↵
**Result**: F(A) depends only on the length of A and **Bitwise Or** of all the elements of A.↵
↵
**F(A) = OR * 2<sup>N-1</sup>** where N = size of A.↵
So the problem was reduced to efficiently calculating the value of OR of a subarray and also deal with updates. This can be done easily with segment trees. ↵
↵
Complexity = **O(N + Q * LogN)** ([Solution](https://www.codechef.com/viewsolution/9261620) by [user:karanaggarwal,2016-01-31]) ↵
↵
If you consider each bit individually, solution will be **O(30 * Q * logN)** BIT will get TLE.↵
↵
---↵
↵
↵
##Utkarsh and Tree Labelling↵
↵
(setter: [user:usaxena95,2016-01-31]) This was supposed to be a cumbersome hurdle which had a subtle solution.↵
↵
One way to solve it is<ul>↵
<li> Do a DFS order</li>↵
<li>Travel in reverse order</li>↵
<li>You need to know the sum of all the unique elements in the range L..R</li>↵
<li>This can be done as in [DQUERY](http://www.spoj.com/problems/DQUERY/) using BIT and map storing the last occurrence of a all values.↵
</li>↵
</ul>↵
↵
Another way to solve it storing for each node **v** all the unique values of F in the subtree of **v** in a set **S[v]** similar to problem Knapsack on Tree which is discussed later. ↵
↵
A very simple observation to make is that value of **F[v]** just depends on the distance of the node **v** from the farthest leaf present in the subtree of **v**. Quite a few participants were able to notice this and were able to finish subtly in 40-60 LOC. ↵
↵
How can we prove this formally? Proof by induction: ↵
**Base case:** The value of F[v] is 0 for all leaves. If Height H = 0 then F[v] is fixed = 0.↵
↵
**Assume** for any node **u** whose height is ≤ **H** has **F[u]** dependent on just **H** (i.e. F[u] = someFunction(Height(u)) )↵
↵
**Induction step:** Consider node **v** with height = **H + 1**. Let **v** have children u<sub>1</sub>, u<sub>2</sub>,..u<sub>n</sub>. It means that some children u<sub>x</sub>'s must have height = H. Other children will have height < **H**. As **subtree of u<sub>x</sub> contains nodes of all the heights from 1 to H**, all those children of **v** whose height is < **H** are useless as their F[u] value must have been present in value of some node in subtree of u<sub>x</sub>. (using induction step that **F[u]** is **independent of connectivity** of graph and just dependent on height of u if height ≤ **H**). ↵
As the other children do not contribute to the calculation of v, we can just focus on child **u<sub>x</sub>**. As F[u<sub>x</sub>] is a function of only H and only this child will contribute to calculation of **F[v]**, therefore F[v] = is a function of only H+1. ↵
↵
We can precalc the answer for any height H as Pre[H]. ↵
if(Pre[i-1] is repeated in prefix i) then Pre[i] = Pre[i-1] + (Pre[H-1]+1) * 2<sup>Pre[H-1]</sup> mod M ↵
else Pre[i] = Pre[i-1] ↵
↵
Complexity **O(N + H*LogH)** ([Solution](https://www.codechef.com/viewsolution/9259836) by [user:gvaibhav21,2016-01-31])↵
O(N) from dfs. H = height of root.↵
↵
---↵
↵
##Shil and Special XorSum ↵
↵
(setter: [user:_shil,2016-01-31]) ↵
In this problem we were required to find Σ **RMQ(i,j) ^A[i]^A[j]** where i<j. **RMQ(i,j)** gives max of all the elements from i to j. ↵
↵
We will use _divide and conquer_ approach for this problem. Suppose we are currently at state (l,r) , lets find **m** such that **A[m]** = max(A[l],A[l+1]..A[r]) and **l** ≤ **m** ≤ **r**. If there are many such **m**, pick anyone. This can be found easily using segment trees.↵
↵
Now we will process for every bit position from 0 to 19. Suppose we are considering jth bit. We will find total number of pairs **(p,q)** such that **l** ≤ **p** ≤ **m** ≤ **q** ≤ **r** and jth bit is on in **A[m]^A[p]^A[q]**.↵
↵
Let **l<sub>1</sub>** be total number of positions in **[l,m]** having j<sup>th</sup> bit on and **l<sub>0</sub>** be total number of positions in **[l,m]** having j<sup>th</sup> bit off. Similarly let **r<sub>1</sub>** be total number of positions in **[m,r]** having j<sup>th</sup> bit on and **r<sub>0</sub>** be total number of positions in **[m,r]** having j<sup>th</sup> bit off.↵
↵
If j<sup>th</sup> bit is on in **A[m]** , then total number of such **(p,q)** pairs is** (l<sub>1</sub>*r<sub>1</sub> + l<sub>0</sub>*r<sub>0</sub> -1 )**. If j<sup>th</sup> bit is off in **A[m]** , then total number of such **(p,q)** pairs is **(l<sub>1</sub>*r<sub>0</sub> + l<sub>0</sub>*r<sub>1</sub> -1)**. Hence we will add in answer 2<sup>j</sup>*(l<sub>1</sub>*r<sub>1</sub> + l<sub>0</sub>*r<sub>0</sub> -1 ) in first case and 2<sup>j</sup> *(l<sub>1</sub>*r<sub>0</sub> + l<sub>0</sub>*r<sub>1</sub> -1 ) in second case. ↵
Then we will move forward to state **(l,m-1)** and **(m+1,r)**. Solution complexity is** O(N*logN +N*20)**.↵
↵
↵
See the solution for more understanding and implementation details:<a href="https://www.codechef.com/viewsolution/9258820">solution </a> by [user:PrashantM,2016-01-31]<br>↵
The recursive solution I explained is implemented in iterative way in above solution.↵
↵
↵
---↵
↵
##Better Purchases↵
↵
(Setter [user:aditya1495,2016-01-31])↵
↵
This question is solvable by modelling it as a Minimum Cost Flow Network. Since it was a bipartite graph, min-cost matching can be used. Constraints are such that we need O(n^3) solution. We can use, for example Hungarian Algorithm which fits in time.↵
↵
M = Number of shelves<br>↵
N = Number of Companies<br>↵
C[i] = Capacity of ith shelf<br>↵
X[i] = Free goods that company i provides<br>↵
Y[i] = Charged goods that company i provides<br>↵
P[i] = Price per unit of charged good of Company i<br>↵
↵
We need some basic greedy things to clear out before we proceed. First step would be to sort the shelves in decreasing order of their capacities. Then if M > N, we'll take largest N shelves else we'll have to use all M. Let M' = min(M, N). We'll take largest M' shelves. Also, we'll take free goods from a company first and then only charged goods.↵
↵
Assume that total number of goods you will order is sum of capacities all the M' shelves i.e. fill all shelves completely. Lets name it MaxGoods.↵
We'll reduce it by counting the empty slots remaining at the end. Now, connect each company with the each shelf with flow capacity 1 and cost being as follows:↵
↵
Cost[i][j] => if (X[i] + Y[i] <= C[j]) then Y[i] * P[i] + (C[j] — X[i] — Y[i]) * INF↵
if (X[i] < C[j]) then (C[j] — X[i]) * P[i]↵
if (X[i] >= C[j]) then 0↵
↵
You can choose INF value greater than Sum (P[i] * Y[i]). Constraints permitted INF = 10^9.↵
Here (C[j] — X[i] — Y[j]) indicates the amount of free slots that will remain if we match company i with shelf j. We "charge" such a match INF for each empty slot it creates, since we want to utilize maximum space (and hence maximum goods!).↵
↵
Finding the min-cost match will give Flow = M' (obvious!). Useful part here would be the value of Cost. Since our matching will try to minimize total cost, it will try matching Companies-Shelves such that INF is used as less as possible and hence maximize goods in shelves. So the number of free slots that will be there in the end will be number of INF that you can reduce from Cost i.e Cost / INF. All the remaining cost will be contributed by charged goods. So actual cost will be Cost % INF. (% is modulo operation).↵
↵
So finally, the number of goods that we could purchase is:↵
↵
PurchasedGoods = MaxGoods — EmptySlots = MaxGoods — Cost/INF.↵
TotalCost = Cost % INF.↵
↵
Many coders tried some greedy approaches which failed testcases. Proof of failure of greedy approach is out of the scope of this write-up (unfortunately). Hence it is left as an exercise for reader. But a bruteforce solution and a test generator can do the trick in case you need such a case.↵
inus; X[i] − Y[i]) * INF<br>↵
if (X[i] < C[j]) then (C[j] − X[i]) * P[i]<br>↵
if (X[i] >= C[j]) then 0<br>↵
↵
You can choose INF value greater than Sum (P[i] * Y[i]). Constraints permitted INF = 10^9.↵
Here (C[j] − X[i] − Y[j]) indicates the amount of free slots that will remain if we match company i with shelf j. We "charge" such a match INF for each empty slot it creates, since we want to utilize maximum space (and hence maximum goods!).↵
↵
Finding the min-cost match will give Flow = M' (obvious!). Useful part here would be the value of Cost. Since our matching will try to minimize total cost, it will try matching Companies-Shelves such that INF is used as less as possible and hence maximize goods in shelves. So the number of free slots that will be there in the end will be number of INF that you can reduce from Cost i.e Cost / INF. All the remaining cost will be contributed by charged goods. So actual cost will be Cost % INF. (% is modulo operation).↵
↵
So finally, the number of goods that we could purchase is:↵
↵
**PurchasedGoods** = MaxGoods − EmptySlots = MaxGoods − Cost / INF.<br>↵
**TotalCost** = Cost % INF.↵
↵
Note that we are doing integer division in Cost / INF.↵
↵
Many coders tried some greedy approaches which failed system test cases. Proof of failure of greedy approach is out of the scope of this write-up (unfortunately). Hence it is left as an exercise for reader. But a brute-force solution and a test generator can do the trick in case you need such a case.↵
↵
---↵
↵
##Shil and Shortest Path↵
↵
(setter [user:_shil,2016-01-31])↵
<p>↵
In this problem , we need to find lexicographical K<sup>th</sup> shortest path from 1 to N. Let d[i] be the length of shortest path from any node i to N and dp[i] be total number of shortest path from any node i to N. Both of these can be found easily using BFS. Now we will build the lexicographical K<sup>th</sup> string step wise. On each step, we will decide which character to add at the end of our current string. Final string formed after processing all such steps will be our lexicographical K<sup>th</sup> shortest path string. Hence we will make d[1] such steps. ↵
</p>↵
↵
<p>↵
↵
Let STATE denotes array of all the nodes we are processing in our current step. Initially, STATE will contain only node 1. On j<sup>th</sup> step, STATE will contain all the nodes having their shortest path distance from N equal to d[1]-j+1 and that could lie on lexicographical K <sup>th</sup> shortest path.While moving for next step, we will build new STATE array and forgot our previous STATE array.At last step, STATE will contain only last node N.↵
↵
</p>↵
<p>↵
In each step, we will iterate from 'a' to 'z' until we have found the character that should be included in our string at j<sup>th</sup> step. When we find that any particular character c should be included in our string, we will add it to the string and move to j+1 <sup>th</sup> step. Now lets see how to decide that character c should be included in our string or not at certain j<sup>th</sup> step.↵
</p>↵
<p>↵
↵
In any particular step , we will iterate on all the nodes U present in our STATE array.For each node U , consider all nodes V adjacent to U such that d[V]=d[U]-1 and label of edge (U,V) is c. Let S denotes the total number of all the shortest path containing the edge (U,V) and their previous edges having the labels we have included in the string till now. If S>=K , we will include character c in our string , else we will subtract S from K and move to c+1 character.After we have decided that we should include certain character c in our string , we have to build new STATE array before moving to next step.This new STATE array can be build by inserting all the nodes V such that there exist edge (U,V) where U is present in our previous state , d[V]=d[U]-1 and label of edge (U,V) is c.↵
For calculating S and dp , we have to take special care to check for overflow since total number of shortest path in any graph could be very high.See the solution for seeing how to calculate S and implementation details.↵
</p>↵
<a href="http://ideone.com/MFOZen">solution </a>↵
↵
---↵
↵
Feel free to discuss your own strategies of solving the problems in the comments. :D
Total Users/Teams who have made a submission: **754**↵
↵
Total Submissions: **4212**↵
↵
Number of distinct users/teams with correct submissions: **498**↵
↵
[Contest Link]( https://www.codechef.com/DIBZ2016)↵
↵
[Feedback form](http://goo.gl/forms/cMY4KZLEJV)↵
↵
↵
---↵
↵
↵
↵
##Winners↵
<li>Rank 1: [user:Sumeet.Varma,2016-01-31]</li>↵
<li>Rank 2: [user:amankedia1994,2016-01-31]</li>↵
<li>Rank 3: [user:PrashantM,2016-01-31]</li>↵
↵
---↵
↵
↵
↵
↵
##Shil and RasenShuriken↵
(setter: [user:_shil,2016-01-31])<br>↵
Total number of pairs such that their product is even. Count total number of odd numbers = x.<br> ↵
Product of two numbers is odd if the both numbers are odd.<br>↵
↵
Ans = **N*(N-1)/2 — x*(x-1)/2**↵
↵
---↵
↵
↵
##Shil Loves Exclusive Or↵
↵
(setter: [user:_shil,2016-01-31])<br>↵
Use the fact that Xor of 2x and 2x+1 is 1.<br>↵
Therefore xor of 1 to 4n+3 is 0.<br>↵
You can derive the appropriate answer from the following results <br>↵
F(4n+3) = 0 <br>↵
F(4n) = 4n <br>↵
F(4n+1) = 4n ^ (4n+1) = 1<br> ↵
F(4n+2) = (4n+2)^1<br>↵
↵
↵
---↵
↵
↵
↵
##Utkarsh and Random Trees↵
↵
(setter: [user:usaxena95,2016-01-31]) ↵
**Dp[i]** = expected distance of node i from root. ↵
**Dp[i] = 1 + 0.5*(Dp[i-1] + Dp[i-2])** ↵
Also an observation is that the height of the tree is equal to the distance of node N from 1. ↵
Therefore ans = **Dp[N]**. ↵
Complexity **O(N + T)** ↵
↵
This is invalid if problem is to randomly take one of last 3 nodes as parent of i. So **Dp[i] = 1 + (Dp[i-1] + Dp[i-2] + Dp[i-3]) / 3** remains analogous. But expected height is not same as **Dp[N]**.↵
↵
↵
---↵
↵
##Same Old Matrix Problem↵
↵
(setter: [user:aditya1495,2016-01-31]) ↵
↵
Solving this problem required considering some cases. ↵
↵
First we will generate 2 DP Tables:↵
↵
1.) dp[i][j] = Maximum money I can collect, moving only right or down and travelling from (1, 1) to (i, j). ↵
2.) rdp[i][j] = Maximum money I can collect, moving from (i, j) to (N, M).↵
↵
We can solve the problem using above two DP tables and splitting the possible scenarios in 6 different cases.↵
↵
Let variable RES store your answer. Initialise RES with dp[N][M], as you are sure to make this profit without any change in direction.↵
↵
Consider the following images for clarity
↵
Red arrow is the move obtained by paying P dollars. Two green arrows indicate moves before and after the move with red arrow. Which one is taken before and which one is after can easily be understood.↵
↵
**Case 1:**↵
↵
↵
Ans: dp[i][j] + A[i &m
↵
**Case 2:**↵
↵
↵
Ans: rdp[i &m
↵
**Case 3:**↵
↵
↵
Ans: dp[i][j] + A[i + 1][j &m
↵
**Case 4:**↵
↵
↵
Ans: rdp[i + 2][j &m
↵
**Case 5:**↵
↵
↵
Ans: dp[i][j] + rdp[i + 1][j] + A[i][j + 1] &m
↵
**Case 6:**↵
↵
↵
Ans: dp[i][j] + rdp[i][j + 1] + A[i + 1][j] &m
↵
Take maximum of RES with Ans for all valid cells (i, j) for all valid cases.↵
↵
Note: Don't forget that you cannot move out of grid. So make sure that
↵
---↵
↵
##Utkarsh and Sub Array Sum↵
↵
(setter: [user:usaxena95,2016-01-31])↵
How to calculate F(A) efficiently ? Lets consider the **i<sup>th</sup>** bit. Let the number of elements in **A** who has **i<sup>th</sup>** bit **ON** be **x**. Number of elements whose **i<sup>th</sup>** bit is **OFF** be **y** = N-x. Xor of a sequence of bits is 1 if the total number of 1's are odd. Number of sub sequences whose xor sum has **i<sup>th</sup>** bit **ON** = number of sub sequences having odd number of **1**.↵
↵
This can calculated by combinatorics = (Take any number of 0's)*(take odd number of 1's) = (2<sup>x</sup>)*(<sup>y</sup>C<sub>1</sub> + <sup>y</sup>C<sub>3</sub> + <sup>y</sup>C<sub>5</sub> +..+) = (2<sup>x</sup>) * (2<sup>y-1</sup>) = 2<sup>x+y-1</sup> = 2<sup>N-1</sup>. We add this to answer if **y ≥ 1**. Which means that add 2<sup>N-1</sup> to ans if OR of i<sup>th</sup> bits of A is 1 (i.e. **y ≥ 1**)↵
↵
**Result**: F(A) depends only on the length of A and **Bitwise Or** of all the elements of A.↵
↵
**F(A) = OR * 2<sup>N-1</sup>** where N = size of A.↵
So the problem was reduced to efficiently calculating the value of OR of a subarray and also deal with updates. This can be done easily with segment trees. ↵
↵
Complexity = **O(N + Q * LogN)** ([Solution](https://www.codechef.com/viewsolution/9261620) by [user:karanaggarwal,2016-01-31]) ↵
↵
If you consider each bit individually, solution will be **O(30 * Q * logN)** BIT will get TLE.↵
↵
---↵
↵
↵
##Utkarsh and Tree Labelling↵
↵
(setter: [user:usaxena95,2016-01-31]) This was supposed to be a cumbersome hurdle which had a subtle solution.↵
↵
One way to solve it is<ul>↵
<li> Do a DFS order</li>↵
<li>Travel in reverse order</li>↵
<li>You need to know the sum of all the unique elements in the range L..R</li>↵
<li>This can be done as in [DQUERY](http://www.spoj.com/problems/DQUERY/) using BIT and map storing the last occurrence of a all values.↵
</li>↵
</ul>↵
↵
Another way to solve it storing for each node **v** all the unique values of F in the subtree of **v** in a set **S[v]** similar to problem Knapsack on Tree which is discussed later. ↵
↵
A very simple observation to make is that value of **F[v]** just depends on the distance of the node **v** from the farthest leaf present in the subtree of **v**. Quite a few participants were able to notice this and were able to finish subtly in 40-60 LOC. ↵
↵
How can we prove this formally? Proof by induction: ↵
**Base case:** The value of F[v] is 0 for all leaves. If Height H = 0 then F[v] is fixed = 0.↵
↵
**Assume** for any node **u** whose height is ≤ **H** has **F[u]** dependent on just **H** (i.e. F[u] = someFunction(Height(u)) )↵
↵
**Induction step:** Consider node **v** with height = **H + 1**. Let **v** have children u<sub>1</sub>, u<sub>2</sub>,..u<sub>n</sub>. It means that some children u<sub>x</sub>'s must have height = H. Other children will have height < **H**. As **subtree of u<sub>x</sub> contains nodes of all the heights from 1 to H**, all those children of **v** whose height is < **H** are useless as their F[u] value must have been present in value of some node in subtree of u<sub>x</sub>. (using induction step that **F[u]** is **independent of connectivity** of graph and just dependent on height of u if height ≤ **H**). ↵
As the other children do not contribute to the calculation of v, we can just focus on child **u<sub>x</sub>**. As F[u<sub>x</sub>] is a function of only H and only this child will contribute to calculation of **F[v]**, therefore F[v] = is a function of only H+1. ↵
↵
We can precalc the answer for any height H as Pre[H]. ↵
if(Pre[i-1] is repeated in prefix i) then Pre[i] = Pre[i-1] + (Pre[H-1]+1) * 2<sup>Pre[H-1]</sup> mod M ↵
else Pre[i] = Pre[i-1] ↵
↵
Complexity **O(N + H*LogH)** ([Solution](https://www.codechef.com/viewsolution/9259836) by [user:gvaibhav21,2016-01-31])↵
O(N) from dfs. H = height of root.↵
↵
---↵
↵
##Shil and Special XorSum ↵
↵
(setter: [user:_shil,2016-01-31]) ↵
In this problem we were required to find Σ **RMQ(i,j) ^A[i]^A[j]** where i<j. **RMQ(i,j)** gives max of all the elements from i to j. ↵
↵
We will use _divide and conquer_ approach for this problem. Suppose we are currently at state (l,r) , lets find **m** such that **A[m]** = max(A[l],A[l+1]..A[r]) and **l** ≤ **m** ≤ **r**. If there are many such **m**, pick anyone. This can be found easily using segment trees.↵
↵
Now we will process for every bit position from 0 to 19. Suppose we are considering jth bit. We will find total number of pairs **(p,q)** such that **l** ≤ **p** ≤ **m** ≤ **q** ≤ **r** and jth bit is on in **A[m]^A[p]^A[q]**.↵
↵
Let **l<sub>1</sub>** be total number of positions in **[l,m]** having j<sup>th</sup> bit on and **l<sub>0</sub>** be total number of positions in **[l,m]** having j<sup>th</sup> bit off. Similarly let **r<sub>1</sub>** be total number of positions in **[m,r]** having j<sup>th</sup> bit on and **r<sub>0</sub>** be total number of positions in **[m,r]** having j<sup>th</sup> bit off.↵
↵
If j<sup>th</sup> bit is on in **A[m]** , then total number of such **(p,q)** pairs is** (l<sub>1</sub>*r<sub>1</sub> + l<sub>0</sub>*r<sub>0</sub> -1 )**. If j<sup>th</sup> bit is off in **A[m]** , then total number of such **(p,q)** pairs is **(l<sub>1</sub>*r<sub>0</sub> + l<sub>0</sub>*r<sub>1</sub> -1)**. Hence we will add in answer 2<sup>j</sup>*(l<sub>1</sub>*r<sub>1</sub> + l<sub>0</sub>*r<sub>0</sub> -1 ) in first case and 2<sup>j</sup> *(l<sub>1</sub>*r<sub>0</sub> + l<sub>0</sub>*r<sub>1</sub> -1 ) in second case. ↵
Then we will move forward to state **(l,m-1)** and **(m+1,r)**. Solution complexity is** O(N*logN +N*20)**.↵
↵
↵
See the solution for more understanding and implementation details:<a href="https://www.codechef.com/viewsolution/9258820">solution </a> by [user:PrashantM,2016-01-31]<br>↵
The recursive solution I explained is implemented in iterative way in above solution.↵
↵
↵
---↵
↵
##Better Purchases↵
↵
(Setter [user:aditya1495,2016-01-31])↵
↵
This question is solvable by modelling it as a Minimum Cost Flow Network. Since it was a bipartite graph, min-cost matching can be used. Constraints are such that we need O(n^3) solution. We can use, for example Hungarian Algorithm which fits in time.↵
↵
M = Number of shelves<br>↵
N = Number of Companies<br>↵
C[i] = Capacity of ith shelf<br>↵
X[i] = Free goods that company i provides<br>↵
Y[i] = Charged goods that company i provides<br>↵
P[i] = Price per unit of charged good of Company i<br>↵
↵
We need some basic greedy things to clear out before we proceed. First step would be to sort the shelves in decreasing order of their capacities. Then if M > N, we'll take largest N shelves else we'll have to use all M. Let M' = min(M, N). We'll take largest M' shelves. Also, we'll take free goods from a company first and then only charged goods.↵
↵
Assume that total number of goods you will order is sum of capacities all the M' shelves i.e. fill all shelves completely. Lets name it MaxGoods.↵
We'll reduce it by counting the empty slots remaining at the end. Now, connect each company with the each shelf with flow capacity 1 and cost being as follows:↵
↵
Cost[i][j] => if (X[i] + Y[i] <= C[j]) then Y[i] * P[i] + (C[j] &m
if (X[i] < C[j]) then (C[j] — X[i]) * P[i]↵
if (X[i] >= C[j]) then 0↵
↵
You can choose INF value greater than Sum (P[i] * Y[i]). Constraints permitted INF = 10^9.↵
Here (C[j] — X[i] — Y[j]) indicates the amount of free slots that will remain if we match company i with shelf j. We "charge" such a match INF for each empty slot it creates, since we want to utilize maximum space (and hence maximum goods!).↵
↵
Finding the min-cost match will give Flow = M' (obvious!). Useful part here would be the value of Cost. Since our matching will try to minimize total cost, it will try matching Companies-Shelves such that INF is used as less as possible and hence maximize goods in shelves. So the number of free slots that will be there in the end will be number of INF that you can reduce from Cost i.e Cost / INF. All the remaining cost will be contributed by charged goods. So actual cost will be Cost % INF. (% is modulo operation).↵
↵
So finally, the number of goods that we could purchase is:↵
↵
PurchasedGoods = MaxGoods — EmptySlots = MaxGoods — Cost/INF.↵
TotalCost = Cost % INF.↵
↵
Many coders tried some greedy approaches which failed testcases. Proof of failure of greedy approach is out of the scope of this write-up (unfortunately). Hence it is left as an exercise for reader. But a bruteforce solution and a test generator can do the trick in case you need such a case.↵
if (X[i] < C[j]) then (C[j] − X[i]) * P[i]<br>↵
if (X[i] >= C[j]) then 0<br>↵
↵
You can choose INF value greater than Sum (P[i] * Y[i]). Constraints permitted INF = 10^9.↵
Here (C[j] − X[i] − Y[j]) indicates the amount of free slots that will remain if we match company i with shelf j. We "charge" such a match INF for each empty slot it creates, since we want to utilize maximum space (and hence maximum goods!).↵
↵
Finding the min-cost match will give Flow = M' (obvious!). Useful part here would be the value of Cost. Since our matching will try to minimize total cost, it will try matching Companies-Shelves such that INF is used as less as possible and hence maximize goods in shelves. So the number of free slots that will be there in the end will be number of INF that you can reduce from Cost i.e Cost / INF. All the remaining cost will be contributed by charged goods. So actual cost will be Cost % INF. (% is modulo operation).↵
↵
So finally, the number of goods that we could purchase is:↵
↵
**PurchasedGoods** = MaxGoods − EmptySlots = MaxGoods − Cost / INF.<br>↵
**TotalCost** = Cost % INF.↵
↵
Note that we are doing integer division in Cost / INF.↵
↵
Many coders tried some greedy approaches which failed system test cases. Proof of failure of greedy approach is out of the scope of this write-up (unfortunately). Hence it is left as an exercise for reader. But a brute-force solution and a test generator can do the trick in case you need such a case.↵
↵
---↵
↵
##Shil and Shortest Path↵
↵
(setter [user:_shil,2016-01-31])↵
<p>↵
In this problem , we need to find lexicographical K<sup>th</sup> shortest path from 1 to N. Let d[i] be the length of shortest path from any node i to N and dp[i] be total number of shortest path from any node i to N. Both of these can be found easily using BFS. Now we will build the lexicographical K<sup>th</sup> string step wise. On each step, we will decide which character to add at the end of our current string. Final string formed after processing all such steps will be our lexicographical K<sup>th</sup> shortest path string. Hence we will make d[1] such steps. ↵
</p>↵
↵
<p>↵
↵
Let STATE denotes array of all the nodes we are processing in our current step. Initially, STATE will contain only node 1. On j<sup>th</sup> step, STATE will contain all the nodes having their shortest path distance from N equal to d[1]-j+1 and that could lie on lexicographical K <sup>th</sup> shortest path.While moving for next step, we will build new STATE array and forgot our previous STATE array.At last step, STATE will contain only last node N.↵
↵
</p>↵
<p>↵
In each step, we will iterate from 'a' to 'z' until we have found the character that should be included in our string at j<sup>th</sup> step. When we find that any particular character c should be included in our string, we will add it to the string and move to j+1 <sup>th</sup> step. Now lets see how to decide that character c should be included in our string or not at certain j<sup>th</sup> step.↵
</p>↵
<p>↵
↵
In any particular step , we will iterate on all the nodes U present in our STATE array.For each node U , consider all nodes V adjacent to U such that d[V]=d[U]-1 and label of edge (U,V) is c. Let S denotes the total number of all the shortest path containing the edge (U,V) and their previous edges having the labels we have included in the string till now. If S>=K , we will include character c in our string , else we will subtract S from K and move to c+1 character.After we have decided that we should include certain character c in our string , we have to build new STATE array before moving to next step.This new STATE array can be build by inserting all the nodes V such that there exist edge (U,V) where U is present in our previous state , d[V]=d[U]-1 and label of edge (U,V) is c.↵
For calculating S and dp , we have to take special care to check for overflow since total number of shortest path in any graph could be very high.See the solution for seeing how to calculate S and implementation details.↵
</p>↵
<a href="http://ideone.com/MFOZen">solution </a>↵
↵
---↵
↵
Feel free to discuss your own strategies of solving the problems in the comments. :D
