We will hold Daiwa Securities Co. Ltd. Programming Contest 2021（AtCoder Regular Contest 128）.
- Contest URL: https://atcoder.jp/contests/arc128
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20211016T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: maspy, yamunaku
- Rated range: — 2799
The point values will be 400-400-600-700-800-1000.
We are looking forward to your participation!
Good luck to everyone!
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.
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 - Water Balance
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.
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.
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 doublesjust 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.
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
can you send your code link
Here.
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].Could you explain why taking logarithm will fix the precision error?
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 =)
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.
how to solve B .explain please
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
but.why it is??? how working??
there is explaination in this link https://atcoder.jp/contests/arc128/editorial/2790
Is there a solution code of problem D by the Official Editorial?
I got one, this is simple code... https://atcoder.jp/contests/arc128/submissions/26587762
how to solve C .Thanks~
https://atcoder.jp/contests/arc128/editorial/2791