### Jellyman102's blog

By Jellyman102, history, 4 years ago,

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
• +57

| Write comment?
 » 4 years ago, # | ← Rev. 2 →   0 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 bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; } template 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) 
•  » » 4 years ago, # ^ |   0 Can you explain what you mean by sacrificing the boolean return?
•  » » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Jellyman102 template X& remin(X& x, const Y& y) { return x = (y < x) ? y : x; } template X& remax(X& x, const Y& y) { return x = (x < y) ? y : x; } template bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; } template bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; } 
 » 4 years ago, # |   +3 template bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } will also work
 » 4 years ago, # |   0 BTW, love the blogs, they help a lot! Please make more! :D
•  » » 4 years ago, # ^ |   0 I'm already short on ideas but I'll make new ones whenever something comes to mind.