hmehta's blog

Topcoder SRM 758 — Registration Open
By hmehta, history, 6 years ago, In English

Hey All!

Topcoder SRM 758 is scheduled to start at 11:00 UTC -4, May 10, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Problem Setters: IH19980412 and misof

This is the first SRM of Stage 4 of TCO19 Algorithm.

Stage 3 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 759 — May 29, 07:00 UTC-4

Good luck to everyone!

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

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

Failing to start arena with following error:

full error

Is it something known? Probably can be related with upgrade to Ubuntu 19.04. `

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

Thank you for the nice problemset! It was a good round except the tester of Div1 500 and 1000 was bugged.

So, will it be rated? Personally I think that it should be unrated, to maintain the quality of TC rating, though.

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

    Implement / DP problems. It is only to fast coding rather than thinking.

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

      Really? I specially liked Div1 Easy. The number like 31143310 is so mysterious and it was like a puzzle to get the regularity to reduce this problem into brute force.

      So I took a few minutes to get the solution. I even think that this Div1 Easy is my favorite in Div1 Easy of past 7 SRMs.

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

    I spent about 15min in Div1 500 because of the bug "Argument #1", and I finished debugging on 1000 after 1 min of coding phase; it got accepted in the practice room.

    I agree that it should be unrated :(

    Btw, Div1 1000 was good(you don't have to do knapsack N times, just 1 time). I like it!

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

      LOL, I thought that the round should be unrated after failing system test on 500. But it results rated and my rating increased.

      About 1000, it quite straightforward for me. Just $$$dp[k][x]$$$ the number of permutations s.t. the sum of first $$$k$$$ elements is $$$x$$$.

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

        Then why you didn't solve :facepalm:

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

The link to the TCO leaderboard seems broken :/

Here is a working link: https://tco19.topcoder.com/algorithm/algorithm-leaderboard

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

Srsly rated? XD

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

    +1

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

      There's also a funny thing.

      I've tried to copy "system: 2 message: sadmausnduasdsa" and send it to admins to ask what's going on. So, I opened a chat, chose admin's mode, pasted it and pressed enter. Smart topcoder thought: hmmm, I'm quite sure that he wanted to send it to the user with nickname "system"... and sent it to public chat.

      Good job.

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

    I initially thought that it should be unrated, but I also thought that it should be no surprise for being rated.

    I wrote something mainly about this in TopCoder forum, and I somewhat realized that many people are saying unrated because we experienced new type of system issue.

    I think you remember that a contest in Codeforces became semi-rated because there was long judge queue for almost half of contest. Even this made semi-rated, but not unrated.

    Obviously the issue happened in SRM 758 is less affected than that. That’s because we can easily do something. Even if we do not have plugins or prepared scripts, we can copy samples in problem statement and judge in local coding environment.

    Finally I quote AtCoder admin chokudai ’s tweet, “if AtCoder’s judge system did not work from equally the same time for all participants, it would be rated with no doubt”. This tweet was the main motivation of which I wrote that in TopCoder Forums.

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

Editorial for the round.

FWIW, sorry about the issues with testing in the arena during the round (and especially to HIR180 whose two nice problems were affected by the bug). It turned out that this was a new issue and it was caused by some pesky whitespace that somehow made its way where it didn't belong. Now that we discovered it, it shouldn't reappear in the future.

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

    Why make it rated though?

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

    I'm sorry, but I don't understand how can it be rated when the judge was bugged until 20 minutes before end?

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

      Agree. It's as though you couldn't test your solution on pretests on CF for three fourths of the contest...

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

        Yep. Also it’s unfair somehow, because plugins probably are very useful in situations like this one. It’s like you could test on pretests only if you submit using API/prepared script.

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

    Happy birthday! Thank you for your efforts in competitive programming!

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

    Hi Misof.

    Regarding SelfDescFind: I am a bit confused about about the first simple observation: " if you are given D digits, the number you are constructing will have exactly 2D digits". For example, if the input is {0, 1, 2, 3} then I can generate a number with less than 2D digits: "101231". As far as I can tell, it meets all the requirements from the problem statement. What am I missing?

    Thank you for the interesting problem!

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

      Hi, I had a similar thought during the round, but when I asked clarification to the the admins they made me realize that the answer is in the statement. I will add bold text to the real statement for emphasis.

      ------------Statement---------------

      The number 31143310 is self-describing because we can read it as the statement "this number contains three '1's, one '4's, three '3's, and one '0'", and that statement correctly describes the whole number.

      More formally, a number is called self-describing if it satisfies the following:

      • It has an even number of digits. Below, we will label the individual digits a[0], b[0], a[1], b[1], ... from the left to the right.
      • The digits b[i] are all distinct.
      • For each valid i, the number contains exactly a[i] copies of the digit b[i].
      • The number does not contain any other digits, except for those described by the statements mentioned above.

      You are given the digits. Find the smallest self-describing number N such that the digits that appear in N are precisely the digits in digits. If such a number exists, return a with its decimal representation. Otherwise, return an empty

      --------------End-Statement---------------------------

      In essence, $$$101231$$$ is not self describing because you have no information in the number regarding the amount of appearences that number $$$3$$$ has. To mimic the statement, you know that $$$101231$$$ contains one $$$0$$$'s, one $$$2$$$'s, three $$$1$$$'s, but you cannot tell how many times number $$$3$$$ appears, despite actually having an appearance.

      I hope this helps you!

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

      The 2 main conditions are:

      1. For each valid i, the number contains exactly a[i] copies of the digit b[i].

      2. The number does not contain any other digits, except for those described by the statements mentioned above

      101231 does not meet the 2nd condition. There is a 3 in the number but it is not described by the number (i.e. there should have been a "13" in the number).

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

Can someone explain Div-2 hard second observation in brief specifically what is integer partition?

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

    If you get the first observation, the integer sequence $$$A = (A_1, A_2, ..., A_D)$$$ should hold:

    • $$$A_1, A_2, ..., A_D$$$ are positive integers
    • $$$A_1 + A_2 + A_3 + \cdots + A_D = 2 \times D$$$

    In Div1 300 / Div2 1000, what we should do in the second observation is to brute-force all possible sequence $$$A$$$. There are exactly $$$C(2D-1, D)$$$ possible sequence.

    Let me give the proof. Let $$$B_i = A_i - 1$$$. The condition of sequence $$$B = (B_1, B_2, ..., B_D)$$$ is as follows:

    • $$$B_1, B_2, ..., B_D$$$ are non-negative integers
    • $$$B_1 + B_2 + ... + B_D = D$$$

    Let's think about permutations of $$$D$$$ o's and $$$D-1$$$ |'s. For example, if $$$D=5$$$, oo|o||oo|| is one valid permutation, and we are splitting circles into $$$2, 1, 0, 2, 0$$$ circles component. Then, we can get sequence $$$B = (2, 1, 0, 2, 0)$$$.
    We can generate all sequence $$$B$$$ by this way. Since there are $$$C(2D-1, D)$$$ permutations of oooo....o|||...|, the sequence $$$B$$$, also for $$$A$$$, has $$$C(2D-1, D)$$$ possibilities.

    In this problem, $$$D \leq 10$$$, so $$$C(2D-1, D)$$$ is at most $$$92378$$$, and it implies that brute-forcing it fits the time limit.

    Note: $$$C(N, K)$$$ is a binomial coefficient

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

      Very clear, Thank you! C(2D-1,D-1) is basically just stars and bars- no. of positive solutions of a1+a2+...+ad = 2D where ai>0.

      → Reply