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

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

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!

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

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

Reminder — the contest will begin in 105 minutes.

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

Funny hard, how to solve it?

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

    What's wrong with my solution? :P

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

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -10 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 4   Проголосовать: нравится -18 Проголосовать: не нравится

            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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

    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.

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

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

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

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

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

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

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

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

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

        It is kinda crapshoot who get the 50 points though

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

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

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

          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.

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

            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.

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

          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.

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

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.