Original_Batman's blog

By Original_Batman, history, 5 months ago, In English,

using namespace std;

int main()
   int n;
   cin >> n;
   int arr[n];           //Variable length array
   return 0;

Hey there, I've seen many people use variable length array in their programs but the problem is I program on Visual Studio and it doesn't allow me to use #include<bits/stdc++.h>. So I wanted to know which particular header file allows us to have variable length arrays.

Read more »

  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By Original_Batman, history, 7 months ago, In English,

I read merge sort trees from here (https://discuss.codechef.com/questions/94448/merge-sort-tree-tutorial) understood the build function but I can't understand the query function.

  1. Why would you go top to bottom? you'll meet the "if( x<=l && r<=y )" condition on the root node itself the program will never traverse down the tree. Also for an array of size 10 and a query with a range 2-6 the sorted array can have elements from 6 — 10 and 1 of the original array.

  2. Also, we can't search on the merge sort tree as the elements have been shuffled in sorting (ie, the indices of original data and sorted array don't match), the only possible way on searching on such a tree should be bottom up ie, leaf to tree root because the leaf nodes are pushed in the order of the original data and subsequently we must climb to parent node whenever possible (because minimising number of binary searches is our motive here) climbing can only be done if both the daughter nodes are included in l to r as they are a part of search range and their order doesn't matter.

Read more »

  • Vote: I like it  
  • -1
  • Vote: I do not like it