MohammadParsaElahimanesh's blog

By MohammadParsaElahimanesh, history, 3 months ago, In English

Hello,

we have array A[n][n] and q queries. each time we get l r x means we should assign A[i][j] = x (l <= i,j <= r)

at end we want to know sum of elements in A, initially A[i][j] = 0

n <= 200'000

q <= 200'000

How we can solve this problem or what is the best time complexity we can reach?

thanks in advance

Read more »

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

By MohammadParsaElahimanesh, history, 3 months ago, In English

Hello, please fix output of test 26 in problem 1553F MikeMirzayanov

formally in this problem we should print n numbers (2 <= n <= 200'000)

but when we do such thing on test 26, occurs this error:(n = 199974 on test 26)

[wrong answer Output contains longer sequence [length = 199974], but answer contains 0 elements]

123563135 wrong answer on test 26

123564261 accepted when i ignore test 26(or n == 199974)

I'm sorry, actually I wasn't sure about where I should report this bug.

UPD : bug fixed and all wrong submissions(for this issue) rejudged.

Read more »

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

By MohammadParsaElahimanesh, history, 7 months ago, In English

Hello, Can we find for example each red node (in picture blow) in O(1)?

I try hard to find a way such as binary operations to get my ans. but i can't :(

Read more »

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

By MohammadParsaElahimanesh, history, 7 months ago, In English

Hello, many times you need to calculate lg2(n) and usually you need just to calculate floor of that. may these functions help you.

/// there are in O(1) and they work for int and long long numbers that is greater than 0
int lg2(const int &x){return 31 - __builtin_clz(x);}
long long int lg2(const long long int &x){return 63 - __builtin_clzll(x);}

Read more »

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

By MohammadParsaElahimanesh, history, 9 months ago, In English

In the name of Allah

--------------------

Hello my friends ! I have a prize for you, Actually I always have a problem with KMP. So I try to use hash string instead. I think it wood be great if we have a struct like hash and can easily work with it. So I make it ! here I implemented hash struct with C++ & you can have fun with it.

#include <bits/stdc++.h>

using namespace std;

template <typename X, typename Y, typename Z>
long long int Pow(const X &a, const Y &b, const Z &mod) /// # O(log(b))
{
    if(b == 0) return 1LL;
    long long int x = Pow(a,b/2,mod);
    return b%2 == 0? x*x%mod : (long long int)a * (x * x % mod) % mod;
}

bool ready = false;
const long long int MAX_Hash = 1e6 + 5;
const long long int mod1 = 1e9 + 7;
const long long int mod2 = 1e9 + 9;
const long long int C = 257LL;
long long int C1[MAX_Hash];
long long int C2[MAX_Hash];
long long int pow1[MAX_Hash];
long long int pow2[MAX_Hash];

void fill_C()
{
    C1[0] = C2[0] = 1LL;
    for(int i = 1; i < MAX_Hash; i++)
    {
        C1[i] = (C1[i-1] * C) % mod1;
        C2[i] = (C2[i-1] * C) % mod2;
    }
}

void fill_pow()
{
    pow1[0] = pow2[0] = 1LL;
    pow1[1] = Pow(C,mod1-2,mod1);
    pow2[1] = Pow(C,mod2-2,mod2);
    for(int i = 2; i < MAX_Hash; i++)
    {
        pow1[i] = pow1[i-1] * pow1[1] % mod1;
        pow2[i] = pow2[i-1] * pow2[1] % mod2;
    }
}

void GetReady()
{
    ready = true;
    fill_C();
    fill_pow();
}

struct Hash
{
    long long int val1 = 0, val2 = 0, S = 0;

    Hash() /// # O(1)
    {
        if(!ready)GetReady();
    }

    Hash(const char &x) /// # O(1)
    {
        Hash();
        push_back(x);
    }

    Hash(char *s, const char *e) /// # O(Len)
    {
        Hash();
        push_back(s,e);
    }

    Hash(const string &s) /// # O(len)
    {
        Hash();
        push_back(s);
    }

    Hash(const Hash &A) /// # O(1)
    {
        Hash();
        push_back(A);
    }

    void clear() /// # O(1)
    {
        S = val1 = val2 = 0LL;
    }

    void push_back(const char &x) /// # O(1)
    {
        S++;
        val1 *= C1[1];
        val1 += (long long int)x;
        val1 %= mod1;
        val2 *= C2[1];
        val2 += (long long int)x;
        val2 %= mod2;
    }

    void push_back(const string &s) /// # O(len)
    {
        for(auto u: s)
            push_back(u);
    }

    void push_back(char *s, const char *e) /// # O(len)
    {
        while(s != e)
        {
            push_back(*s);
            s++;
        }
    }

    void push_back(const Hash &A) /// # O(1)
    {
        val1 *= C1[A.S];
        val1 += A.val1;
        val1 %= mod1;
        val2 *= C2[A.S];
        val2 += A.val2;
        val2 %= mod2;
        S += A.S;
    }

    void push_front(const char &x) /// # O(1)
    {
        val1 += (long long int)x * C1[S];
        val1 %= mod1;
        val2 += (long long int)x * C2[S];
        val2 %= mod2;
        S++;
    }

    void push_front(const string &s) /// # O(len)
    {
        for(int i = s.size()-1; i >= 0; i--)
            push_front(s[i]);
    }

    void push_front(const char *s, char *e) /// # O(len)
    {
    if(e == s)return;
        do
        {
            e--;
            push_back(*e);
        }while(s != e);
    }

    void push_front(const Hash &A) /// # O(1)
    {
        val1 += A.val1 * C1[S];
        val1 %= mod1;
        val2 += A.val2 * C2[S];
        val2 %= mod2;
        S += A.S;
    }

    void operator+=(const Hash &A) /// # O(1)
    {
        push_back(A);
    }

    void operator+=(const char &x) /// # O(1)
    {
        push_back(x);
    }

    void operator+=(const string &s) /// # O(len)
    {
        push_back(s);
    }

    void pop_back(const char &x) /// # O(1)
    {
        S--;
        val1 -= (long long int)x;
        val1 *= pow1[1];
        val1 = ((val1%mod1)+mod1)%mod1;
        val2 -= (long long int)x;
        val2 *= pow2[1];
        val2 = ((val2%mod2)+mod2)%mod2;
    }

    void pop_back(const string &s) /// # O(len)
    {
        for(int i = s.size()-1; i >= 0; i--)
            pop_back(s[i]);
    }

    void pop_back(const char *s, char *e) /// # O(len)
    {
        if(e == s)return;
        do
        {
            e--;
            pop_back(*e);
        }while(s != e);
    }

    void pop_back(const Hash &A) /// # O(1)
    {
        S -= A.S;
        val1 -= A.val1;
        val1 *= pow1[A.S];
        val1 = ((val1%mod1)+mod1)%mod1;
        val2 -= A.val2;
        val2 *= pow2[A.S];
        val2 = ((val2%mod2)+mod2)%mod2;
    }

    void pop_front(const char &x) /// # O(1)
    {
        S--;
        val1 -= (long long int)x * C1[S];
        val1 = ((val1%mod1)+mod1)%mod1;
        val2 -= (long long int)x * C2[S];
        val2 = ((val2%mod2)+mod2)%mod2;
    }

    void pop_front(const string &s) /// # O(len)
    {
        for(auto u: s)
            pop_front(u);
    }

    void pop_front(char *s, const char *e) /// # O(len)
    {
        while(s!=e)
        {
            pop_front(*s);
            s++;
        }
    }

    void pop_front(const Hash &A) /// # O(1)
    {
        S -= A.S;
        val1 -= A.val1 * C1[S];
        val1 = (val1%mod1+mod1)%mod1;
        val2 -= A.val2 * C2[S];
        val2 = (val2%mod2+mod2)%mod2;
    }

    void operator-=(const Hash &A) /// # O(1)
    {
        pop_back(A);
    }

    void operator-=(const char &x) /// # O(1)
    {
        pop_back(x);
    }

    void operator-=(const string &s) /// # O(len)
    {
        pop_back(s);
    }

    void operator=(const char &s) /// # O(1)
    {
        val1 = (long long int)s;
        val2 = (long long int)s;
        S = 1LL;
    }

    void operator=(const string &s) /// # O(len)
    {
        clear();
        push_back(s);
    }

    void operator=(const Hash &A) /// # O(1)
    {
        val1 = A.val1;
        val2 = A.val2;
        S = A.S;
    }

    bool operator==(const Hash &A) const /// # O(1)
    {
        return (val1 == A.val1 && val2 == A.val2 && S == A.S);
    }

    bool operator==(const string &s) const /// # O(len)
    {
        Hash A(s);
        return (val1 == A.val1 && val2 == A.val2 && S == A.S);
    }

    bool operator==(const char &x) const /// # O(1)
    {
        return (val1 == (long long int)x && val2 == (long long int)x && S == 1);
    }

    bool empty() /// # O(1)
    {
        return (S == 0);
    }

    long long int size() /// # O(1)
    {
        return S;
    }
}EMPTY, PLUS, MINUS;

template <typename T>
Hash operator+(const Hash &A, const T &B)
{
    PLUS = A;
    PLUS += B;
    return PLUS;
}

template <typename T>
Hash operator-(const Hash &A, const T &B)
{
    MINUS = A;
    MINUS -= B;
    return MINUS;
}
int main()
{

    return 0;
}


you can push_back, pop_back, push_front, pop_front a char*, string ,a char and also a hash to your hash and many other work. notice mainly when you want to use a string or a char* program handle on O(length) but when you use hash or a char it will be O(1). and also for the first time you want to hash some thing program does Preprocessing in O(MAX_Hash) where MAX_Hash is max length of a string you want to hash it, you can easily set it. its default is 1e6 + 5.

For the theory part you can visit : https://cp-algorithms.com/string/string-hashing.html

about variable I use: S is length of hashed string, val1 is hash of string in mod mod1, val2 is hash of string in mod mod2. note : there is no Anti-hash yet that can hack you with this hash function.

Now I want to introduce functions one by one in examples:

    char t[20] = "Hash Struct . . .";
    string s = "OK!";
    Hash A; /// simple
    Hash B("Hello codeforces !"); /// give a string
    Hash C(t,t+17); /// give a char* with two pointers
    Hash D(B); /// give an other Hash

    B.clear(); /// now B is completely empty

    D.push_back('@'); /// -@- will added to end of D
    B.push_back(s); /// string s will added to end of B
    B.push_back(t,t+4); /// -Hash- (t,t+4) will added to end of B
    C.push_back(A); /// A will added to C but A was empty and has no effect

    D.push_front('_'); /// -_ will added to front of D
    B.push_front("String B is :"); /// -String B is :- will added to front of B
    A.push_front(t+5,t+12); /// -Struct - (t+5,t+12) will added to front of A
    C.push_front(A); /// A will added to front of C

    B += D; /// D will added to end of B
    A += '%'; /// -%- will added to end of A
    C += "I am C !"; /// -I am C !- will added to end of C

    /*
        notice pop_back and pop_front should give a real char, string, char* or a Hash
        for example A is "Struct" now and we can:
    */
    A.pop_back('t'); /// -Struct- -> -Struc-
    A.pop_back("uc"); /// -Struc- -> -Str-
    A.pop_back(t+7,t+8); /// -Str- -> -St-
    A.pop_back(A); /// It's unusual way to clear a Hash !

    /// B's front is -String B is :-
    B.pop_front("String"); /// -String B is :- -> - B is :-
    B.pop_front(' '); /// - B is :- -> -B is :-
    B.pop_front(t+4,t+4); /// nothing
    B.pop_front(B); /// It's unusual way to clear a Hash !

    /// -= is like pop_back so now C has -I am C !- at end
    C -= '!'; /// -I am C !- -> -I am C -
    C -= " C "; /// -I am C - -> -I am-
    C -= C; /// C now is empty but if for example Hash E = " am", you can write C -= E => -I am- -> -I-

    D = '*'; /// now D is just -*-
    A = "ABCD"; /// now A is just -ABCD-
    B = A; /// now B is just like A means -ABCD- here

    A == B; /// return true if A is_equal to B else false
    D == "ABDE"; /// return true if A is_equal to -ABDE- else false
    D == '*'; /// return true if D = -*- else false

    C.empty(); /// return true if and just if length of C is 0
    C.size(); /// return length of C

    D = A + B - C; /// D will be A + B - C(it's different from A - C + B)

At last If you have a suggestion or want to know something or find a bug(you can't find bug but maybe) or else please and please tell me by writing comments.

Hope to enjoy it.

THE END . . .

Read more »

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