Jellyman102's blog

An Explaination of ckmin and ckmax [C++]
By Jellyman102, history, 5 years ago, In English

Since my previous blog (using dy/dx arrays on grids) seemed to be helpful for some beginners, I wanted to share another very common trick that saves time with dp (and other optimization problems) and is much less error prone than it's counterpart. Again, this is a very minor trick and won't make the difference between solving a problem and missing it, but it's helpful to understand how it works in case you want to try it at some point (many LGMs have this in their templates). Somewhere in your template, start by writing these two functions.

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }

We'll talk about ckmin since ckmax does the same thing but with max. Let's say you want to find the number of integers in an array that are smaller than all the integers before it. To solve this in O(n), simply maintain int ans = 0 and int currMin = INF and iterate over the array. Normally you may see something like this:

if(a[i] < currMin){ currMin = a[i]; ans++; }

While this works, the functions I posted above can be used like so:

if(ckmin(currMin, a[i])) ans++;

If you look closely at the implementation of ckmin, it should be clear that these two are identical.

Although it seems like a practically useless detail, using ckmin and ckmax can be much less error prone in more difficult problems and can lead to very clean dp implementations (such as 0-1 knapsack, which I would put here if I knew how formatting code actually works on these blogs).

I hope this makes sense. If I think of more common tricks to explain in the future I'll post about it so keep your eyes open.

  • Jellyman
  • Vote: I like it
  • +57
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice insight!

In fact, we can make ckmin and ckmax even more general (so we can use them for long long, long double, etc. -- not just int) 

template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }

Or, if you are not opposed to having macros (and sacrificing the boolean return), even easier: 

#define ckmin(a,b) a = min(a,b)
#define ckmax(a,b) a = max(a,b)
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain what you mean by sacrificing the boolean return?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With his macros, he can't use those in if statements as shown in the post. The whole idea of it is to use if(ckmin(a,b)) to run code whenever a is actually changed. Using #define ckmin(a,b) a = min(a,b) doesn't do this.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Jellyman102

    template<typename X, typename Y> X& remin(X& x, const Y& y) { return x = (y < x) ? y : x; }
template<typename X, typename Y> X& remax(X& x, const Y& y) { return x = (x < y) ? y : x; }
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
    → Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it 
template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }

will also work

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

BTW, love the blogs, they help a lot! Please make more! :D

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm already short on ideas but I'll make new ones whenever something comes to mind.

    → Reply