papa-ka-para's blog

By papa-ka-para, history, 3 weeks ago, In English

I would like to share much valuable lesson I learnt today in Div2- 986 contest. I wasn't able to Solve B, and that costs me not solving C and D.

For anyone, not being able to solve an EASY problem, is more frustrating than not being able to solve HARD problem.

Chronology:

1) 2 wrong submissions in B:

Since 10 ^ 18 * 10 ^ 18 was too large, I wrote of writing code in c++, and convert it to python. Which Got TLE . First wrong submission started panic mode.

Then, I started to find O(1) solution for Problem B, and missed edge cases. Wasn't able to solve B for first 50 minutes of the contest and I couldn't control emotionally.

2) Read Problem C, found it very easy. Submitted, which failed on Pretest 2

I submitted this C, during the contest. just by changing one of <= condition to < gave me AC. I would have easily debugged this, if I would have been calm.

3) I misread D, implemented wrong, couldn't even pass pretest-1 As I have mentioned in this comment, I had missed one crucial detail in the problem D.

After the contest, I solved B,C,D all together. I figured out, that C and D I was quite close to solve. Even if I had solved C and D, and left B unsolved during the contest, I would have been satisfied with my performance.

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by papa-ka-para (previous revision, new revision, compare).

»
3 weeks ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

The same thing happened to me in the Educational Round 159.

I have accepted the problem of A and E :)

»
3 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Seems like a good number of people had a similar experience. I spent the first 30 mins without solving A and B, started worrying that this would be a terrible performance, and then moved on to C to solve that first instead. Only after that did I perceive having the time to solve A and B.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

You can apply two minor changes to your Python submission to get AC easily: 290992623

  1. Use PyPy 3 instead of Python 3. PyPy 3 is generally much faster.
  2. Use fast input by inserting the following lines:
import sys
input = lambda: sys.stdin.readline().rstrip()
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    To be honest, I don't get why a D2B problem had to have so many cases in one test while having a strict one second of TL. I was naive to run my PyPy3 code in global scope and it barely passed with 890 ms. There shouldn't be a need to include that many random tests to test every kind of edge cases...

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

      Sure, this is another learning as well.

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

      this is true story, after I got TLE in 2036C - Anya and 1100 once I read others code and found out the template mentioned as above.

      Not only I started to optimize my solution, but also I started to using fastIO for read and output.

      Of course sometime fast submit is more important then I'll just use normal I/O. But now I rather have weapons at my own disposal when the time limit + algo complex is very clutch.

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

      Nope, there were only 2 cases and could be done in O(1) instead

      void solve () {
      	int n, b, c;
          cin >> n >> b >> c;
          if (!b && c < n - 2) cout << -1;
          else {
              int lwr = (c < n) + (!b ? 0 :  max(0ll, (n - 1 - c) / b));
              cout << n - lwr;
          }
      }
      
      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it +9 Vote: I do not like it

        The binary search part isn't the bottleneck. It's the slow nature of Python's default input/output that causes these TLs.

        And even if binary searches were slow, if the constraints accepts binary searches in C++ but not in Python, the constraint is likely to be unnecessarily tight.

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

          The normal way of input also passes comfortably in 500ms 291002807

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
            Rev. 2   Vote: I like it +12 Vote: I do not like it

            Okay, you're right. Still, it's unnecessary to be harsh on binary searches, which really only threatens Python and not other languages.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In round 985, I couldn't solve the first question and my morale was destroyed, and it turns out that I knew how to solve B and C but I never checked them. Lost my pupil, but I'm motivated to get back

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

a7 carrilho goat

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

This is indeed painful experience. Not only this round but I'm also remember there's recently a few rounds with the same pattern (i.e. this one is also very tricky div2B 2032B - Medians). So I might actually getting used to it and feeling less painful by time...

Yesterday I'm done C with 2 minutes too late. Submit immediately after practice mode and Accepted.

It's just kinda happened, sometimes I'm pondering should I solve the problems backward at my level (doing D-C-B-A for div. 2)

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

    I also had same logic. Might implement this from next contest.

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

      I'm actually don't have enough courage to do so. Since I'm aiming for expert rank and kinda stuck in pupils for months already...

      Another painful series of events, or maybe I'm just bad.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

same happened with me not able to solve A fast and did wrong submissions couldn't debug solved after around 50mins and it costed me whole contest not able to solve any other problem