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!
Thank you for changing registration start time to 24 hours. I have missed few 6:30AM SRM because of this!
clash with educational round on codeforces.
hmehta can you delay start of round?
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.
"Note: Registration for SRMs will now open 24 hours before the match." — God bless you
Why in the hard problem the limit was changed from 500000 to 300000 during challenge phase? That seems extremely strange.
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.
Yeah, it seems worth mentioning, but it still is extremely strange (or bad)
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.
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 ??
https://codeforces.com/blog/entry/61252?#comment-451721 (I have to say I agree with misof)
Thanks. Infact I wanted to tag Swistakk hoping he might have experienced this with high probability :)
How is the checker in Div1 250 implemented? Here is my solution from the practice room:
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
It would be better to upload your code, as it might have a bug?
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
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.
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.
A checker must be in Java in Topcoder system, so it isn't an issue at all :D
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?
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.
Prove that a float-based checker that "accepts all correct answers and rejects all incorrect ones" does not exist.
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.
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.
Ah, okay. That makes sense! Good point.
Edit: I still agree with you, but challenges can make this a bit confusing.
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.
A quiz regarding d2 med: prove that a 50x50 board can't be covered by 16 queens.
Since the number of rows is greater than the number of queens, there must be a row that doesn't contain any queens. Let's call one such row X.
Each queen can cover at most three cells in X (because the queen itself is not in X). So, in total, they can cover at most 3 * 16 = 48 cells of X. But there are 50 cells in X. Contradiction.