Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### McDic's blog

By McDic, history, 3 years ago,

Hello.

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

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

• -16

 » 3 years ago, # | ← Rev. 2 →   -13 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 :)
•  » » 3 years ago, # ^ |   0 Linear sieve? Do you mean Sieve of Eratosthenes?
•  » » » 3 years ago, # ^ |   0 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..).
•  » » » » 3 years ago, # ^ |   +4 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.
•  » » » » » 3 years ago, # ^ |   0 +1 Good luck
•  » » » » » » 3 years ago, # ^ |   0 Adhami Added n-dimensional dynamic segment tree with generalized feature support and Graham's scan( Convex hull ).
•  » » » » » 3 years ago, # ^ | ← Rev. 5 →   +3 Yes, I meant the Sieve of Erathosthenes but implemented in O(n) time. :) vector primes; vector 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 :)
•  » » » » » » 3 years ago, # ^ |   +1 That's interesting. Thank you for providing the code. I will prove myself and implement it later.
•  » » » » » » 3 years ago, # ^ |   0 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(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
•  » » » » » » » 3 years ago, # ^ | ← Rev. 3 →   +3 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.
•  » » » » » » » » 3 years ago, # ^ |   +1 Oh it was my mistake! Yeah there are 1270607 primes under 2e7. Sorry to confuse.
•  » » » » » » » » 3 years ago, # ^ |   0 I should put your code outside of if(isPrime[i]), I thought only prime numbers matter to do that.
•  » » » » » » » » » 3 years ago, # ^ |   0 No Worries. All integers matter here since we are doing it in this way.
 » 2 years ago, # |   0 Auto comment: topic has been updated by McDic (previous revision, new revision, compare).