hmehta's blog

Topcoder SRM 742 — Registration open!
By hmehta, history, 6 years ago, In English

Topcoder SRM 742 is scheduled to start at 11:00 UTC -5, Nov 28, 2018. Registration begins 24 hours before the match and closes 5 minutes before the match begins. Note: Registration for SRMs will now open 24 hours before the match.

Problem Writers: monsoon and misof

This is the first SRM of Stage 2 of TCO19 Algorithm.

Stage 1 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 743 — December 8

Hope to see most of you competing! All the best!

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

Comments Comments (26)
| Write comment?
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thank you for changing registration start time to 24 hours. I have missed few 6:30AM SRM because of this!

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

clash with educational round on codeforces.

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

    hmehta can you delay start of round?

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

      Hey CodeLeague, Sorry saw this late, but after announcements and setup it is difficult to move the match. But we will try and be more careful going forward.

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

"Note: Registration for SRMs will now open 24 hours before the match." — God bless you

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

Why in the hard problem the limit was changed from 500000 to 300000 during challenge phase? That seems extremely strange.

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

    I guess the limit never was 500000 in the checker (that is, the statement and checker had different limits when the contest started). That is worth mentioning even after coding phase, because people who prepared cases to get TLE would then get an unexpected error message from the checker and ask for a clarification.

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

      Yeah, it seems worth mentioning, but it still is extremely strange (or bad)

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

        Sorry, our bad.

        Nothing was changed.

        The constraint was supposed to be 300,000 and it was 300,000 everywhere: both in test data we had prepared and in the checker. Test data wasn't changed at all during the SRM.

        A very old version of the statement said 500,000 and somehow this constraint made its way into the version you saw in the arena. Might be some caching issue, I don't know at the moment. I'll try to investigate how it happened.

        The announcement was made late because only then we became aware of the discrepancy. It's better to make it late than to not make it at all.

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

I added ( #define int ll ) in my Div1-easy and it was not giving correct answer on samples.Once I removed it,it worked.

Did anyone experience it before,what is the reason ??

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

How is the checker in Div1 250 implemented? Here is my solution from the practice room:

  • Build 1/10 from 1 by building, in turn, 2, 1/2, 2/5, 1/5, 1/10.
  • Build 1/10^9 from 1/10 by repeating the above procedure several times.
  • Build 2^k / 10^9 for 0 < k < 60.
  • Build the required resistance bit by bit using serial connections. However, we do not have a zero, so use 1/10^9 as the starting value.

This construction achieves the resistance of exactly (required+1) nanoOhms, thus having the absolute precision of 10^(-9). However, it fails the system tests.

Note that the statement is formulated in terms of the real numbers and not the floating-point numbers and in this particular problem

  1. It matters.
  2. A precise checker can be implemented since all the possible numbers it has to deal with are rational.
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    It would be better to upload your code, as it might have a bug?

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

      The code is in the first revision of this post. The test is 9876. The error message is the following:

      Answer checking result:

      Resistance outside tolerance: expected 9.876E-6 received 9.877E-6

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    A precise checker can be implemented since all the possible numbers it has to deal with are rational.

    Then the checker would either have to be able to handle intermediate bigints, or it would require some extra constraints in the statement. Seems like a bad idea.

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

      I disagree. The main job of a checker is to accept all correct answers and reject all incorrect ones, where "correct" is defined by the problem statement. If the statement does not restrict intermediate numbers, then this must be handled by the checker. Besides, both Python and Java have native big integers.

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

        A checker must be in Java in Topcoder system, so it isn't an issue at all :D

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        You're missing the point. Is it easier to write a fraction-based checker than a float-based checker that does exactly what it should?

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

          I don't see how you could implement a float-based checker that "does exactly what it should", although I can write a "wrong checker". So yeah, I think it's far easier to write a former one.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it -25 Vote: I do not like it

            Prove that a float-based checker that "accepts all correct answers and rejects all incorrect ones" does not exist.

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

          I now see your point. Typically I'd agree with you, but this problem is special in my opinion. That is because the input is given in nano-ohms, and the output is meant to be correct up to 10^(-9) ohms, that is, 1 nano-ohm.

          While in (say) a geometry problem, getting a distance wrong by exactly 10^(-9) would be extremely implausible, in this case it merely represents subtracting 1 from the input. Since the corresponding answer is explicitly allowed by the statement (and it allows for a natural simplification in some correct solutions, as demonstrated by fetetriste), the checker has to accept error 10^(-9) and reject error 10^(-9) + eps for any eps > 0. Since 10^(-9) is not exactly representable by a floating point (base-2 mantissa) number, writing a floating-point checker under these constraints can be extremely tricky.

          I guess what I'm saying is that writing a checker that tests for error exactly at most 10^(-9) is always very hard (think interval arithmetic, and I'm not even sure it's feasible). Calculating the correct answer with doubles and checking if the distance to the contestant's answer is at most 10^(-9) gives a very good approximation to the checking problem, but an approximation is not good enough here.

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

            But the checker doesn't have to reject error 10^-9+eps. It just has to accept error up to and including 10^-9. In the statement, it doesn't say "your solution will be rejected if...". I'd even say that failing such solutions is an unnecessary dick move.

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

              Ah, okay. That makes sense! Good point.

              Edit: I still agree with you, but challenges can make this a bit confusing.

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

                Yeah, it seems the problem here is comparing <= 1e-9 instead of <= 1e-9 + eps. That should be fixable without having to deal with everything related to an exact checker (such as maximum running time of the checker). It's a useful possibility anyway.

                Challenges with floats... ew. They always carry some amount of risk. Imagine a problem where the answer is guaranteed not to significantly change when the input is rescaled/translated/something in main tests, now good luck guaranteeing it in challenges. Regular imprecision of floats poses a similar risk (a submission can fail because it neglects something that doesn't appear in main tests at all and it pushes the error for example to 3e-6 instead of < 1e-6). It's just worse in this case because the required precision is higher.

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

A quiz regarding d2 med: prove that a 50x50 board can't be covered by 16 queens.

Spoiler
→ Reply