maroonrk's blog

Daiwa Securities Co. Ltd. Programming Contest 2021（AtCoder Regular Contest 128） Announcement
By maroonrk, history, 3 years ago, In English

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!

  • Vote: I like it
  • +135
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Good luck to everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it
Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Same for CF Round 749 and Atcoder Beginner Contest tomorrow :)

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Now I feel like I should have gone for ARC. A very bad choice going for kickstart

    → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

There Would be conflict between Kick-start Round G and in this round, it might be great if this round happens tomorrow.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +25 Vote: I do not like it

problem C:I spend about 1 hour proving that there are at most two different positive numbers in the sequence ...

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is that necessary? It seems that my solution didn't use it :-_

    → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

In fact, the structure of the optimal solution in C is exactly the same as 1299C - Water Balance

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    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) $$$
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for your explanation!

          → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Me too, but the range of the values is quite large, which indicates there must be a better solution.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          ← Rev. 3   Vote: I like it +8 Vote: I do not like it

          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 ....

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You make great sense! What actually restricts me is my poor floating number knowledge xD

            → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you send your code link

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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].

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you explain why taking logarithm will fix the precision error?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 =)

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve B .explain please

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there a solution code of problem D by the Official Editorial?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C .Thanks~

→ Reply