Monday, 31 August 2015

Fatal Eagle has decided to do something to save his favorite city against the attack of Mr. XYZ, since no one else surprisingly seems bothered about it, and are just suffering through various attacks by various different creatures.

Seeing Fatal Eagle's passion, N members of the Bangalore City decided to come forward to try their best in saving their city. Now Fatal Eagle decided to strategize these N people into a formation of AT LEAST K people in a group. Otherwise, that group won't survive.

Let's demonstrate this by an example. Let's say that there were 10 people, and each group required at least 3 people in it for its survival. Then, the following 5 groups can be made:

10 - Single group of 10 members.
7, 3 - Two groups. One consists of 7 members, the other one of 3 members.
6, 4 - Two groups. One consists of 6 members, the other one of 4 members.
5, 5 - Two groups. One consists of 5 members, the other one of 5 members.
4, 3, 3 - Three groups. One consists of 4 members, the other two of 3 members.

Given the value of N, and K - help Fatal Eagle in finding out the number of ways he can form these groups (anti-squads) to save his city.

Input format:
The first line would contain, T - denoting the number of test cases, followed by two integers, N and K denoting the number of people who're willing to help and size of the smallest possible group which can be formed.

Output format:
You've to print the number of ways in which groups can be formed.

Constraints:
1 <= T <= 30
1 <= N, K <= 200

Sample Input

(Plaintext Link)

2
10 3
20 5

Sample Output

(Plaintext Link)

5
13

A very good way to brush up recursive DPs. Here the given problem is a variation of the standard integer partition problem . Only the limitation being, the group size should be atleast k.To do these first we understand that how things are broken up. An important observation is for thinks like 7 and k=3 we may repeat the counting of the group like (4,3) and (3,4). So , I suggest recursuve manner.

No we keep two things in our recursion the left number of soldiers to be allotted and the last alloted group. We always try to ensure the fact that the present group is given more than equal to the last group and obviously greater than K. the base cases are

(1) If dp is known return it;

(2) If present falls to 0 return 1, becuase that arrangment is possible.

(3) If present is less than K than forming that group is impossible so return 0;

The code goes here

#include<bits/stdc++.h>
using namespace std;
long long int dp[250][250];
long long int solve(int present, int k,int prev )
{
 //cout<<present<<" "<<prev<<endl;
 if(present==0)
 return 1;
 if(present<k)
 return 0;
 if(dp[present][prev]!=-1)
 return dp[present][prev];
 else
 {
  dp[present][prev]=0;
  for(int i=k;i<=present;i++)
  {
    if(i>=prev)
    dp[present][prev]+=solve(present-i,k,i);
  }
 // cout<<"returning dp "<<present <<" "<<prev<<" "<<dp[present][prev]<< endl;
  return dp[present][prev];
 }
 
}
int main()
{
int t;
cin>>t;
while(t--)
{
 int n;
 cin>>n;
 int k;
 cin>>k;
 for(int i=0;i<210;i++)
 {
   for(int j=0;j<210;j++)
   dp[i][j]=-1;
 }
 long long int ans=solve(n,k,0);
 cout<<ans<<endl;
}
return 0;
}

You are given a sequence of N integer numbers A. Calculate the sum of A_i AND A_j for all the pairs (i, j) where i < j.

The AND operation is the Bitwise AND operation, defined as in here.

Input

The first line of input consists of the integer N.

The second line contains N integer numbers - the sequence A.

Output

Output the answer to the problem on the first line of the output.

Example

Input:
5
1 2 3 4 5

Output:
9

Scoring

Subtask 1 (13 points): N <= 1000, A_i <= 1.

Subtask 2 (39 points): N <= 1000, A_i <= 10⁹.

Subtask 3 (21 points): N <= 10⁵, A_i <= 1.

Subtask 4 (27 points): N <= 10⁵, A_i <= 10⁶.

A very well designed problem that can be easily tackled with bit logic and hashing.

Let us observe few things, The and operator results in one only when both the bits are ON. So first step is hashing the

On bits . i.e finding the number of numbers for which 0th bit is on then 1th bit is On then 2nd bit is on and so On. there can be maximum 30 bits.

Now for a present number we break it bitwise. Suppose the ith bit of the number is ON then we first decrease the hash count of that bit and then we add power(2,i)*hash[i] to the result . as power(2,i) is the value in decimal of that bit being on

and hash[i] gives the count of such bits on the right side.

*** code goes here******

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int hash[35];
long long int ans=0;
long long int arr[100010];
long long int power(int n ,int k)
{
if(k==0)
return 1;
long long int temp=power(n,k/2);
if(k%2==0)
return temp*temp;
else
return n*temp*temp;
}
int main()
{
int n;
cin>>n;
// cout<<power(2,5)<<" "<<power(2,10)<<endl;
for(int i=0;i<n;i++)
{
cin>>arr[i];
for(int k=0;k<31;k++)
{
if(arr[i]&1<<k)
hash[k]++;
}
}
ans=0;
// cout<<"done "<<endl;
for(int i=0;i<n;i++)
{
// cout<<arr[i]<<endl;
for(int k=0;k<31;k++)
{
if(arr[i]& 1<<k)
{
// cout<<"for k ="<<k<<endl;
hash[k]--;
ans=ans+power(2,k)*hash[k];
}
}
//cout<<"ans wer is "<<ans<<endl;
}
cout<<ans<<endl;
return 0;
}
****** ends here *****

Twilight Sparkle was playing Ludo with her friends Rainbow Dash, Apple Jack and Flutter Shy. But she kept losing. Having returned to the castle, Twilight Sparkle became interested in the dice that were used in the game.

The dice has m faces: the first face of the dice contains a dot, the second one contains two dots, and so on, the m-th face contains mdots. Twilight Sparkle is sure that when the dice is tossed, each face appears with probability $\text{[math]}$ . Also she knows that each toss is independent from others. Help her to calculate the expected maximum number of dots she could get after tossing the dice n times.

Input

A single line contains two integers m and n (1 ≤ m, n ≤ 105).

Output

Output a single real number corresponding to the expected maximum. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.

Sample test(s)

input
6 1

output
3.500000000000

input
6 3

output
4.958333333333

input
2 2

output
1.750000000000

Note

Consider the third test example. If you've made two tosses:

You can get 1 in the first toss, and 2 in the second. Maximum equals to 2.
You can get 1 in the first toss, and 1 in the second. Maximum equals to 1.
You can get 2 in the first toss, and 1 in the second. Maximum equals to 2.
You can get 2 in the first toss, and 2 in the second. Maximum equals to 2.

The probability of each outcome is 0.25, that is expectation equals to:

$\text{[math]}$

You can read about expectation using the following link: http://en.wikipedia.org/wiki/Expected_value

This is a question based on observation and the observation has to be kept on mind. First read the editorial

Brief description:

Calculate the expected maximum number after tossing a m faces dice n times.

Analysis:

Take m = 6, n = 2 as a instance.

6 6 6 6 6 6
5 5 5 5 5 6
4 4 4 4 5 6
3 3 3 4 5 6
2 2 3 4 5 6
1 2 3 4 5 6

Enumerate the maximum number, the distribution will be a n-dimensional super-cube with m-length-side. Each layer will be a large cube minus a smaller cube. So we have:

$\text{[math]}$

My observation m=6 and n=2;
for max =1 (1,1) for max=2 (2,1) (1,2) for max=3 (3,1) (3,2) (3,3) (1,3) (2,3)
The numberof ways of getting i as the maximum is i^n -(i-1)^n . And this formula is strictly followed.
Here s the code
#include<bits/stdc++.h> using namespace std; double power(double x, int y) { if(y==0) return 1 ; double temp=power(x,y/2); if(y%2==0) return temp*temp; else return x*temp*temp; } int main() { int n,m; cin>>m>>n; double ans=0.00; for(int i=1;i<=m;i++) { double temp=power((double)i/(double)m,n)-power((double)(i-1)/(double)m,n); ans=ans+(double)i*temp; } printf("%.7lf",ans); }

Tuesday, 11 August 2015

Cooking dishes

Problem code: COOKFOOD

All submissions for this problem are available.

As you might know, cooking is the process of taking a food item and subjecting it to various processes(like heating, roasting, baking etc).
A food item gets prepared after it has been subjected to exactly N processes.
The order in which the processes are applied matters(heating and then baking is different from baking and then heating). Also, the same processes cannot be aplied twice in succession. For example, heating → baking → heating is allowed, but heating → heating → baking is not allowed because 'heating' comes twice in succession.
Any given sequence A₁, A₂, A₃, ... A_N of N processes can be used to cook a food item if and only if A_i ≠ A_i+1 for all 1 ≤ i ≤ N-1.
The chefs kitchen has got K equipments for K different processes.
Chef has to cook two dishes in parallel.
This means that if the first dish is prepared by applying processes A₁, A₂, A₃, ... A_N in this order, and the second dish made by processes B₁, B₂, B₃, ... B_N, then A_i ≠ B_i for any 1 ≤ i ≤ N, because otherwise chef would need two equipments for the process A_i.
Needless to say, 1 ≤ A_i, B_i ≤ K, no two consecutive elements of A are same, and no two consecutive elements of B are same.
Given N, K your task is to find the number of ways in which in which he can prepare the two dishes. Since the number of ways can be very huge, you have to report it modulo 1000000007.

Input Description

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case is described by line containing two space separated integers, N and K as per the problem description.

Output Description

For each Test case, output a separate line containing the answer modulo 1000000007.

Sample Input

3

2 2

2 3

1 3

Sample Output

2

18

6

Explanation

For first test case, there are two ways:
a) A = {1, 2} and B = {2, 1} and b) A = {2, 1} and B = {1,2}.

For third test case, A and B are of length 1. A₀ can take three different values and for each value of A₀, B₀ can take any of the other two values.

Constraints

T ≤ 100
1 ≤ N, K ≤ 10⁹

Subtask 1 (30 points):

N, K ≤ 5

Subtask 2 (20 points):

N, K ≤ 10000

the answer(without taking modulo 1000000007) will be at most 10⁴.

Subtask 3 (25 points):

N, K ≤ 10000

Subtask 4 (25 points):

No special constraints

Explanation:

Let us fill in values for the processes for A and B simultaneously from i = 1 to N. For i = 1, there are K choices for A₁ and K-1 choices for B₁. For a general other i, when we fill in A_i and B_i, we wish only that A_i != A_i-1, B_i != B_i-1 and A_i != B_i.
So, there seem to be K-1 choices for A_i != A_i-1 and similarly for B_i. but we haven't ensured that A_i != B_i. We have to still subtract from these (K-1)^2 choices, those where the two are equal to each other, but aren't equal to the previous two. There are K-2 choices for the them not being equal to the previous two, and for each of these choices, by setting A_i and B_i to this value, we get such a bad case. Thus the total number of ways of getting from i-1 to i, is (K-1)^2 - (K-2).
Another way of arriving at the above is, let us first fill in A_i and then B_i. We have two cases:
Case 1: A_i != B_i-1 and A_i-1 : there are K-2 cases.
Given this, B_i != B_i-1 as well as A_i, hence there are K-2 choices for B_i.
Case 2: A_i = B_i-1. This already gives us that A_i != A_i-1. There is 1 choice for this.
Given the above, B_i != B_i-1 only (since its anyway equal to A_i). Thus, there are K-1 choices for B_i.
The above reasoning gives us that the number of choices for A_i and B_i are (K-2)^2 + K-1. Note that this is also what we had got earlier.
Thus, final answer = (K * (K-1)) * ((K-2)^2 + K-1)^(N-1).

***** code goes here ****
#include<bits/stdc++.h>
using namespace std;
long long int mod=1000000007;
long long int pow(long long int a, long long int b)
{
    if(b==0)
    return 1;
    if(b%2==0)
    {
          return (pow(a,b/2)*pow(a,b/2))%mod;
    }
    else
    return (((pow(a,b/2)*pow(a,b/2))%mod)*a)%mod;
}
int main()

{
    int t;
    cin>>t;
    while(t--)
    {

    long long int n;
    cin>>n;
    long long int k;
cin>>k;
    long long int fact1=((k-2)*(k-2))%mod;
    long long int fact2=(fact1+k-1)%mod;
    long long int res=pow(fact2,n-1);
    long long int ans=(((k*(k-1))%mod)*(res))%mod;
    //cout<<"here "<<endl;
    cout<<ans<<endl;

}
return 0;
}
*******ends here *****

Monday, 10 August 2015

Queries on the String

Problem code: QSET

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian.

You have a string of N decimal digits, denoted by numbers A₁,A₂, ..., A_N.

Now you are given M queries, each of whom is of following two types.

Type 1: 1 X Y: Replace A_X by Y.
Type 2: 2 C D: Print the number of sub-strings divisible by 3 of the string denoted by A_C,A_C+1 ...
A_D.

Formally, you have to print the number of pairs (i,j) such that the string A_i,A_i+1...A_j,
(C ≤ i ≤ j ≤ D), when considered as a decimal number, is divisible by 3.

Input

There is only one test case.
First line of input contains two space separated integers N, M.
Next line contains a string of N digits, denoting string A.
For next M lines, each line contains a query.
Each query is given by three space separated integers.
The first integer denotes type of the query. For each query of type 1, next two integers denote X_i, Y_i.
For each query of type 2, next two integers denote C_i, D_i.

Output

For each query of type 2, print the required answer in a single line.

Constraints

0 ≤ A_i ≤ 9
1 ≤ X_i ≤ N
0 ≤ Y_i ≤ 9
1 ≤ C_i ≤ D_i ≤ N

Subtasks

Subtask #1 (10 points): 1 ≤ N, M ≤ 10³ and only type 2 queries.
Subtask #2 (15 points): 1 ≤ N, M ≤ 10³
Subtask #3 (20 points): 1 ≤ N, M ≤ 10⁵ and only type 2 queries
Subtask #4 (55 points): 1 ≤ N, M ≤ 10⁵

Example

Input:
5 3
01245
2 1 3
1 4 5
2 3 5

Output:
3
1

Explanation

For first query, the sub-strings S[1,1]="0", S[1,3]="012" and S[2,3]="12" are divisible by 3.
After second query, the string A becomes "01255".
For third query, only sub-string S[3,5]="255" is divisible by 3.

A very firm understanding of this question is the key to solve it .

For each node we require 4 things. the number of substrings divisible by 3 on the segment , the total sum of the segment and the prefix and the suffix array .

where prefix array stands for the number of elements starting with the prefix and whos sum%3 gives 0,1 ,2. It is the same for prefix array. Now while ,merging two nodes , we first need to create the prefix and suffix arrays for the node

Rikhail Mubinchik believes that the current definition of prime numbers is obsolete as they are too complex and unpredictable. A palindromic number is another matter. It is aesthetically pleasing, and it has a number of remarkable properties. Help Rikhail to convince the scientific community in this!
Let us remind you that a number is called prime if it is integer larger than one, and is not divisible by any positive integer other than itself and one.
Rikhail calls a number a palindromic if it is integer, positive, and its decimal representation without leading zeros is a palindrome, i.e. reads the same from left to right and right to left.
One problem with prime numbers is that there are too many of them. Let's introduce the following notation: π(n) — the number of primes no larger than n, rub(n) — the number of palindromic numbers no larger than n. Rikhail wants to prove that there are a lot more primes than palindromic ones.
He asked you to solve the following problem: for a given value of the coefficient A find the maximum n, such that π(n) ≤ A·rub(n).

Input

The input consists of two positive integers p, q, the numerator and denominator of the fraction that is the value of A ( $\text{[math]}$ , $\text{[math]}$ ).

Output

If such maximum number exists, then print it. Otherwise, print "Palindromic tree is better than splay tree" (without the quotes).

Sample test(s)

Input

1 1

Output

Input

1 42

Output

Input

6 4

Output

The key thing of this question was the calculation of the highest number till which n

can go, and this is briefly expalined in the context editorials.

It is known that amount of prime numbers non greater than n is about $\text{[math]}$ .
We can also found the amount of palindrome numbers with fixed length k — it is about $\text{[math]}$ which is $\text{[math]}$ .
Therefore the number of primes asymptotically bigger than the number of palindromic numbers and for every constant A there is an answer. Moreover, for this answer n the next condition hold: $\text{[math]}$ . In our case n < 10⁷.
For all numbers smaller than 10⁷ we can check if they are primes (via sieve of Eratosthenes) and/or palindromes (via trivial algorithm or compute reverse number via dynamic approach). Then we can calculate prefix sums (π(n) and rub(n)) and find the answer using linear search.
For A ≤ 42 answer is smaller than 2·10⁶.
Complexity — $\text{[math]}$ .

Now , it is easy to see that we calculate the primes till 2*10^6 and palindromes upto that range and store them in an array. After this is done , we just check form manx to 0 to see if the condition is satisfied. If yes we take it as the maximum number.

******* Here goes the code*****

#include<bits/stdc++.h>
using namespace std;
int sv[2000010];
int n=1200000;
int palinhash[2000010];
char c[20];
int numpr[2000010];
            int      numprcnt[2000010];
            int palin[2000010];
            int palincnt[2000010];
int sumpr[2000100];
    int sumpalin[2000100];
    bool ispal(int x) {
int l = 0;
while(x>0) {
    c[l] = x%10;
    l++;
    x/=10;
}
for(int i=0; i<l/2; i++) {
    if(c[i]!=c[l-i-1]) return 0;
}
return 1;
}

void seive()

{
    //cout<<"started "<<endl;
    sv[2]=0;
    for(int i=2;i<=sqrt(n);i++)
    {
          if(!sv[i])
          {
             for(int j=2;j*i<=n;j++)
             {
                   sv[i*j]++;
               }
          }
    }
}
int main()
{
    int t;
    seive();
   // cout<<"dne "<<endl;
    int top=0;

// cout<<"here "<<endl;
    int val=0;
    int last=0;
    for(int i=1;i<=n;i++)
    {

         // int l=strlen(str);
          if(ispal(i))
          {

                 palinhash[i]++;

          }


    }
//cout<<n<<endl;

    int p;
    int q;

    sumpr[0]=0;
    sumpalin[0]=0;
    sv[1]=1;
      for(int i=1;i<=2000001;i++)
      {
        sumpalin[i]=sumpalin[i-1];
        sumpr[i]=sumpr[i-1];
         if(sv[i]==0)
         {

         // cout<<"hjere "<<i<<endl;
               sumpr[i]=1+sumpr[i-1];
           }
           if(palinhash[i]==1)
           {
         //     cout<<i<<" ";
              sumpalin[i]=1+sumpalin[i-1];
           }
      }


   //   cout<<sumpalin[10001]<<endl;
    // cout<<sumpr[100001]<<endl;
     cin>>p>>q;

     double a = (double)p / q;
      int ans=0;
for (int i = n; i >0; i--) {
    if((double)sumpr[i] <= (double)a*sumpalin[i]){
    // ans=i;
       cout<<i<<endl;
       return 0;
    }
}

cout << "Palindromic tree is better than splay tree" << std::endl;
return 0;
}
********* ends    here* ***