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!

Failing to start arena with following error:

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

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.

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

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.

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!

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$$$.

Then why you didn't solve :facepalm:

The link to the TCO leaderboard seems broken :/

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

Srsly rated? XD

+1

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.

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.

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.

Why make it rated though?

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

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

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.

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

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!

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 textto the real statement foremphasis.------------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

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

describedby 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 describingbecause 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!

The 2 main conditions are:

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

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).

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

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

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:

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

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.