Me & My Experiences !!

Maximum sum 2D: Problem: Given 2D array with some +ve & -ve integers. You have to compute the sum of submatrix(subrectangle-may be square) with maximum sum. Link:  here  IDEA:     1.) Fix one column lft .    2.) Fix one column rgt from lft to rgtmost corner.    3.) For every fixed lft & rgt column, traverse below rowwise & calculate cumulative sum .         Note: We have to precalculate rowise sum earlier.    4.) If sum becomes negative then, make it 0 & update maximum sum on every step. So, overall complexity is O(n^3). Source code: #include <bits/stdc++.h> #define PI acos (- 1.0 ) #define M 1000000 #define S ( a ) scanf ( "%d" ,& a ) #define P ( a ) printf ( "%d \n " , a ) #define S2 ( a , b ) scanf ( "%lld%lld" ,& a ,& b ) #define clr ( a ) memset ( a , 0 , sizeof ( a )) #define ff ( a ) memset ( a , false , sizeof ( a )) #define pb ( x ) push_back ( x ) #def

string tostr(int n) {     stringstream ss;     ss<<n;     string s=ss.str();     return s; }

PROBLEM:    Given n digits number-N. (n<=12, so that ans always fit in 64-bit int) .    We have to calculate the sum of all of its permutation numbers. for example: N= 123. Then, n is 3 (digits.) 123 132 213 231 312 321 ------ 1332 Here, if we fixed '1' in first postion,then we can arrange remaining digits in (n-1)! ways. so, 1 can be in pos-0 in (n-1)! times.      so, add- (1* fac[n-1]*dig[pos] )=1*2*1       1 can be in pos-1 in (n-1)! times.       so,add = 1*2*10=20;       1 can be in pos-2 in (n-1)! times.        so,add = 1*2*100=200; Overall for 1=220. similarly, for 2=444 for 3=666 -------------- so, ans= 1322. NOW, consider if digits are not unique then ?? ----->> Nothing to be amazed, Just multiply -- (n-1)! by occurace of remaining digits except fixed one. Suppose for 3 digit number - 1 1 2 Here, if we fix 1 then,  for every digit position multiply ans & add- 1*2!*dig[pos...]. = 220  finally, if we fix 2 then, for every d

Problem: TOPCODER SRM 403 :  TheSumOfLuckyNumbers   Statement : we have to say can we get N by adding lucky numbers as minimum as possible.. :) Facts: 1.There are only 1022 lucky numbers from 1 to 10^9 and only 126 from 1 to10^6. :) Solution:  1.first generate vector of lucky numbers using BFS. for eg: LUCKY NUM GENERATION 2.Then, again one BFS to calculate minimum distance of number using lucky numbers . 3. then Print the required solution using iterative for loop & while condition !! That's it. int dis[1000005]; bool vis[1000005]; class TheSumOfLuckyNumbers { public:     vector <int> sum(int n)     {       // 1. generate Lucky numbers in a vector         vector<long long>v;         vector<int>ans;         queue<long long>Q;         Q.push(4);         Q.push(7);         while(!Q.empty())         {             long long s=Q.front();             Q.pop();             if(s<=1000000)             {                 v.push_back(s);    

CATALAN NUMBERS: unsigned long long ar[ ]= {1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452,18367353072152,69533550916004, 263747951750360, 1002242216651368, 3814986502092304, 14544636039226909 };   Formula: C n = 2n C n /(n+1) = 2n!/{(n+1)!n!} we can also use this formula C 0 = 1 C n = C n-1 *(4n-2)/(n+1)  Source code: http://ideone.com/wwbQAk  Applications: 1. How many ways are there to construct n pairs of parentheses which are correctly matched. [Analysis: The leftmost parenthesis l matches some right parenthesis r. Suppose there are k pairs between l and r, there will be n-k-1 pairs outside. Hence, the number of possibilities will be] 2. Counting the number of paths across a lattice which do not cross the diagonal line . More generally, Cn is the number of Dyck words of length 2n. A Dyck w

SIMPLE DP-Knapsack Problem solution: Problem: We have given n -items each ni with weight w[i] and we can get profit v[i] from each item.  Size of our Knapsack is only W . We have to maximize profit as much as possible as much as  using low Knapsack size. Solution:- #include <bits/stdc++.h> #define fr ( i , a , n ) for ( i = a ; i <= n ; i ++) #define SET ( a ) memset ( a ,- 1 , sizeof ( a )) using namespace std ; typedef long long ll ; int n , W , dp [ 102 ][ 505 ], w [ 102 ], v [ 102 ]; int main () { int i , j , mxfn , mncst ; while ( cin >> W >> n && ( W && n )) { fr ( i , 1 , n ) { cin >> w [ i ]>> v [ i ]; } fr ( i , 0 , n -1 ) dp [ i ][ 0 ]= 0 ; fr ( j , 0 , W ) dp [ 0 ][ j ]= 0 ; mxfn = 0 ; mncst = INT_MAX ; fr ( i , 1 , n ) { fr ( j , 1 , W ) {

 SOME USEFUL LINKS:::: 1 .Good site to practice JAVA PROBLEMS:      http://codingbat.com/java 2. Knapsack Problem:  http://sadakurapati.wordpress.com/2013/11/30/algorithm-knapsack/   3. Gauss elimination to solve linear systems!! 4. Different Numbers in Mathematics :) http://www.tanyakhovanova.com/Numbers/numbers.html  5. GEOMETRY GOOD SITE :   http://www.mathsisfun.com/geometry/  

SIMPLE ADDITION OF TWO NUMBERS USING GUI IN JAVA !! import java.awt.BorderLayout; import java.awt.EventQueue; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.border.EmptyBorder; import javax.swing.GroupLayout; import javax.swing.GroupLayout.Alignment; import javax.swing.JButton; import javax.swing.JLabel; import javax.swing.LayoutStyle.ComponentPlacement; import javax.swing.JTextField; import java.awt.Color; import java.awt.event.ActionListener; import java.awt.event.ActionEvent; public class MyJframe extends JFrame {     private JPanel contentPane;     private JTextField textField;     private JTextField textField_1;     private JLabel lblNewLabel;     private JButton btnAdd;     /**      * Launch the application.      */     public static void main(String[] args) {         EventQueue.invokeLater(new Runnable() {             public void run() {                 try {                     MyJframe frame = new MyJframe();                     frame.setVisible(tr

JAVA : OPP : An example of BOX class!! http://ideone.com/BnAb1I