Блог пользователя hmehta

Автор hmehta, история, 6 лет назад, По-английски

Topcoder SRM 741 is scheduled to start at 21:00 UTC -4, Oct 30, 2018. Registration begins 4 hours before the match and closes 5 minutes before the match begins

Featured Problem Writer: Blue.Marylucyanna2018

Match Result and Overview: http://community.topcoder.com/stat?c=round_overview&er=5&rd=17316

Editorials: https://www.topcoder.com/blog/single-round-match-741-editorials/

TCO19 Points Leaderboard: https://tco19.topcoder.com/home/algorithm/algorithm-leaderboard

Handle Points Sum of Scores
tourist 25 6915.64
xudyh 25 6775.42
Petr 22 5682.8
neal_wu 20 4365.07
Um_nik 20 4521.47
pashka 19 3616.54

Congratulations to tourist for qualifying for TCO19 Algorithm Finals!

Topcoder Java Applet: https://drive.google.com/file/d/1gVJZxhWYMuUNx3PfSSTkkk-b9AeJkL4j/view

Hope to see most of you competing! All the best!

Next SRM 742: Nov 28, 11:00 UTC-4

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

What will happen if tourist and jqdai0815 both place 2-10 and thus get 4 more points — are they going to both advance directly to the TCO onsite?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    From https://tco19.topcoder.com/home/algorithm/algorithm-rules:

    "In the event of a tie for any advancing position during the Online Stage, the tie will be resolved in the following manner:

    The highest total point accumulation including only those rounds in which all tied competitors participated.

    If a tie still remains, all remaining tied Competitors will advance."

    Sounds like they should coordinate together to end up with the exact same point total ;)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I thought that points here are TCO points, not SRM points. So that will be easy since both participated in all rounds.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Yeah, but advancing many people to the onsite instead of one does not make much sense, so maybe the word "points" means different things in different parts of the rules? In particular, if in this sentence it means SRM points as neal says, then everything makes sense.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          I'm pretty sure those were intended to be sums of actual SRM scores. By the point you got there, you already know that you have some people who are tied in TCO points, there is no point to check those again. (I don't realistically see someone winning without taking part in all events.)

          I'll try to get this clarified before the SRM.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится

            Thanks! Ideally the leaderboard would also include those points, as it can greatly affect the strategy in this last SRM — not sure how feasible it is to add this to the leaderboard on such short notice.

            I guess all we need is a volunteer to count this based on the data feeds :)

            • »
              »
              »
              »
              »
              »
              »
              6 лет назад, # ^ |
                Проголосовать: нравится +11 Проголосовать: не нравится

              I have it up and ready ;) Will add here to the post to make it more interesting.

              And from stage 2 will have it added to the leaderboard :)

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится

            Sorry for being late on this! It actually means SRM scores/points. I will update the rules to make it more clear.

            Should be:

            The highest total SRM scores accumulation including only those rounds in which all tied competitors participated.

            Would be interesting if both end up having the same points total ;)

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I don't know where to write this so...

I noticed that avatars are shown in leaderboard and set avatar about a month ago. But nothing is shown for me.

»
6 лет назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

My plugin was broken. It took me 20 minutes to fix it.

My heart is broken now.

Congrats to tourist and see you in the next stage. >_<

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +48 Проголосовать: не нравится

    Sorry to hear that. It was indeed very unusual to see that you had had only the 250-pointer opened half an hour into the contest.

    Could you have just disabled the plugin and typed the class/method definition manually?

    On the other hand, when I opened the 1000-pointer with half an hour to go, knowing that you had opened it too, I had a weird feeling. I was sure you could solve it very quickly, as the hardest subproblem -- finding the sum of primes in [L;R] -- is well-known and almost definitely present on some OJ, and I thought you probably could just copy its solution.

    At the same time, even though I found the formula on the Internet, I still couldn't finish debugging in time -- and even after I did that, my solution took 23 seconds on the last example test case...

    By the way, kudos to neal for solving the 1000-pointer in a creative way :)

»
6 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

I think the idea of TCO19 points is pretty bad in this case. Since rank 2~10 got the same score, for the tops it's likely just comparing the times of getting rank 1 and comparing sums of SRM scores sounds bad since the maximum scores are set by the setters. I feel rather sad for jqdai0815 :(

Also, I don't like this set. 500 is nice but a bit too easy and implementation-heavy. 1000 as a kind of well-known problem (at least in China), has different difficulty for persons who copy and paste their old codes and people trying from scratch.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -30 Проголосовать: не нравится

    [comment deleted.]

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, that is a good point.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +49 Проголосовать: не нравится

      This is not really fair

      If you want to introduce some problems to the rest of the world you can write a blog post like some others do

      Instead you gave chinese competitors a huge advantage. In the end it didn't matter in terms of TCO points but it matters considering just SRM results

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      "To 1000-pointer, since it's a well-known problem "at least in China", I decide to introduce it to Topcoder as it's not a well-known one in Topcoder."

      That's ridiculous. You took a known problem and you want money for that? I'm going to start talking with my friends about problems from my future contests, or I will just start reusing old Polish problems.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +35 Проголосовать: не нравится

        I believe this is an issue with Blue-Mary's English. At least as far as I know, they did not copy a known problem (which may be what the above sounds like), they came up with an original one and only the general technique needed to solve it is what's "well-known".

        (And after seeing the problem I expect "well-known" to be quite an exaggeration of reality :) )

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

    I don't like this problem set too. I spent most of my time solving 500. When I opened 1000, I found it's very easy but I couldn't solve it before the contest ended. 1000 is well-known and lack of insights. I don't think such problems could appear as the hardest problem in a SRM.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey TLE, That's why to avoid any problems we are only going to compare those SRM scores of those matches in which both of them competed.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think that the score given by the author isn't always that accurate, say, every match's 1000-pts problem might not be of the same difficulty and have different passing rates. Thus, simply adding those scores up might not be a good choice. Adding SRM ranks or log(ranks) up might be better.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        IMHO, in most cases the race will be won or lost on TCO points. It's quite the coincidence that already the first season ended in a tie, but you can see that for the rest of the people on the top the points have quite a spread, and statistically ties like this one should not happen too frequently.

        There is no perfect way to set a tiebreaker. Results of contests are necessarily just an imprecise approximation of the contestants' skill. Statistically speaking, if there is a tie at the top, the few matches we saw don't give us enough data to be certain enough in stating which of the two amazing contestants did better. Regardless of what system you put in place, if you encounter two evenly matched contestants, in the end you can still essentially be forced to "flip a coin".

        One advantage I see for taking SRM scores and not one of the other measures you mention is that this is something the contestant can directly influence and calculate with it. Ranks are relative and depend on what other people do. SRM score depends (almost) only on what you do. In the last round, you can look at the score difference between you and your rival and adjust your strategy accordingly.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

          Also, I don't think the fact that "every match's 1000-pts problem might not be of the same difficulty and have different passing rates" really matters. In the end, both contestants were given the same set of problems and each of them was worth the same amount of points to both of them. The setting is perfectly fair. If one of them managed to solve significantly more of them than the other (especially mediums and hards), they will come up on top in the sum of SRM scores regardless of whether a specific hard was a 900 or a 1000. And if they are still too close to tell... they are too close to tell.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't believe that anyone except 3 or 4 people can be in top-10 for all contests, especially without pretests. But points are bad anyways.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

What about a fencing duel to resolve ties? Topcoder would have to cover travel costs, but this new format would bring more people to topcoder!

And congrats to tourist for the win.

»
6 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Seems that editorial writer had made a small mistake in Div1 Hard.

A clever way to compute these values is based on the following recurrences:
T(n,1) = n(n+1)/2
T(n,p) = T(n,p’) – p*T(n/p,p), where p’ is the biggest prime smaller than p, or 1 if there is no such prime

Instead of

T(n,p) = T(n,p’) – p*T(n/p,p)

It should be

T(n,p) = T(n,p’) – p*T(n/p,p-1)

As there can be multiple p in a number's prime factors.