### maroonrk's blog

By maroonrk, history, 2 months ago, We will hold Daiwa Securities Co. Ltd. Programming Contest 2021（AtCoder Regular Contest 128）.

The point values will be 400-400-600-700-800-1000.

We are looking forward to your participation! Comments (31)
 » Good luck to everyone!
 » Spoiler •  » » Same for CF Round 749 and Atcoder Beginner Contest tomorrow :)
•  » » Now I feel like I should have gone for ARC. A very bad choice going for kickstart
 » There Would be conflict between Kick-start Round G and in this round, it might be great if this round happens tomorrow.
 » 7 weeks ago, # | ← Rev. 4 →   problem C:I spend about 1 hour proving that there are at most two different positive numbers in the sequence ...
•  » » Is that necessary? It seems that my solution didn't use it :-_
 » In fact, the structure of the optimal solution in C is exactly the same as 1299C - Водный баланс
 » Is it possible to solve problem A by dp? My dp solution submission fails on most test cases. Can someone please help in finding the problem.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   I did it with DP. The problem behind your solution is the multiplication. The workaround for that is to take the logarithm in some base and then, every multiplication becomes and addition and every division becomes a subtraction. $\log(a\cdot b) = \log(a) + \log(b)$ $\log({a\over b}) = \log(a) - \log(b)$
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   Could you please explain why there isn't precision error when taking the logarithm? Or why the precision error of taking the logarithm won't make the answer incorrect?I thought about if taking the logarithm was OK during the contest, but I thought that it would be incorrect in some strict test cases and I didn't try in this way.
•  » » » » Well, I don't know any formal proof. I just thought this way:An upper bound for the final answer is $10^{9\cdot 2\cdot 10^5}$; $\ln(10^{18\cdot 10^5}) = 18\cdot 10^5\cdot \ln 10 \approx 4\cdot 10^6$, so the numbers I will deal with will have a small length, and hence I will have a very large precision. I used long doubles just in case.
•  » » » » » Thanks for your explanation!
•  » » » » Me too, but the range of the values is quite large, which indicates there must be a better solution.
•  » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   I don't think the maximum value that we can reach has any link with possible precision errors.The DP is :DP[i][gold] = max(DP[i-1][gold], DP[i-1][silver]/Ai)DP[i][silver] = max(DP[i-1][silver], DP[i-1][gold]*Ai)We are taking multiplications and not any kind of additions so whether your current power of 10 is 1 or 200 it doesn't matter for the precision error. And between the two value compared, the maximum ratio before multiplying/dividing for the final values to be approximately equals (which is where a precision error could happen) is max(Ai) which is 10^9 which is above the double precision (approx 10^-14 relative to the current power I believe ?). On the other hand, the maximum value being huge can cause an exponent overflow but you just need to reset it from time to time if (dp[i] > 10^100) dp[i] /= 10^100 ....
•  » » » » » » You make great sense! What actually restricts me is my poor floating number knowledge xD
•  » » » Thank you!!
•  » » I guess after some time of multiplying and dividing you will start losing precision and these comparisons will start failing: dp[i][flag]==dp[i-1][1-flag]/(long double)v[i-1], dp[i][flag]==dp[i-1][1-flag]*(long double)v[i-1].