Fork512Hz's blog

By Fork512Hz, history, 6 weeks ago,

I implemented the solution described in the editorial, with KMP instead of Z-function, but all my submissions ended up TLE41 (261016696) and I couldn't get the log^2 solution right.

By dividing the submission into $>\sqrt{n}$ and $\le\sqrt{n}$ parts I found my solution would finish in 3.2 seconds and I tried my best to squeeze in but still couldn't.

Could anyone help me optimize the constant factor further, or is KMP unable to pass?

• +1

By Fork512Hz, 2 months ago,

Hello Codeforces!

Solving 5 problems in Educational Codeforces Round 164 (Rated for Div. 2) gave me an unexpected +125 and I leaped across *1800 right into the lower bounds of purple. This means I am finally touching the eligibility to take part in contests with many of the brightest competitive programmers!

Within the 3 months after registering my account, I have learned many new techniques, with the most representative being modular inverse, segment tree with lazy propagation, fenwick tree and Tarjan's algorithm. I really believe segment tree is something like "Welcome to the realms of div.1!" However, my rating revolved around 1790 and was incredibly stable and I doubted if I was improving. But in several training sessions and VPs I managed to do well. Never mind, CM has come, and I finally start to believe I can go on in CP and reach for my goal in an ICPC regional. The next step is to defend CM, and I'm planning to learn:

• More STL
• KMP and AC automaton
• Decomposition and Mo's algorithm
• Maxflow and Mincut: Dinic's algorithm
• Euler's sieve
• Matching on a bipartite?
• Suffix array of a string?
• Fast Fourier Transformation?
• Heuristic searching and pruning techniques?

Fun fact: Div 1+2s finish at 1:35AM in China, so I did not register for CodeTON 8 because I would get up early to enjoy cherry blossoms the next day, but when upsolving I solved ABC1C2, skipped D and took down E within 90 minutes and the trip cost me 2 TON...

• +81

By Fork512Hz, history, 3 months ago,

Problem:

Given a directed graph and $q$ queries. For each query, you need to answer whether a path exists from point $x$ to point $y$. Each query needs to be processed within $O(1)$.

A BF solution is, we can do $V$ DFSs from every vertex and set the bits in the answer matrix for each visited vertex, and the complexity of preprocessing is $O(V^2)$. You can do some optimizations to reduce the steps taken in the traversal by a lot, but as long as you store the answer in a matrix, $O(V^2)$ space complexity leads to an inevitable $O(V^2)$ time complexity.

Now the question is: is it possible to do the preprocessing within less than $O(V^2)$ time, or at least, less than $O(V^2)$ space? At least, if queries are to be processed online, it seems highly improbable.

I wrote DAG in the title, because we can run Tarjan's to find out SCCs and if $x$ and $y$ belong to the same SCC it's a clear YES.

UPD: There seems to be some paper on this: Paper

• +2