Posts

Showing posts from October, 2015

D-query :spoj (MO) (for only queries in range )

                                              http://www.spoj.com/problems/DQUERY/en/                                           DQUERY - D-query In this question , the concept of rearranging queries is used , the method known as "MO".  In the question, it is asked to find total different numbers present in the range [l,r] . "add" and "del" functions are written accordingly. #include<bits/stdc++.h> using namespace std; int readInt () { bool minus = false; int result = 0; char ch; ch = getchar(); while (true) { if (ch == '-') break; if (ch >= '0' && ch <= '9') break; ch = getchar(); } if (ch == '-') minus = true; else result = ch-'0'; while (true) { ch = getchar(); if...

Question which include only Queries. (MO) concept

                                   http://codeforces.com/problemset/problem/221/D                                           D. Little Elephant and Array In this question ,we used the concept of MO , i.e. idea of rearranging the queries according to our beneficial. Firstily , we sort the queries using this cmp function . In all the questions in which ,the concept of MO is used "cmp" is same and  four "while loops"  will be same. :) we just have to change the "add" and "del"  functions for each question. :P #include<bits/stdc++.h> using namespace std; long long int readInt () { bool minus = false; long long int result = 0; char ch; ch = getchar(); while (true) { if (ch == '-') break; if (ch >= '0' && ch <= '9') break; ch = g...

All possible sub-matrices sums.

                                              Save the nature https://www.codechef.com/problems/SVNTR (Lunch Time oct 2015)  In this problem , you have to count number of sub-matrices whose sum is less than or equal to k (given). Approach for this problem : firstly calculate the all possible column sum , i.e for c number of columns ,there will be c*(c+1)/2 columns created.  for example : 1 2 3                                 1  3  6   2   5   3                        4 5 6                 --->>>     4  9  15  5  11  6   after creating "b" matrix from the given "a"  matrix.  Calculate all p...

use of sscanf , takes interger from messy string R23C55.. or R2323434C44554

                                          http://codeforces.com/contest/1/problem/B                                                       B. Spreadsheets 55 = BC 27 = AA 28 = AB sscanf takes out number from a messy string input : for example : if the input is R5564C757 , it takes (sscanf(s,"  %*c   %d    %*c     %d  ",&x,&y);  x=5564  y=757 #include<cstdio> #include<bits/stdc++.h> using namespace std; void g(int t) {  if(t)  {  g((t-1)/26);  putchar(65+(t-1)%26);  } } int main() {   int n,x,y;   char s[64],*p;   for(scanf("%d ",&n);n--;)   {     gets(s);     if(sscanf(s,"  ...

No. of subsets whose gcd is 1

                                                                     Subtraction Game 2                                       https://www.codechef.com/problems/AMSGAME2                        It is only a branch and bound type of recursion. #include<bits/stdc++.h> using namespace std; long long int n,i; long long int a [ 1000 ] ; long long int dp [ 70 ] [ 50010 ] ; long long int go ( long long int cur_indx, long long int cur_gcd ) { if ( cur_indx>=n && cur_gcd== 1 ) return 1 ; else if ( cur_indx>=n && cur_gcd!= 1 ) return 0 ; if ( dp [ cur_ind...

wilson's theorm + fermat's theorem :---BORING Factorials

                                   SPOJ :-  BORING - Boring Factorials  According to wilson's theorem   for prime numbers  ((n-1)!) mod n = n-1 In the question Boring factorials we hv to find :---   N! mod P (1*2*..*(n-1)*(n)*..*(p-1) )mod P= P-1  (wilson's) (1*2*..*(n-1)*(n) )mod P  (this is the question) =(P-1) / ((n+1)*(n+2)*..*(P-2)*(P-1)) mod P #include<bits/stdc++.h> using namespace std; #define ll long long int long long int read_int(){ char r; bool start=false,neg=false; long long int ret=0; while(true){ r=getchar(); if((r-'0'<0 || r-'0'>9) && r!='-' && !start){ continue; } if((r-'0'<0 || r-'0'>9) && r!='-' && start){ break; } if(start)ret*=10; start=true; if(r=='-')neg=true; else ret+=r-'0'; } if(!neg) return ret; ...

ETF - Euler Totient Function

                                      ETF - Euler Totient Function SPOJ: - http://www.spoj.com/problems/ETF/ CodeChef :- Rational Numbers (it is sum of phi upto n) In number theory, Euler's totient function (or Euler's phi function), denoted as φ(n) or ϕ(n), is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. (These integers are sometimes referred to as totatives of n.) This is very common in number theory the formula for finding the number of numbers less than and co-prime with n is N(1-1/p1)(1-1/p2).... where p1,p2.... refers to the distinct prime divisors of the number. A example always makes it clear ,lets take n=20 hence the prime divisors are 2,5 hence by formula the number of numbers less than and prime to 20 should be 20*(1-1/2)(1-1/2)=20(1/2)(4/5)=8 Now we can count also 1,3,7,9,11,14,17...

maximum contiguous sum in the range [l,r] .

                                                 http://www.spoj.com/problems/GSS1/ GSS1 - Can you answer these queries I In this question we have to find the maximum contiguous sum in the range[l,r].  To find this  1) total sum is required  2) suffix max is required  3) prefix max is required = max(left child prefix max ,  left child sum + ri8 child prefix max ). 4) maximum contiguous = max ( ri8 child maximum contiguous , left child maximum contiguous,                                                           left child suffix max + ri8 child prefix max )                              ...