### 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!

• +125

 » 7 weeks ago, # |   +13 Good luck to everyone!
 » 7 weeks ago, # |   +23 Spoiler
•  » » 7 weeks ago, # ^ |   +5 Same for CF Round 749 and Atcoder Beginner Contest tomorrow :)
•  » » 7 weeks ago, # ^ |   +32 Now I feel like I should have gone for ARC. A very bad choice going for kickstart
 » 7 weeks ago, # |   +24 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 →   +25 problem C:I spend about 1 hour proving that there are at most two different positive numbers in the sequence ...
•  » » 7 weeks ago, # ^ |   0 Is that necessary? It seems that my solution didn't use it :-_
 » 7 weeks ago, # |   +24 In fact, the structure of the optimal solution in C is exactly the same as 1299C - Водный баланс
 » 7 weeks ago, # |   +3 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 →   +7 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 →   0 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.
•  » » » » 7 weeks ago, # ^ |   +9 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.
•  » » » » » 7 weeks ago, # ^ |   0 Thanks for your explanation!
•  » » » » 7 weeks ago, # ^ |   0 Me too, but the range of the values is quite large, which indicates there must be a better solution.
•  » » » » » 7 weeks ago, # ^ | ← Rev. 3 →   +8 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 ....
•  » » » » » » 7 weeks ago, # ^ |   0 You make great sense! What actually restricts me is my poor floating number knowledge xD
•  » » » 7 weeks ago, # ^ |   0 Thank you!!
•  » » » 7 weeks ago, # ^ |   0 can you send your code link
•  » » » » 7 weeks ago, # ^ |   0 Here.
•  » » 7 weeks ago, # ^ |   +1 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].
•  » » » 7 weeks ago, # ^ |   0 Could you explain why taking logarithm will fix the precision error?
•  » » » » 7 weeks ago, # ^ |   0 I don't understand the solution with logarithms. I approached the problem differently: sell high, buy low. That is I track the local maximum and sell gold at that point. After that I look for the local mimum to buy gold again. I don't even know whether someone solved it the same way =)
•  » » » » » 7 weeks ago, # ^ |   +3 Read this comment, if you just do multiplication it'll overflow the safe range for doubles and C++ with only take the numbers in exponential form.
 » 7 weeks ago, # |   0 how to solve B .explain please
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 max of below: max(a, b) if (abs(a, b) % 3 == 0)max(a, c) if (abs(a, c) % 3 == 0)max(b, c) if (abs(b, c) % 3 == 0)solution by Official Editorial
•  » » » 7 weeks ago, # ^ |   0 but.why it is??? how working??
•  » » » » 7 weeks ago, # ^ |   0 there is explaination in this link https://atcoder.jp/contests/arc128/editorial/2790
 » 7 weeks ago, # | ← Rev. 2 →   0 Is there a solution code of problem D by the Official Editorial?
•  » » 7 weeks ago, # ^ |   0 I got one, this is simple code... https://atcoder.jp/contests/arc128/submissions/26587762
 » 7 weeks ago, # |   0 how to solve C .Thanks~
•  » » 7 weeks ago, # ^ |   0