More than 31 Style elements cause IE crash

Last week, I was trying to add Twitter Widget on my Webpage, it was working fine in Firefox, Chrome and Safari but in all versions of IE, it was causing crash :O

"Oh IE I love, I can write an HTML file that can crash you"

After figuring out the JavaScript of that twitter widget and some Google work, I got to know that the basic cause of IE crash is not the Twitter widget. The basic cause was that twitter widget adds a "style" HTML element dynamically, that causes crash for IE.

I just squeeze all those 31 imports in one "<style> </style>" and hurray!!!! the problem is resolved.

Reference: Microsoft Support about 31 style tags

Finding 100 factorial

Problem Statement:
Write a program that takes input between 1 and 100 and finds its factorial.

Solution
Often students find this problem as assignment or algorithm exercise. Some of them even get fed up and skip this problem because you have to make calculations on large numbers. We all know that C++ 32 bit unsigned integer can hold data up to 4294967295 and long long i.e. 64 bit integer can handle at max 2⁶⁴ - 1 = 18446744073709551615. What do you think what is the maximum value whose factorial can be saved in 64 bit int. You can't even store 25's factorial in it as 25! = 15511210043330985984000000 :)

In this post, I will explain how easy it is to actually implement this algorithm. In the second part of this post, we will optimize our algorithm and will reduce some calculations.

Let us start!

First thing we have to keep in mind that we actually need a function that has the capability to multiply fairly large numbers.

We multiply two numbers usually by multiplying each digit of first number with each digit of 2nd number. For example if I have to multiply 123 to 1234:

1. I will actually find 3 x 1234 = 3702, 2 x 1234 = 2468 and 1 x 1234 = 1234.
   
2. I also have to add some zeros on the right side as I move from right to left.
   
3. And then I will add all these values i.e. 3702 + 24680 + 123400 = 151782.
   

Voila!!! you noted something, we have to implement another function that can add two large numbers. Don't worry, it is good that we have found it initially. Let us assume that we already have a function that can add two numbers 'string add(string str1, string str2)' Now the function mul is quite simple to write that will multiply two very large numbers.

string mul(string str1, string str2)
{
 string ans;
 for(int i = str1.size()-1; i>=0; i--)
 {
  string sum;
  int carry = 0; 
  //Step 1. above
  for(int j = str2.size()-1; j >=0; j--)
  {
   //multiply two digits and add carry
   int k = ((str1[i]-'0')*(str2[j]-'0') + carry); 
   sum = (char)((k % 10) + '0') + sum;
   carry = (k/10);
  }
  
  if(carry > 0)
  {
   sum = (char)(carry+'0') + sum;
  }
  //Step 2. above
  for(int j = 0; j < str1.size() - 1 - i; j++)
  {
   sum+="0";  
  }
  //Step 3. above
  ans = add(ans, sum);
 }
 return ans;
}

And here we go with the add function, I think it is pretty simple to understand

string add(string str1, string str2)
{
 int n1 = str1.size(), n2 = str2.size();
 for(int i = 0; i < n1 - n2; i++)  //Make 134 as 00134 if 2nd number is 12345
  str2 = "0" + str2;
 for(int i = 0; i < n2 - n1; i++)
  str1 = "0" + str1;
 string ans;
 int carry = 0;
 for(int i = str1.size() - 1; i >= 0; i--)
 {
  ans = (char)((str1[i] - '0' + str2[i] - '0' + carry) % 10 + '0') + ans;
  carry = (str1[i] - '0' + str2[i] - '0' + carry)/10;
 }
 if(carry > 0)
  ans = (char)(carry + '0') + ans;
 return ans;
}

Now what is more difficult for you. Here comes the Factorial function:

int N = 25;  //We need 25!
                string ans = 1;
  for(j = 1; j <= N; j++)
  {
   stringstream ss;
   ss << j;
   ans = mul(ss.str(),ans);
  }

Optimization Just check one important thing, even we have to multiply small numbers. we have to make large calculations. For example, if I want to multiply 10000 to 9999. I have to make 20 calculations but it is possible in just 1 calculation and the result can also be saved in an integer so we can optimize our algorithm in this way. We will not call mul( ) function, until and unless it exceeds the limit of an integer that is '2147483647' and then multiply it with the next number. 25! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 21 x 22 x 23 x 24 x 25 Now we can find product upto 12 i.e. '479001600' and from 13 to 19 i.e. '253955520' and then call mul( ) function on these two strings.

I am sure, it will save a lot of calculations.

Lecture about dynamic programming (Urdu)

Hi all,

While searching educational stuff on youtube, I found these videos those I would like to share with you.



and the next part is:

Topcoder | SRM 449 experience

This time the performance was a bit disappointing. The problems were related to mathematics and trigonometry.

I spent some time on 250 ptr and just didn't understand that if I scale its lower parts to upward, it will become a bigger triangle, and I just have to find the lengths of base and perpendicular of that bigger triangle. The formula was sqrt(2)*(max(finish) - min(start)). This is the solution.

Just no idea clicked and I decided to open 500 ptr because I was pretty sure that it would have been a simpler one. It was simple(only problem statement :) ), as you might have seen but wasn't easy. Again it was a mathematical trick, because brute force solution will surely leads to time out. This was the logic behind it. (The following statements are copied from editorial)

-> If we see, the greatest odd divisor that divides N is N if N is odd or if N is even the greatest odd divisor of N is F(N/2).
-> For (1,N) if N is odd we get 1 + 3 + 5 + ...N + F(2) + F(4)+....F(N-1). The greatest even N is F((N-1)/2).
-> That means the sum F(2) + F(4)+...F(N-1) = F(1) + F(2) + F(3) + F((N-1)/2). Now this is our original problem with N as (N-1)/2.
-> In case of N as even our problem is split into 1+3+5+ ....N-1 and F(2)+ F(4) + ......+ F(N), which is again sum(1,N/2).
-> Now the sum of 1+3+5+.....+N= (N+1)*(N+1)/2

Click here for its solution.

After a sad Coding phase, I decided to gain some points in challenge phase, I was sure that many participants will attempt 500 ptr as brute force so I attacked them, I made 3 challenges one of them was wrong and finished at 75.

Next day, I opened the page to see how much rating points I lost, I was amazed that these were not too many.