McDic's blog

I just constructed my github repository to store my implementations.
By McDic, history, 6 years ago, In English

Hello.

Just started to participate contests to fill 25 participation in codeforces, now I even created my github repository to store my implementation :)

The link is here: https://github.com/McDic/MyImplementations/

Just wanted to show public, you can freely see or criticize my code anytime.

<2019-08-23> Now I have following my own implementations:

  • Trie and Aho Corasick
  • Segment Tree and Lazy Propagation
  • Shortest path algorithms such as Dijkstra and Floyd Warshall
  • Disjoint Set Union
  • Eratosthenes Sieve (both and O(n))
  • Convex Hull (both Graham Scan and Monotone)
  • KMP and Polynomial String Hashing
  • Matrix (but no advanced operations yet)
  • LCA
  • and some other uncompleted stuffs

My further future implementation goal is:

  • Minimum Spanning Tree (I don't know why I don't have this in my repository. This is easier, I will implement this asap)
  • Heavy Light Decomposition (What the heck this is too hard to implement myself)
  • Fast prime decomposition and primality test (like Pollard Rho's, Miller-Rabin primality test)
  • Optimized Matrix stuffs (Gaussian elimination, Determinant, etc)
  • Big Integers and Fractions with basic arithmetic and comparison operators
  • Strongly Connected Components

Thank you for reading this.

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

»
6 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

One suggestion I have is that if you are building a repository of implementations, why not store the linear O(n) implementation of the Sieve of Erathosthenes :)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Linear sieve? Do you mean Sieve of Eratosthenes?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's why people would like to see the implementations of a red rather than blue. There are some advanced algorithms you didn't put in your github (Convex Hull, FFT, etc..).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Yeah I know but that's not problem at least I think? I'm just making my own tower to improve my competitive programming skill and I never forced anyone to see mine.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          +1 Good luck

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Adhami Added n-dimensional dynamic segment tree with generalized feature support and Graham's scan( Convex hull ).

            → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 5   Vote: I like it +3 Vote: I do not like it

          Yes, I meant the Sieve of Erathosthenes but implemented in O(n) time. :)


          vector <int> primes;

vector <int> is_prime(N, true);
is_prime[0] = is_prime[1] = false;

for(int i = 2; i < N; i++)
{
      if(is_prime[i]) primes.push_back(i);

      for(int j = 0; j < primes.size() && i*primes[j] < N; j++)
      {
               is_prime[i*primes[j]] = false;

               if(i%primes[j] == 0) break;
      }
}

          The reason this is O(N) is because every element is touched at most once. We maintain the invariant that is_prime[x] = false, is done only one time, when we are visiting x's smallest prime factor.

          We break when i%primes[j] == 0 because it means that (i*primes[j + 1]) will have the smallest prime factor of primes[j]

          Just a suggestion :)

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            That's interesting. Thank you for providing the code. I will prove myself and implement it later.

            → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            ghoshsai5000 Sorry, it seems the algorithm from your code is incorrect. I tried with your code and it says there is a different amount of primes under 2e7. Commented part is your code. (Your code says 4 is prime.)

            primes.clear();
	isPrime = std::vector<bool>(n+1, true);
	isPrime[0] = false; isPrime[1] = false;
	for(int i=2; i<=n; i++){
		if(isPrime[i]){
			for(int j=2*i; j<=n; j+=i) isPrime[j] = false;
			/*for(int j=0; j<primes.size() && i*primes[j] <= n; j++){
				isPrime[i*primes[j]] = false;
				if(i % primes[j] == 0) break;
			} */
			primes.push_back(i);
		}
	}
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 3   Vote: I like it +3 Vote: I do not like it

              Hi McDic, I have used this in problems many times. I have also tested it on ideone here to check and it looks fine to me.

              Probably, one thing I didn't do in the code snippet I presented was declare the vector 'primes'. I updated it.

              Also, could you tell me how many primes there are under 2 × 107 ? I have tested my code here. There might be some bug related to overflow.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it +1 Vote: I do not like it

                Oh it was my mistake! Yeah there are 1270607 primes under 2e7. Sorry to confuse.

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I should put your code outside of if(isPrime[i]), I thought only prime numbers matter to do that.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  No Worries.

                  All integers matter here since we are doing it in this way.

                  → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by McDic (previous revision, new revision, compare).

→ Reply