Блог пользователя hmehta

Topcoder SRM 808
Автор hmehta, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Note: Round starts 5 minutes earlier than usual time!

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Gentle Reminder: Round Begins in 20 mins!

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Error
→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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 Linux
      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
        ← 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/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
        → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

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

    → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve the DIV-2 500 point problem ?

→ Ответить
»
3 года назад, # |
← Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

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
→ Ответить
»
3 года назад, # |
← 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$$$.

→ Ответить
»
3 года назад, # |
← 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}$$$.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +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

→ Ответить
»
3 года назад, # |
← 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.

→ Ответить