hmehta's blog

By hmehta, history, 5 years ago, In English

Topcoder SRM 738 is scheduled to start at 12:00 UTC -4, Sept 30, 2018.

UPD: Editorialshttps://www.topcoder.com/blog/single-round-match-738-editorials/

Featured Problem Writer: wild_hamster

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

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 739: October 10, 11:00 UTC-4

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +87 Vote: I do not like it

hmehta every-time when I try advice to my friends to write SRM -- I will get negative answers. Answers are like this "What? I will write program in Java Application?", "Bad Interface", "I didn't get how write SRM and go out from site". It's not user-friendly. Topcoder lost it's popularity. Generally I am bad at CP but I can get top 100 easily in div2.

Also I see web arena -- but didn't heard something good about web arena too and in blog you not advising use web arena.

But I and CP community like topcoder. It's has nice problems and good editorials. I want that this project become popular again and user-friendly.

When we can see topcoder in user-friendly way?

Sorry for my bad english

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

    TC asked the community to fix it themselves: https://codeforces.com/blog/entry/61107

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

    We are working on one right now. Within a few days, you will see a form in which we will ask you to put in the problem details, we will manually add it to the system and do most of the work for you. Later we will make that form a web app with all the features.

    I can help you if you want to write add the solutions to the system. Just send me an email and I will take care of it. :)

    We are taking it step by step — Like we had this page for How to compete for making it easier for the new members to understand around the specific way of writing solutions to topcoder problems and ofcourse using the arena. https://www.topcoder.com/community/competitive-programming/how-to-compete

    Also working on the main home page https://www.topcoder.com/community/competitive-programming/ to have everything related competitive programming, be it match list, editorials, tutorials, forums, blogs, results, stats etc.

    Problem difficulty is not as high as it used to be. We are bringing back more number of SRMs.

    Hope to bring things back in place very soon :)

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

topcoder arena is not loading

»
5 years ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

Self-promotion

I will stream on Youtube just after SRM ends. It isn't an official stream but I hope to solve some problems and talk about solutions. And later I will go through some div1-hards from TCO qualification rounds. Link: https://www.youtube.com/channel/UCBr_Fu6q9iHYQCh13jmpbrg.

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

Still can't enter the room:( So when will srm738 start?

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

    There was an announcement in the arena, 20-minute delay.

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

      Does it allow you to enter the arena?

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

        No, I can't even login to the arena now. Maybe they are restarting it.

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

    I can't login now,what should I do?

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

    More than 20 minutes has passed...

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

I still can't login to the arena (after they kicked me out ~5mins ago, presumably for restarting the arena). Is anyone else experiencing the same problem?

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

What is the meaning of "Your JRE does not support AES-128. Login not allowed ?"

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

    It means arena isn't configured yet, it should be ready in 5 minutes based on their prediction

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

    Had the same problem: first attempt — timeout, second attemp — AES-128 error. Restart java applet — timeout again.

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

Has there been another announcement after the "20 minutes" one?

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

Please postpone

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

Someone please drop a comment if they manage to login successfully.

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

I cannot login neither in the applet, nor in the web arena...

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

    Please wait, I will notify here when it is back up!

    Sorry for the issues. All in the process to make it better.

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

      I cannot log in into the web arena.

      UPD: It's ok now.

»
5 years ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

It works now. But there seems to be no contests.

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

It is possible to login to the arena now

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

    but there is no active contest on there.

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

    Things are back up! We will be starting at 13:00 UTC -4.

    Which is about 10mins from now!

    Hope you guys enjoy the problems!

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

Unable to write in code arena

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

Medium was very old when I started doing CP.

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

    To be honest it was quite non-trivial for me, I even wrote brute force to get some experimental results.

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

      I was pretty pleased with myself when I solved harder version of this task. This was more than 5 years ago :)

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

      I'm glad I was able to challenge you a little :)

      I like this trick. It's quite obvious once you see what's going on, but at the first glance the rules do a very good job to disguise that the bulbs are in fact independent games. I haven't seen this particular trick used at a contest, but I'm sure that some generalizations / similar problems must have appeared before, the setting is quite natural.

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

How to solve easy and medium?

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

    Easy: Prove or guess that all sides must be integers. Generate all vectors of integer length up to 500 and try all pairs of them.

    Medium: The only trick is to realize that this is still a sum of independent games, even though it tries to pretend it isn't.

    Imagine that instead of lightbulbs we play the game with pebbles. "Turn a lamp off" is "remove a pebble", "turn a lamp off and another on" is "move a pebble", and "turn two lamps X and Y off" is also "move a pebble from X to Y". In the last case you will get two pebbles at Y (instead of zero lightbulbs), but those two pebbles can be ignored because of symmetry. A longer version of this argument will be in the editorial.

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

    Pretest for MED seems weak. I made a silly mistake :(

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

      The samples (at least at TopCoder) are there to help you understand the statement, not to verify the correctness of your solution. Correctness is your responsibility.

      If applicable, we try to have the samples cover potential issues such as overflows and error messages -- in addition to their primary purpose, the examples do also try to make sure that you won't fail because of something unrelated to the problem.

      In this particular case, the fact that examples are small and simple is intentional, as I did not want people to guess the solution and "verify" their guess by testing on a big sample.

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

Thanks for the round!

My screencast with commentary: https://youtu.be/a_AglzG7ieo

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

    (so far seems to only be available in 360p, 1080p is still processing and should be available soon)

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

Is it just me or has the editorial been mangled so badly that the solution to the Div1 900 is completely unreadable?

»
5 years ago, # |
Rev. 2   Vote: I like it -25 Vote: I do not like it

Why the editorials of topcoder SRM was posted in codeforces? That's not good.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody please help me prove, why in Div1 Easy all the sides of the triangle must be integers?

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

    because out of square root(or any root) of integer number comes integer or irrational. (You can prove this fact by contradiction i.e suppose m1/n1 = sqrt(2) and m1, n1 lowest among all values, then you eventually find m2,n2 even more lower)

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

      What you wrote is not a sufficient proof yet.

      More precisely, it is a sufficient proof that the square root of a positive integer is either integer or irrational. But that's not enough here.

      In Div1 Easy what we need is to prove that for positive integers a, b, c the fact that sqrt(a)+sqrt(b)+sqrt(c) is integer means that all three values sqrt(a), sqrt(b), sqrt(c) must be integers.

      The above is not a trivial statement. For example, note that if we change one + into a -, it stops being true: sqrt(2)+sqrt(2)-sqrt(8) is integer even though the three terms aren't.

      If you only want to be sure that your solution is correct, you can in fact afford to examine all triples (a,b,c) that are small enough.

      The general proof is conceptually simple: Do a proof by contradiction, so start by assuming that sqrt(a) + sqrt(b) + sqrt(c) = p/q for some relatively prime integers p and q. Then, get rid of most sqrts by squaring the equation twice, and find the contradiction by getting an expression where one side is rational and the other is irrational because it's the last remaining sqrt.

      Details follow. (Written off the top of my head, quite ugly, may be buggy.)

      Start from the above assumption.

      Note that we can write sqrt(a) + sqrt(b) — sqrt(c) as (p/q — 2*sqrt(c)).

      We can now go back to the previous equation and multiply both of its sides by sqrt(a) + sqrt(b) — sqrt(c) to get:

      (sqrt(a) + sqrt(b))^2 — sqrt(c)^2 = p*(p/q — 2*sqrt(c)) / q

      a + b + 2sqrt(ab) — c = p^2/q^2 — (2p/q)*sqrt(c)

      Let's rearrange terms to get a single term with sqrt(ab) on the left hand side:

      2q^2*sqrt(ab) = p^2 + (c-a-b)*q^2 — 2pq*sqrt(c)

      Square it again:

      something_rational = something_rational — 4pq(p^2 + (c-a-b)*q^2)*sqrt(c)

      something_rational = 4pq(p^2 + (c-a-b)*q^2)*sqrt(c)

      We can now divide both sides by the nonzero rational 4pq^3, getting:

      something_rational = ( (p/q)^2 + (c-a-b) ) * sqrt(c).

      Finally, (p/q)^2 is rational and obviously (p/q)^2 > a+b+c, hence the large parenthesis on the right hand side is rational and positive. Thus, we can divide by it and get that sqrt(c) must be positive, a contradiction.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please explain the solution of Div 2 Medium ? Could not understand it from the editorial.

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

    Let's store all possible divisions in set(let's store them in sorted array order). At first we have division with given number {N}. We launch recursive function, where we remember current division and try to go to all possible divisions from this state(if this state was not used earlier) and launch recursive function from them. For example for {3, 5} all possible next divisions is {1, 1, 1, 5} and {1, 1, 1, 1, 1, 3}. For example how should it work with N = 6:

    launch go({6}): {6} was not used yet, so we increment amount, add 6 to answer, launch go({1, 1, 1, 1, 1, 1}), go({2, 2, 2}), go({3,3})

    go({3, 3}): {3, 3} was not used yet, so we increment amount, add 3*3 to answer, launch go({1, 1, 1, 3}) and go({1, 1, 1, 3})

    go({1, 1, 1, 3}): {1, 1, 1, 3} was not used yet, so we increment amount, add 1*1*1*3 to answer, launch go({1, 1, 1, 1, 1, 1}). When we will launch go({1, 1, 1, 3}) next time, we will just exit as it was already used.

    We will stop when we will visit all possible states. As number of possible states is at most 105, we can do it fast. We can also precomputate answers for all N ≤ 90. There are also some possible optimizations in the editorial, you can see them there.

    Is it clear enough?

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

      Thank you very very much. This explanation helped me understand and solve the problem. Would be great if you include this with the editorial as well. I found the initial reading of the editorial of the problem very abstract as nothing had been mentioned about how to store the divisions. I used set< vector< pair<int, int> > > to do so as per the idea that you mentioned. BTW, how can we say that the no. of possible states is at most 105 ?

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

        We can just find all the answers for N ≤ 90 and can see, that there will be not more than 105 states. Also it is mentioned in the sample test case N = 90.