BumbleBee's blog

By BumbleBee, 3 weeks ago, In English,

Given a string $$$S$$$ , I want to find the number of different substrings of each length in the range $$$[1,|S|]$$$.

I can do it using LCP array which can be constructed using the Suffix Array of the given string. But I am trying to perform this task using Suffix Automaton.

Is it possible to do this using Suffix Automaton? If yes, then how?

Read more »

 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

By BumbleBee, history, 12 months ago, In English,

I want to count the number of non-negative solutions of the equation: ax + by = c.

I know the naive approach where I can iterate over all non-negative y such that c - by is non-negative and count if c - by is divisible by a. Before starting iteration, I can check if c is a multiple of the greatest common divisor of a and b. If not, then I can simply return zero. But this will cost huge runtime for large values of a, b and c.

What is the most efficient solution for this?

Read more »

 
 
 
 
  • Vote: I like it
  • -13
  • Vote: I do not like it

By BumbleBee, history, 12 months ago, In English,

I am trying to solve problem J of this gym contest.

In short, I am given non-negative integers n, m, a and k. I have to find such integers p and q that satisfies:
p > 0
q >  - 1
k + pa = n + qm

I wrote the third equation in this way:
pa + ( - q)m = n - k

Then using extended Euclidean algorithm I found such integers x and y that,
xa + ym = g, where g = GCD(a, m)

Multiplying (n - k) / g on both side we get:
[x(n - k) / g]a + [y(n - k) / g]m = n - k

Finally, I get p = x(n - k) / g and q =  - y(n - k) / g

The problem is, my implementation finds such x and y that resulting p and q violates the constraints p > 0 and q >  - 1.

For example, if n = 3, m = 5, a = 2 and k = 2, using extended GCD I am getting:
x =  - 2, y = 1 and then p = x(n - k) / g =  - 2, q =  - y(n - k) / g =  - 1.

But I need to find x = 3, y =  - 1 so that I can get p = x(n - k) / g = 3, q =  - y(n - k) / g = 1.

Here is my implementation of extended Euclidean algorithm:

int gcdExt(int a,int b,int &x,int &y)
{
    if (a==0){
        x=0,y=1;
        return b;
    }
    int p,q;
    int r=gcdExt(b%a,a,p,q);
    x=q-(b/a)*p,y=p;
    return r;
}

How can I change this function to find coefficients x and y that give such p and q that satisfies given constraints?

Read more »

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

By BumbleBee, history, 13 months ago, In English,

Recently I found this article which describes the way to perform range minimum query with point update using the binary indexed tree.

I understood the query part quite well, implemented it myself and solved some problems with it too. Here is my code.

But I am facing problems with the update function described in this article. First of all, they said that if we make two query calls in the update function the complexity will become O(log^2(n)). So they provided with an efficient way to update without using query calls to achieve an amortized complexity of O(log(n)). But I am neither being able to understand this part nor being able to implement it.

Can anyone explain this part in a better/easier way with the code of the update function implemented in the way described here?

Read more »

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

By BumbleBee, history, 15 months ago, In English,

I was studying about matrix exponentiation here and it requires a prerequisite which says that I need to know how to find the nth power of a square matrix of dimension d in O((d^3)log(n)).

But I couldn't find any well-explained article on this topic. Can anyone please provide me with some links to blogs/articles that explain this technique?

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By BumbleBee, history, 20 months ago, In English,

Suppose, I have N distinct integers. I have to make M non-empty sets using these integers. An integer may not present in any of the sets and an integer can present in only one of the M sets. I have to print all possible ways to make M sets using these N integers.

For example, if I have N = 3 integers which are 1, 2 and 3, then there are 6 possible ways to make M = 2 sets:

1. {1} {2}

2. {1} {3}

3. {2} {3}

4. {1,2} {3}

5. {1,3} {2}

6. {1} {2,3}

How can I find out the number of ways to make M sets using N distinct integers according to the rule given above? What is the most efficient way to print all the possible ways?

I tried to solve this problem using dynamic programming, but I am having trouble to define DP states.

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

By BumbleBee, history, 20 months ago, In English,

Recently I was trying to solve the problem Sum of MSLCM from ACM ICPC Live Archive.

After a little analysis, I found out that the answer is S — 1, where S is the sum of all X such that,

X = A * (int)(N / A) for all A in the range [1, N].

int ans=0
for(int a=1;a<=n;a++){
    ans+=a*(int)(n/a);
}

But my solution won't pass the time limit if I iterate over the range [1, N] as N can be as large as 20000000.

I couldn't find another solution even after several hours of thinking and decided to search for the solution on the internet. While searching for the solution I found the following code.

#include <bits/stdc++.h>
using namespace std;
#define long long long int
int main()
{
    ios_base::sync_with_stdio(false);
    long n;
    while(cin>> n && n){
        long ans=0,a=1;
        while(a<=n){
            long x=n/a;
            long y=n/x;
            ans+=x*(((a+y)*(y-a+1))/2);
            a=++y;
        }
        ans--;
        cout<< ans <<endl;
    }
    return 0;
}

This solution passed the time limit for the given input range and got accepted.

But I still couldn't understand the formula used in this code. The only optimization I see here is that it doesn't iterate over all the numbers in the range [1, N]. But how does that work?

I want a mathematical explanation of this solution.

Read more »

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

By BumbleBee, history, 21 month(s) ago, In English,

I usually find the number of digit in the binary representation of an integer in the following way:

int digit = 1 + (int)log2(n);

I used to think that this way is absolutely correct as I never found any error. But today I got WA in problem number B (Codeforces Round 456) due to finding the number of digits in this way and I understood that this way isn't 100% correct. An integer n = 288230376151711743 was given in the case in which I got WA verdict.

While testing the error, I printed the 2 base log of 288230376151711743 using the log2() function of C++ and it printed 58. According to that 2^58 should be equal to 288230376151711743, but it isn't. 2^58 is equal to 288230376151711744.

So I guess, the value of log2(288230376151711743) is 57.99999999... or something like that which is very close to 58 and due to precision issues log2() function returns 58 in this case.

To avoid such errors I changed the way of finding the number of digits in binary in the following way:

int digit = 1 + (int)log2(n);
long long int x=(long long int)pow(2,d-1);
if(x>n) d--;

After changing my code in this way I got AC verdict, but I am still not sure about the accuracy of my way.

I want to know how much accurate is this way of finding the number of digits. If it is still not accurate, kindly suggest some other ways of finding the number of digits in the binary form of an integer which are accurate and efficient enough.

Read more »

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

By BumbleBee, history, 21 month(s) ago, In English,

Somwtimes we use different user deffined data structures in C/C++. For example,

struct data1{
    string name;
    int id;
    double marks;
}

We can also use operator overloading and user defined functions in structers.

struct data2{
    string name;
    int id;
    double marks;
    
    bool operator < (const data &a) const{
        return id<a.id;
    }

    void addMarks(double x)
    {
        marks+=x;
    }
}

Using operator overloading or user defined functions makes the use of these structures easy.

Now my question is, when I declare an array or vector of a structure, will it allocate more memory if the structure contains some user defined functions in it?

For example, if I declare two vectors of the structures declared above ( data1 and data2 ) like given below, will they allocate same amount of memory?

vector <data1> v1(1000);
vector <data2> v2(1000);

Is the amount of memory allocated increases if the structures contains some functions in it?

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By BumbleBee, history, 21 month(s) ago, In English,

I want to test a C++ program using a large input file which is in txt or other format and size of the file is almost 13 mb.

I tried the custom test option of Codeforces but it won't take files larger than 256 kb.

I just want to know that is there any online tool/compiler where I can run my C++ program with my large input file and get the execution time and memory used by the program?

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it