Binary_ToothLess's blog

By Binary_ToothLess, 10 years ago, In English
  • Vote: I like it
  • -21
  • Vote: I do not like it

By Binary_ToothLess, 10 years ago, In English

http://e-maxx-eng.github.io/

Here some of important algorithm are translated in English by GitHUB. Thanks! GitHUB.

But we need full English version of this site...Cause this site is just Stunning. Can anyone give me the link of this site where I get full English version of it???....PLZ..........

Full text and comments »

  • Vote: I like it
  • +29
  • Vote: I do not like it

By Binary_ToothLess, 10 years ago, In English

I just write here a structure for coin change problem:

433A — Kitahara Haruki's Gift

http://codeforces.net/problemset/problem/433/A

int recursion(int index, int amount){//initially index is 0, amount = amount of destination money

if(i >= total_types_of_Coin){//e.g:1c,5,10c = 3 types of coin here..

if(amount == 0)return 1;// base case

else return 0;

}

int way1 = 0, way2 = 0;

if(dp[index][amount] != -3)dp[index][amount];//dp was memset by the value of -3 in main function

if(amount-Coin[index] >= 0)way1 = recursion(index, amount-Coin[index]);//if we get same coin for several times otherwise index will be (index+1) that means try next coins;

way2 = recursion(index+1, amount);

return dp[index][amount] = way1+way2;

}

try it...i think this will work for following problems... UVa — 357, 674, 11137, 562;

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By Binary_ToothLess, 10 years ago, In English

Don't be afraid this is not very difficult....

For new programmer, this is very essential... We know a little bit for that we don't answer many problem as like "largest sum contiguous sub array" that's really very easy to determine largest sum if we know the following algorithm.....

Initialize: max_so_far = 0

max_ending_here = 0

Loop for each element of the array

(a) max_ending_here = max_ending_here + a[i]

(b) if(max_ending_here < 0) max_ending_here = 0

(c) if(max_so_far < max_ending_here) max_so_far = max_ending_here

return max_so_far

Explanation: Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

Lets take the example:

{-2, -3, 4, -1, -2, 1, 5, -3}

max_so_far = max_ending_here = 0

for i=0, a[0] = -2 max_ending_here = max_ending_here + (-2) Set max_ending_here = 0 because max_ending_here < 0

for i=1, a[1] = -3 max_ending_here = max_ending_here + (-3) Set max_ending_here = 0 because max_ending_here < 0

for i=2, a[2] = 4 max_ending_here = max_ending_here + (4) max_ending_here = 4 max_so_far is updated to 4 because max_ending_here greater than max_so_far which was 0 till now

for i=3, a[3] = -1 max_ending_here = max_ending_here + (-1) max_ending_here = 3

for i=4, a[4] = -2 max_ending_here = max_ending_here + (-2) max_ending_here = 1

for i=5, a[5] = 1 max_ending_here = max_ending_here + (1) max_ending_here = 2

for i=6, a[6] = 5 max_ending_here = max_ending_here + (5) max_ending_here = 7 max_so_far is updated to 7 because max_ending_here is greater than max_so_far

for i=7, a[7] = -3 max_ending_here = max_ending_here + (-3) max_ending_here = 4

Code :

for(int i = 0; i < N; i++){

max_ending_here += Number[i];

        if(max_ending_here > max_so_far)max_so_far = max_ending_here;

        if(max_ending_here < 0)max_ending_here = 0;

    }

So the complexity for this code is O(n)...

Happy coding...:)

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it