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

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 <bits/stdc++.h>


#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<int, int>

#define padd pair<dd, dd>

#define pall pair<ll, ll>

#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[1000009];
ll num_dr[10];//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<<final_ans<<endl;

    return 0;
}
এর দ্বারা পোস্ট করা এই সময়ে কোন মন্তব্য নেই:

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

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<s.length();a++)
{
    AmodB = (AmodB*10 + (int)(s[a] - '0'))%mod;
    
}

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<stdio.h>
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;
}
এর দ্বারা পোস্ট করা এই সময়ে কোন মন্তব্য নেই:
এতে সদস্যতা: পোস্টগুলি (Atom)