[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:

[SegmentTree][SPOJ] BRCKTS

BRCKTS

Question statement:

We will call a bracket word any word constructed out of two sorts of characters: the opening bracket "(" and the closing bracket ")". Among these words we will distinguish correct bracket expressions. These are such bracket words in which the brackets can be matched into pairs such that

• every pair consists of an opening bracket and a closing bracket appearing further in the bracket word
• for every pair the part of the word between the brackets of this pair has equal number of opening and closing brackets

On a bracket word one can do the following operations:

• replacement -- changes the i-th bracket into the opposite one
• check -- if the word is a correct bracket expression

Task

Write a program which

• reads (from standard input) the bracket word and the sequence of operations performed,
• for every check operation determines if the current bracket word is a correct bracket expression,
• writes out the outcome (to standard output). 

My approach:

Well well well. This one took a lot of time for me to understand how exactly I would get the answer for the current node. Initially I thought in the direction of having a single value for each node, which is a total for the range, in which a '(' is counted as a 1 and ')' as a -1.

Then I thought of having valid and invalid nodes, depending on the values of their children. But no point into going into the wrong approach.

Well what struck me was the point that all we needed to see the brackets which were imbalanced. That is, the ones that are not matched. So, I could keep the track of left unmatched brackets and right unmatched brackets, for a node, for the range to which it corresponds. Cool.

How to maintain this property?

That is, given that we have these values for the left and right children of a node, can we get the values for the parent node?

Let's say that the left child has $L_{l}$ left unmatched brackets, and $L_{R}$ right unmatched brackets. Similarly, the right child has $R_{l}$ left unmatched brackets, and $R_{r}$ right unmatched brackets.

Now when we're merging the ranges of the left and the right children, we can see that the left unmatched brackets of the left child and the right unmatched brackets of the right child cancel out!

Example: L: )((()) has one left and one right unmatched bracket
                R: )(      has one left and one right unmatched bracket
So, while merging, we can do $cancelledBrackets = min(L_{l},R_{r})$, and for the parent node:
$$P_{l} = L_{l}- cancelledBrackets+R_{l}$$
And:
$$P_{r} = L_{r}+R_{r}-cancelledBrackets$$

So, this is how we can build our segment tree.

For updation, we can simply change the 1 to 0 and a 0 to 1, for both the left and right brackets, at the leaf. And then we can update the parents using the method as described above.

Here is my elegant code minions:

[Segment Tree][SPOJ] FREQUENT

FREQUENT 

Here is the problem statement:

You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , ... , a_j. 

Input Specification

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.
The last test case is followed by a line containing a single 0.

Output Specification

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

My Solution:

This is a segment tree question. Not because it can only be done via a segment tree, but because I am trying to learn segment trees, and it's amongst the questions I'm practicing. 

So, IMO there are two things one should think about when using segment trees:

1. Merge

2. Update

Merge  here means that assuming you've your answer for the left and the right child of a node, how will you percolate the result up? What intermediate values must you store in the child nodes such that the current node's solution can be reached efficiently?

Update depends upon the context. Do you have a point update or a range update? How will you manage to update the values of the node efficiently for whole of the segtree?

So these are the things I thought.

So, let's say a node contains the maximum occurring number and it's count. Cool cool. Now how does it's parent benefit from this information? It'll have the max count of it's left and right children. Good. But is there any merging required here? That can only be possible if there is an element that is in both the left and the right child. That means that the element is at the right most part of the left child and the leftmost part of the right child. 

But we don't save this information! So let's save that too. The count of the leftmost and the rightmost element of the node. When we merge, we check these too, and update the max element and it's count accordingly.

Now just go till the top and enjoy.

There's no update so no worries. :)

Some elegant code

My code :/

[Arrays][InterviewBit] Find the duplicate

Find the duplicate

Question:

Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) time and using only constant memory space. 

Here  is the link

 Solution:

So basically you can't use a hashSet initially. So we have to find some way so that the number of checked elements are decreased.

Buckets! These days they are everywhere. We can create equal

  sized buckets here too, and limit the search to a single bucket. What should be the size of such a bucket? If $ \delta = (MAX-MIN)$, and there are $n$ elements, then we can create each bucket of size $$\frac{n}{\delta}$$. But this too will be a $O(n)$ search, so let's do something better.

We can decide to use buckets of size $\sqrt{n}$. 

Now the plan.

We can have $\sqrt{n}$ buckets. While going through all the elements we are given, we can check which bucket it belongs, and then increase the size  of that  bucket. Now the bucket that overlaps will be the one which has the duplicate element. Now, use the hash set. Go again through all the elements and then put the ones in the range in the hash set. Boom. You're done. The element that was already in the hash set will be the duplicate element.

Corner case.

Now this is magical fucking information. When you'll implement this stuff,  you'll realize $\sqrt{n}$ is like never an integer. So you'll have to make an array of buckets of size $\lfloor \sqrt{n} \rfloor+1$ and you'll check if any bucket reaches $\lfloor \sqrt{n} \rfloor$. But there'll be a point when no such bucket will be found because the duplicate is in the last bucket, which doesn't even have a size near to $\sqrt{n}$, so boom you're done. Take care of this case and you'll be okay.

Here is the code:

 

[Arrays] [InterviewBit] Increasing decreasing arrays

Given relationship between consecutive elements of an array, generate the array

Problem statement:

Given a positive integer $n$ and a string $s$ consisting only of letters $D$ or $I$, you have to find any permutation of first $n$ positive integer that satisfy the given input string.
$D$ means the next number is smaller, while $I$ means the next number is greater.
Notes

• Length of given string $s$ will always equal to $n - 1$
• Your solution should run in linear time and space.

Initial Thoughts:

What? How will I generate an array given only the relationship between consecutive elements? Plus they're also dependent upon the elements far after and before the elements. How?

Actual Solution:

Meh. Well after I thought a lot about it, generation can be a greedy procedure. You know how much in total increase is to be done. You also know how much decrease is to be done. The main problem is that once an increase is required, an increase must be done. So, basically you can't increase after the maximum element et cetera.

So I know that $i$ increases must be done after an element and $d$ decreases must be done after an element. So I must leave a gap of $i$ above the element $e$ I will select for the current position, and a gap of $d$ below $e$. That means, I've to select $d+1$th element. 

Meh.

So, the first element will be the $d+1$th element. All increases will go up, and all decreases will go down. So, I can create two pointers $uptr$ that goes up and $dptr$ that goes down. $uptr = d+2$ and $dptr = d$ initially. Everytime, an $I$ comes in the string, I put $uptr$ value in the current position and increase $uptr$ by $1$. 

Similarly, everytime I see a $D$ in the string, I put $dptr$ in the current position and decrease $dptr$ by $1$.

Done. EOD. Hence proved. Fuck off.

Code:

[Arrays] [InterviewBit] [GeeksforGeeks] Maximum Consecutive Gap

Maximum Consecutive Gap

Question Statement:

Given an array, find the maximum difference between its two consecutive elements in its sorted form.

And do that in $O(n)$ space and time, just for the fun of it.

My initial solution:

InterviewBit said that the numbers are all 32 bits, so obviously radix sort was on my mind. Take counting sort for each bit, from right to left. Done in $32 \times n$ time. Then check the maximum gap. Thank God I didn't implement this, otherwise I won't be able to know how to solve this correctly. 

Actual Solution:

Remember PigeonHole principle? Yes. That is what we'll be using here, got damnitwhatthefuckpeopledothesedays.

So, initially find the maximum and the minimum of the array. Done? Now here me out, create $n-1$ buckets each of equal size. 

Now out of $n$ elements two are the minimum value and the maximum value. So, we're left with $n-2$ elements. So it is impossible that each bucket will contain an element. At best, there will be a bucket that'll be empty. And guess what, if a bucket is empty, the gap between the maximum element of the previous bucket and the minimum element of the next bucket is obviously  greater than any gap between two elements inside the same bucket. Right? So what we have to do is put elements in these buckets, and then find the gap between consecutive (alive) buckets. And boop boop we're done.

Here is my code, which you don't give a fuck about:

  

Building a COOL lexical analyzer generator using JLex

The reason for making this post, is to give an overview of the procedure I followed while making a lexical analyzer generator for the COOL programming language, under this Stanford course. 

CHEATING:

Not exactly, but that's how I made the lexical analyzer generator (LAG). Why you ask? Yeah, coming on that topic. What would you call copying someone else's code your starting point of work? PLAGIARISM! 

Yes, I definitely did it. 

I copied whole of the code from here. "Boy you're a bad one!" might be your line of choice, but I'd rather ask you to wait and listen, that when I tried to submit this code (not to skip the work, just curious about the accuracy of the solution), and got a score of 11 out of 63. 

"What's a score?" you ask? Well, it tells us about the successful recognition of tokens in cool program files. So, a score of 11 out of 63 would tell that there are a lot of cool files whose tokens, weren't recognized properly.

This, was good. The effort put to make this score better made me understand a plethora of stuff, that I didn't know about earlier.

So, here I'll discuss the modifications I made to the code, and the reasons for doing so. Some are general explanations on the things that I think I should've known before.

STRINGS:

Oh dear. I love strings. They are so, curiously built, have so much inside them, still remain under a single name. Ohh the unity.

 1. How to recognize Strings?
Well, we all know that a string starts with a quote, that is the '\"' character. So, you'll be needed to   recognize that when in the initial (YYINITIAL) state, and then change the state to a state that represents a string only. We can call it the STRING state.
The initialization state and it's code looks like this :

<YYINITIAL> \"  { 
  string_buf.delete(0, string_buf.length());
  yybegin(STRING); 
  stringTooLong=false;
  nullInString=false;
  stringError=false;
  skip = false ;
 }

2. What to do when a string has just started?
You'll definitely want to save the string and return it when you recognize one. So, in order to do that, you have two options:

1. Use a String object, or
2. Use the String buffer.

We're more used to using the String class, but it has a problem, that it is immutable.  We can't change the stuff that has gone inside the string. But wouldn't we have to just add characters as we see and then return the string when the ending quote is seen? No. I wish it was that easy.

We would have to use the String buffer, as we need to make changes to characters already added to the buffer (will explain later you hungry beast).

So, when  the string recognition phase has just started, we'll initialize a string buffer.

string_buf.delete(0, string_buf.length());

Here, this initialization is to delete the previous string saved (if any) inside the buffer.

The next step is to change the state from the YYINITIAL  to STRING. This can be done by :

yybegin(STRING) ; 

Next is to check for a "null" in a string, or if the string is too long. If the previous string had a "null" in it then the boolean variable nullInString would be true. So when we see a new string, we'll change it back to false. Same for the variable stringTooLong. 

There is one more variable skip inside the initialization, but we'll discuss it later.
3. What to do when inside the string?This one is pretty complex. We'll reach this stage after the current state (which is given by yy_lexical_state ), has changed from YYINITIAL to STRING state. This can be divided into three major parts:

1. The ending quote.
2. All the stuff inside the string, except the newline, or a quote
3. The newline

The newline is considered separately because in COOL, we need to escape the newline. So, extra measures have to be taken when we see a newline inside a string.

A. The ending quote has been recognized while traversing the string

<STRING> \" {
 // If an escape character appears before a quote, we must put a quote into the string
  if(stringTooLong) {
        yybegin(YYINITIAL) ;
 
    return new Symbol(TokenConstants.ERROR, "String constant too long");

  } else if(nullInString) {
        yybegin(YYINITIAL) ;
       return new Symbol(TokenConstants.ERROR, "Null character appeared in string");
  } else if(stringError) {
        yybegin(YYINITIAL) ;
    return new Symbol(TokenConstants.ERROR, "Error occurred while parsing string");
  } 
  

  if(!skip && string_buf.length()>0 && string_buf.charAt(string_buf.length()-1)=='\\') {
    string_buf.setCharAt(string_buf.length()-1, '\"');
  } else {
    yybegin(YYINITIAL); 
    return new Symbol(TokenConstants.STR_CONST, AbstractTable.stringtable.addString(string_buf.toString())); 
  }
 }

When the ending quote has been recognized, then we are sure that the current string has ended. So, if some error ocurred while the recognition of the string, then we can reject the string after raising an error.

Note that I will not discuss Symbol, TokenConstants, and AbstractTable here, (because I just don't understand them properly yet). They will be added as a footnote later or as another blog post, as soon as I understand them.

We'll have to change the current state to YYINITIAL in order to signify that what comes next is code not string.

This is done for all the errors that could be raised.

Now did you realize, that a quote can also come inside a string, when escaped. Boom. That was an increase in complexity. So, how will you know that the current quote is THE end quote, or just some normal escaped quote inside the string?

This can be done by checking the last entry of the string buffer. That is, checking the

string_buf.charAt(string_buf.length()-1)

for '\\'. If it is '\\' then we know that the quote is escaped, and thus it simply should be added to the string buffer, as '\"'. Note that we replaced '\\' by '\"' inside the String buffer. The input doesn't take "\n" as '\n' but as '\\' and 'n'. 

But when we know that the current quote is not escaped and is not to be skipped, then we can safely conclude that the current quote is THE ENDING QUOTE. And we can safely go back to the YYINITIAL state and add the string to the AbstractTable.

What about "skip"?
Wait, until normal character recognition comes in. Just wait. Please.

B. All the stuff inside the string, except the newline, or a quote

<STRING> [^\n\"] { // Code for handling other characters encountered in strings
  // including special cases for escaped characters
  if(string_buf.length()==0) 
  {
    string_buf.append(yytext());
  } else 
  {
    
    // Check if null character appears in input stream
    if(yytext().charAt(0)=='\0' || nullInString) 
 {
      nullInString=true;
    } else
    {
      int length=string_buf.length();
      if(string_buf.charAt(string_buf.length()-1)=='\\') 
   {
  if(skip)
        {
   string_buf.append(yytext()) ;
   skip = false ;
        }
  else
       {
        switch(yytext().charAt(0))
  {
  case 'b':
    string_buf.setCharAt(length-1, '\b');
    break;
  case 't':
    string_buf.setCharAt(length-1, '\t');
    break;
  case 'n':
    string_buf.setCharAt(length-1, '\n');
    break;
  case 'f':
    string_buf.setCharAt(length-1, '\f');
    break;
  case '\\':
    string_buf.setCharAt(length-1, '\\');
    skip = true ;
    break;
  default:
    string_buf.setCharAt(length-1,yytext().charAt(0)) ;
  }
       }
 
      }
     else
  {
  string_buf.append(yytext());
     }
    }

  }
    if(string_buf.length()>=MAX_STR_CONST)
  {
    stringTooLong=true;
  }
 }  

This looks scary. It isn't. Simply, check if the buffer is empty, if yes then add whatever is coming in. Then some error checking. Bleh. Boring.

Remember when I said that "\n" is seen as '\\' and 'n'? Yeah, now we'll have to do that for all escaped characters. The special ones like a backspace and tabs are like "\b" and "\t", so they're actually '\\' with 'b' and '\\' with 't'. So, if the last character seen is a '\\' then we'll have to handle this escaping procedure.

Note that we can't have a newline here, so we don't have to worry about it much.

By "handling this escaping procedure" I mean that we'll replace the seen '\\' with the correct characters, like '\t' and '\r' et cetera.

What's a 'n' doing in there? Aren't newlines not allowed?

Yeah but that isn't a newline! That is just  "\n"  in a string. A newline is \n or "
"

Pressing "Enter"  creates a newline. Simply writing "\n" won't simulate it$^1$. Though we can explicitly tell the receiver that my "\n" means a newline, then only it can simulate a newline. Even though without the said agreement, \n has no real meaning of it's own.

So, we'll do the same for a "\n" as we did for "\t" or "\b".

Also note the '\c' has no special significance, and is equivalent to 'c'.

What if the last '\\' seen, itself is an escaped '\\'? 

Boom. Boom. Boom. High complexity levels. Existential crisis in here.

Yeah, what will you do now? If we didn't do anything, then strings like "Hello \\\kitty", which actually is "Hello \kitty" is converted to "Hello kitty", removing the '\\' altogether. This happens in this sequence:

1.  "\\" is converted to "\"
2. "\k" is converted to "k"

This is problematic. The solution that seemed apt to me was to skip the next character from this "if the previous character was '\\' check" altogether, signifying that the '\\' is not to escape anything at all.

So, skip is initialized to false. It is made true when a '\\' is seen after a '\\' and is made false again, when a character is skipped.

We must skip the conversion of a escaped newline into a newline, if the last '\\' doesn't signify the newline's escape. Same for a quote.

We also must re-initialize skip to false when we see a new string.

Everything else in the code is self explanatory and I will not bother to explain them.

C. A newline is seen

<STRING> \n { // Code for newline characters
  // If a newline appears in a string, it must be escaped, else error
  if(string_buf.length()==0 || skip || string_buf.charAt(string_buf.length()-1)!='\\') {
    curr_lineno++;
    yybegin(YYINITIAL) ;
    return new Symbol(TokenConstants.ERROR, "Unterminated string constant");
  } else {
    curr_lineno++ ;
    // Replace '\' character in string buffer with newline
    string_buf.setCharAt(string_buf.length()-1, '\n');
  }
 }

A newline is seen in the string. This is a rare and auspicious occasion. No. Not really.

We just need to check if the current newline is legit or not. If it isn't then we need to return an error, otherwise we add it to the buffer after making some modifications.

 COMMENTS:

Comments in cool are of the form (*...*). They can be nested as well. Again when a '(' is seen before a '*'  while in the initial YYINITIAL state, then we can say that a comment has begun and thus go to the BLOCK-COMMENT state.

When in the BLOCK-COMMENT state if a '*' or a ')' or a '(' is seen then, it's okay! They shouldn't be together though. if we see a "(*" then we increase the nestedCommentCount and when a "*) " is seen then we decrease it. When it reaches zero, then we can simply change our current state back to YYINITIAL. Here is the code telling you the same thing, you dumbo:

<YYINITIAL> "(*" { yybegin(BLOCK_COMMENT); }
<BLOCK_COMMENT> \(\*  { nestedCommentCount++; }
<BLOCK_COMMENT> \n  { curr_lineno++; }
<BLOCK_COMMENT> [^\n\)\*] { /* Do Nothing */ }
<BLOCK_COMMENT> \*  { /* Do nothing */ }
<BLOCK_COMMENT> \)  { /* Do Nothing */ }
<BLOCK_COMMENT> \*\) {
  if(nestedCommentCount!=0) {
    nestedCommentCount--;
  } else {
    yybegin(YYINITIAL);
  }
 
}

Minor Points:

1.  Pressing "Enter" in windows means "\r\n" not "\n" only. '\r' is carriage return, that brings back the cursor back to the initial point, and '\n' is simply the newline or the linefeed.
2. Know that [==] isn't the same as "==" or ==. It simply means a =.

These are the main points of the things I learned while building the LAG for COOL. I consciously excluded discussion over JLex' functioning, and the minor errors that I got. They aren't that important as they are either easy to learn or debug.

Here is my code for the LAG: