Topcoder SRM 737 is scheduled to start at 07:00 UTC -4, Sept 19, 2018.
Featured Problem Writer: Blue.Mary — lucyanna2018 on codeforces!
You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.
TCO19 Points Leaderboard: https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard
UPD
Div II MysteryGuy MysteryGuy
Editorials: https://www.topcoder.com/blog/single-round-match-737-editorials/
Thanks to Blue.Mary aka. lucyanna2018 and misof for the editorials.
Don’t know how to compete in Topcoder SRMs?
Topcoder Java Applet — You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide)
Hope to see most of you competing! All the best!
Next SRM 738: September 30, 12:00 UTC-4
Remainder: Contest starts in less than 12 hours. This is the first time I write SRM at Topcoder.
Is there anybody that writes SRM in web arena?
My debut today was in web arena. I had to code all solutions from scratch.
Now I am trying to upsolve, but the code doesn't compile. A fast pop-up appears saying "Please wait for compiling results", but nothing more happens. When I try to test, a fast pop-up appears saying: "Please wait for test info". When I submit, there is a message saying I must to compile first.
My questions is: is it "really" possible to use web arena to train at Topcoder? If yes, how? At college, I am unable to log in applet.
WTF is "Unused code rule" and why does it exist?
TL,DR version:
"Unused code rule" is a rule that states your submission should not contain pages of prewritten code that isn't actually computing anything.
It exists as a part of the rules against code obfuscation. The intent is to make the submissions reasonably easy to read during the challenge phase.
Do you really think it is a reasonable thing to have? For me it's ridiculous and very inconvenient. Ain't nobody got time for manually removing not used parts of prewritten code and I hope you are not gonna tell us that we should not use prewritten template because that is "obfuscation". Good that I have plugin taking care of that for me. Moreover prewritten code is usually a prefix of solution, so during challenge phase we can just scroll to definition of class.
Which plugins do you use?
You're lucky cause I already have the most elaborate answer on this topic which I wrote recently: http://mirror.codeforces.com/blog/entry/61252
Back when I competed at TC I also had a plugin for that, so yeah, I get you.
I think some form of this rule is a good thing to have. I don't think the current version is the best one, but I wouldn't go as far as "ridiculous and very inconvenient". I see is as "necessary evil and very mildly inconvenient". Having a small fixed code template + using copy&paste for the big prewritten functions you need is at most a few extra seconds. There are much bigger problems that need fixing before this one.
The claim that "prewritten code is a prefix of the solution" is only a part of the truth. E.g., sometimes you need to look up a specific function within the prewritten code if the coder uses it in their solution and you 1) have no idea what it does from the name, or 2) you suspect that it may not do what they need.
But I have a lot of one-liners in my prewritten template that I use let's say once per 5-10 problems. If I copy all of them, I break unused code rule. If I decide to use them then I will get a lot of annoying compile errors which I will need to fix by copying and pasting some single lines from my more elaborate template. And because of habits and muscle memory, I can't simply decide to not use these macros etc.
"E.g., sometimes you need to look up a specific function within the prewritten code" — well, "Find" function is in applet for a reason.
And on a side note ... you better look up whether someone uses #define int long long if you want to hack on overflows xD. But well, "find" again for a rescue.
If you had to keep some version of this rule but had the freedom to set the limits it imposes, what ones would you find appropriate?
I am aware my reply is not gonna please you, but I will just remove it completely since I do not see this as an appropriate rule in any way. Just changing the percent of allowed unused code (because that's what you asked, right?) may trigger this warning less often, but when it does it will still be annoying and it does not solve the problem at its roots. It's like making a round semirated :P
Fair enough :)
I'm not pushing to keep the rule. I just want to explore multiple options. This answer was in fact also useful to me.
+1 on "ridiculous and very inconvenient".
There are plenty of ways to make hard-to-read code, and I feel it is just ruling out an arbitrary set of them. It's not intended for an obfuscation, and usually they are not hard-to-read compared to other sort of codes.
And it's very inconvenient... My prewritten BigInt code is about 25KB long, and after the warning I removed all divisions or whatever I thought was useless. Usually it caused CE (The code was not written by me, but even if I wrote that nothing will change much) and then I go back again desperately finding another things to erase. I think I did this for at least 5 minutes.
As my points were falling, I gave up, submitted, and thought "Ok fine, I'd rather get banned and never participate on this kind of contest." Now I'm actually happy to get FST on med.
I maintain that in most cases the inconvenience isn't that big.
Bigints and geometry are two very specific cases in that these code libraries aren't a collection of stand-alone functions but usually have a lot of dependencies. I would absolutely be in favor of being able to just use your whole bigint library. Doing what you described is annoying and completely unrelated to the point of the contest.
The problem with all obfuscation-related rules is that you (provably) cannot define them syntactically.
Would you like it better if the unused code rule went away and there was only a rule along the lines of "You cannot make your code intentionally hard to read, and if someone complains that you did, a human will decide whether to penalize you"? (And listing "having lots of unused and unrelated code in your submission" as one of the examples for when that rule applies?)
I definitely think that's better. Specifying "what is obfuscation" is very hard, and I doubt it will even work on practice (for example, this one).
I'd want to add "for code obfuscation" in the back. I insist that the meaning of obfuscation should depend on a context and the intent of competitor, and it should not harm any innocent competitor.
I mean, some people have templates that are basically obfuscation, so...
How to enable python in Fileedit? Even web arena did not provide me with python template — had to guess it.
Editorial: https://www.topcoder.com/blog/single-round-match-737-editorials/
Is there an easy way to solve Med?
Of course we can solve it with careful analysis of various cases, but some people solved it very quickly.
The fastest two submissions that didn't fail the challenge phase are Petr's (10m53s) and qwerty787788's (12m36s). Those very quick ones did all fail, as far as I can tell.
You could sort them with some criteria and do dynamic programming
But if you know how to sort them you can just do greedy instead
Any way to view the scoreboard after the contest? I can't access the contest page from the applet.
Don't know if this is a good place for this, but...
I can't login into my account with the applet. 30 minutes ago, I still can login, but now I entered the same username and password as before and it said that username/password is invalid.
Me too. I logoffed about 10 minutes ago and cannot login now.
Same issue, seems like this is the problem admins talked about
In 800 div1 I got to knapsack but how to solve it fast enough? I thought the limits were too big to do standard dp[weight] with O(n) time for each state, was that it? :( (editorial just says it's knapsack)
Sorry, I could have gone into more detail. Here's the main idea of one such solution in a bit more detail: Once you fix the number of 7s, you know the value of placing a 3 into their middle. Let that value be W. You are now looking to add 3s in some other positions in such a way that (X minus their sum) becomes divisible by W. To do this, you just need W states, not X.
thanks! :) is it really important to choose the middle one? would any possible W (i * (number_of_7 -i)) work?
Conceptually, you can choose any position, the idea would still work. However, the limit on the total number of characters in your output string isn't that loose. If you use 3s that are close to the ends of the string, you may need too many of those to reach X.
One knapsack is OK. We can get the solution for biggest X if the number of '7' is about 2 / 3 of total length. Let's try to run knapsack for this number of '7' (248 in my solution) locally, we can see that the biggest number for that we don't get a solution is something about 8000. For such small X we can run all the knapsacks.
So for X≥8000ish you run only one knapsack fixing 248 7s and for smaller X you do try all possible number of 7s, right? :D that's nice. It doesn't seem intuitive to me that with a fixed number of 7s (248) we can get all X in such a big interval [8000 .. maxX], thanks :)
When there are 248 '7's we can get all numbers that can be represented as sums of 247 * 1, 246 * 2, 245 * 3, ...
But even only with the first two numbers we can get everything above about 60000 (in general, if x and y are comprime, all numbers above xy are sums of x and y).
Thanks! Didn't know about that, more generally, I know that if gcd(a,b) divides c we can get x,y such that a*x + b*y = c, what you said generalizes when gcd(a,b) > 1? obviously, not for all c>a*b but the multiples of gcd(a,b).
Thanks
Those are two slightly different things.
If you have fixed integers a, b and you can use arbitrary integer coefficients x, y (including negative ones), the set of all integers of the form (ax+by) are precisely all multiples of gcd(a,b).
Keyword to search for more: Extended Euclidean algorithm.
In this case you can only use non-negative integer coefficients x, y in the linear combination, because you cannot use, for example, -14 copies of a '3' in some location.
If you have relatively prime positive a, b, the largest integer you cannot write in the form (ax+by) for non-negative x, y is the number (ab-a-b)
Keyword to search for more: Frobenius coin problem.
why tourist's solution doesn't fall into infinite loop? Are the tests weak or is there advanced math behind it?
my solution of div1 800
I am unable to use applet from past one month.I am getting this error "Unable to connect to server".
So are you going to penalize full big integer class in C++ instead of only few relevant functions as 'unused code'? :)
P.S. don't you think it's lame to ask long arithmetics in 2k18?
I have a more general question. Why did such problem appear as div1 med and why was it worth 600 pts?
It is almost the same as div2 C: http://mirror.codeforces.com/contest/1042/problem/C + handling 1 and -1 and big ints.
The logic for this task is worth 200-250 pts + 50 for big ints.
I did not manage to get all the cases because I spent most of the time solving 300. 300 was an interesting task, worth its amount of points. But 600 is misunderstanding. How is it possible that such experienced coders and problem setters allowed such an easy task to be div 1 med and gave it 600 pts? It was also more or less the same version of the problem, which appeared 3 days earlier in another contest...
That problem is completely different.
I'm sorry, but your comment proves itself..
Plus, I think the mentioned div2C is completely different, and it gives near zero observation. "handling 1 0 -1 and big ints" are almost everything for this problem.
The only thing it proves is that I spent too much time on 300 ptr and did not manage to solve 600 on time.
Handling 0's was also the part of div2c as well as getting maximum value for multiplication.
However your comment proves my thesis: ""handling 1 0 -1 and big ints" are almost everything for this problem." — definitely worth 600 pts.
Just look at the final scoreboard. Do you think you can solve all “implementation” problem?
I did manage to get all the cases :)
So, can I say that task is actually easy and contains no idea at all, nothing but the case work and long arythmetics (which is not really ok here, cause people who use Java/Python or have bigint class to copy-paste get advantage) which is, in my opinion, pretty bad for medium div1 problem.
P.S. Though Topcoder problems far from good anyway nowadays. Not so far ago I solved div1 "hard" problem which was to find hamyltonian cycle in strongly connected tournament in
.
Yeah this problem is really bad, but tbh it's kinda expected from TC
Auto comment: topic has been updated by hmehta (previous revision, new revision, compare).
I think nika is not Errichto. Both they are in my room...
nika on Topcoder is Coder on Codeforces.
By the way, your links to Topcoder profiles are broken.
My code for SimpleMathProblem is giving WA on 3rd test case. I used euler's theorem and CRT. Can anyone help me please. My code