chrome's blog

Topcoder Single Round Match 682
By chrome, history, 8 years ago, translation, In English

Hi there!

In a few hours, at 05:00 MSK will be held Topcoder SRM 682.

Let's discuss problems after contest!

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

»
8 years ago, # |
  Vote: I like it -18 Vote: I do not like it

It will be my first time to participate, The arena looks exciting :)

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

    It will look terrifying soon enough :D

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

      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.

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

        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.

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

        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.

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

          1. https://www.topcoder.com/tc?module=ProblemArchive

          2. 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.

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

            1. problemSOLVING — I want to see you submit on that page

            2. 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

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

              Once you install Greed, it goes way better. This is what my opinion is.

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

        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.

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

          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.

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

            I just tested it again, by writing the following solution for problem "YetAnotherTwoTeamsProblem":

            #include <vector>
using namespace std;
class YetAnotherTwoTeamsProblem
{
    public:
    long long count(vector<int> skill)
    {
        return 0;
    }
};

            Pressing "Compile" shows me the following:

            Your code compiled successfully, but generated warnings:
Standard Error:
In file included from top level:3:0:
YetAnotherTwoTeamsProblem.cc:6:15: warning: unused parameter 'skill' [-Wunused-parameter]
long long count(vector<int> skill)
^

            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:

            #include <vector>
using namespace std;
class YetAnotherTwoTeamsProblem
{
    public:
    #pragma GCC diagnostic ignored "-Wunused-parameter"
    long long count(vector<int> skill)
    {
        return 0;
    }
};
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it +11 Vote: I do not like it

              Just submitted your first code for 997.65 points from arena java applet. Maybe the issue persists only in browsers.

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

                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).

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

        The main and the only issue in arena is its existence.

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

        Too many downvotes.

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

How to do Div 2 1000 ?

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

    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.

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

How to solve Div1 300?

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

    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.

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

      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!

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

    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

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

      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.

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

    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).

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

    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.

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

    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.

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

    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.

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

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it -20 Vote: I do not like it

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 :(

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

When I was trying to challenge div1 300 of people in my room I was getting a request timed out error.

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

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

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

    Interesting. After finding the first bug why didn't you correct it instead of searching for a bug in the second problem?

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

      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!

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

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?

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

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.

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

What is this 30% unused code rule? Will it be applicable for upcoming contests also?

→ Reply