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
Countdown to the round: https://www.timeanddate.com/countdown/generic?p0=98&iso=20210625T07&msg=SRM%20808
Note: Round starts 5 minutes earlier than usual time!
UPD: It's fixed now. Starts at usual time.
Gentle Reminder: Round Begins in 20 mins!
Can you share the editorial?
Unfortunately, I updated my system last week, which in turn also updated the Java version. Now I can no longer run contest applet.
Roll down your java version for the contest and revert back later, it'd just takes 2 commands
javaws was deprecated in java 11 so you need to downgrade. Kind of tricky to do on ubuntu: https://mirror.codeforces.com/blog/entry/90503?#comment-789564
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 —
Following 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, \
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/jre
or simply
% export JAVA_HOME=/usr/lib/jvm/java-8-openjdk
I 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 fromjava.security
.So, full snippet is:
On Linux, I've had success with https://openwebstart.com/
How to solve the DIV-2 500 point problem ?
Editorial isn't ready yet (IOI, no sleep, etc), so here are some quick solution ideas until then.
Your worst placement is when you do your worst and everyone else does their best.
Process subtasks one at a time, maintain the total probability of having each possible score.
Imagine 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 +.
The 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.
Solution for 1000p :
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$$$.
(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: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 withb5
if moving in the other direction fromb3 = 1
tob2 = 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:
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}$$$.
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
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.