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