hmehta's blog

Topcoder SRM 785
By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 785 is scheduled to start at 12:00 UTC -4, May 09, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to espr1t for writing the problem set and misof for testing and coordinating the round.

This is the third SRM of Stage 3 of TCO20 Algorithm Tournament.

Stage 3 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs

Some Important Links
Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

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

Anyone else have problems with "Your login request timed out"? Web arena is working, but it is not really place where I want to write contest

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

    Yes, I am having the same trouble.

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

    Just wanted to ask the same thing,

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

    restarting applet worked for me

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

      Not for me, unfortunately

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

    Hey Egor , KAN Can you try logging out of the web arena and then log in using the applet. I mean press logout in the web arena. It works for me.

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

      I was never logged in web arena, but restarting the applet worked for me now.

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

I am getting Your JRE does not support AES-128, login not allowed :(, Any help?

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

Login Request timed out !

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

    Same here! :( Seems like the applet isn't working

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

    Same. Cant login.

    First stackoverflow answer of clearing cache didn't help. Redownloaded applet on ubuntu didn't help.

    Edit — ping www.topcoder.com takes forever on my wifi (JioFibre in India). Fortunately, I couldn't access topcoder 2 days ago as well and I knew switching to mobile data is the only way out. I never faced such problem in past with wifi. I'm sure there is no problem with wifi as I can access all other websites.

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

I was getting various errors, I got both "Your login request timed out" and "Your JRE does not support AES-128, login not allowed", however something like my fifth login attempt was successful. I suggest you guys just have to be persistent.

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

    Entering the web arena and logging out worked for me (maybe just by chance)

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

    Just read your comment and thought to give another try and it worked !

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

    What if you get logged out in the mid of competition?

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

    I am having this exact problem. Already tried more than 5 times, still no luck :(

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

Hard

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

    Ouch. I figured it is close to a very well-known problem and can be given before — but tried finding similar problems and couldn't. None of the testers knew it was given either, sorry about that. :(

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

      For a fixed position, why is it never optimal to change more than one zero (say, three) to ones?

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

        If you solve the problem from the most-significant bits to less significant ones (and all more-significant ones are already okay) changing a single zero to one would fix the current bit. Changing 3 can also fix it, but they will require strictly more operations. And, since you are changing a number, it will have all-zeroes in its less-significant bits — thus, you won't have all-one bits case in the less-significant bits.

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

        Because when you change the digit from 0 to 1, the following ones become all 0, so they're all equivalent, so having three of those is not better than having one of those for the following digits. Therefore at least two of them can be kept all 0s. And then it's better to stop at 011111 instead of 100000 for those two.

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

        (Simpler explanation?)

        Assume that all numbers are in $$$[0,2^{b+1})$$$ and remain in that range at the end. First, sort them in increasing order. We can choose to increase the $$$x$$$ greatest elements less than $$$2^b$$$ such that all of them equal $$$2^b$$$, where the parity of $$$x$$$ is such that the $$$b$$$-th bit of the XOR is 1. Then take all numbers modulo $$$2^{b}$$$ and recurse for $$$b-1$$$. Note that

        • $$$x\le 2$$$ always. For example if $$$x=3$$$ then at least two of the increased numbers will still equal $$$2^b$$$ after all future increases. So it would take fewer increases to make two of them equal $$$2^b-1$$$ at the end instead (and the XOR would not change).
        • $$$x=2$$$ can be chosen at most once.

        This easily gives a $$$O(N\log^3 (10^9))$$$ solution. Code

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

    Well, OK. How is it possible that my Hard failed, while Danylo99 passed? It is exactly the same code (that's because of problem mentioned above was from team contest, where we participated together).

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

      undefined behavior in your code?

      this looks fishy:

      // assert(idx != -1)
sum ^= A[idx];
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        It is not the case as our codes are exactly the same (they differs only by LINF constant, but as answer never exceed 10^18, it doesn't matter).

        UPD. Sorry, I misunderstood. I will investigate it.

        UPD2. My constant INF was too small:)

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

Why do you write "variant of Nim" instead of "Nim"? We end up searching for differences from standard Nim even though there aren't any.

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

    Nim was originally played in its misere variant — thus I wanted to specifically point out it is the normal play nim.

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

It is really depressing when there are 25 people above you with one less correctly solved task.

I started with TC rounds after many years of competing, and now they are most interesting rounds to me — probably because they require more standard programming skills than "IMO 1995 shortlist tricks". As well I understand people who likes opposite.

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

can someone explain the DP solution of DIV2 NIM

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

Anyone else have issues with the 500? I was repeatedly testing my solution on the max case; sometimes it would run in less than 3s and other times it would TLE ...

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

    yes. And I also did it super optimized in my opinion.

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

How do these leaderboard points exactly work? It's rather clean that Gennady won't advance for the second time, but is it expected that these $$$5$$$ points awards are awarded to him?

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

Sorry if this is a stupid question, but in DIV1 500, the statement says something like "calculate the expected value", and is the same for the editorial: "Calculate the chance (expected value)..."

This confused me a bit, aren't we supposed to calculate the probability of the ratings be the same, instead of the expected value? Not saying that I couldn't solve the problem because of this, but I want to know if I'm missing something

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

    When I read expected chance I thought of a meme like: a normal guy sitting down doing nothing: “probaility”. A super god with some lights going out of his head “expected chance”

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

Apparently topcoder allows numpy so I am trying to see if a python solution can pass the div1 500.

Although it takes less than 2 seconds on my machine, it can't even pass the n=42 example test case when running on topcoder's test servers. Anyone see any other optimizations? https://pastebin.com/QzVvNXCT

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

    This problem will be extremely hard to pass in Python I think. It is both very memory inefficient (although I believe the floats, in contrast to integers, are IEEE, thus may be okay) and very slow, and in this problem performance was crucial.

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

      Numpy is vectorized which is sometimes enough to make up for the slowness of the python glue code.

      My solution (linked above) runs the n=52 case in 1.5 seconds locally so it would've probably been fine if topcoder had slightly more modern CPUs!

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

    Virgin CF: error 13131313 when importing default libraries in runtime

    Chad TC: import numpy

    → Reply