neal's blog

By neal, 6 years ago, In English

For today's Div 1 problem D, 1067D - Computer Game, once you succeed at a quest, it's clear you should upgrade and play the quest that maximizes your expected reward pi × bi for the remainder of the game.

However, before you succeed at a quest, you have a difficult tradeoff to make: should you take a quest with a high probability of succeeding, to maximize your chances of upgrading and gaining optimal points for the rest of the game? Or should you take a quest that gives you more expected reward pi × ai right now?

It turns out the answer to this tradeoff depends on T, the number of seconds left. As T gets smaller, we should switch to quests with lower pi but higher immediate reward pi × ai. This is because the long-term value of upgrading and maximizing future rewards becomes less relevant compared to getting more reward now. In particular, the optimal quest to pick (when we have not yet succeeded at any) can change multiple times as T gets smaller and smaller. My solution 44819755 uses multiple binary searches along with a stack to determine the optimal switching points.

Unfortunately, the system tests are extremely weak at testing this logic. Many competitors submitted solutions that never even choose to switch quests. This actually passes all of test cases 1 through 104. It will only fail on test case 105, the very last test case, where ironically N = 2:

2 10
1000 1001 0.1
10 1000 0.5

In this case, except when T = 1 you should always perform the second quest, as this gives you a 50% chance of upgrading and getting 0.5 × 1000 = 500 expected reward every turn thereafter. However, when T = 1, upgrading has no more value, so you should perform the first quest instead for an expected reward of 0.1 × 1000 = 100, as opposed to the second which only gives 0.5 × 10 = 5 immediate reward. So this test case requires just one quest switch at the very end.

This case was enough to catch the majority of wrong submissions. However, since it's very simple, it was still possible for incorrect solutions to get through. In-contest, I believe only one did: 44804123. In particular here is a case where two switches are required:

3 3
3 4 0.5
6 25 0.4
15 16 0.2

The maximum pi × bi here is 0.4 × 25 = 10, which is the amount we will get each turn after succeeding and upgrading.

When T = 1, we should choose quest 3 for an immediate reward of 0.2 × 15 = 3, the maximum possible.

However when T = 2, we should choose quest 2, which gives us an expected value of 0.4 × (6 + 10) + 0.6 × 3 = 8.2. Choosing quest 3 only gives us 0.2 × (15 + 10) + 0.8 × 3 = 7.4. Similarly, choosing quest 1 only gives us 8 points.

When T = 3, we should actually choose quest 1, which gives us an EV of 0.5 × (3 + 2·10) + 0.5 × 8.2 = 15.6. This is higher than choosing quest 2, which gives us 0.4 × (6 + 2·10) + 0.6 × 8.2 = 15.32.

So the answer for this test case is 15.6. However bazsi700's Accepted solution above outputs 15.5 because it never uses quest 2.

If you're working on this problem in practice mode and want to know whether you actually solved it, make sure to test the case above and a few others like it!

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

»
6 years ago, # |
  Vote: I like it +124 Vote: I do not like it

I really think that Um_nik should stop creating problems.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +210 Vote: I do not like it

    What if he didn't have enough time for tests? What if he was too busy judging other authors problem setting abilities?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it

    I have to say, ignoring this issue I liked the problem quite a lot! And luckily test 105 ended up mostly saving the day.

    Though I will say that I wish it had been worth more points than problem E ;)

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

    Do you think only the tests were weak, or his mind as well?

»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Is there exists a test with a big value of T (more than 105) on which greedy solution doesn't work? Because if no, then we can write simple dynamic programming solution in O(T·N) or for small T, and greedy solution which never switches for large T.

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    I guess it's such a test:

    2 10000000000
    10000 20007 0.000000001
    3 3 0.000000002

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

      Are you sure?

      The greedy solution gives 190069.500020, while the correct solution gives 190069.507940. The relative error between these two numbers is 0.0000000415, which is less than 10 - 6.

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 6   Vote: I like it +10 Vote: I do not like it

        I tried neal's submission, and it says we should switch after 100M turns.
        Which greedy solution you try? I checked your submission from contest and it gives wrong answer: https://ideone.com/uGRQ0N

        Ok, check please following test:

        2 1000000000
        100 180 0.000000001
        30 30 0.000000002

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          It's because of %I64d in my solution. Ideone uses Linux OS, so you should change %I64d to %lld in the scanf. With %lld my solution gives the correct answer: https://ideone.com/DqziP6.

          New test really breaks a greedy solution, thank you!

»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Thanks for the information. It's pretty saddening that this case wasn't included in the 100+ tests. Sometimes weak pretests bring me down, now weak system tests bring me up.

»
6 years ago, # |
Rev. 2   Vote: I like it +60 Vote: I do not like it

To be fair, Um_nik did have a test that required switching quests 20,000 times; it just didn't make a difference bigger than 1e-6. Goes to show that if you want to break a wrong solution, you really have to implement the solution and make sure it fails.

This leads to a nice challenge though: what's the highest number of mandatory quest switches you can fit into a test case? (i.e., choosing to use fewer quest switches leads to the answer being wrong by more than 1e-6) Bonus points for making T large in order to break various slower solutions. Looks like MrDindows already has a good start.

»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Thanks! I've added everything from this blog to the tests, (of course, there will be no rejudge of contest submissions). Feel free to write if you will come up with new helpful testcases ;)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Official standings were also affected by the rejudge. If you go to the profile of bazsi700 you can see that he was theoretically 19'th and when you go to the standings, you can see he was 61'st.