Improving at competitive coding

 How not to bitch about solving lesser problems

Whenever I ask anyone about how to improve, all they say is "Solve more problems". Bitch. I know that. Do you have anything else to offer? 

So just like other things, this too we have to do on our own. And what does that mean? Analysis!

So I thought of all the phases of solving a problem and made this shitty diagram : 

My main aim to find the most time taking stages. What I understood was, that the main "problem solving" stage, where we think the hardest is the most important one. It might not be the one that takes most of the time itself, but surely is the one that directly affects the total time taken.

Let's just say that I as a person can solve some problem in $T$ minutes, when no re-implementation or code changes are made.

Now let's consider the case that I ran some tests on the code, and it failed for some case. Either we did some silly mistake, so we need to debug it, or our solution is wrong, and we need to rethink the problem.

In this case, again, intense thinking is required, and immense time is wasted. What we can do is make sure that the solution we're implementing is the best version we can give. It's well tested, via dry runs, and should have the least amount of bugs. 

This is a doable thing. It's more of a good habit, than a skill upgradation, as it doesn't require you to improve problem solving, but just stopping a while, testing the solution well in mind, creating some edge cases, and then  implementing it. 

This should save massive amounts of time in competitions. Let's see if this actually improves anything, or is just the intuitive thing people anyways follow. Big eh time.

1335C - Counting Triangles - How to be a bitch of a problem 101

 1355C - Counting Triangles

Problem:

So here is this 1800 rating question acting like it's not that  hard by being a Div2 C. No, fuck you 1355C, we know your truth.

The problem can be found here.

What does it say?

Well you have to make a triangle. You're given four values $A,B,C \text{ and } D$, such that $A \leq B \leq C \leq D$. Now you have two create a triangle, such that the sides of the triangle are of lengths $x,y,z$ such that, $A \leq x \leq B \leq y \leq C \leq z \leq D$. 

Initial thoughts

A triangle can be created when $ x + y \geq z $, $y + z \geq x$ and $x+z \geq y$. Since we have to have only those triangles which have a positive are, thus the equal to sign is removed. Thus $$ x+y > z \\ y + z > x \\ x+z > y $$.

But since $z$ is already greater than $x$ and $y$, you only need to consider $ x+y > z$.

Delving deeper

So, since the differences between A,B,C and D can go upto $5 \times 10^5$, forget brute force. If you have something $O(n^2)$, forget it too. We need something better here.

We have three areas (A to B for x, B to C for y and C to D for z) to cover. So, we might lean into pointers or something, I don't know I'm illiterate.

Since, I know the answer now (which I definitely knew after reading the editorial only), I don't have any other option than to delve straight into the solution.

The Solution

We take two pointers, $xp$ for $x$ and $zp$ for $z$. Now we can calculate minimum $y$, that satisfies our condition by $yp = zp-xp+1$ (remember that we had removed the equals sign).

We can check whether this $yp$ value is sane or not, by checking if it's between B and C only, but more on this later.

Now we know that a triangle can be formed by $xp$, $yp$ and $zp$. Notice that if we increase $yp$, the condition would still hold. That is, $$xp+yp > zp \\ xp+yp+1>zp$$.

Glad to know that. So, that means if we keep $xp$ and $zp$ constant, all eligible y's, from $yp$ all the way to $C$ are eligible triangles.

We can get their number as $C-yp+1$

Noice.

Now, what if we increased $xp$ by one? 

So if $$xp+yp>zp \\ xp+1+(-1)+yp>zp \\ xp + 1 + yp -1 > zp $$

What does it mean? It means that if we increase $xp$, then we can still satisfy the same condition by decreasing the value of $yp$. So, notice that in this case, our eligible triangles would increase by one from the previous case.

To be precise, it would be $C-yp+2$.

Do we see a pattern here? 

Yes. As we increase $xp$, we can decrease $yp$ and increase the number of eligible triangles.

But there should be some limit right. Yes. So you can only decrease $yp$ until $B$. Anything less is not acceptable.

So we increase the value of eligible triangles till then, which would be $C-B+1$, in the end.

But what if we still have some x's left? That is, we traversed by increasing $xp$ and decreasing $yp$. Our value of $yp$ could not be reduced anymore because it had reached it's limit $B$, but $xp$ still had not reached it's upper limit $B$. So since the current value of $xp$ satisfies the condition $xp+yp>z$, we know that if we increase $xp$, then the constraint would still be satisfied.

Notice, that in that case, the total number of eligible triangles would be limited to $C-B+1$ for each such "extra" $xp$.

Now you're getting a hang at it don't you.

Now coming back at the sanity of $yp$ initially. you should know that if intially $yp$ is greater than $C$, then no valid $y$ value satisfies that. So in that case, your $x$ was not good enough to create something greater than $z$, so you increase $xp$.

If in some case $yp$ is less than B, then voila! For all the remaining x's, you can take whole range of $y$. That is $C-B+1$.

I think this should be enough to make the core concept of the problem clear.

Anyhow, if you don't get something or something is wrong here, please leave a comment.

Here is my submission.

Gradient of a softmax classifier and it's loss function

Softmax classifier and it's gradient

The function itself:

The softmax function can be seen as:

$$ S_i = \frac{e^{a_{i}}}{\sum_{k}{e^{a_{k}}}}$$

and the loss function can be seen as:

$$L_i = -log(S_i)$$

The partial derivative as taken from here  :

If you do a partial derivative of $S_i$ w.r.t the $a_{i}^{th}$ element, then, remember the quotient rule:

If $$f(x) = \frac{g(x)}{h(x)} $$

Then,

$$f'(x) = \frac{g'(x) \times h(x) - h'(x)\times g(x)}{h(x)^2} $$

Here, $g(x) = e^{a_i}$, and $h(x) = \sum_{k}{e^{a_k}}$,

So $g'(x) = e^{a_i}$, when partially derived w.r.t $a_i$, and $g'(x) = 0$, when partially derived w.r.t $a_j$, where $j \neq i$, because in that case it'll be a constant.

$h'(x) = e^{a_j}$ always, because only one of all the terms in the summation will not be treated as a constant. All others will be treated as a constant, and thus they'll be diminished to zero after being derived. 

Thus when $i=j$, our 

$$\frac{\partial {S_i}}{\partial a_i} = \frac {e^{a_i}\times \sum - e^{a_i}\times e^{a_i}}{\sum^2} = S_i(1-S_i)$$

And when $i \neq j$

$$\frac{\partial S_i}{\partial a_j} = \frac {0 \times \sum - e^{a_i} \times e^{a_i}} {\sum^2}= -S_i \times S_j$$

Now keep these in mind. Now following this stackoverflow solution : 

$$\frac{\partial L}{\partial o_i}=-\sum_ky_k\frac{\partial \log p_k}{\partial o_i}=-\sum_ky_k\frac{1}{p_k}\frac{\partial p_k}{\partial o_i}\\=-y_i(1-p_i)-\sum_{k\neq i}y_k\frac{1}{p_k}({\color{red}{-p_kp_i}})\\=-y_i(1-p_i)+\sum_{k\neq i}y_k({\color{red}{p_i}})\\=-y_i+\color{blue}{y_ip_i+\sum_{k\neq i}y_k({p_i})}\\=\color{blue}{p_i\left(\sum_ky_k\right)}-y_i=p_i-y_i$$

And thus we have our solution! 

I took some time to understand this, so a good I decided to create some resource for me too look back to.

[Persistent Segment Trees] 351 - D Jeff and Removing Periods

351 - D - Jeff and Removing Periods

Problem statement:

Problem can be found here.The gist of the  problem is:

We're given an array $a$ of length $n$. With that we're given $q$ queries too, which are of the form $l r$. We have to answer the total number of unique numbers in that range plus if any number present with a constant gap (AP of indices) in the range then add 0, else if no such element is present then add 1.

Notice that if an element is present two or one times, then it automatically satisfied the condition mentioned

Approach:

There are two approaches to solve this question:

1. Mo's algorithm for sorting the queries and finding the answer. I have done this question and here is the solution. We will not discuss it here, since it is already discussed in the editorials.
2. Persistent segment trees. 

I followed rlac's submission to understand  this method.

Description:

You need to know about persistent segment trees, in order to understand this solution. If you don't then you can find material regarding them at these places:

• GKCS-MKTHNUM (SPOJ)
• This codechef tutorial

In my opinion, the idea isn't that much hard to understand. It's just like version control. Once you update some value, which is a leaf, you create new parents till the root, for each update.

Now to solve this problem we need two persistent segment trees:

1. To find the total number of  unique numbers for a range $l,r$
2. To find whether any element's indices follow any AP for a range $l,r$

For the first tree, the logic can be like:

We go from 0, to n-1 in this case.

You create an array pos, which saves the element's last occurrence. So, if the current element has been seen before, then we update that position with a zero (this creates a new root). Then for the current number, we update the for the current index with a 1. We can save this root as the ith root.

When queried, we can query the segment tree root r. The operation performed is the sum operation. That is, the parent's value is calculated by adding the values of the left child and the right child.

Initially, I thought why not just use a regular segment tree? But actually changing the one to zero, might affect some answers, so a regular segment tree might have not worked in that case.

Now, for the second tree, we can again use pos to save last occurrences, next_pos, to save the next position of an element in the array, and last to save the element after the last element of the AP.

Note that we go from n-1 to 0, in this case.

So, if the current element was present before, then it's index' value is set to zero for this segtree. Now if we have a next->next element, then we check if an AP is being formed. If not, then we know that two elements always form an AP, so the last value of the current element is the next->next value.

If next->next indeed follows an AP, then we have atleast three elements in AP, maybe more, maybe less. A check must have also been done for the next element which was saved in pos[a[i]]. We can save it's last value as last[i].

Now when queried, we go for the lth 2nd segment tree, and check for (l,r). Here the operator is the max. That is, the value for the parent node is calculated by taking the max of the left and right child.

If the queried result is less that r, then we know the AP got fucked up before the query r. So we know no AP is present in the range.

If the queries results is more than r, then we know that there is an AP in the given range, as the last element after the AP is more than r.

I hope this explanation helps

Here is my submission which I absolutely stole from rlac.

[Trees][Binary Lifting] 501 - D Misha And Permutations

Misha and Permutations

Problem statement:

The problem can be found here. The gist of the problem is:

You're given two permutations of $n$. Their order might be $a$, and $b$. By "order" I mean, the index of the permutation. That is, for $n=3$, $0,1,2$ is the first permutation, whereas, $2,1,0$ is the last (=6th). 

So, we have to find $(a+b)%(n!)$th permutation. 

This is it. Simple. Isn't is? 

No. Nope. Nada. Wtf is this question man?

Okay, rants apart.

Ideas:

The major point here is the conversion of order, and the permutation. We convert the initial permutations into the order. Add them. Mod by n!, and then find the resulting permutation.

There are many problems with this approach. You'll have to find ways to interconvert order and permutation, plus the mod by n!. Since $1 \leq n \leq 200000$, thus $n!$ can be a very large number. You don't want to solve, this way.

Enter the [Factorial Number System](https://en.wikipedia.org/wiki/Factorial_number_system).

As the name suggests, it's the factorial number system. Instead of bases, you have factorials! An example would be:

$$ 4\times 4! + 3\times 3!+2\times 2!+1\times 1!+0\times 0!$$.

This number in factorial representation (or factoradic) can be written as $43210_{!}$, which in decimal representation can be written as $119_{10}$. 

A good property is that, we can represent permutations using factoradics. This way, we can ignore the decimal representation altogether. But you'll say what about the n! mod? We'll come back to that later. I promise.

Pemutation to factoradic conversions:

Given a permuation $3,0,2,1$. It's factoradic representation is not simply $4132_{!}$. We have to put some mind to it. 

We have $n=4$. So we have $A\times 3! + B\times 2! + C\times 1! + D\times 0!$. We have to find the values of $A,B,C$ and $D$. 

A = We can simply do that by finding number of elements smaller than 3. That is 3. 

Now we remove 3 from consideration, and have $\{0,1,2\}$. 

B = Number of elements smaller than 0? None. So 0. Remove 0. We're left with $\{1,2\}$.

C = Number of elements smaller than 2? 1. So 1. We have $\{1\}$ left.

D = 0

So, we have $3010_{!}$, representing $3,0,2,1$. To double check, you can find the decimal value, which comes out to be: $3\times 3!+0\times 2!+1\times 1!+ 0 \times 0! = 18+0+1+0 = 19$

As you can see here, 3021, is indeed the 19th permutation for n=4. 

The basic inference you can get from here is that factoradic representation gives the rank of the number, for the remaining numbers. 

This can be done by fenwick trees / Binary indexed trees, easily.

Modulus n!: 

Thanks to Ecenerwala's solution.

So, until now, we have converted the permutations into their factoradic representations, and added them. How do we do the mod n!?

A factoradic representation is of the form (for n):

$$X_{(n-1)!}\times (n-1)!+X_{(n-2)!}\times(n-2)!+...+X_{2!}\times 2!+X_{1!}\times 1!$$.

Thus if $X_{(i-1)!}>=i$, then it can be written in the form: $X_{(i-1)!} = i+(X_{(i-1)!}-i)$. Thus, the term $$X_{(i-1)!}\times (i-1)! = i \times (i-1)! + (X_{(i-1)!}-i\times (i-1)!) \\= i!+(X_{(i-1)!}-i\times (i-1)!$$

This extra $i!$ can be added to the next greater element. So, if we percolate up to $(n-1)$, then we might get an extra $n!$ element. That's it!

Isn't that what we want? We know that there can be at most one n! extra. You can check that. (Kuchh to krlo khud se)

Code for that:

Good. Beautiful.

Factoradic to permutation conversion:

So, as I mentioned earlier, factoradic-> Rank (well actually, number of elements smaller). So you have ranks, and  you want the permutation now. Consider $3010_{!}$ again. You want the (3+1)th element, amongst $0,1,2,3$ = 3. Remove 3. $\{0,1,2\}$ left. You want the (0+1)st element. You get 0. Remaining $\{1,2\}$. You want the (1+1)nd element. You get 2. Remaining $\{1\}$. You want the (0+1)st element. You get 1. So $3,0,2,1$ formed.

This can be done by binary searching on he fenwick tree, or doing binary lifting on it. 

My submission can be found here.

[Math][Codeforces] 1247C P Binary

P Binary:

My solution:

I was giving a virtual contest for this. The question before this one took 1 hour (ughh), and thus I couldn't solve this in time. So I solved this later.

So you're given a number $n$, which we need to check how many p-binary numbers are needed to make this $n$ number. 

What are you gonna do?

So basically let's say we have $n$ which we describe using $m$ p-binary numbers. That will look like:

$$ n = (2^{x_1}+p)+(2^{x_2}+p)+...+(2^{x_m}+p)$$

That can be made to look like:

$$ n = (\sum_{i=1}^{m} 2^{x_i})+m*p$$

That is equal to:

$$ n - m*p = (\sum_{i=1}^{m} 2^{x_i}) $$

We do not know the value of $m$ here. So,we can create an array with:

$$ n-i*p$$ where i goes from ${1,...,100}$, because you don't need more than that.

Now, check the number of set bits for each number in the array, starting from the left. Once you reach a point, where $\text{number of set bits} <= i$, you stop. As you can create $i$ such elements in the expansion given above, from a lesser number of bits. Just remember that you can create 2 elements from one set bit if the number is not 1. 

For example if you have a 2 (10), you can have two 1s (01). Similarly, you can see that you can the same for 4,8, et cetera. But you can't divide 1. So remember to check that $n-i*p>=i$, which means that the number can create $i$ elements. 

The logic here is that a number $j$ can, at max, be divided into $j$ elements.

It's a good question. 

Here's the code:

[SegmentTree][SPOJ] ORDERS

ORDERS

Problem statement:

As you are probably well aware, in Byteland it is always the military officer's main worry to order his soldiers on parade correctly. In Bitland ordering soldiers is not really such a problem. If a platoon consists of n men, all of them have different rank (from 1 - lowest to n - highest) and on parade they should be lined up from left to right in increasing order of rank.
Sounds simple, doesn't it? Well, Msgt Johnny thought the same, until one day he was faced with a new command. He soon discovered that his elite commandos preferred to do the fighting, and leave the thinking to their superiors. So, when at the first rollcall the soldiers lined up in fairly random order it was not because of their lack of discipline, but simply because they couldn't work out how to form a line in correct order of ranks. Msgt Johnny was not at all amused, particularly as he soon found that none of the soldiers even remembered his own rank. Over the years of service every soldier had only learned which of the other soldiers were his superiors. But Msgt Johnny was not a man to give up easily when faced with a true military challenge. After a moment's thought a solution of brilliant simplicity struck him and he issued the following order: "men, starting from the left, one by one, do: (step forward; go left until there is no superior to the left of you; get back in line).". This did indeed get the men sorted in a few minutes. The problem was solved... for the time being.
The next day, the soldiers came in exactly the same order as the day before, and had to be rearranged using the same method. History repeated. After some weeks, Msgt Johnny managed to force each of his soldiers to remember how many men he passed when going left, and thus make the sorting process even faster.
If you know how many positions each man has to walk to the left, can you try to find out what order of ranks the soldiers initially line up in?

Input

The first line of input contains an integer t<=50, the number of test cases. It is followed by t test cases, each consisting of 2 lines. The first line contains a single integer n (1<=n<=200000). The second line contains n space separated integers w_i, denoting how far the i-th soldier in line must walk to the left when applying Msgt Johnny's algorithm.

Output

For each test case, output a single line consisting of n space separated integers - the ranks of the soldiers, given from left to right in their initial arrangement.

Example

Input:
2
3
0 1 0
5
0 1 2 0 1

Output:
2 1 3
3 2 1 5 4 

My approach:

There was an approach of mine that worked in $O(n^2 log n)$ time. So bravo I'm a genius. So I read solutions for this question everywhere, then I understood the answer, and eventually it was pretty easy.

So you're at the right most element. It says "1". That means it has one element that is greater than it on the left of it. We have 5 numbers available, 1,2,3,4 and 5. Now, if it were 3, then we would have a 2, as 4 and 5 are definitely in the array. So, no, it must be a 4. As 4 has one element that is greater than it. Cool. Now we can move forward without 4. So we have 1,2,3, and 5.

We are at the 4th position now, which says 0. So, it has no element on the left of it that is greater than it. What such element can be possible? The greatest of those left. Right? That is $(\text{total elements left} - \text{number of elements greater than it})^{th}$ element. That's $4-0 = 4$, that is, the 4th element in the numbers that are left out. That seems to be 5. So we remove it, and we're left with 1,2,and 3.

Again, we are at the 3rd position, which says  2. So, we find the element which has 2 elements greater than in in the remaining elements. That is, $3-2=1$. So we're talking about 1. So, let's put 1 at this position and move forward. So, now we have only 2 and 3 remaining.

You get my point. Right?

So how will you do it optimally? We have to care for the removed elements. We should know that the 4th element after the removal of 2 is 5. So, we can create a segment tree for that, where each number has a 1 assigned to it.

Once we use that number, it's 1 becomes a 0. The parent nodes have the sum of the child nodes. Updation is easy peasy too.

Here is the code: