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
Posts
Tostr(int n) : useful function to change integer / long long to string !!
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
Desktop icons are gone, taskbar won't showUP: Solution: 1. Go alt+Ctrl+Delete at the same time and wait for a box to open 2. when the box is open Click "file" at the top and then Click "New Task (Run...)" 3. When you get another small box with something to type in, type in "explorer.exe" (without the ") 4. Your Taskbar and Icons will now load, If not your computer is corrupt. If that happens take your computer to your local IT Guy and ask Him to install explorer for you because it is corrupt Or you Can do This : (You Have to know a bit about your computer) 1. Go to Run Like in Above 2. Now instead of typing "explorer" type in http://www.google.co.za (or any other web address) 3. Your Default web browser should open. Now type in in the top "C:\" (without ") and your files should open. dont do anything yet 4. Now go Alt+Ctrl+Del and click on the tab "Processes" Find Explorer.exe in that list and clic
HY VISITORS , IT'S ME BISHAL GAUTAM. THIS BLOG IS FOR A PERSON WHO WANT TO LEARN SOMETHING FROM MY EXPERIENCE. BEFORE WRITING ANYTHING IN MY BLOG , I WOULD LIKE TO INTRODUCE MYSELF. HERE'S MY INFORMATION: NAME: BISHAL GAUTAM BIRTHPLACE: RUPERNDEHI,BUTWAL, NEPAL. EDUCATION: CSE 2ND YEAR UNIVERSITY: JAHANGIRNAGAR UNIVERSITY,SAVAR,DHAKA, BANGLADESH. EMAIL: Bsal.gautam16@gmail.com CONTACT NO: +8801740399245 FB: http://www.facebook.com/Bsal.gautam