Problem 629D (heaviest increasing subsequence) discussion

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Problem 629D - Babaei and Birthday Cake asks for the heaviest strictly increasing subsequence of a set of volumes. When I saw this problem (in practice) I immediately recognized that this was probably a well-known problem, so I looked up code. I found some code from StackOverflow, but it occured to me that this code only found the heaviest nondecreasing subsequence. Not willing to change the code too much, I came up with the following idea. If taking the array one by one is like:

l = []
for r in range(n):
    k = int(input())
    l.append(k)

then in order to make the heaviest strictly increasing subsequence roughly equal to the heaviest nondecreasing subsequence, do something along these lines. This should work, because the epsilon is small enough such that the relative order should not be changed, but equal terms will have a difference: terms which come closer to the front will be ever so slightly larger than equal terms closer to the end.

l = []
for r in range(n):
    k = int(input())
    l.append(k + (n-r)*0.000001)

I submitted this idea, 16347971, but it did not succeed. Why? Because floats do not have sufficient precision, and the numbers in the array can range from 1e15 to 1. Hence, this will have negligible difference under this. The naive way to fix this is just to increase the precision of the numbers, like this:

l = []
for r in range(n):
    k = int(input())
    l.append(Decimal(k) + Decimal((n-r)*0.000001))

I tried this too, but it turns out that we in fact get TLE when we try this, even when we water down the precision: 16348275. And who can blame this? We clearly have to undergo a paradigm shift, because this is bad: since the numbers change so much: a fixed error for each term is not acceptable. How about instead of an absolute error, we use a relative error?

This would look like:

l = []
for r in range(n):
   k = int(input())
   l.append(k + (n-r)*k*0.00000001)

The reason this works is that equal terms are still larger when they come at the front. However, this method has its own flaws: for instance, there is a chance that if k is large enough, this term will become larger than k+1. Furthermore, the sum of all terms in the subsequence will have a significant difference with the original value. This can be fixed, however, by using a small enough epsilon, as seen below:

l = []
for r in range(n):
   k = int(input())
   l.append(k + (n-r)*k*0.00000000001)

Surely enough, this gets AC! 16348026

Hopefully this brightened up your day!

History