### hmehta's blog

By hmehta, history, 8 months ago, ,

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.

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

 » 7 months ago, # |   +16 Reminder — the contest will begin in 105 minutes.
 » 7 months ago, # |   +10 Funny hard, how to solve it?
•  » » 7 months ago, # ^ |   +10 What's wrong with my solution? :P
•  » » » 7 months ago, # ^ |   +10 It won't transform into a math proof :D Which I believe setter should have
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +21 Why? There are only 1000 inputs, so one can just check them all before submission (I did that).
•  » » » » » 7 months ago, # ^ |   -10 Well, of course I am talking about arbitrarily big values of n, I am not that narrow-minded :P
•  » » » » » » 7 months ago, # ^ | ← 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.
•  » » 7 months ago, # ^ | ← 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)
•  » » 7 months ago, # ^ | ← 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.
•  » » 7 months ago, # ^ |   +46 $2.635...^{50}$
•  » » » 7 months ago, # ^ |   0 Uh oh, seems I got ideas in good directions, but not quite there. Thanks
•  » » » 7 months ago, # ^ |   +8 for each unit (consists of 7 vertices), there is 864 coloring which don't color red the root vertex. $864^{1/7} = 2.62725340284...$
•  » » » 7 months ago, # ^ |   0 What did you use to generate the image?
•  » » » » 7 months ago, # ^ |   +10 this. it's using Vis.js.
 » 7 months ago, # |   +26 Wow, turns out I can type "1000" really fast.
•  » » 7 months ago, # ^ |   +10 Seriously though, problems like Hard shouldn't be in contests with hacks.
•  » » » 7 months ago, # ^ |   0 Why not? It is up to participant to decide should they submit their unproved unchecked solution or not.
•  » » » » 7 months ago, # ^ |   0 It is kinda crapshoot who get the 50 points though
•  » » » » 7 months ago, # ^ |   +20 Because challenge phase was decided by who types "1000" and clicks "Challenge" button faster. It's meaningless and not fun.
•  » » » » » 7 months ago, # ^ |   +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.
•  » » » » » » 7 months ago, # ^ |   +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.
•  » » » » » 7 months ago, # ^ |   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.
•  » » » » » 7 months ago, # ^ |   +36 There is still strategy involved. I hacked with "20" instead of "1000", saving 2 keystrokes per challenge.
•  » » » » » » 7 months ago, # ^ |   0 Wouldn't 99 have a better chance of failing then.
 » 7 months ago, # | ← Rev. 2 →   +11
•  » » 7 months ago, # ^ |   0 What? There are at most 5,607 turtles.
•  » » 7 months ago, # ^ |   +18
 » 7 months ago, # |   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.
 » 7 months ago, # |   0 Can anyone explain how to solve Div 2 ReallyMagicSquare?