Hi there!
In a few hours, at 05:00 MSK will be held Topcoder SRM 682.
Let's discuss problems after contest!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hi there!
In a few hours, at 05:00 MSK will be held Topcoder SRM 682.
Let's discuss problems after contest!
Name |
---|
It will be my first time to participate, The arena looks exciting :)
It will look terrifying soon enough :D
Why are some people always criticizing the Topcoder arena. I know some things like it has infinite power over my system, it is difficult to change color(if possible) but that is it.
Can you point out some real mistakes/issues in the arena.
I find the arena way too good and sometimes better than platforms other than Codeforces. Moreover, the quality of questions is just too awesome.
Internet keeps fluctuating in my hostel so the arena keeps crashing and I have to login again and again which wastes a lot of time.
My main complaint is that it has a steep (though not long) learning curve. It put me off at first simply because there's no clear HTML access to problemsolving.
Another thing is that it doesn't work offline. HTML loads once when reading a problem, another time when submitting; if I have a poor connection, I'll have to log in everytime I'm testing something.
And it fails somehow, occasionally — but that's every programming site's problem.
https://www.topcoder.com/tc?module=ProblemArchive
Use plugins for offline testing. Example: Greed. www.vexorian.com/2013/09/getting-started-with-topcoder-greed.html
Arena is awesome. We should support Topcoder in what it is providing us.
problemSOLVING — I want to see you submit on that page
plugins get broken recently, also I fail to see how having to run two things (arena+plugins) is better than having to run zero (HTML) — that's what I mean by a steep learning curve
Once you install Greed, it goes way better. This is what my opinion is.
Here is an example of what I consider a real issue. I wanted to participate in a SRM for the first time since 2013, so I tried to test the new interface/arena before the contest. When I tried to compile a dummy code, I got a message saying "Your code compiled successfully, but generated warnings: [...]". Ok, that's fine. Now when I wanted to submit this code it said "You can't submit unless you have successfully compiled first". I asked an admin whether that is a bug, and got a reply that it's "pretty normal".
Discovering that I have to write warning-free code pretty much killed my motivation there, especially if I have to use Arena to get rid of all the warnings. A number of years ago I would have taken this as an opportunity to learn writing a better code, but right now I see it much more of a nuisance than anything else.
I don't remember any time when arena would not allow to submit code with warnings. You must have changed something in your code between compiling and submitting. Even just a single space will do.
I just tested it again, by writing the following solution for problem "YetAnotherTwoTeamsProblem":
Pressing "Compile" shows me the following:
Next, pressing "Submit" (immediately after "Compile") results in: "You can't submit unless you have successfully compiled first."
I got the same behavior on February 21 and 23. Each time I tested two different problems, one in IE and one in Chrome. I also checked that unused or uninitialized variables result in the same behavior. I also tried to be clear about what my problem is when I spoke with an admin in the lobby, when I asked whether that's a known bug. Are you sure you can submit source code with warnings?
A possible workaround suggested by madars is to use #pragma to disable warnings. Indeed, the following "YetAnotherTwoTeamsProblem" solution can be successfully compiled and submitted:
Just submitted your first code for 997.65 points from arena java applet. Maybe the issue persists only in browsers.
You are right, everything is fine in the applet. I assumed it was no longer available, since all links from the new webpage lead to the browser version of Arena. (And indeed, the only way I could find the applet now is to google for it).
The main and the only issue in arena is its existence.
Too many downvotes.
How to do Div 2 1000 ?
OK I'll take a stab at showing my thought process. I got it accepted.. after the contest naturally :-(
Let n = |s|
Because n <= 300, the worst we can shoot for is O(n^3)
So we can't do a recurrence based on a function like:
f(x,y,p,c) = max claps,
........if robot is at (x,y), and
........at position p in the program, and
........c allowed changes are remaining
Because that would be O(n^4), even worse since x,y can be -300..300 (yes, yes it's still O(n^4).. you know what I mean).
So I tried for a recurrence based on this:
f(p,c) = max claps if robot is at the origin, and
........the program is at position p in the program, and
........c changes are remaining.
With that definition of f, we want to know f(0, changesAllowed).
Basically the problem boils down to, what is the maximum number of contiguous substrings we can split up "s" into, such that each substring returns robot to (0,0).
To know f(p,c) consider a substring of the program from [p..q]. The robot is at (0,0) now and suppose with "t" changes we can make that substring return the robot to (0,0). Then we can check 1+f(q+1,c-t).
Thus we can check
result=0;
for (q = p; q < n; q++)
if (s[p..q] can be returned to origin with t changes && t <= c)
result = max(result, 1+f(q+1, c-t));
With memoization, this recurrence has n^2 states. If you can do the loop in O(n) then the runtime is enough. To do the loop in O(n) you need to be able to compute the vertical/horizontal delta of the program substring s[p..q] in O(1) time, which can be done with some precomputed arrays or, as I later saw some smarter people do, just by keeping track of the count of U,D,L,R chars as you iterate the above loop.
I got everything above in the contest except I couldn't nail down the condition in the if() statement above, which is the actual movement logic of the blasted robot with the allowed changes. First, the substring s[p..q] needs to be even in length. Second, by adding up the U,D,L,R in s[p..q] then |U-D|+|L-R| is the manhattan distance M of the robot from the origin. To bring him back to the origin, you need to be able to change at least M/2 characters, so finally, you need (|U-D|+|L-R|)/2 <= c in order to continue the recurrence with this q.
To see this last part, consider that any string like "DL" can be turned into either "RL" or "DU", i.e. by changing half the letters we can bring him back to (0,0).
Sorry, I don't know how to write short.
Thanks , Got it ! :)
How to solve Div1 300?
Make a depth-first search for each starting node and try to reach a depth of 4. Obviously you have to remember the nodes of your current path, so that you don't visit a node twice.
Hey,
I tried solving it with DFS and must've implemented it wrong. I tried looking through some solutions in the arena but they're all different solutions, that I'll also take a look at, but it would be cool to see a correctly implemented DFS solution to this problem. Could you link me to yours/someone else's?
Cheers!
You can see this beautiful solution : http://www.topcoder.com/stat?c=problem_solution&rd=16652&pm=14162&cr=23311400
Great thank you!
I see I forgot an important line in making the vertex unvisited after searching all existing paths through it.
Thank you!
I solved it this way:
If there were n-1 edges, check if the diameter of the tree is >= 4
If there were n edges, delete each edge one by one and check diameter
Else, if there are more than n edges there will always be a path of length 4
There are simpler solutions .-. I completely overthought the problem
Why do you need to remove each edge and check diameter if there are total n edges? As long as there are >=5 nodes and >=n edges, won't there always be a path of length 5? This means that there is at least one cycle in the graph. If there's a cycle of length >=5, that is itself the desired path. If there's a cycle of length 4, there is at least one other vertex connected to some member of the cycle, giving us the 5 nodes of the path. If there's a cycle of length 3, there are at least two other vertices connected to either same member of the cycle or different members, giving us the 5 nodes of the path in this case.
UPD: I missed one case. eg. There are 5 nodes, with edges 0-1, 1-2, 2-0, 2-3 and 2-4.
It's called color coding. Let k = 5.
(1) Assign one of k "colors" uniformly at random to each vertex. (2) Check if there is a simple path of length k with distinct colors (it can be solved in O(2^k * E) using a simple bitmask DP) (3) Repeat the above process sufficient number of times.
In each iteration, the probability of success is k! / (k^k) ~ 1 / e^k, so we need to repeat it O(e^k) times. In total the problem can be solved in O((2e)^k * E).
You need to choose a pair of edges (a, b) and (c, d) such that b and c are adjacent and there is an edge from a to some vertex e such that e != b, e != c, e != d. If the degree of a is greater than 3, it's always possible, otherwise check all neighbours of a.
The solution with bitsets: let's iterate over (x, y) the second and the fourth vertices. Now we can check if they have common vertex by ANDing their bitsets (g[x] & g[y]).count() > 0. And the last thing that we should check that the degrees of vertices x, y are at least 2. The only bad case that we should not count when degree[x] = degree[y] = (g[x] & g[y]).count() = 2.
Another approach: there are K edges (K <= 2000), so you can compute all 3-point segments in O(K^2). Each segment is like this:
(End node 1) — (Mid node) — (End node 2).
For each segment, I had to check if there is a segment such that [end node 1 or 2] is end point, but the other nodes are different from original.
Iterating over segments vector, I computed how many times node x is end and node y appears (used count[N][N]). Also, saved how many times node x is end (used freq[N]). After that, just checked for each segment if freq[end_1] >= count[end_1][mid] + count[end_1][end_2]. Note '>=' is because original segment was counted twice.
I just wrote five nested loops which clearly have a coding-deep-at-night look. They perform just like the simple recursive search mentioned above. The complexity is perhaps O(n2) on a connected graph: the graphs for which the answer is
:(
are very restricted, and otherwise, an answer is easy to find.ffao showed a simple proof that the complexity is O(edges^2) — his comment
Thanks for the link! That's neat and concise.
It's bad idea to write a contest at 5 am. Submitted easy for 247 points, opened medium and a minute later realized that I have a bug. Fixed it, lost ~50 points. And it turned out that I fixed it wrong. And medium was too easy. The solution is so obvious. You have to merge everything except leaves and 1 or 2 vertices on a cycle. For quite a long time I was thinking: "Where's the catch? This is too easy to be right. So why is it wrong?" I rechecked everything and didn't manage to find any flaws, so I wrote it being sure that it will fail. And in the end it passed and the problem I was sure about failed :(
When I was trying to challenge div1 300 of people in my room I was getting a request timed out error.
It is my first time to compete in Div1 and got ...0 marks,haha I found the bug of my solution in 250 and 500 in the last 3 minutes and solve the first bug ~5 second after the coding phase. So sad
Interesting. After finding the first bug why didn't you correct it instead of searching for a bug in the second problem?
I am using adj matrix in the first problem, in the beginning I feel it should be okay, after I finished the second one I found only ~30% people in my room finished the first two. You know, it is not a good feeling haha I know I am not that good. I am trying to resubmit my first first using adjlist and DFS, and during that time I found I ignore the circle case in the second problem. So... that's it, but at least a good experience!
There was useful page "Competition history" in old TC site. Now I can't find it. Instead of it there are only page "Past SRM". I tried to understand in which order SRM are sorting there, but the only reasonable variant is "in order the database gives it". Is there now some normal way to see statistics?
Is this one fine?
Nice) Thanks.
Should a dfs starting at each node pass for Div 1 300? My intuition tells me that this should TLE, (and I think a lot of people did fail), but I couldn't come up with a test to make it fail during the contest.
My solution instead was to consider a given vertex and do casework with the vertices at distance at most 2 from it. This is O(n2), as the number of triples (a, b, c) with a connected to b connected to c is [ \sum_{v} 2\binom{\deg v}{2}\le O(\binom{E}{2})=O(E^2) ] by convexity.
What is this 30% unused code rule? Will it be applicable for upcoming contests also?