Kuber's blog

Need help with CF Contest #605, D problem
By Kuber, history, 2 years ago, In English

I'm stuck in test case #10 in D. The test case has n = 20000. Is there a way I can see the complete test case?

I'd be thankful if someone can review my solution: https://codeforces.net/contest/1272/submission/166760372

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not sure if seeing it will help you out in some way, but basically you can output the vector for example saying if the first number == 33125630.

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

    From testcase #5 onwards, the values are in the range of 10^7 — 10^9 and n is 20000. I feel, I am probably missing some edge case. I have been thinking about it for two days. I am unable to see. I have seen solutions from the editorial as well as top rankers from the contest. They have slightly different implementation which is clearer than my solution. However, I'm not over invested in my solution and really want case I'm. missing.

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

      N is 200000.

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

        Yes. Sorry. N is 200000 from testcase#5 onwards.

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

          Any reason behind doing space optimized solution?

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

            I did not think about it as dp at all. I just thought that to calculate the answer I don't need more than 3 values at once. It is a coincidence that the solution is a space optimized dp.

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

              Does s denote a max with 1 deleted element and f with all consecutive elements?

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

                Yes

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

                  Last else if states that v3 > v1, but if it is less then all variables reset to 0/1. Consider the case when v3 <= v1, but v2 > v1.

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

                  I am actually not quite sure if we can consider such case having only 3 variables. I'll try once more in a bit, but I might assume it either needs a bit more of variables or is impossible.

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

                  Nope, I can't find a way to solve it using 5 variables only.

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

Take a look at Ticket 15977 from CF Stress for a counter example.

→ Reply