Lewin's blog

By Lewin, history, 6 years ago, In English

Hi! Topcoder SRM 730 will happen soon.

Time: 7:00am EDT Tuesday, February 20, 2018

Calendar: https://www.topcoder.com/community/events/

I'm the writer of this round. Hope to see you all participate!

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

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

Reminder: The contest starts in 4 hours! Both SRM 730 and Humblefool Cup Qualifier's registeration has started!
Note that registeration ends in 5 minutes before the contest. Don't miss!

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

There is some kind of 'reward' survey when I'm trying to register this round. I did not participated in SRM 722, 723, 724, 726 and not interested in 'a chance to be recognized by the Harvard-NASA Tournament Lab and Topcoder' (btw, what does 'recognized' here mean?), but the survey asked me to select one of three. What should I do?

»
6 years ago, # |
Rev. 4   Vote: I like it +31 Vote: I do not like it

Hope you enjoyed the round! Here is some example code and some short explanations.

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

    "By an exchange argument, you can show that sorting the children by w[p] — dp[p] gives an optimal permutation." -Div2Hard

    Can you explain this?

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

    Easier combinatoric interpretation:

    Let's look at all subsets of x or more elements and leave only x largest elements in each subset. Now each subset S of x elements appears exactly 2min(S) - 1 times.

    So the answer is sumi = xnC(n, i), which is easy to count.

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

    I solved Div1 500pts in (probably) different way:
    Let's think about the following sub-problem:

    Sub-problem

    Going back to the main problem, graph has edge (i, j) if and only if i ≠ j and i + j < n. And the "selection" is, you can restrict to selecting "either vertex k or vertex 2n - k - 1 (not both)". Let this vertex, "level-k" vertex.
    Suppose that you select from level-n - 1, n - 2, n - 3, ..., 0 vertex in preceding order. If you select k in level-k, the number of edges on subgraph increases by n - k - 1, and if you select n - k - 1 the number of edges doesn't change. So, you can choose arbitrary subset of level 1, 2, 3, 4, ..., n, and the "increase value" of number of edges is (n - 1, n - 2, n - 3, ..., 0). This is equivalent to the sub-problem, which N = n - 1, K = x.
    So this problem can be solved in O(N3), which is equivalent to output size, and the implementation is pretty easy (practically 17 lines):

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

    Another solution for div1 1000:

    f(n, x) is of the form 2n + 1 - Px(n), where Px(n) is some polynomial of degree x - 1, and Px(i) = 2i + 1 for all i < x.

    Proof:

    f(n, 1) = 2n + 1 - 2

    for x > 1. (Just iterate on the maximum).

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

      Yes! In this way we can solve for any power. I see we need compute a sum like: . And I guess that sum is a polynomial of degree x - 1 plus .

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

        Do you have any proof for this?

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

          Since you guess out it, it is not hard to proof. Just do an induction from recurence formula: f(x, n) = f(x, n - 1) + f(x - 1, n - 1).

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

          It is clearly true for x = 1.

          We can now use induction. For x > 1, If it is true for x - 1,

          = (by rearranging some terms, and using is a polynomial of degree k + 1)

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

    Did you expect d1 hard to be hard? (It wasn't even 900).

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

      I didn't expect it to be hard, but it seems we forgot to adjust points accordingly (I had prepared this round a few weeks ago, so it wasn't at the top of my mind until a few days ago).

      The testers didn't find a combinatoric interpretation at first (and one solved it for general powers first). I believe it can be easy to miss, but it also seems obvious after the fact. I briefly considered changing the power so it's not 2 which would have made it significantly harder, but decided it's better to let some of these easier solutions pass also rather than get almost no solves.

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

    Div2Hard:

    I guess it's just a typo, but in the problem statement it says that weights are "non-decreasing". Or it depends on which direction you look at the tree — bottom-up or vice versa :)

    Update: another typo seems to be dp[c], looks like you meant dp[i] instead.

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

A question unrelated to this round in particular -- why do the lower numbered rooms have more red participants than higher numbered rooms? Is it intentional and "fair"? I'd expect that hacking in a room with 50% red is much more difficult, as higher percentage of submissions is expected to be correct, and there are better and faster hackers.

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

    As I understand first coders are distributed randomly and then rooms are ordered based on strength

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

    When I was the admin, there were a few algorithms for room assignment. In SRM it was named "Random Seeding", in TCO it was named "Ultra Random Seeding", though I don't know details.

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

      It used to be the case that they only used actual uniform random for rounds that had monetary prizes (TCO, sponsored SRMs). For regular SRMs they used some biased algorithm that made it more likely for higher-rated coders to end up in lower-numbered rooms. This was intentional.

      Given that nowadays TC doesn't really care about their Algorithm track, I'm quite sure this is still the case, and that these are the two seeding algorithms [h]rng_58[/h] mentions.

      (I don't know why they decided to use the biased seeding algorithm. It's not completely fair, but at the same time the bias isn't large enough, so the contestants never complained too loudly about it, I guess.)

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

        majk is complaining. I was also complaining when I found myself in the room 1, with Petr and a bunch of reds. The rest was yellows and 2 blues.

        However it is also not completely true, that this is such a disadvantage. If the tasks are difficult, quite often lower rated coders do not submit anything, whilst higher rated coders are more likely to submit a solution. Because the task is tricky/difficult, there is also a higher chance for them to make a mistake, so I started to wonder, whether my complains were reasonable.

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

          In SRM 729 it was quite fortunate situation for uwi, who managed to win the SRM because of lot of wrong solutions in my room and his excellent speed and solid preparation in the coding phase (and my inability to stop thinking about the hard task and concentrate on the challenges :-)).

          The complaints are not unfounded, though. However, I doubt that they will change anything, since I also have the feeling that the algorithm track lacks a bit of love from TC staff. Case in point, the time in the web arena is still off by 4 hours.