hmehta's blog

Topcoder SRM 808
By hmehta, history, 3 years ago, In English

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

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

Comments Comments (17)
| Write comment?
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Countdown to the round: https://www.timeanddate.com/countdown/generic?p0=98&iso=20210625T07&msg=SRM%20808

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

Note: Round starts 5 minutes earlier than usual time!

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

Gentle Reminder: Round Begins in 20 mins!

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

    Can you share the editorial?

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

Unfortunately, I updated my system last week, which in turn also updated the Java version. Now I can no longer run contest applet.

Error
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Roll down your java version for the contest and revert back later, it'd just takes 2 commands

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

    javaws was deprecated in java 11 so you need to downgrade. Kind of tricky to do on ubuntu: https://codeforces.net/blog/entry/90503?#comment-789564

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

      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 Linux
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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 needed
        Although 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
        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    On Linux, I've had success with https://openwebstart.com/

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

How to solve the DIV-2 500 point problem ?

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

Editorial isn't ready yet (IOI, no sleep, etc), so here are some quick solution ideas until then.

div2 easy
div2 medium
div2 hard / div1 easy
div1 medium and hard
→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

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

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

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

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

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

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.

→ Reply