AQZZ's blog

By AQZZ, history, 4 years ago, In English

After searching online and doing some modifications, I found a way to create a multidimensional vector with arbitrary dimensions in C++14:

// Easily create k-dimensional vectors (C++14).
template <class T>
vector<T> create(size_t size, T initialValue) {
    return vector<T>(size, initialValue);
}

template <class T, class... Args>
auto create(size_t head, Args&&... tail) {
    auto inner = create<T>(tail...);
    return vector<decltype(inner)>(head, inner);
}

Usage:

auto dp = create<long long>(n, m, k, 1LL); // Makes an n by m by k vector filled with ones.
auto adj = create<int>(n + 1, 0, 0); // Creates the adjacency lists for a graph of n vertices.

The last argument must be of type T, otherwise there will be a compile time error. Any improvements are appreciated.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By AQZZ, history, 4 years ago, In English

I started C++ and Code Forces on April 23 2020, and so far to learn I've been reading C++ documentation, doing virtual contests and upsolving them, and learning new techniques from reading the CP handbook and CP-algorithms articles. In my practice I used to just focus on solving div2 D-E problems, but my main problem in contests was that I was taking so long on div2 A-C and implementing them that I didn't even reach div2 D-E. Therefore, recently I switched to doing virtual contests in order to improve my speed and implementation skills while still learning new things from upsolving problems I couldn't solve in the virtual contest time. It seems that this method of practice is working as I finally got blue, but is this a good way to practice in general?

Summary: What is a better way to improve? Should I do virtual contests and upsolve them, or should I only focus on solving problems above my level and hope my speed improves somehow?

Full text and comments »

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

By AQZZ, history, 4 years ago, In English

Recently I've been learning about segment tree from here: https://cp-algorithms.com/data_structures/segment_tree.html and I am wondering why they allocate an array of size 4 * N when the tree uses indices up to at most 2 * 2^(ceil(log2(N)). In the worst case, when N = 1 + 2^k for some integer k > 0, say N = 65, then they allocate 260 when only 256 is needed, but in my submissions, using the optimized memory amount cut the memory usage by 13% or more. My guess would be that the memory optimization usually isn't necessary for C++ (being one of the most efficient languages) and its more convenient to type 4 * N than 2 * (1 << int(ceil(log2l(N)))). P.S. if anyone knows a better way to get the smallest power of 2 greater than or equal to x I would like to know.

Full text and comments »

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

By AQZZ, history, 4 years ago, In English

Currently I compile with these flags: alias bd='g++ -std=c++17 -Wshadow -Wall -Wextra -o "a" -g -fsanitize=address -fsanitize=undefined'

Most of the time when I access an out of bounds index I get an error from the sanitizer that tells me the line number, which is good. But sometimes I just get an error that memory is leaked but I get no line number. Are there any flags/compilers which can print the line number consistently when this error occurs, similar to Java's index out of bounds exception?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By AQZZ, history, 4 years ago, In English

I saw many articles saying that Java Arrays.sort() on int[] has worst case complexity O(n^2) but according to the Java docs:

" public static void sort(int[] a, int fromIndex, int toIndex) Sorts the specified range of the array into ascending order. The range to be sorted extends from the index fromIndex, inclusive, to the index toIndex, exclusive. If fromIndex == toIndex, the range to be sorted is empty. Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations. "

Does this mean that Arrays.sort() is safe to use now in Java? Does it also hold for Kotlin, or does Kotlin use a lower version of Java that still has the hack-vulnerable quick-sort?

Full text and comments »

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