Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### hmehta's blog

By hmehta, history, 5 months ago, ,

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.

Good luck to everyone!

• +10

 » 5 months ago, # |   0 Failing to start arena with following error: full errornet.sourceforge.jnlp.LaunchException: Fatal: Launch Error: Could not launch JNLP file. The application has not been initialized, for more information execute javaws/browser from the command line and send a bug report. at net.sourceforge.jnlp.Launcher.launchApplication(Launcher.java:582) at net.sourceforge.jnlp.Launcher$TgThread.run(Launcher.java:945) Caused by: java.lang.reflect.InvocationTargetException at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62) at java.base/jdk.internal.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) at java.base/java.lang.reflect.Method.invoke(Method.java:566) at net.sourceforge.jnlp.Launcher.launchApplication(Launcher.java:576) ... 1 more Caused by: javax.xml.parsers.FactoryConfigurationError: Provider for class javax.xml.parsers.SAXParserFactory cannot be created at java.xml/javax.xml.parsers.FactoryFinder.findServiceProvider(FactoryFinder.java:305) at java.xml/javax.xml.parsers.FactoryFinder.find(FactoryFinder.java:261) at java.xml/javax.xml.parsers.SAXParserFactory.newInstance(SAXParserFactory.java:147) at com.topcoder.client.ui.impl.XMLUIManager.(Unknown Source) at com.topcoder.client.ui.UIFactory.getUIManager(Unknown Source) at com.topcoder.client.ui.UIFactory.getUIManagerFromResource(Unknown Source) at com.topcoder.client.contestApplet.common.LocalPreferences.getAllUIManagers(Unknown Source) at com.topcoder.client.contestApplet.ContestApplet.(Unknown Source) at com.topcoder.client.contestApplet.runner.generic.main(Unknown Source) ... 6 more Caused by: java.lang.RuntimeException: Provider for class javax.xml.parsers.SAXParserFactory cannot be created at java.xml/javax.xml.parsers.FactoryFinder.findServiceProvider(FactoryFinder.java:302) ... 14 more Caused by: java.util.ServiceConfigurationError: javax.xml.parsers.SAXParserFactory: Provider org.apache.xerces.jaxp.SAXParserFactoryImpl not found at java.base/java.util.ServiceLoader.fail(ServiceLoader.java:588) at java.base/java.util.ServiceLoader$LazyClassPathLookupIterator.nextProviderClass(ServiceLoader.java:1211) at java.base/java.util.ServiceLoader$LazyClassPathLookupIterator.hasNextService(ServiceLoader.java:1220) at java.base/java.util.ServiceLoader$LazyClassPathLookupIterator$1.run(ServiceLoader.java:1267) at java.base/java.util.ServiceLoader$LazyClassPathLookupIterator$1.run(ServiceLoader.java:1266) at java.base/java.security.AccessController.doPrivileged(Native Method) at java.base/java.util.ServiceLoader$LazyClassPathLookupIterator.hasNext(ServiceLoader.java:1269) at java.base/java.util.ServiceLoader$2.hasNext(ServiceLoader.java:1299) at java.base/java.util.ServiceLoader$3.hasNext(ServiceLoader.java:1384) at java.xml/javax.xml.parsers.FactoryFinder\$1.run(FactoryFinder.java:287) at java.base/java.security.AccessController.doPrivileged(Native Method) at java.xml/javax.xml.parsers.FactoryFinder.findServiceProvider(FactoryFinder.java:283) ... 14 more Is it something known? Probably can be related with upgrade to Ubuntu 19.04. 
 » 5 months ago, # | ← Rev. 2 →   +23 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   -39 Implement / DP problems. It is only to fast coding rather than thinking.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +6 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.
•  » » 5 months ago, # ^ |   +51 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!
•  » » » 5 months ago, # ^ |   -29 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$.
•  » » » » 5 months ago, # ^ |   +33 Then why you didn't solve :facepalm:
 » 5 months ago, # | ← Rev. 2 →   +3 The link to the TCO leaderboard seems broken :/Here is a working link: https://tco19.topcoder.com/algorithm/algorithm-leaderboard
 » 5 months ago, # |   +96 Srsly rated? XD
•  » » 5 months ago, # ^ | ← Rev. 2 →   +33 +1
•  » » » 5 months ago, # ^ |   +13 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +10 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.
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   +58 Why make it rated though?
•  » » 5 months ago, # ^ |   +53 I'm sorry, but I don't understand how can it be rated when the judge was bugged until 20 minutes before end?
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +31 Agree. It's as though you couldn't test your solution on pretests on CF for three fourths of the contest...
•  » » » » 5 months ago, # ^ |   +23 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.
•  » » 5 months ago, # ^ |   +54 Happy birthday! Thank you for your efforts in competitive programming!
•  » » 5 months ago, # ^ |   +4 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!
•  » » » 5 months ago, # ^ |   +8 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!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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).
 » 5 months ago, # |   0 Can someone explain Div-2 hard second observation in brief specifically what is integer partition?
•  » » 5 months ago, # ^ | ← Rev. 3 →   +1 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
•  » » » 5 months ago, # ^ | ← Rev. 4 →   0 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.