Some thoughts around fenwick trees

References

• Questions
• https://codeforces.com/contest/863/problem/E
• https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/
• Two's complement : https://en.wikipedia.org/wiki/Two%27s_complement
• Proof of correctness : https://cs.stackexchange.com/questions/86835/proof-of-fenwick-trees-correctness
• Range update point query : https://cp-algorithms.com/data_structures/fenwick.html#2-range-update-and-point-query

Details

How does it work?

Sigh.

Again divide things into power of 2s.

All about $x \& (-x)$

This gives back the last set bit in a number $x$.

How do you represent $-x$?

So we use 2's complement to represent signed integers in binary. This just means that $-x_2 = 2^n - x$
So let's say we want to represent -6, then we find the bitwise representation of $6 = (0110)_2$
Now to find $-6 = 2^4 - 6 = 16 - 6 = 10 = (1010)_2$

Another way to do this is to just change the first bit from 0 to 1, where 1 always represents a negative number, then flip all the remaining bits (perform a bitwise not operation), and then add 1.

Again $6 = (0110)_2$

So $-6 = (1001)_2 + 1_2 = (1010)_2$

2's complement is the standard way to represent negative numbers in almost all hardwarres.
 

Finding the last set bit now

A very good explanation for this is present at : https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

Let's say you have $x = a1b$ where 1 is the last set bit, b is all zeroes, and a can have both 1s and 0s.

We know that $-x = (a1b)' + 1$, where $'$ means NOT operation.

$-x = a'0(1...1) + 1 = a'1(0...0)$

So if we do $x \& -x = (a1b) \& a'1(0...0) = (0...0)1(0...0)$
That's why this operation works to find the last set bit in the number.

How does that help with fenwick trees?

Let's first work for the standard fenwick tree use case of point update, range query, where we can update certain indices with different running values, and in between we can have range queries.

For example : Let's say this array is already present : [1, 3, 0, 2, 5]

As operation 1, we say that add 1 to index 3, then this becomes : [1, 3, 1, 2, 5]

Then as operation 2, we ask what is the sum of elements in the range 2 to 4, so the answer would be 3 + 1 + 2 = 6.

The last significant bit represents the size of the range that the current number supports. So for example, $lsb(10) = 2$ so it supports two indexes - 9 and 10. When we add $lsb$ to itself, then we find another range. So $10 + lsb(10) = 10 + 2 = 12$, where 12 represents 9, 10, 11 and 12 - therefore whatever we are updating in 10, needs to get updated in 12 as well.

So basically, there are multiple overlapping ranges, which have the same index - therefore when this index is updated, all of these ranges are required to be updated.

Now LSB is the range of numbers that $i$ covers. If I *add* LSB to $i$, then it will give us a number that will have a higher LSB. That means that by default, that number would contain $i$ in it's range.

But how do we ensure that all relevant indexes that cover this index are updated?

When we are going up the tree, we add $LSB(i)$ to $i$ - but why this specifically? And what if this doesn't cover all the indexes that cover i? In that case we would miss updating some valid indexes, and one of our query operations would be wrong.

How do we do range update and point queries?

Ref : https://cp-algorithms.com/data_structures/fenwick.html#2-range-update-and-point-query

Consider a case where as an operation you can update ranges, and then you need to query the values at some points, after these range updates.

We can use fenwick trees here, by re-using the point-update, range query method above.

This stems from the basic pre-fix sum method of ranges. If you have a set of ranges, and you want to query the number of ranges covering a point, you can just put a +1 at L and -1 at R + 1. Then you can start from the leftmost point, and keep on adding till the right.

For example, let's say we have an array of size 5 : [0, 0, 0, 0, 0] and we have the following ranges:
1. [1,3]
2. [3,4]
3. [1,5]
4. [4,5]

Now for each index, we want to find the number of ranges covering them. So using the above mentioned methodology:

1. [1,3] : [1, 0, 0, -1, 0]
2. [3,4] : [1, 0, 1, -1, -1]
3. [1,5] : [2, 0, 1, -1, -1]
4. [4,5] : [2, 0, 1, 0, -1]
Let's make this a pre-fix array:

[2, 2, 3, 3, 2]

Now 1 is covered by 2 ranges : [1,3] and [1, 5] - so this is correct
2 is covered by the same two ranges
3 is covered by 3 ranges : [1,3], [3, 4] and [1,5]
4 is covered by 3 ranges as well : [3, 4], [1, 5] and [4,5]
5 is covered by 2 ranges : [1, 5] and [4, 5]

Therefore this method indeed works

How to do that via fenwick trees:

Let's say we have an empty array of size 5 : [0, 0, 0, 0, 0], and we want to update a range [2,3] with 1s. So this becomes : [0, 1, 1, 0, 0]

We can use a fenwick tree for this by:
1. For range [2,3], increase by 1, the index 2 in the BIT.
    1. So this will mean that in the tree : [0, 1, 0, 1, 0] will happen, because an update in 2 will mean an update in 4 as well.
2. Now for range above 3 (that is from index 4), decrease that by 1 : That will update only 4 : [0, 1, 0, 0, 0]
3. Now when you query for index 1, you get 0
4. When you query for index 2, you get 1
5. When you query for index 3, you get 1
6. When you query for index 4 you get 0
7. When you query for index 5 you get 0

Some thoughts around sparse tables

References

• https://cp-algorithms.com/data_structures/sparse-table.html
• Problems:
• https://codeforces.com/blog/entry/70418
• Very good : https://codeforces.com/blog/entry/101083
• https://codeforces.com/blog/entry/75611
• There is something called as a [[Disjoint sparse trees]] as well

Details

What's the main idea?

The major use case that sparse tables solve is the range minimum query - for an immutable array, in $O(1)$ time.

The main idea behind that is : If I want to get the minimum of a range say $[L,R]$ = then that's equivalent to saying $min(min(L, L + k), min(R - k + 1, R))$ where $k \geq \frac{L + R} {2}$. This is because even if some middle elements in the range are common in both the ranges, the output still remains correct.

If you've this minimum of sub-ranges already pre-calculated for ks of appropriate size, then this operation can be done in $O(1)$ time.
 

How's the pre-calculation done here?

We can keep ranges like this:
- For every index inside the array - we keep the minimums for all powers of 2 (only until it makes sense, that is at max $log_2(n)$ where $n$ is the size of the array).

So let's say we have an array like this : [1, 2, 9, 4, 11]

Here, if we are talking from the perspective of index = 1, which is 2, then we will keep:

• Range of size 1 ( $= 2^0$ ) from index = 1, has min = 2 (only 2 in the current range)
• Range of size 2 ($=2^1$) from index = 1, has min = 2 (2 and 9 in the current range)
• Range of size 4 ($=2^2$) from index = 1, has min = 2 (2, 9, 4 and 11 in the current range)
• Range of size 8 - not possible, as array size itself is just 5.

We save this information for all the indexes of the array. This, therefore is saved inside a 2-D matrix. Let's call this matrix $st$, where $st[i][j]$ = minimum for the range from index $i$ of size $2^j$

Therefore note that $st[i][0]$ will just be the array itself.

Now we can calculate this easily by noticing that for a range of size 4, you can get the answer from ranges of sizes 2. That is for min of [a, b, c, d], you can use the min of [a, b] and [c, d].

Therefore we can calculate each power of 2 level-wise, and use that to calculate the next level.

Therefore we can say:

$$ st[i][j] = min(st[i][j - 1], st[i + (1<<(j - 1))][j - 1]) $$

This just means that for the range of size $2^j$, we are making use of two ranges of size $2^{j-1}$. One that starts from $i$ and goes until the middle element of the range : $i + (1<<(j - 1)) - 1$. Second that starts from next of the middle element : $i + (1<<(j - 1))$, till the end of the range which is $i + 2 \times (1 << (j - 1))$ which is just equal to $i + (1<<j)$. That's how this calculation works under the hood.

Now once $st$ is pre-calculated, you can use this to answer range minimum queries.

Let's say you need to find the min for the range $[L, R]$, you can do so by:
1. Find the size of the range = $R - L + 1$
2. Find the largest power of 2 that is lower or equal to this range = $log_2(R - L + 1)$. Let's call this $h$
3. Now use $h$ to calculate : $min(st[L][h], st[R - (1<<h) + 1][h]$

The final output will give you the min of the range. 

1476D - Journey

Tags :

Problem statement

Link : https://codeforces.com/contest/1476/problem/D
 

Gist

There are $n$ cities, connected by one directional roads (L or R). If you move from one city to it's neighbouring city, then the direction of the roads reverses. Find the number of unique cities visitable from each city.

$1 \leq t \leq 10^4$

$1 \leq n \leq 3 \times 10^5$

Solution

Let's say that the current world is the normal world. If you move one time then all the roads are reversed, then we would have a "reversed" world.

Inference 1 : Even and odd moves affecting output world

If I am at city A, and I take odd number of moves to reach city B. Then if at A I was in the normal world, then at B I would be in the reversed world. But if I take even number of moves to reach city B, then I would be in the normal world.

We can create two DPs here : Ldp and Rdp.

Ldp[i] will have two values, 0 -> Number of cities visited, and reached city i while ending in a normal world. 1 -> Number of cities visited, and reached city i while ending in a reversed world. Note that Ldp will only consider reaching the city i from it's left.

Similarly, Rdp[i] will also have two values, 0 -> Number of cities visited, and reached city i while ending in a normal world. 1 -> Number of cities visited, and reached city i while ending in a reversed world. Note that Rdp will only consider reaching the city i from it's right.

Inference 2 : To end up in a normal world, the previous world should be reversed.

If I want to end up in a normal world, then the previous state should be a reversed world - because in one step, the reversed world will become the normal world.

Therefore to calculate $Ldp[i][0]$ we can use $Ldp[i-1][1]$ and check whether the road joining them is L in the normal world. This is because in the reversed world this L will be a R, therefore you can go from $i-1$ to $i$. If yes, then $Ldp[i][0] = Ldp[i-1][1] + 1$ otherwise it will be zero.

Similarly to calculate $Ldp[i][1]$ we can use $Ldp[i-1][0]$ and check whether the rod joining them is R in the normal world - because $Ldp[i-1][0]$ suggests that it's a normal world.

We do the similar thing to find $Rdp$.

Now for each city $i$ we have $Ldp[i][0]$, $Ldp[i][1]$, $Rdp[i][0]$ and $Rdp[i][1]$. We need to find a way to combine these to find our answer.

Inference 3 : $Ldp$ is an arrow from left to city $i$ and $Rdp$ is an arrow from right to left to city $i$

We can see $Ldp$ and $Rdp$ as arrows *towards* the city $i$ - so they can't just be added without thought.

Inference 4 : Even length paths between two cities are bi-directional

Consider that A->B<-C->D<-E

The reverse world is A<-B->C<-D->E

You can go from A -> B, then B->C, then C->D then D->E

Similarly, you can go from E->D, then D->C then C->B and then B->A

Inference 5 : Reverse of even length paths is useless

A->B<-C is useful

A<-B->C has no use

Inference 6 : Reverse of odd paths are useful

A->B<-C->D

A<-B->C<-D

Both of these are useful. Just the direction changes

Inference 7 : If I reach a place in odd steps, from a normal world, then it will be a reversed world at that place

A->B<-C->D

A -> B (reversed world)

B -> C (normal world)

C -> D (reversed world)

Inference 8 : Normal world even + anything works

If $Ldp[i][0]$ and $Rdp[i][0]$ both are even:

We can simply add $Ldp[i][0]$ and $Rdp[i][0]$ because we can reverse one of the arrows,

So initially it's -><- and I can reverse one arrow with no repercussions ->-> which makes a path, therefore I can add them.

Similarly, let's say one of these arrows is of odd length and the other of even length, then -><-. The even length arrow can be reversed to get ->-> OR <-<- depending upon which arrow was of even length. Again we can just add.

Inference 9 : Odd + Odd in a normal world also works

If $Ldp[i][0]$ and $Rdp[i][0]$ both are odd, then too we can add them.

Initially it looks like -><-.

If I use one arrow to reach $i$ then since the length is odd, the world becomes a reversed world. But the second arrow is an <- arrow in a normal world. Therefore we can reverse it in a reversed world. So this becomes ->-> which again is valid.

Inference 10 : We don't need to check $Ldp[i][1]$ and $Rdp[i][1]$

This is because the endings are inside reversed worlds. But if there is a path, then that would have been covered under the normal world checks because each path has cities which will be in a normal world and some cities which will be in the reversed world.

Working submission : https://codeforces.com/contest/1476/submission/308874075

1557C - Moamen and XOR

Problem statement

Link : https://codeforces.com/contest/1557/problem/C
 

Gist

You are given numbers from \[0, $2^{k}$), where you can select any number with repetitions, to create an array of size $n$. Once you do so - you then & all the numbers to get A, and ^ all the numbers to get B.

Find the number of possible arrays such that $A >= B$
 

Solution

Let's look for a case where we are looking into only the bottom $i$ bits. So we have from \[0, $2^i$) to create an array of size $n$. Now, we can divide this range into two - \[0,$2^{i-1}$) and \[$2^{i-1}$,$2^i$). Let's call them groups A and B respectively.

If we select all the $n$ numbers from group B, then the highest bit will be the $(i-1)^{th}$ bit.

Now if $n$ is even, then ^ of this highest bit will be zero. But & of the highest bit will be one - which by default makes the & greater then ^ no matter what values of the lower bits is taken. Therefore in this case, we can select any numbers from group-B = $(2^{i-1})^{n}$

If $n$ is odd, then ^ and & both are zero, which then makes this equivalent to the case, when the highest bit is equal to zero - which is equal to getting the answer for group A. That is, for $i$ we are using the answer from $i-1$.

Now let's think about picking only *some* items from the group-B. If we select odd items, then & will be zero (as all higher bits are not 1 only *some* are), but ^ will be 1. So we can not do that.

So let's think selecting even items - then both & and ^ are zero.

If we select zero items from group B = ans(i-1)

If we select 2 items from group B = $^{n}C_2$ - to decide the positions of where to put 1s $\times$ ans(i-1) (because the lower bits will need to take the responsibility of satisfying the & >= ^ condition)

Again we select 4 items from group B = $^{n}C_4 \times \text{ans(i-1)}$
...
And this goes until we reach the highest even number under n (note that not n, as we already have calculated that)

We can take the ans(i-1) as common, and pre-compute $^{n}C_2 + ^{n}C_4 + ...$

And multiply this with ans(i-1) later.

Also we need to add the case when we deliberately are not selecting any number from group B, that is again just equal to ans(i-1)

Summing all this gives you ans(i), and you can create a dp, to calculate ans(k) which would be the answer.

My submission : https://codeforces.com/contest/1557/submission/306945910
 

Learnings

- Only deep thinking can solve these problems. Surface level thinking is just a waste of time for these problems.

1528B - Kavi on pairing duty

Problem statement

Link : https://codeforces.com/problemset/problem/1528/B
 

Gist

There are $2 \times n$ points on the X-axis. You join every point to *some* other point. So it can have different permutations. A permutation is "good" if for all the connections, at least one these hold:
1. Connection A is within connection B - so let's say we have 1,2,3 and 4. And 1 and 4 are connected, and 2 and 3 are connected. So 2 and 3 is *within* 1 and 4. Therefore this works.
2. Connection A is of the same length as connection B. Again let's say we have 1,2,3 and 4. 1 and 2 are connected, and 3 and 4 are connected. Since 1 and 2's connection is of length 1 and 3 and 4's connection is also of length 1 this is a good permutation.

Given the input $n$ we need to output the number of good permutations.

Solution

Thinking

Let's think about the case of over-arches. That is, let's say you have some $n$, and you have a connection from 1 to 2n. Then you have 2n-2 points inside this connection / arch. For each of these connection & this arch, the first condition holds, as each connection is within this arch. Therefore we can just add the answer of $n-1$ input to get that value.

Let's think about the cases when there are no arches.

Can we have small arches which have the other arches within them, but are separate from other small arches? Like for example, let's say $n = 10$. Then you can divide it into 5 groups of 4 points. So can we re-use the answer for 4 here?

The issue here is that the arch of group1 and the inner connection of group2 don't satisfy any condition. Neither they are within each other - as the group 2 connection is not within group 1's arch. Nor do they have the same length, as group 2 connection is smaller than group 1's arch.

One other condition where this can work is you have a group of connections which are of the same length, which are archs for other connections which are smaller but again of the same length. So again the same rule applies like the 1 super arch. Everything inside actually satisfies the first property with these archs, so we can use the previous answers here. So instead of just adding $ans(n-1)$ we add everything from $ans(1)$ ... $ans(n-1)$ here.

Now that, that is out of the picture, besides the 1 super arch, can we have cases when connection lengths are different? If there are two connections with different lengths then one of them needs to be inside the other connection. Since we can't have groups of such archs, having smaller connections within them, then this would mean that if we have connections with different length, we need to have a composition of arches within each other. 1-10, 2-9, 3-8, 4-7, 5-6 - but this is already covered as the first case. 1-10 + $ans(8)$ as the answer of 8 will already contain this case.

Therefore from this we understand that the other case is the only one when all of the connection lengths are the same.



How do we calculate them? So basically you have $2 \times n$ points, and you want to divide them into *some* equal points. Seems like the number of factors would do? Yep.

So for $n$ we find the number of factors - all of them, and add those to $\sum_{i=1}^{n-1} ans(i)$ - and that pretty much is the answer here. This summation can be saved in a var.
 

Implementation

My implementation took 999ms when the time limit was 1000ms. Take this with a grain of salt. I think there definitely should be a better solution.

$dp[n] = (\sum_{i=1}^{n-1}dp[i]) + factors(n)$

Here finding $factors(n)$ efficiently is the main problem. I did it by keeping a vector of `unordered_map`s which kept the number of prime factors. So for example, for $12 = 2^2 \times 3^1$ we save in the map 12 : {{2,2}, {3,1}}. Now if you want to find the number of factors, you just do $(powerOf2+1) \times (powerOf3 + 1)$ = $(2 + 1) * (1 + 1)$  = 6.

12 has 1, 2, 3, 4, 6, 12 as the factors. Yes we are counting the number itself as well in this case.

You get a list of primes, using sieve of eratosthenes, and then find the first prime that divides $n$. Once you get that, you re-use $n / prime$ to query the `unoredered_map` to get it's factors, and then add 1 to the $prime$ you found. Then you use the current map to get factors, and save the map to the `unoredered_map` for $n$.

Here is the submission : https://codeforces.com/contest/1528/submission/304791168




## Learnings



## Timelog

 812B - Sagheer, the Hausmeister

Problem statement

Link : https://codeforces.com/problemset/problem/812/B

Gist

There are $n$ floors and there are some lights on in some rooms, at *some* floors. There are $m$ rooms per floor, and two stairways - one at the start and one at the end.

You can change floors only via the stairs. So implicitly there are $m + 2$ columns, and $n$ rows.

Edge cases:

- You start from the bottom-most row, from the left-most stair-case.

- You don't need to traverse all the rows. If you've turned off all the required lights, you can stop.

Solution

The solution is in the direction of dynamic programming, atleast that's how I did it (because of DP upsolving).

Observations & line of thought:

1. Let's say there are many rooms on the floor from 2,3,4,5...,10, where the light it on. In this case, 3,4,..9 are irrelevant. Only the first and the last rooms with the lights on matter.

2. There are 3 states for a floor, which need different handling in different cases

1. More than one room with lights on

2. One room with lights on

3. No room with lights on

3. For each floor, we can keep track of the minimum cost to reach the starting or the ending point. We can use that by using this cost for the previous (lower) floor.

4. If there are more than one room with lights on, then while calculating the transition cost for the first room, we need to cover the last room on the current floor.

1. This means that if there is a floor $F_2$ and it has rooms with lights on at 2 & 6, and we have floor $F_1$ and it has rooms with lights on at 3 & 7, then if you want to calculate the min cost to reach $F_2${2} then you must cover $F_2${6}, and vice versa.

1. This just means that if you're calculating from $F_1${3} to $F_2${2}, then it must have 6 in it's path, and similarly for $F_1${7} to $F_2${2}, $F_1${3} to $F_2${6} (which should have 2 in it's path) & $F_1${2} to $F_2${7} (which should have 2 in it's path)

5. If there is only a single room with lights on, then all transitions from the previous floor's starting and end points are valid, as you don't need to cover any other points

1. That is $F_1${3} to $F_2${2} is valid, even from the left (3 -> 0, change floors, and then 0 -> 2)

6. If there is no room with lights on, then we have two options, the first column, and the last one, which have stairs in them. 

1. Note that the behaviour of this case is NOT similar to the case when you've two rooms, as you can (and will) ignore the second stair. 

2. But since both options are relevant - which means that the next floor can use a transition from any of the stairs - left or right, we need to do this calculation for both of the columns.

3. Note that you can mimic the single room case, if you place the room with the lights on at the first stair - get the answer, and then at the last stair - get the answer, and the reset the floor with no rooms with lights on.

Using all these observations, I submitted my code: https://codeforces.com/contest/812/submission/299218591

/* 
"I will come again & conquer you 
because as a mountain you can't grow, but as a human, I can.” 
- Sir Edmund Hillary.

https://codeforces.com/problemset/problem/812/B
 */
#include
using namespace std ;


typedef long long ll ;
typedef long double lld ;


#define f(i,s,n) for(int i=s;i<(int)n;i++) 
#define fn(i,s,n) for(int i=s;i>=(int)n;i--)

#define fl(i,s,n) for(ll i=s;i<(ll)n;i++)
#define fln(i,s,n) for(ll i=s;i>=(int)n;i--)


template void mini(C&a4, C b4){a4=min(a4, b4); }
template void maxi(C&a4, C b4){a4=max(a4, b4); }

#define vi vector
#define vii vector>
#define vl vector
#define pb push_back 
#define X first 
#define Y second 
#define pii pair 
#define pll pair 
#define pli pair 
#define pil pair 
#define vll vector
#define all(x) x.begin(),x.end()
#define parr(x) {cout<<#x<<" :\n" ;for(auto el:x) cout<& startEnd, vector& dp, int row, int m) {
    assert(row > 0);
    
    dp[row].X = dp[row - 1].Y + endLinkCost(startEnd[row - 1].Y, startEnd[row].X, m);
    mini(dp[row].X, dp[row - 1].X + endLinkCost(startEnd[row - 1].X, startEnd[row].X, m));
    dp[row].Y = dp[row - 1].X + startLinkCost(startEnd[row - 1].X, startEnd[row].Y, m);
    mini(dp[row].Y, dp[row - 1].Y + startLinkCost(startEnd[row - 1].Y, startEnd[row].Y, m));

    if (startEnd[row].X == startEnd[row].Y) { // only a single 1 in the row
        mini(dp[row].X, dp[row - 1].X + startLinkCost(startEnd[row - 1].X, startEnd[row].X, m));
        mini(dp[row].Y, dp[row - 1].Y + endLinkCost(startEnd[row - 1].Y, startEnd[row].Y, m));

        int minVal = min(dp[row].X, dp[row].Y);
        dp[row].X = minVal;
        dp[row].Y = minVal;
    }
}

void solve() {
    int n,m;cin>>n>>m;
    vector presence(n, vi(m + 2));
    vector startEnd(n, {m + 2, -1});
    int rowsToProcess = n;
    bool emptyRowsFromTheTop = true;
    fn(i, n - 1, 0) {
        string s;cin>>s;
        f(j,0,m + 2) {
            if (s[j] == '1') {
                presence[i][j] = 1;
                mini(startEnd[i].X, j);
                maxi(startEnd[i].Y, j);
            }
        }
        if (startEnd[i].Y == -1) {
            // empty row 
            if (emptyRowsFromTheTop) {
                rowsToProcess = i;
            }
            startEnd[i].X = 0;
            startEnd[i].Y = (i == 0 ? 0 : m + 1);
        } else {
            emptyRowsFromTheTop = false;
        }
    }

    vii dp(n, {0,0});
    dp[0].Y = startEnd[0].Y;
    dp[0].X = startEnd[0].Y + (startEnd[0].Y - startEnd[0].X);

    f(i,1,rowsToProcess) {
        if (startEnd[i].Y == m + 1) {
            // set fake point at 0
            startEnd[i] = {0, 0};
            fillRowDp(startEnd, dp, i, m);
            int startDpValue = dp[i].X;

            // set fake point at m + 1
            startEnd[i] = {m + 1, m + 1};
            fillRowDp(startEnd, dp, i, m);
            int endDpValue = dp[i].Y;

            startEnd[i] = {0, m + 1};
            dp[i] = {startDpValue, endDpValue};
        } else {
            fillRowDp(startEnd, dp, i, m);
        }
    }
    
    if (rowsToProcess == 0) {
        cout<<"0\n";
    } else {
        cout<

Learnings

 - Focus on thinking more before writing a single line of code. Writing is easy, thinking is hard.

1498C - Planar reflections

Problem

We have a set of $n$ 2D planes. A particle comes from the left, and goes through all the planes. Initially it has power $k$. When this particle touches a plane, another particle with power $k-1$ is created, but in the reverse direction.

Find the total number of particles created in this process.

Note that the created particles can create more particles as they themselves hit the planes.
 

Solution

As soon as a particle hits a plane, we know that a new particle with $k-1$ power will be created in the reverse direction. And the initial particle itself will carry on, with the same power $k$.

Note that the new particle now can touch the planes that were before (on the left of) the initial particle - therefore this particle should have knowledge on how many planes are on the left of it, and how many on the right.

Note that left + right will always be $n$, therefore we can just keep track of the number of particles on the left, and the right ones will be $n - left$.

So to represent the state of a particle, we can say that there are $left$ particles to the left of it, and it has $k$ power, and it's going in the direction $dir$, which can be left or right.

We can create a memoization based DP, where we save outputs for these values in a map.

The key of the map will be $\{left, \{k, dir\}\}$  which will be represented by `pair<long long, pair<long long, long long>>` . (Even though $dir$ can be 0 / 1 I have used a `long long` here)

This map will output the total number of particles created because of this particle.

Now we can create a simple recursion based on the original statement.

$$ getDp(left, k, dir) = getDp(left, k - 1, 1 - dir) + getDp(left + 1, k, dir) $$
 Here the first item in RHS is the new particle created going in the reverse direction with 1 less power, and the second item is the original particle which now has one less plane to see.

This is pretty much the logic to the problem.

The interesting part is in the implementation itself.

I tried to submit the solution 6 times - let's iterate on each of the submission, and see how we improved it until an AC.

Implementations

Submission 1 : 1:* DP

Link : https://codeforces.com/contest/1498/submission/278463113

The DP in this case was not the one mentioned above. Instead it was different.

As a particle goes through multiple planes, with power $k$, it will create particles of power $k-1$ in the reverse direction for each such plane.

So I created the DP around that with

If the particle is going in the right direction:

$$ getDp(left, right, k, direction) = 1 + \sum _{i = 1}^{right} getDp(left + i - 1, right - i + 1, k - 1, 1 - direction)$$

If the particle is going in the left direction:

$$ getDp(left, right, k, direction) = 1 + \sum _{i = 1}^{left} getDp(left - i + 1, right + i - 1, k - 1, 1 - direction)$$

The time complexity of this is *high* (what exactly and why?) therefore this easily gave me TLE

On time complexity of the above recursion

It's basically something like $O(right \times left \times right \times ...\text{k times})$
Since $O(right) = O(left) = O(n)$, the upper bound of this is $O(n^k)$.

But let's look into the total number of items possible inside DP. That is $O(left) \times O(right) \times O(k) \times 2 = 10^3 \times 10^3 \times 10^3 \times 2 = 2 \times 10^9$

But note that $left + right = n$ always, therefore there can be only $10^3$ valid combinations of left and right (ex : both left and right can not be 1)

Therefore a tighter bound on the number of items would be then $2 \times 10^6$

Which means the total number of possible states is within limits. But the number of times these states are accessed is high. (Basically one state inside the DP is accessed multiple times, leading to a high time complexity)

Submission 2 : 1:2 DP

Link : https://codeforces.com/contest/1498/submission/278717744

In this case, I improved upon by using a DP that had a lower time complexity. Basically similar to the one as used in the description, but note that I was still using a $right$ attribute which was actually not required. At this point I started to get a WA (wrong answer) instead of a TLE.
 

Time complexity of the new recursion

Earlier we had a n-ary tree, and now a binary one, with height = $O(n)$ or $O(k)$. Total number of nodes then are $2^{O(n)} = 2 ^ {10^3}$ which is lower than the time complexity of $n^k$ mentioned above.

Note that we are memoizing the answers so actually it's not $2^{10^3}$, as unique states are again $2 \times 10^6$ only. The *number* of times a state is accessed is reduced as compared to the first submission.
 

Submission 3 : MOD

Link : https://codeforces.com/contest/1498/submission/278717889

I realized that I was not MODing the answer. After adding that, I again started to get TLEs

Submission 4 : Removing $right$

Link : https://codeforces.com/contest/1498/submission/279037448

I realized that $right$ is not actually required in the DP, so I removed it, and used only $left$.

Earlier I was getting a TLE in TC 3, and not I was getting a TLE in TC 25, so this was an improvement
 

Exact improvements after removing the concept of `right`

I think the item size inside the map reduced, and that might have lead to some constant improvement in querying of the map.

As mentioned here : https://stackoverflow.com/a/22607155/5345646, https://stackoverflow.com/a/1843264/5345646

During searching inside the map (which in c++ is a red black tree), we compare the keys. Bigger the key, larger the time it will take to do this comparison - though it will always be a constant proportional to the key size.
 

Submission 5 : Emphasis on the reverse key

Link : https://codeforces.com/contest/1498/submission/279275375

So the key = $\{left, k, direction\}$ should give the same output for $\{n - left, k, 1 - direction\}$ because it's basically the same situation but in the reverse direction.

I tried to save this reverse key as well inside the DP when we calculate the main key, but that caused MLEs.
 

Submission 6 : Total removal of the reverse key concept

Link : https://codeforces.com/contest/1498/submission/279275427

As soon as I removed the concept of $reverseKey$ totally, the submission was accepted. This might not be because of asymptotic improvements, but instead because of constant improvements - because we are no longer making `count` calls on a `Map` which is $O(log\text{ } n)$. In this case if $n$ is large enough, this is going to take time. 

 

How much impactful was $reverseKey$?

In this case, as soon as we removed reverse key, we removed both items from the map, and queries to the map. Removing items from the map, improves the query performance for the remaining cases, if the number of items are large. Also, removing queries directly impacts the time complexity.