hmehta's blog

Topcoder SRM 737 — Results are Up!
By hmehta, history, 6 years ago, In English

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

Results Div I fjzzq2002 . TLE

tourist . tourist

Petr . Petr

qwerty787788 . qwerty787788

nika . Coder

Div II MysteryGuy MysteryGuy

Batrr . 998kover

ezoixx130 . ez_zh

acheing . Acheing

paulinia . paulinia

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

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

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

Remainder: Contest starts in less than 12 hours. This is the first time I write SRM at Topcoder.

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

Is there anybody that writes SRM in web arena?

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

    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.

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

WTF is "Unused code rule" and why does it exist?

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

    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.

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

      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.

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

        Which plugins do you use?

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

        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.

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

          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.

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

            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?

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

              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

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

                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.

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

          +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.

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

            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?)

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

              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).

              "having lots of unused and unrelated code in your submission"

              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.

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

        I mean, some people have templates that are basically obfuscation, so...

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

How to enable python in Fileedit? Even web arena did not provide me with python template — had to guess it.

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

Editorial: https://www.topcoder.com/blog/single-round-match-737-editorials/

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

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.

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

    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.

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

    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

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

Any way to view the scoreboard after the contest? I can't access the contest page from the applet.

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

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.

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

    Me too. I logoffed about 10 minutes ago and cannot login now.

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

    Same issue, seems like this is the problem admins talked about

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

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)

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

    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.

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

      thanks! :) is it really important to choose the middle one? would any possible W (i * (number_of_7 -i)) work?

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

        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.

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

    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.

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

      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 :)

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

        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).

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

          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

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

            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.

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

    why tourist's solution doesn't fall into infinite loop? Are the tests weak or is there advanced math behind it?

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

my solution of div1 800

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

I am unable to use applet from past one month.I am getting this error "Unable to connect to server".

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

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

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?

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

    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://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...

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

      That problem is completely different.

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

      such an easy task

      I did not manage to get all the cases

      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.

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

        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.

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

          Just look at the final scoreboard. Do you think you can solve all “implementation” problem?

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

        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 .

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

          Yeah this problem is really bad, but tbh it's kinda expected from TC

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

Auto comment: topic has been updated by hmehta (previous revision, new revision, compare).

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

I think nika is not Errichto. Both they are in my room...

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

nika on Topcoder is Coder on Codeforces.

By the way, your links to Topcoder profiles are broken.

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

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

→ Reply