hmehta's blog

Topcoder SRM 769 — Registration Open
By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 769 is scheduled to start at 07:00 UTC -4, Oct 19, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to misof for writing the problems for the round. Also thanks to DuXSerbia for testing the problem set.

This is the second SRM of Stage 1 of TCO20 Algorithm Tournament.

Stage 1 TCO20 Points Leaderboard | Topcoder Java Applet | Next SRM 770 — Nov 2, 07:00 UTC-4

Some Important Links
Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

Comments Comments (28)
| Write comment?
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Reminder — the contest will begin in 105 minutes.

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

Funny hard, how to solve it?

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

    What's wrong with my solution? :P

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

      It won't transform into a math proof :D Which I believe setter should have

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +21 Vote: I do not like it

        Why? There are only 1000 inputs, so one can just check them all before submission (I did that).

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          Well, of course I am talking about arbitrarily big values of n, I am not that narrow-minded :P

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 4   Vote: I like it -18 Vote: I do not like it

            However, I don't believe that there exist $$$2.62^n$$$ solution for infinitely big number $$$n$$$. In my intuition the upper-bound is $$$2.594^{n+o(n)}$$$ but the large $$$o(n)$$$ factor is like multiple of $$$\log(n)$$$ or $$$\log(\log(n))$$$ or something others. (not yet proved, though)

            UPD: Seems like $$$2.62^n$$$ for infinitely large $$$n$$$ is feasible.

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

    The output checker can be written in $$$O(n)$$$ with tree-dp and maintaining logarithm of the number of ways.

    During the contest I thought about doing "hill-climbing" of $$$c_i$$$'s (letting $$$c_i$$$ is the number of $$$i$$$'s in answer array). It seems like it is optimal to be $$$c_0 \geq c_1 \geq c_2 \geq ... \geq c_{n-2}$$$ (experimented for $$$n \leq 12$$$).

    So I thought about doing hill-climbing of $$$(c_0, c_1, ..., c_{n-2})$$$, and the neighbor is to increase/decrease $$$c_i$$$ by 1 and decrease/increase $$$c_{i+1}$$$ by 1, but couldn't finish implementation in the coding phase. (however, not sure it will pass)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +31 Vote: I do not like it

    Another idea can be to find a small graph with (no of valid coloring where root is not painted red)^(1/n)>2.62 and connect these graphs. We can use a 7 node graph with 3 nodes connected to root and one node connected to each of those. (960^(1/7) = 2.66) This should work for infinite n too.

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

    $$$2.635...^{50}$$$

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

      Uh oh, seems I got ideas in good directions, but not quite there. Thanks

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

      for each unit (consists of 7 vertices), there is 864 coloring which don't color red the root vertex. $$$864^{1/7} = 2.62725340284...$$$

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

      What did you use to generate the image?

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

Wow, turns out I can type "1000" really fast.

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

    Seriously though, problems like Hard shouldn't be in contests with hacks.

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

      Why not? It is up to participant to decide should they submit their unproved unchecked solution or not.

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

        It is kinda crapshoot who get the 50 points though

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

        Because challenge phase was decided by who types "1000" and clicks "Challenge" button faster. It's meaningless and not fun.

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

          You could get -25.

          How it is different from 95% of challenges? Most of the time there is one common wrong solution, so you just going through codes and check if it is that kind of wrong. Of course, this time you don't have to come up with test against given solution, but it can be done in intermission, so challenge phase itself is still "Ctrl-C challenge". That is, if you believe that all solutions are wrong.

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

            Maybe that's why I usually skip the challenge phase.

            And I didn't assume that all solutions are wrong. I assumed that if I spend time reading code, someone else will surely hack it before me. With that assumption if you think that solution is wrong with probability at least 1/3 you should hack it immediately.

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

          This seems like the most common TC challenge strategy. Find a problem that's easy to fail and with a lot of submissions, craft a test that should fail often, try that immediately on everything. Shit sucks.

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

          There is still strategy involved. I hacked with "20" instead of "1000", saving 2 keystrokes per challenge.

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

            Wouldn't 99 have a better chance of failing then.

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

500 — notorious coincidence

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1095

https://morris821028.github.io/2014/11/21/uva-10154/

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

I started the contest and electricity (= wifi) died after about 8 minutes. It went back on later, but I'm surprised it even did. Shit sucks.

→ Reply