Fork512Hz's blog

By Fork512Hz, history, 6 weeks ago, In English

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?

Full text and comments »

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

By Fork512Hz, 2 months ago, In English

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?
  • More ad-hoc constructive problems
  • More ad-hoc dp problems

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...

Full text and comments »

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

By Fork512Hz, history, 3 months ago, In English

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

Full text and comments »

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