### hmehta's blog

By hmehta, history, 5 weeks ago,

Topcoder SRM 808 is scheduled to start at 07:00 UTC-4 on June 25, 2021

Registration is now open for the SRM in the Arena or Applet and closes at 06:55 UTC-4. The coding phase will start at 07:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area

Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.

Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),

Best of luck!
- The Topcoder Team

• +33

 » 5 weeks ago, # |   +14 Countdown to the round: https://www.timeanddate.com/countdown/generic?p0=98&iso=20210625T07&msg=SRM%20808
 » 5 weeks ago, # |   0 Note: Round starts 5 minutes earlier than usual time!
•  » » 5 weeks ago, # ^ |   0 UPD: It's fixed now. Starts at usual time.
 » 5 weeks ago, # |   +13 Gentle Reminder: Round Begins in 20 mins!
•  » » 5 weeks ago, # ^ |   0 Can you share the editorial?
 » 5 weeks ago, # |   0 Unfortunately, I updated my system last week, which in turn also updated the Java version. Now I can no longer run contest applet. Errornetx: Initialization Error: Could not initialize application. (Fatal: Application Error: Cannot grant permissions to unsigned jars. Application requested security permissions, but jars are not signed.) net.sourceforge.jnlp.LaunchException: Fatal: Initialization Error: Could not initialize application. The application has not been initialized, for more information execute javaws from the command line. at net.sourceforge.jnlp.Launcher.createApplication(Launcher.java:823) at net.sourceforge.jnlp.Launcher.launchApplication(Launcher.java:531) at net.sourceforge.jnlp.Launcher$TgThread.run(Launcher.java:946) Caused by: net.sourceforge.jnlp.LaunchException: Fatal: Application Error: Cannot grant permissions to unsigned jars. Application requested security permissions, but jars are not signed. at net.sourceforge.jnlp.runtime.JNLPClassLoader$SecurityDelegateImpl.getClassLoaderSecurity(JNLPClassLoader.java:2487) at net.sourceforge.jnlp.runtime.JNLPClassLoader.setSecurity(JNLPClassLoader.java:385) at net.sourceforge.jnlp.runtime.JNLPClassLoader.initializeResources(JNLPClassLoader.java:808) at net.sourceforge.jnlp.runtime.JNLPClassLoader.(JNLPClassLoader.java:338) at net.sourceforge.jnlp.runtime.JNLPClassLoader.createInstance(JNLPClassLoader.java:421) at net.sourceforge.jnlp.runtime.JNLPClassLoader.getInstance(JNLPClassLoader.java:495) at net.sourceforge.jnlp.runtime.JNLPClassLoader.getInstance(JNLPClassLoader.java:468) at net.sourceforge.jnlp.Launcher.createApplication(Launcher.java:815) ... 2 more 
•  » » 5 weeks ago, # ^ |   0 Roll down your java version for the contest and revert back later, it'd just takes 2 commands
•  » » 5 weeks ago, # ^ |   +8 javaws was deprecated in java 11 so you need to downgrade. Kind of tricky to do on ubuntu: https://codeforces.com/blog/entry/90503?#comment-789564
•  » » » 5 weeks ago, # ^ |   0 Thanks. I had a different distro and 3 versions installed 8,11 and 16. Just switching between them 5 mins before the contest wasn't enough. I have followed equivalent commands for my distro.For others — Briefly this is what I did on arch LinuxFollowing instructions similar to what randomQuestionsAcc wrote for ubuntu 18. I just literally uninstalled everything related to java. pacman -Qe | grep jre would list out. Some of them had other dependencies on other things as well. But I anyway didn't need clion, goland and pycharm packages. So I just removed them. You would have to look for how to take care of dependencies like this. Then I installed jdk-8 and icedtea-web again. But this wasn't enough. As mentioned by randomQuestionsAcc this most important step for me. Others facing issues first just try this - # javaws still doesn't work because of the signing errors. # Disable security by deleting "MD5" from the line that starts with "jdk.jar.disabledAlgorithms" in the following file: sudo vim /usr/lib/jvm/java-1.8.0-openjdk-amd64/jre/lib/security/java.security # Before: jdk.jar.disabledAlgorithms=MD2, MD5, RSA keySize < 1024, \ # After: jdk.jar.disabledAlgorithms=MD2, RSA keySize < 1024, \
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 You don't need to "uninstall everything related to java", you just need to set default/current version of java to 8:# archlinux-java set java-8-openjdk/jreor simply% export JAVA_HOME=/usr/lib/jvm/java-8-openjdkI also run javaws -Xclearcache between consecutive runs, but I don't know if it is really neededAlthough I didn't managed to run javaws ContestAppletProd.jnlp until I removed MD5 from java.security.So, full snippet is: sudo pacman -S jre8-openjdk icedtea-web sudo sed -i 's/jdk.jar.disabledAlgorithms=MD2, MD5/jdk.jar.disabledAlgorithms=MD2/g' /usr/lib/jvm/java-8-openjdk/jre/lib/security/java.security # if you want to make java8 default: sudo archlinux-java set java-8-openjdk/jre # if you want to make java8 only for this terminal export JAVA_HOME=/usr/lib/jvm/java-8-openjdk # if you already unsuccessfully tried to run javaws javaws -Xclearcache javaws ContestAppletProd.jnlp 
•  » » 5 weeks ago, # ^ |   +27 On Linux, I've had success with https://openwebstart.com/
 » 5 weeks ago, # |   0 Hope to see similar(and more) difficulty level SRM in future, I found problems interesting and non trivial. Thanks for the problems!!
 » 5 weeks ago, # |   0 How to solve the DIV-2 500 point problem ?
•  » » 5 weeks ago, # ^ |   0 DP, similar to Knapsack
 » 5 weeks ago, # | ← Rev. 3 →   +13 Editorial isn't ready yet (IOI, no sleep, etc), so here are some quick solution ideas until then. div2 easyYour worst placement is when you do your worst and everyone else does their best. div2 mediumProcess subtasks one at a time, maintain the total probability of having each possible score. div2 hard / div1 easyImagine the difference in votes as the "capacity" of a directed edge from winner to loser. S(A,B) is then simply the biggest capacity of a path from A to B. One easy way to compute all S(A,B) is Floyd-Warshall, but with max and min instead of the usual min and +. div1 medium and hardThe model used is Fractran, it's by John Horton Conway (the guy of Game of Life fame) and it's Turing complete.Medium is just about getting used to how stuff works. Powers of some primes can be regarded as variables. One easy-to-implement idea to find the median of five numbers is "while you can decrement at least three of a,b,c,d,e, decrement all you can and increment the output".Probably the easiest way to do hard is essentially the same way you can show Turing-completeness: use some primes as your variables, use other primes as states (exactly one of these is always present in the current value, and dictates what we can do next). Multiplication can be implemented as repeated addition: when computing x*y, y times add x to the result.
 » 5 weeks ago, # | ← Rev. 2 →   +8 Solution for 1000p : 1/7 5*13*17/3*11 5*11*17/3*13 1/11 1/13 3/17 11/2 1/3 First remove the useless $7$, then the loop runs for $x$ times, and remove $3$'s in the end.During each loop, $11$ and $13$ are flags that alternates, $3$ decreases and $5,17$ increase, calculating the answer while keeping the value of $y$.
 » 5 weeks ago, # | ← Rev. 2 →   +8 (CF bugging out, hopefully this will post)In div1 500 and 1000, we can spot combinations of simple assembler instructions: CBZ "if non-zero execute block of instructions, otherwise jump beyond that block" and ADD/SUB #constant, but with arbitrary numbers of input/output registers. Each prime exponent is a register. In 500, there's not much programming involved since we're just subtracting from all non-zero registers until there are less than 3 of them, but in 1000, we can also notice that some exponents can serve as bits in a flag register. There's a general way to write a cycle with $n$ iterations if we have a flag bit b1 set: b1 = 0, b2 = 1 while true: if b2 and n > 0: b2 = 0, b3 = 1, n--, execute inner block elif b3 and n > 0: b3 = 0, b2 = 1, n--, execute inner block else: break now we can unset b2 or b3 (whichever is 1) and set b1 Note that it's simplest if the inner block is one instruction, but it's doable with more by adding extra flag bits that are set/unset one by one in a chain, e.g. b2 = 0, b4 = 1, n--, inner instruction 1; b4 = 0, b3 = 1, inner instruction 2 or with b5 if moving in the other direction from b3 = 1 to b2 = 1.It's similar to brainfuck but more versatile since we're not limited to one-input instructions. In the absence of JMP and SET instructions, the required number of primes still grows rapidly with complexity of the program.Therefore, in 1000, we can do the following: use 7 as flag bit for outer loop: while x > 0, do x-- and while true: /3 * 5 * 17 while true: /17 * 3 delete 7 and powers of 3 In each iteration of the outer loop, we go from $2^{x-z} 3^y 5^{zy}$ to $2^{x-z-1} 3^y 5^{zy+y}$.
 » 5 weeks ago, # |   +13 My blog article about strategies to challenge other topcoders' code in SRM — https://shadek07.medium.com/topcoder-srm-challenge-phase-how-to-find-bugs-in-code-88353bc19823?sk=2082e79e6a3d1ddc2a1bc75fcb1d5a8e
 » 4 weeks ago, # | ← Rev. 2 →   0 The limits to 1000 were quite comical for my solution.I did all the fractions (2 ^ X * 3) from x = 1 to 20, and then used a binary counting mechanism to add to 5s.If I used 3 numbers for my binary mechanism, there would be 26 fractions. (Since I need 3 for the system, and then 3 sinks for 2,3,7).If I used 2 numbers, it would overflow. (biggest number would be 35 bits)If there wasn't a 7 there (which after reading solutions I see it's because of the initial state you need to be in), then I wouldn't have needed a 1/7 fraction and it would've worked. If the prime selected for state (7) would've been bigger, I could've used it in the system, and no overflow.It seemed that if any of the limits were relaxed my solution would've worked perfectly, but they all worked together to make my initial solution hard to implement. In the end I realized that using ternary counting system just managed to squeeze in with these limits.