## বুধবার, ২৫ মে, ২০১৬

### Codeforces 10 C

When , I first attempted this problem (in a contest) I had no idea how to solve it.When, I saw the solution it seemed a lot easier but the solution requires some steps :-P

CF 10 C Digital Root

The code with Documentation :-D

//Lets first find all digital roots of i for i = 1 to N
//There's a O(1) formula for digital root

//We need to calculate all digital root up to max possible range as, when in the num_dr[dr*dr2]
//We would need to calculate DR of dr*dr2 which maybe >N so,if we just run this loop
up to N we 'll miss some values

digital_root[x] = 1 + (x-1)%9 ; //https://en.wikipedia.org/wiki/Digital_root
//for base b , 9 can be replaced with (b-1)

//Now we need to find all such triplets (x,y,z) such that
// z != x*y   but   digital_root(z) = digital_root(digital_root(x)*digital_root(y))

//Try to understand the statement carefully . It seemed a bit confusing to me first

"Not long ago Billy came across such a problem, where there were given three natural numbers
A, B and C from the range [1, N], and it was asked to check whether the equation AB = C
is correct. Recently Billy studied the concept of a digital root of a number. We should
remind you that a digital root d(x) of the number x is the sum s(x) of all the digits
of this number, if s(x) ≤ 9, otherwise it is d(s(x)). For example, a digital root of
the number 6543 is calculated as follows: d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9.
Billy has counted that the digital root of a product of numbers is equal to the
digital root of the product of the factors' digital roots, i.e. d(xy) = d(d(x)d(y)).
And the following solution to the problem came to his mind: to calculate the digital
roots and check if this condition is met. However, Billy has doubts that this condition is sufficient."

//So, in brief billy has invented an algorithm he believes that if
//for some triplets (A,B,C) it can be showed that DR(A) = DR(DR(B)*DR(C)) //DR for digital_root()
//Then , A = B*C
//For example ,
// DR(6) = DR(DR(3)*DR(2)) so, 6 = 3*2  -> Billy's algorithm gives correct result
// DR(21) = DR(DR(3)*DR(4))  but, 21 != 3*4  -> Billy's algorithm gives wrong result

//You are asked to find the number of triplets (A,B,C) such that Billy's algorithm gives wrong answer

//Observe , we can easily apply modular property and see that , from definition of digital root (That we used using %)
// If, A = B*C
//Then , A%9 = (B%9*C%9)%9
//But,that's the number of correct ans , we are looking for number of wrong answers
//So,lets calculate number of all ans for which , DR(A) = DR(DR(B)*DR(C)) both correct ans and wrong ans

//This can be easily done
//Lets save number of digital_roots with value i ; i= 1 to 9
//As,we know digital root is bounded function [1 to 9]
//We use counters where we save this information

//Now a bit of combinatorics
//A simple example,
//You have "m" numbers whose digital root is x .You have "n" numbers whose digital root is y .
//and You have "o" numbers whose digital root is DR(x*y) . //and as we know DR(some number) is always >=1 .. <=9
//So,  1=< x <=9   1=< y <=9   1=< DR(x*y) <=9
//(x,y,DR(x*y)) is such a triplet
//How many triplets can be made this way
//for x we have m possibility ,for y we have n possibility ,for DR(x*y) we have o possibility

//But now we must subtract all the correct ans
//How can we do that , easy by finding all such triplets
//A = B*C in the range 1 to N
//For example , if we fix N = 5
//such triplets are , (1,1,1) (2,1,2) (4,2,2) (3,1,3) (4,1,4) (5,1,5)
//We can show that , this can be calculated this way ,

//1)number of X <=N which has factor 1   //2)number of X <=N which has factor 2   //3)number of X <=N which has factor 3 ...... //N)number of X <=N which has factor N

//Why this works ? 1)-> (1,1,1) (2,1,2) (3,1,3) ..... (N,1,N)
//2)-> (2,1,2) (4,2,2) (6,2,3) ..... (N,2,N/2)
//..... This way we get all those triplets we are looking for
//And we number of X<=N with factor i is just floor(N/i)
//For example,1.. N has N numbers with factor 1 , 1.. N has N/2 numbers with factor 2 ...easy to realize

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182``` ```/**************************************** @_@ Cat Got Bored *_* #_# *****************************************/ #include #define loop(i,s,e) for(int i = s;i<=e;i++) //including end point #define pb(a) push_back(a) #define sqr(x) ((x)*(x)) #define CIN ios_base::sync_with_stdio(0); cin.tie(0); #define ll long long #define ull unsigned long long #define SZ(a) int(a.size()) #define read() freopen("input.txt", "r", stdin) #define write() freopen("output.txt", "w", stdout) #define ms(a,b) memset(a, b, sizeof(a)) #define all(v) v.begin(), v.end() #define PI acos(-1.0) #define pf printf #define sfi(a) scanf("%d",&a); #define sfii(a,b) scanf("%d %d",&a,&b); #define sfl(a) scanf("%lld",&a); #define sfll(a,b) scanf("%lld %lld",&a,&b); #define mp make_pair #define paii pair #define padd pair #define pall pair #define fs first #define sc second #define CASE(t) printf("Case %d: ",++t) // t initialized 0 #define INF 1000000000 //10e9 #define EPS 1e-9 using namespace std; int digital_root; ll num_dr;//How many digital roots with value i int main() { int N; sfi(N); ms(num_dr,0); //Lets first find all digital roots of i for i = 1 to N //There's a O(1) formula for digital root int N_max = 1000005; loop(x,1,N_max) //We need to calculate all digital root up to max possible range as, when in the num_dr[dr*dr2] { //We would need to calculate DR of dr*dr2 which maybe >N so,if we just run this loop up to N we 'll miss some values digital_root[x] = 1 + (x-1)%9 ; //https://en.wikipedia.org/wiki/Digital_root //for base b , 9 can be replaced with (b-1) if(x<=N) num_dr[ digital_root[x] ]++; //We wont add to counter if x is bigger than N } //Now we need to find all such triplets (x,y,z) such that // z != x*y but digital_root(z) = digital_root(digital_root(x)*digital_root(y)) //Try to understand the statement carefully . It seemed a bit confusing to me first /* "Not long ago Billy came across such a problem, where there were given three natural numbers A, B and C from the range [1, N], and it was asked to check whether the equation AB = C is correct. Recently Billy studied the concept of a digital root of a number. We should remind you that a digital root d(x) of the number x is the sum s(x) of all the digits of this number, if s(x) ≤ 9, otherwise it is d(s(x)). For example, a digital root of the number 6543 is calculated as follows: d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9. Billy has counted that the digital root of a product of numbers is equal to the digital root of the product of the factors' digital roots, i.e. d(xy) = d(d(x)d(y)). And the following solution to the problem came to his mind: to calculate the digital roots and check if this condition is met. However, Billy has doubts that this condition is sufficient." */ //So, in brief billy has invented an algorithm he believes that if //for some triplets (A,B,C) it can be showed that DR(A) = DR(DR(B)*DR(C)) //DR for digital_root() //Then , A = B*C //For example , // DR(6) = DR(DR(3)*DR(2)) so, 6 = 3*2 -> Billy's algorithm gives correct result // DR(21) = DR(DR(3)*DR(4)) but, 21 != 3*4 -> Billy's algorithm gives wrong result //You are asked to find the number of triplets (A,B,C) such that Billy's algorithm gives wrong answer //Observe , we can easily apply modular property and see that , from definition of digital root (That we used using %) // If, A = B*C //Then , A%9 = (B%9*C%9)%9 //But,that's the number of correct ans , we are looking for number of wrong answers //So,lets calculate number of all ans for which , DR(A) = DR(DR(B)*DR(C)) both correct ans and wrong ans //This can be easily done //Lets save number of digital_roots with value i ; i= 1 to 9 //As,we know digital root is bounded function [1 to 9] //We use counters where we save this information //Now a bit of combinatorics //A simple example, //You have "m" numbers whose digital root is x .You have "n" numbers whose digital root is y . //and You have "o" numbers whose digital root is DR(x*y) . //and as we know DR(some number) is always >=1 .. <=9 //So, 1=< x <=9 1=< y <=9 1=< DR(x*y) <=9 //(x,y,DR(x*y)) is such a triplet //How many triplets can be made this way //for x we have m possibility ,for y we have n possibility ,for DR(x*y) we have o possibility ll num_all_triplets = 0; loop(dr,1,9) //DR is in this range { loop(dr2,1,9) // We want to find such pairs x,y -> x*y this forms a valid triplet (x,y,xy) { num_all_triplets+= num_dr[dr]*num_dr[dr2]*num_dr[ digital_root[dr*dr2] ]; } } //But now we must subtract all the correct ans //How can we do that , easy by finding all such triplets //A = B*C in the range 1 to N //For example , if we fix N = 5 //such triplets are , (1,1,1) (2,1,2) (4,2,2) (3,1,3) (4,1,4) (5,1,5) //We can show that , this can be calculated this way , //1)number of X <=N which has factor 1 //2)number of X <=N which has factor 2 //3)number of X <=N which has factor 3 ...... //N)number of X <=N which has factor N //Why this works ? 1)-> (1,1,1) (2,1,2) (3,1,3) ..... (N,1,N) //2)-> (2,1,2) (4,2,2) (6,2,3) ..... (N,2,N/2) //..... This way we get all those triplets we are looking for //And we number of X<=N with factor i is just floor(N/i) //For example,1.. N has N numbers with factor 1 , 1.. N has N/2 numbers with factor 2 ...easy to realize ll num_correct_triplets = 0; loop(i,1,N) { num_correct_triplets += (N/i) ; //Works same way as floor function } ll final_ans = num_all_triplets - num_correct_triplets; cout<

## শনিবার, ১২ ডিসেম্বর, ২০১৫

### A mod B in O(number_of_digit_in(A))

Lets say you have a Big Integer A and an integer B . You want to calculate A mod B in O(length_of_(A)) time complexity . How to do that?

Lets say : A = 1234 (Not that big :-P ) and B = 6

I want to calculate 1234 % 6 . Now ,

s1 = 1234 % 6  =  ((123%6)*10 + 4)%6
=   (s2*10 + 4) %6  [If I know s2 I can calculate 1234 % 6 in O(1) now]

s2 = (123%6)  =  ((12%6)*10 + 3)%6
=  (s3*10 + 3)%6   [If I know s3 I can calculate 1234 % 6 in O(1) now]

s3 = (12 % 6 ) =  ( (1%6)*10 + 2)%6
=      ( s4*10 + 2) % 6 [If I know s4 I can calculate 1234 % 6 in O(1)  and s4 can be calculated in O(1)]

Now, We can easily implement this with a single loop which runs in O(n) . where,length(A) = n

So,

 ``` 1 2 3 4 5 6 7 8 9 10 11 12``` ```//A is taken as string //mod = B int AmodB = 0; for(int a=0;a

AmodB is initially (0*10 + 1)%6 = 1 (s4)
then,                       (1*10 + 2)%6 = 0 (s3)
then,                       (0*10 + 3)%6 = 3 (s2)
and finally,             (3*10 + 4)%6 = 4  (s1)

Theory : For any X , (X*k + m)%d = ((k%d)*X + m)%d

as, k can be written as a (multiple of d + remainder) this way  k = a*d + k%d ,for some integer a.
now, (X*k + m)%d

=   (X*(a*d + k%d) + m)%d
=   (X*a*d + X*k%d + m)%d
=   (k%d*X + m)%d  [as,X*a*d % d = 0]

Now,put X = 10

Another approach : (1234)%6 = (4 + 3*10 + 2*100 + 1*1000)%6

so, ans =  (sigma(i = 0 to n-1)  (10^i*digit[i])%mod
The problem is how can I calculate (10^i%mod) efficiently and avoiding overflow?

Look, 10^5%mod = ((10^4)%mod*(10%mod))%mod
So,we can just save 10^(i-1)%mod in the loop and in the i'th iteration I'll find 10^i%mod by multiplying 10^(i-1)%mod [which I have already saved] and 10%mod [I can also save this into a variable to avoid repeated calculation] and "mod"ing the multiplied result.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15``` ```int mod_loop = 1; int tmp = 0; int ten_mod = 10%mod; //saving this for(int a=s.length()-1;a>=0;a--) { tmp+=(mod_loop*(int)(s[a] - '0' ) )%mod; mod_loop =((mod_loop)*ten_mod)%mod; } int ans = tmp%mod ```

Problems : Type 1) You'd need to mod a Big Integer very fast / You'd need to check divisibility (if B divides A) avoiding overflow and in O(length(A))

Type 2) You'll be given B and you have to find A such that B divides A and digits of A has a certain pattern such as A = 1111111........  , 12121212121212.................

## বুধবার, ৯ ডিসেম্বর, ২০১৫

### LOJ 1010 Knights

Problem id :    LOJ 1010

To maximize the number of knights we have to place knights in a particular pattern.

Code :

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71``` ```#include int main() { int tc,cas = 0 ; int ans = 0; scanf("%d",&tc); while(tc--) { int m,n; scanf("%d %d",&m,&n); //ans = solve(m,n); //ROW / COL = 1 if(m==1) ans = n; else if(n==1) ans = m; //ROW / COL = 2 else if(m==2) { ans = 0; for(int i=1,cn=1; i<=n; i+=4,cn++) { // if(cn&1) { if(i==n) ans +=2; else ans += 4; } } } else if(n==2) { ans = 0; for(int i=1,cn=1; i<=m; i+=4,cn++) { // if(cn&1) { if(i==m) ans +=2; else ans += 4; } } } //ROW / COL > 2 else if(m&1)//odd { if(n&1)//odd ans= (m/2 + 1)*(n/2 + 1) + (m/2)*(n/2); else //m odd n even ans= (m/2 + 1)*(n/2) + (m/2)*(n/2); } else { if(n&1)//odd ans= (m/2)*(n/2 + 1) + (m/2)*(n/2); else ans= (m/2)*(n/2) + (m/2)*(n/2); } printf("Case %d: %d\n",++cas,ans); } return 0; } ```