thanhchauns2's blog

Some short snippets that will shorten your time.
By thanhchauns2, history, 21 month(s) ago, In English

Hi there!

In this blog I would like to share some of the code snippets that can shorten your time in future contests. Of course, I'll ignore the "international snippets"

like:

Sometimes you may find typing the identical thing again and again is boring, this blog is about some method that a few people use to get rid of them (or just only me).

So, let's get started.

Scanning/printing the whole vector in a single std::cin/std::cout

Snippet
Usage

Scanning/printing std::pair

Snippet
Usage

Ordered set and ordered multiset

Snippet
Usage

Short declaration of 2D and 3D vectors

Snippet
Usage

Erase repeated neighbor elements

Snippet
Usage

Prime test for large numbers

Snippet

Longest Increasing Subsequence

Snippet

Longest Strictly Increasing Subsequence

Snippet

Some snippets are mine, some are taken from the internet. If you want to add some snippets on the blog, please let me know in the comment section.

You can read more about ordered_set and ordered_multiset here: https://codeforces.com/blog/entry/11080

Thanks for reading! Hope this can help you.

A little surprise
  • Vote: I like it
  • +37
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +145 Vote: I do not like it
A little surprise
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +51 Vote: I do not like it

I prefer kactl's prime test as it's deterministic

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -32 Vote: I do not like it

You missed something very important sir. Without that, this blog would be incomplete. Binary Search! 

def binarySearch(arr, key):   # search lower bound(key)
    beg, end = 0, len(arr) - 1
    found = False
    ind = -1
    while beg <= end:
        mid = beg + (end - beg) // 2    # to avoid mid overflow
        if key == arr[mid]:             # condition
            found = True
            ind = mid
            # end = mid - 1     # lower bound
            break                  # traditional BS
        elif key < arr[mid]:
            end = mid - 1
        else:
            beg = mid + 1
    if not found:     # insertion point = beg (beg < end == True)
        return -1 
    else:
        return ind

I guess Um_nik would be proud of me on this day :P

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I guess we can use simple binary_search (start,end,key) function.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +349 Vote: I do not like it

    Since you thought it is a good idea to tag me: this implementation is an abomination, you should be ashamed of yourself.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +38 Vote: I do not like it

    Since someone posted an implementation of binary search, I can't not use this opportunity to popularize lifting-style binary search.

    int ans = 0;
for (int k = 1 << 29; k != 0; k /= 2)
  if (is_ok(ans + k))
    ans += k;

    which finds the greatest integer $$$x$$$ in $$$[0, 2^{30} - 1]$$$ such that is_ok(x) is true (assuming the function is binary-searchable, of course).

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Just wondering, is it better to use OR operation instead of addition? In my template which I copied uses OR instead.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        no

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Very likely it is the same; if OR is any faster, the compiler should be smart enough to see that it can be used.

        Also, if you do this thing on floating-point numbers (replacing k != 0 with k > EPS), you can't use |= anymore but can use +=.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          it also doesn't work if u start at anything other than 0

          → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    When did binary search get so complicated

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

Great blog but I prefer conventional way , because it lets me know the code structure during debugging

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

One short tip that will shorten your time:

You can delete many template <typename T> if you use auto.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it -10 Vote: I do not like it

    Not quite, the auto isn't that magical. To be more precise auto can only be use with lamda function, and some struct/class variables

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      In C++20 you can use it in many more places

      → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How about providing ordered set and ordered map instead of ordered multiset? It would be helpful to do this and teach them to use the comparators with equality (less_equal, etc) instead for a multiset. This is an example snippet:

Snippet
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (do note that I made the template format same with std::set and std::map)

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +23 Vote: I do not like it

LIS is obviously wrong.

Countertest
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I forgot to mention it is used for finding the longest LIS available's length, not itself.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      In that case it is better to return S.size(), not the multiset itself. Also, multiset is too excessive here, vector would be just better.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 3   Vote: I like it +102 Vote: I do not like it

        The shortest implementation I know is this (if you need only the length):

        // d = {INF, ... INF (n times)}
for (int x : arr) *lower_bound(d.begin(), d.end(), x) = x;
// length == position of first INF in d

        Amazing how this not so easy algorithm is a one-liner.

        And upper_bound makes it non-decreasing.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it -10 Vote: I do not like it

also let me advertise this (probably not so) short snippet which I like to call the "Universal Container Input". Simply said, it lets you use std::cin for almost any iterable container whose value type is one that could be used with std::cin (which, in turn, could be another container type). The only exception is the dynamically allocated array, which I have not found a way. Here's the snippet:

Snippet
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (oh, and std::string and char* will not use this, in this case the overload is useless and therefore I made them not use this)

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

hard to remember last time I needed to find LIS (except maybe in last 10 years)

about multivectors: c++17 allows to use $$$O(d)$$$ vectors instead of $$$O(d^2)$$$ to define required:

vector a(n, vector(m, vector<int>(k)))

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm very curious about the gnu c++ segment tree... could someone explain how it works and how to use it?

→ Reply