vovuh's blog

Codeforces Round #374 (Div. 2)
By vovuh, history, 8 years ago, translation, In English

Hello, Codeforces!

30th September 2016 at 17:05 MSK Codeforces Round #374 (Div. 2) will take place for second division participants. Traditionally, participants from the first division will be able to join out of competition. Please, notice that the start time is unusual.

This is my second Codeforces round, I tried to make problems interesting for everyone, so I recommend to read all problems statements! I hope that everyone will find something new and interesting. I wish lots of accepted runs and higher rating to all participants.

I want to thank Michael MikeMirzayanov Mirzayanov for wonderful platforms Polygon and Codeforces, and for help in preparing the problems, my best friends Danil danilka.pro Sagunov also for help in preparing the round and Ivan BledDest Androsov for testing the problems.

Participants will be given five tasks and two hours for solve them. Scoring system will be announced traditionally closer to round start. :)

The scoring is almost the standard: 500-1000-1500-2000-2750

UPD: Editorial

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

Comments Comments (246)
| Write comment?
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

30 September

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

Unfortunately, this round will be conflict with Jordan-cpc :/

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

I am loving the that timing is being rotated around! It unfortunately makes a lot of people unhappy but I think it is still a great opportunity for people in different time zones, so nobody misses out.

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

"Unusual" is the new usual.

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

wish to see a programming contest not a hacking contest :D

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

    I think hacking contest is interesting~

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

      I know that you believe that you understand what you think he said, but I am not sure you realize that what you read is not what he meant.

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

      but there is no hack in the programming competitions like ICPC or IOI

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

    I think some pretests are little bit weak :<

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

      the pretest of the last 4 or 5 contests were too weak

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

        pretests must be weak, then someone can hack!

        but I think it should be strong enough to not see somebody hacks about 15 people on one problem!

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

          the pretest of problem A and B should be stronger~

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

          there is someone hacked 16 people on problem A last contest

          he took points like the points on problem E :\

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

    if you hack a person once, you would not say this again =)

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

bad round PS : one of my friend has comment it when we has class, sorry author :((

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

one's day may be night for others. so we should appreciate this "unusual" time.

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

my best friens Danil danilka.pro Sagunov also for help in preparing the round

what does "friens" mean??

UPD: fixed.

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

good luck

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

salam

are problems sorted in order of their difficulty?

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

    Usually they do, but it is still recommended to read all the problems, just in case.

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

Why Kotlin is not allowed in this round? It seems to be the only language missing compared to rounds 371-373. Edit: In the end system accepted Kotlin submissions too.

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

Round 374.
374 = 2 × 11 × 17 , Sphenic Number

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

I hope the platform will be stable today. Currently there are 7+ pages of pending submissions....

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

The judge queue of practice problems is very very very long now. I hope this issue will be resolved soon and have no impact on this round.

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

    In my opinion, the active contest should have significantly higher priority on the queue than practice.

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

      In my opinion, there should be more servers for running the submissions. And to make things better, the machines should be Linux so that it can produce more exact execution time, instead of "15ms" on Windows.

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

Hit like if you think your rate will be increased today :v

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

    then Hit Like if you think your rate will be decreased today :v

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

      An old trick for getting upvote , stop it or you will get downvotes again!

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

I hope that I have become better.

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

Score distribution ?

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

Auto comment: topic has been updated by danilka.pro (previous revision, new revision, compare).

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

After reinstalling windows, I am unable hack in firefox.

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

the cool trick in div2 A is that you shouldn't test all samples on your code :v

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

Quick question, if I can't get pretests passed for anything I submitted, I'm still eligible for rating drop, right?

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

So codeforces allows submit the same code now?

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

    That apparently counted as resubmitting twice... Isn't that a bit of a problem?

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

    I think you will get 50 point penalty for resubmitting.

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

    if you click on submit button several times, your solution submit several time (your picture show us you did it). but if you submit a code and after your code passed the queue, you try again to submit the same code, your solution can't submit.

    sry 4 my bad english

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

Div2B hack?

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

    There could be multiple occurrences of the same string in list of passwords, that are same as actual password. Some people did not handle that. My own solution does not handle it.

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

      they are pairwise distinct though, no?

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

        Maybe not. Problem statement did not look clear. The last line says "It is guaranteed that the Vanya's Codehorses password is equal to some of his n passwords."

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

      The next n lines contains passwords, one per line — pairwise distinct non-empty strings consisting of latin letters and digits.

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

      "pairwise distinct non-empty strings consisting of latin letters and digits."

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

      The statement has said "pairwise distinct non-empty strings"

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

      Its written passwords are distinct

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

      Why did you resubmit Div2 C? I saw that most of the people used ~100 MB memory which means a 2d dp state. How did you solve it?

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

        I had done wrongly thought Dijkstra on {cities not visited, time} could work. It took me a lot of time to realise I was wrong.

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

          What is the problem with that solution?, I could not get the mistake. I did a dijkstra from n to 1, and then a dp from 1, trying to search what is the higher depth of the graph.

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

      But it is mentioned that the strings will be pairwise distinct & non-empty.

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

Nice contest.. Anyone can tell me how to solve problem D??

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

    First, if the amount of negative numbers is even, we want to make it odd. So we pick the number with smallest absolute value and apply operation until it's signal is swapped (sometimes we don't have enough operations but it doesn't matter, just keep trying until the signal is swapped or until you don't have more operations).

    Then, we simulate the process. While we can apply operation at least one more time, we apply it to the number with smallest absolute value at each step, raising its absolute value. We can use a priority queue to simulate this. Turn all numbers into positive numbers and store the signal separatedly, so it's easier to work with the priority queue.

    Then, after we used all available operations, we push the results to an array and print the answer.

    This solution is correct because it is possible to prove that for any set S with only positive numbers, if we can increase any number by K, the total product is maximized if we always pick the smallest one.

    Code: http://codeforces.me/contest/721/submission/21037453

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

      Can you prove that why choose smallest abs value and apply opration on it in first step is true ??

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

        Because if we pick the smallest abs number, we will waste a minimum number of operations to swap its signal. These operations will only reduce the abs value of our product or increase it by a smaller value than if we used the operation to increase other value, so we dont want to do a lot of these operations because we want to maximize the abs product (and have an odd amount of negative numbers so the signal of the product is negative and then the total product is the minimum)

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

        Consider that you have two elements ai and aj, |ai| < |aj|. Let m be the smallest number of operations required to change the sign of aj. If you apply them to aj, you will get two numbers, ai and new aj, and now |aj| (the new one)  = m·x - |aj|. If you apply all those m operations to ai instead (there might be some better ways, but let's consider this), there will be new ai: |ai| (the new one)  = m·x - |ai|, and aj will remain unchanged. |aj| > |ai|, m·x - |ai| > m·x - |aj|, and you need to maximize the absolute value of product, so you get a worse situation if you change an element with non-minimum absolute value.

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

      But let's say we have the numbers -2 and 1, an x=4 and t=2 Then by your algorith we wouldn't do anything and leave the product as -2. But we could actually add 4 to the first one and subtract 4 from the second one and get the product 2*(-3)=-6, which is smaller What is wrong in my logic?

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

How to solve C guys?

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

    d[j][i] = minimal cost to visit j verticles with and last vertex i.
    P.S. I had to keep only previous state to fit it in the memory limit.

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

    I used dp and dfs to get the maximum number of visited showplaces before visiting showplace i under time T. Then reconstruct the route using backtrack or without backtracking.

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

Is there a special algorithm to do C? I kept getting time limit with a breadth and depth first search.

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

    I was on the same boat for a while. The trick (for me, at least) was topological sorting.

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

      So that's what it was. I've only done a few topological sorting problems so I guess that's why I didn't notice it.

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it
    1. Do a topological sort of vertices.
    2. For each vertex (in a topological order) calculate minCost[v][pathLength + 1] = minCost[parent][pathLength] + timeToTravelFrom[parent][v] and save where you came from previousVertex[v][pathLength] = parent.

    pathLength is the number of vertices on some path from vertex 1 to the current vertex v. Among all the possible paths from 1 to v which have pathLength vertices between them, there exists the shortest path. We track the cost of that path here minCost[v][pathLength + 1].

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

      Can you clarify your answer regarding nodes which have multiple parents? If we just loop through all parents of a node and all pathlengths, we get O(n^2 * m). This would be similar to my solution, which barely passed the time limit after contest. Other people have solved it way faster and I'm trying to figure out how...

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

        Sure.

        Let's consider, for example, a DAG with 6 vertices: v1, v2, v3, v4, v5, v6.
        The goal is to arrange all vertices in layers or floors. Let's stick to floors.
        Imagine there is a 6-storey building:
        [ floor 6 ]
        [ floor 5 ]
        [ floor 4 ]
        [ floor 3 ]
        [ floor 2 ]
        [ floor 1 ]

        Floors somehow (we don't know yet how) correspond to vertices in a graph. We only know the identity of 2 vertices: v1 is [ floor 1 ] and v6 is [ floor 6 ], because we always gain access to all of the verices in a graph from vertex v1 (we always gain access to the floors of a building through the first floor) and we end our travel in a graph in vertex v6 (we cannot move further up from the floor 6).
        Now, we base our decisions about correspondance of vertices v2, v3, v4, v5 and floors on the fact that if v2 is some [ floor i] then all of the outgoing edges from v2 should point to higher floors. That is, once we are on the [ floor 4 ], the floors [ floor 1 ], [ floor 2 ], [ floor 3 ] become blocked for us — we cannot move to these floors from the current [ floor 4 ] by using outgoing edges of current vertex.

        At first we have some unordered set of vertices {1, 2, 3, 4, 5, 6}. Then we use topological sort to create an ordered set of vertices with the specified property (we cannot move down from higher floors). Formally, topological sort is a map:
        {1, 2, 3, 4, 5, 6} (1, 4, 2, 3, 5, 6).

        Below is a graphical representation of that mapping ( topological sort ).

        The distinctive property of the picture from the right is that all of the edges are looking to the right. None of the edges look to the left (backwards). Not a single child is pointing to a parent. That means, when you reach vertex v[i] as you go from left to right, there is no way you can update the state of v[i] later as you continue moving to the right.

        Actually, the graph on the right is an abstract representation of the concept of dynamic programming. We consider sequence of vertices 1 → 4 → 2 → 3 → 5 → 6 in the specified order. When we are standing on the vertex v[i] it has optimal property (in our case time to travel to that vertex). We update from that vertex v[i] all of it's children. The next vertex in a sequence after v[i] now also has optimal property, because it was updated by parents which had optimal property themselves.

        All of that brings us to a conclusion that after we do topological sort we can just look into each of 10 edges (only once) in the following order:

        1. 1 → 4
        2. 1 → 2
        3. 4 → 2
        4. 4 → 3
        5. 2 → 3
        6. 2 → 5
        7. 2 → 6
        8. 3 → 5
        9. 3 → 6
        10. 5 → 6
        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          We have 2 ways of reaching node 2 in your example:

          A: Via 3 nodes, cost 7
B: Via 2 nodes, cost 3

          Why is it sufficient to process node 2 only once? We can't know yet whether route A or route B will be part of the final answer, so don't we have to accommodate both possibilities? Like this:

          1. 1 -> 4
2. 1 -> 2
3. 4 -> 2
4. 4 -> 3
5A. 2 -> 3
5B. 2 -> 3
6A. 2 -> 5
6B. 2 -> 5
7A. 2 -> 6
7B. 2 -> 6
8A. 3 -> 5
8B. 3 -> 5
...etc...
          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Good question. Do not stop asking until you fully and completely understand.

            The node 2 is updated twice.

            The first time it was updated on the step 2: 1 → 2.
            During that step we updated our estimate of time to travel to that node from ∞ to 3. It is important to understand that the time 3 is the best time to travel from node 1. We cannot get better than that.

            The second time we try to update it again on the step 3: 4 → 2. This time we will not update our estimate with number 5 + 2 = 7, because the previous update was better. But again, the time 7 is the best time to travel from node 4. We can only improve that number if we reduce the time to travel to node 4. But we cannot reduce that time, because there are no backward edges pointing to node 4 and we have already explored all of the edged coming inside node 4 and updated it's state.

            The general pattern here is following. We only use edge u → v if we are 100% sure about the optimality of vertex u. That is, we have to consider all of the edges coming into u before we start looking at the edges coming out of the node u.

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

              Thanks for your help. Your illustration of topological sorting is very nice. However, I don't think your solution works. "The second time we try to update it again on the step 3: 4 → 2. This time we will not update our estimate with number 5 + 2 = 7, because the previous update was better." If I understood you correctly, you mean we would forget about the 7 cost path because the path with cost 4 is cheaper? It's not correct. For example, if T=1000, then the optimal path will visit all 6 nodes (including the 7 cost path 1->4->2).

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

                I was asnwering your question regarding the complexity O(n2 × m).

                That is, I showed how we can find the shortest path in a Directed Acyclic Graph with complexity O(n + m) (which is better than O(n × m)). We managed to reduce the complexity by doing topological sort.

                We can use the same strategy in the original problem to reduce the complexity from O(n2 × m) to O(n2 + m).
                There is one more idea remaining on top of what I have already described.

                Let's concentrate on some vertex v[i]. There is a set of different paths from vertex v[1] leading to v[i].

                Now, as it is drawn in the picture, we split the set of all possible Paths from vertex v[1] to vertex v[i] into groups (disjoint subsets).
                Within each of those groups we will be performing comparison of travel times of those paths and look for a path with a minimum travel time. I've circled the minimum cost path in a group with red.

                In the worst case there are 5000 different path lengths (not paths!) from v[1] to v[i], because the maximum number of vertices in a graph is 5000 and we cannot make a path with repeating vertices.

                So, for each vertex we will be storing an array of minimum cost paths to that vertex:

                int minCost[5000][5000];

                The number minCost[i][5] stores the minimum time to travel from v[1] to vertex v[i]. But it is not NOT among all the possible paths, it is only among the paths in the group 5 (paths of length 5).

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

                  Nicely illustrated again, but I feel like you are describing my slow solution:

                  for each node in topological order:
    for each v in minCost[node][v]:
        for each outoing edge in node:
                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  ← Rev. 2   Vote: I like it +5 Vote: I do not like it

                  Ok, you've sowed a seed of doubt =)

                  I wanted to solve this problem after a week or two (when I forget the problem and the solution), but here we go...

                  The solution that I described: 21115101

                  Feel free to ask any questions about the code.

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

                  I can see your solution passed in 93ms, but I can't figure out how. You even have those 3 nested loops:

                  while (!sortedVertices.empty())
  for (childV : g[curV])
    for pathLength = 0 -> n-1

                  The outer-most loop is 5000 worst case. The middle loop is 5000 worst case. The inner loop is 5000 worst case. How does this not lead to 5000^3?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 years ago, # ^ |
                  ← Rev. 3   Vote: I like it +5 Vote: I do not like it
                  • The string of code
                  while (!sortedVertices.empty())

                  gives us the complexity O(n).

                  • The following string of code
                  for (int pathLength = 0; pathLength < n - 1; pathLength++)

                  increases our complexity to O(n2).

                  • And this string of code
                  for (auto childV : g[curV])

                  does not multiply the complexity O(n2) to make O(n2 × m). This loop adds to the outer loop (which gives O(n + m)) and multiplies inner-most loop (which gives O(n × m)).

                  If we combine them, we get the complexity O((n + m) × n) = O(n2 + n × m).

                  Edit:

                  No, I am wrong. The following lines (both of them together)

                  while (!sortedVertices.empty())
   for (auto childV : g[curV])

                  give us complexity O(m) — we touch each edge only once.

                  When we add inner-most loop we get total complexity of order O(n × m).

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

                  Thanks! Now that you put it like that, it's obvious the complexity is O(n x m). Problem now is I have the same 3 nested loops in my solution, and with a ton of optimizations that code is still running for 3000ms. You probably don't want to scour through this, but I'll link it for reference in any case:

                  http://codeforces.me/contest/721/submission/21047724

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

                  Insert the counter in your code and calculate how many loops the code does.

                  The worst time is achieved on case #59. It starts with these 3 numbers:
                  3615 4935 245435090

                  So, you need to print the amount of loops when you encounter that case:

                  if (n == 3615 && m == 4935 && maxTotalCost == 245435090)
{
  io.print(performanceCounter);
  return 0;
}

                  Your code will fail and you will see in the result how many times the inner-most loop was executed.

                  Here is my result: 21118607

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

                  Your code made 17M iterations, mine did 3M. And yours is 30x faster somehow.

                  http://codeforces.me/contest/721/submission/21168815

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

                  That means the problem is not in the algorithm.
                  The problem is either in the data structures (probably, collisions in HashMap) or in the input. I doubt that input is bottleneck, because in its maximum it is just about 1500 numbers.

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

                  Weird thing is I'm only putting longs and integers into the maps and there is a Java solution to this problem which also uses HashMaps and runs in 200ms.

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

                  Look at the cases #8, #9, #10. They both have the maximum possible input and your solution works in 150 ms!

                  But something interesting happens in the case #12. It is not the hugest input. Just 1686 vertices and 4331 edges, but it makes your solution go over 1 second.

                  On the case #10 the program does only 29611 operations and it takes 140ms to perform them.
                  The case #12 takes 2237322 operations and the times blows up to 1076ms.

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

                  Look at this: 21172009

                  17835090 operations and only 265ms!

                  The only difference I see is that there are no HashMaps and no TreeMaps.

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

                  Thanks for your help. There are HashMap-based solutions which perform in 200ms, so it's still unclear to me what exactly makes my solution slow, but I feel like it may not be worth pursuing further.

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

      Pixar,

      I have done step 2 of your solution using recursion. Can you please explain why step 1 (topological sort) is necessary?

      Basically, I define a recursive DFS (vertex1, N, time) which stores number of vertices covered and time taken; and call DFS(1,n,T).

      My code — CODE gives TLE on test case 11, although I guess DFS algorithm in itself is not exponential time?

      Any idea why this might be happening?

      Thanks in advance.

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

        We need to know the order in which to process the sequence of vertices. Searching for the right order is called sorting.

        Now, what is right order? For us the right order is the situation when we finish processing children of vertex v[i], the next vertex in our order v[i + 1] has the cost (time to travel) which cannot be improved.

        What does it mean to improve the cost of the vertex? That means we have found some parent vertex from which we can reach the current vertex by using a smaller cost.
        Well, the whole algorithm is a continuous reevaluation of our estimates of the times to travel to each vertex. After each evaluation we reduce our estimates. At first we say that each vertex in a graph has very big cost. On each pass of our algorithm we do these reevaluations of the costs. We reduce and reduce until our estimate becomes the real minimum cost.

        How many times should reevaluation of the estimate cost happen?
        Let's take some vertex vk. For example, it has 3 parent vertices: v1, v2, v3. Then we will do the reevaluation of the cost only 3 times!
        On some step of our algorithm we become sure that we cannot improve the estimate of the cost to travel to v1. At that moment, we update estimate of child vertex vk.
        On some other step of the algorithm we become sure in the estimate of v2. Then we do the second update of the state of the vertex vk.
        And situation repeats for the vertex v3.

        If we have processed all of the parents v1, v2, v3 of the vertex vk, there is no way we could ever improve the estimate of the vertex vk! Why? Because there are no more vertices left which lead to vk and we can only improve the estimate of the cost of vk from vertices leading to vk. What does this mean for vk? It means that vk itself became optimal and we can update the estimates of the children of vk.

        • I don't think it is possible to solve this problem using DFS.
        • The complexity of DFS is O(n + m).

        I was wrong regarding the impossibility to solve it with DFS. Here is the solution with DFS.

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

I just hope 2d dimensional dp for both path parent and cost in Div2C doesn't give memory limit exceed on Div2C. It was pretty close on sample tests :|

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

    I did 2d dp where a[i][j] is the minimum time to get to i after visiting j nodes in O(n*m). If I understand what you did it is O(n*t). That will get TLE on some possible cases.

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

Did someone experience problem with lack of memory in Div2C?
This is the first time it happened to me.

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

    Yeah. The cost dp could be reduced to 2*N array though and that will decrease the memory by half.

    However i just tried to reduce the path storing one to unsigned short o.O But not sure whether it will pass in main tests.

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

      Me too. But it wasn't necessary to store that much memory. Use map instead of arrays as there are only 5000 edges.

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

        @rachitjain I used map instead of array to store my dp states but it still gave mem limit exceeded on test case 11. Then I have to change my dp state from 2-d to 1-d. I think it will give a TLE in main tests.(fingers crossed)

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

    I did, could have probably optimized memory complexity but I chose to just make stuff shorts instead of long longs and ints.

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

    I solved it using int dp[5000][5000][2] and it didn't give me MLE

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

I would have had a successful hack if the contest had 5 more seconds :(.I have already written and copied the hacking input when the time was out.

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

I was surprised that so many people solved C

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

Pretests in div2 B are weak because i didnt increment time by 5 sec due to typo error still pretests passed. hope my final solution passes

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

what's an unexpected verdict?

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

I wonder if this solution for Div2E is correct... I finished the debugging minutes after the contest and I have no idea if it would fail on test case 12 again.

http://pastebin.com/AJ7HrMF6

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

Hhmmm...

seems odd

dkjsfkhg accepted C and D at 1:58 and 1:59.

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

    D was already submitted before and the passed solution differs from the past solution (Which got wrong on answer on 6) only in one line which is an 'abs' function. Of course it is easy to change a single line of your code in a minute.

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

      see? you got WA on C, told you that's odd.

      I believe you thought that I'm saying that you have cheated, but that wasn't what I meant, actually I meant(amazing-intresting) by "odd", sorry for my bad English.

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

      Now it's really ODD.

      all your submissions were skipped :|

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

could anyone explain why the following code fails (TLE)? 21035958

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

In the last three contest Div 2C is a DP problem...

Seems like its time to start practicing DP

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

    DP is a great concept and I think it fits nicely into Codeforces rounds

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

I really liked the problemset. Solved D, but submitted 1-2 seconds after the contest ended. It would've been the first D I solved on a contest. Anyways, I hope everyone did well and more importantly had fun. Now just to wait for system testing :)

Also, what was the idea behind C, DFS got TLE. Seems like it's DP but I can't think of a formula.

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

    dp[i][j] is min time to get to i after visit j node,and it will get MLE if you use long long

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

    a guy in my room use DFS but he had passed the pretests

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

      I thought I solved C with DFS, but then I realized I missed something and it added a lot to my time complexity after I fixed it. Before I started thinking of optimizations, I switched to D, but I'm sure there are optimizations that make DFS possible.

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

    I use BFS to solve this problem by DP. First get TL using long long, then changed it to int and check not to use times bigger than T. Hope it's right solution.

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

    21049347 is my solution using DFS and it's Accepted, after the contest though :(

    Let me know if you have any doubts :)

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

      Hey nice implementation, i actually wanted to confirm one thing.. The line where you check

      if (path_data[a][visited].second > cost) path_data[a][visited] = mp(cur_parent,cost);

      You acted greedy here right ?? As in if at the current node the path length encountered already exists but with a greater cost and we have a lesser cost in hand at current, then update this with the current {parent,cost} pair as this can further lead to a greater path length. Am i right?? If not please clarify..

      Thanks :)

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

        Yes, it was a greedy step. Actually due to that step, I'm unable to calculate how much improvement I made in the time complexity. Attempted but couldn't prove it :( I'm still a beginner. Space complexity : O(n^2)
        Glad to know that you found my solution helpful :)

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

PTs for Div.2B are really weak.I was so foolish that I locked it before making hack data.Then i found that i can hack myself...

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

    What was the hack?

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

      Just a simple case. 7 2 a b cd dc abc acd acc acc

      and the ans:15 22 good luck..

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

    So as Div2D... I just realized I made a very, very foolish mistake.

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

      Are there any of us that didn't handle negative test cases?;D

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

I feel so frustrated again because of not solving the C problem. During the contest, I did not have any thought about DP, I used only DFS...

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

My B solution got hacked, What would be the problem with that code? http://codeforces.me/contest/721/submission/21032401

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

    you should get the sum of cnt[1~len-1],rather than count one by one.

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

      Can you explain a little bit more please?

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

        You divide every cnt with m and divide by 5, so for: 5 4 a b ab cd abc abc

        You will get no periods of 5seconds, even though you have to test 4 wrong passwords before the right one.

        Instead, you should've done ((cnt[1]+cnt[2])/m)*5+cnt[1]+cnt[2]

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

        get the sum of cnt[1~len-1], and the min ans is sum + 1 + (sum / m * 5),it should not get every cnt[i] / m * 5.

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

    Here's a hack case for your code.

    6 3 ab ac abc abd abcd abcf abcd

    The 5 sec pause that happens after k tries should be calculated globaly, but you are calculating it inside of the loop, and you get inaccurate results when the division isn't exact (in this case the count of sz[2], sz[3] and sz[4] is 2, and k=3, so the division always returns 0, but if you calculate it globally, it would be (6-1)/2 = 1 pause)

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

Expecting lots of hacks(System testing failure) on 2nd question. No pretest to bound best part of question passwords

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

hacking test case of B is very interesting, but not many people see it, so we don't see hack war :D(like 373)

PS : I will get WA on B because that. That is so sad

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

    I realised my solution way too late. At 1:34 from the start of contest, I realised I fucked up and then hacked one too.

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

How would O(N^2logN) gets TLE in 3 sec, problem C -_-

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

    that's about 3*10^8 repetitions, you should never have that many.

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

      it got AC now with a little more optimization but still O(N^2logN) 21043948

      very strict TL -_-

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

        I think the intended solution is O(nm)

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

    solved C with Dijkstra , it took 623 ms

    better check your code

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

I see about 1100 people passed pretest on C but about 600 accepted, why ??

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

    Because of DP

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

    Wow, I got WA on TC 66 because of integer overflow.

    To get AC, I changed a > b + c to a - b > c (where a, b, c are distance and dp values)

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

    Graph-related problems lead to tricky cases quite often. We've also seen lots of lots of failed attempts (including myself TUT) in a recent problem (715B - Complete The Graph). (Making these test data also requires great care and patience IMO so let's thank the preparers and hackers :P)

    I got WA on test 63 for starting the topological process with vertex 1 instead of all vertices with zero incoming edges... Somehow interesting that it can still make its way through such a large part of system tests.

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

http://codeforces.me/contest/721/submission/21030275 Memory Limit exceeded in 33 test case ... :| I saw some solutions with similiar limits ... unfair !

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

    Actually, It's fair because your bfs() add a lot of unnecessary vertexs.

    You should just add a vertex u when all the vertex which can go to u have already been added.

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

    you should use priority_queue instead of queue , your code is about O(n^3)

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

wrote a generalised soln for div 2 C ( maximum nodes which can be covered starting from 1 ) until after contest when i read the output statement of question ( path has to end at n ) !

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

    please do not use "bad" words in your comments.

    my country bans the sites with bad words and then we can only reach these sites by changing our IP address and that's not easy for us.

    thank you for your observance.

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

      sorry brother , updated my comment didn't know that your country follows such strict policies .

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

This code gives me the correct answer in my computer. But it is wrong in their machine.

Can anyone tell me what is the reason behind this??

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

    You should not use cin and getchar/scanf when ios::sync_with_stdio(false) is being used.

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

      Why it is bad? And when i should use this code?

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

I received a really strange Runtime Error on problem B and am not able to identify the reason.

What is wrong here? 21044715

I suspect the error is on the first sort after playing with the answers that Codeforces give me.

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

    Comparing function in std::sort must be written in such a way that if a < b is true, then b < a is false. And in your code, if strings a and b are both different form the right password, but their sizes are equal, then a < b and b < a. That's why it's RE

    Try changing true to false in the last line of comparing function, I think this will work.

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

      Yes, it worked.

      So we may have a < b and b < a being both false, but we can't have a < b and b < a being both true. Is this correct?

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

        Yes in the first case sort will think that a = b.

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

          I see. Thanks a lot for the help!

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

        Yes. If a < b and b < a are both false, then it just means that a = b for this comparing function.

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

          I see. Thanks a lot for the help!

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

Is something is wrong with the ratings? I think all three should be "Became Candidate Master"

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

    This bug takes place when the ratings have just been updated, however, five minutes later, the bug gets automatically resolved. This is just a minor rating to color mapping bug.

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

Wonder! I noticed the solving time of problem a of rank 1 holder in standing(he is from div1). How is it possible to read problem description and write such long code only within 1 minute !! His code

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

    Perhaps it's because he's familiar with crosswords from his own country (just geuessing XD)

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

    the logic portion is only the 'solve()' function. Everything else was prewritten.

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

Auto comment: topic has been updated by vovuh (previous revision, new revision, compare).

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

Why this code gives http://codeforces.me/contest/721/submission/21026545 gives runtime error while http://codeforces.me/contest/721/submission/21044409 gives accepted. The only difference between the two codes is that i am using comparator function for sorting the strings in non-decreasing order of length in 1st code

comparator function

Can someone help what is the problem when i am using the above comparator function and thus causing the runtime error ?

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

In problem C, I took the maximum number as 10^9 and got Runtime error case 66, Now submitted the same code with value 10^9+1. Got Accepted. Why am I so stupid ? -_-

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

I got Skipped, can you tell me why ?

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

kudos to the author for the awesome contest, where even 4th question was well in reach! looking forward to more rounds from your side @vovuh

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

Hello , Can someone solve some of my doubts!
My solution 21045986 passes even though the first line of my loop( while(K--) ) has a pair < int , int > which can obviously overflow(first element is the element of the array) and I resubmitted it after changing it to pair < long long , int > and got AC. But to my surprise this submission also gets AC(I don't get why ) . Can someone explain?

Moreover is there some compiler flag which I can use to warn me whenever I try to typecast a data type to other which can cause data loss?

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

    Actually, you never use the value of x.first in the loop, so your solution works even if the value you assign to it is greater that int type can store.

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

      Oh Okay I get it , I wish I never saw this :D . BTW can you answer the second question?

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

66 test cases of a problem and the one your code gets WA on, 66

Life is hard

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

why so serious to down vote my comments !?

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

Can you guys help me with some debugging tips?

  1. How do you efficiently debug big codes?
  2. How do you quickly find out which part of the code has the problem?
→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Using search engine (Google.com or bing.com for example) provides good results! Here's one : http://programmers.stackexchange.com/questions/10735/how-to-most-effectively-debug-code

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

      I don't want a gazillion suggessions. I want some practices that actually work. eg — the rubber duckie method is a little silly. Writing test cases is not always feasible, you have to generate lots of random inputs and you have to write a generator, a brute force solution checker, which can take time. Btw, I've read some of these tips earlier, I just wanted to know if there's something else out there I don't know about.

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

Can anyone explain C? I got ACC with a 3000ms solution but I can see many people with <200ms solutions. I process nodes in topological order and maintain dp[i][j] (or map for the same purpose due to memory constraints) where dp[i][j] = minimum cost to reach vertex i through j vertices. What am I missing here?

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

    map increases time,you don't need them. Ordered Maps can cause difference of upto log n. 2D int array will pass whereas 2D long array causes Memory Limit to exceed.

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

    How did you even manage to pass with this solution? I suppose it is nicely optimized O(N3), so I doubt you can make it work.

    The O(NM) solution uses well-known Bellman-Ford algorithm.

    On iteration K if you can reach vertex N, that means you can visit this vertex using K edges. Now we are going to read the statements and see this:

    'there are no cyclic routes between showplaces.'

    That means that on iteration K all the edges are different, and more than that, there can not be two equal vertexes on this path. This means that this path consists of K + 1 different vertexes.

    In conclusion, you simply run Bellman-Ford and if you can hit vertex N on iteration K in  ≤ T time, then K can be the answer. After that you need to recover the path for answer, you can do this in O(NM) memory which fits memory limit I guess.

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

      Thanks, I now got a 600ms solution using a modified version of Bellman-Ford.

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

Concerning problem C, "output any solution" means I can choose any solution ? I can't pass because sometimes my path differs from the judge but it is correct :/

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

    and why is the second example correct ? Why can't we go through 1 2 4 6 5 for a total time of 7 (which is not exceeding 7) ?

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

      You have to finish the journey in the showplace n.

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

      The problem statement asks to find a path from 1 to n. Here n = 6. In your output path, last node should have been 6 instead of 5

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

Publishing editorials after such long delay kills excitement. BTW, why can't editorials published just after contest ends? Any alternate solutions discovered during contest can be added to editorials later..

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

can someone tell me whats wrong with my D solution? http://codeforces.me/contest/721/submission/21054178

here i consider 0 to be positive first, if the number of negative numbers is even, i find the number with the lowest abs value, keep reducing its abs value untill its sign is changed.

then while we still have operations left, find the number with the smallest abs value, and increase its abs value.

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

I'm looking forward to the solution... The problem E was a little bit hard for me. :D

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

I have no idea why did my code failed on test case 50... Can anyone help point it out?

http://codeforces.me/contest/721/submission/21056370

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

    Because you were failing at this test case [Even I did] :- 

    5 3 3

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

.

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

Were I in problem E, I would probably sing when there weren't light because I would be frightened by the dark and sing to encourage myself.

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

Can anyone explain why 21030683 receives runtime error, but 21056614 passes? All i did was add a random comment at the beginning. Also if i send exactly the same code that got RE with C++14 it passes without any comment magic.

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

    How did you even realize that adding comment would fix it? :o

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

      CF usually doesn't let you submit 2 identical source codes, that's why I added this :D Apparently if you send it using different languages it's fine.

      Also, i did some more testing and found that the verdict changes depending on what you write in the comment. For example 21063149, 21063169, 21063271. I think it only happens with C++11.

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

        Is there any way we can contact codeforces team to tell us what exactly that RunTimeError is?

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

        I think it's a problem of codeforces platform.
        21074703 is the same code you submitted during the contest and it is Accepted when I submitted it.
        This is a serious issue, CODEFORCES TEAM!!! IF YOU ARE READING THIS, please make a note!

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

Im wondering how author can check D's solutions correct or not? Is it necessary to calculate product of array by using prime accumulation? Ps: I accidentally posted in Russian version, so I must re-post :((

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

where is the editorial??

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

Hey guys,

Thank you for the contest, but the problem statements really pissed me off during the contest:

Problem B:

Vanya is managed to enter his favourite site Codehorses.

What does that even mean? He wants to enter the web-site? He has managed to enter? He wants to sign in?

Vanya uses n distinct passwords for sites at all in total.

Vanya will enter passwords in order of non-decreasing their lengths

Just when Vanya will have entered enters the correct password, he is immediately authorized on to the site

But if Vanya will enter wrong password k times in a row, then he is able allowed to make the next try only 5 seconds after that

Vanya makes each try immediately, that is, at each moment when Vanya is able to enter password, he is doing that he enters a password as soon as he is able to do so

Also I missed the sentence about the fact that the input contains the actual password of Vanya, because it was only mentioned in a sentence inside the Input part of the problem statement. Although I should probably pick on myself for that, authors should have mentioned that in the problem description. I believe that the Input and Output parts should only describe the format of the input and output, NOT add any meaning or logic to the problem.

Problem D:

he invented positive integer x

Wait, what? Do we still invent numbers these days? He came up with a number, he found a number, but certainly he didn't invent a number.

Maxim is a curious minimalis minimalist

Is that a joke or a pun? Because minimalism doesn't really refer to a desire to minimize numbers in an array.

thus he wants to know what is the minimum value that the product of all array elements (i.e. ) can reach, if Maxim would apply no more than k operations to it :

thus -- people around don't really say "thus", they say "so", unless they are coming from the 18th century.

Here's what I think would make this sentence clearer and correct: So he wants to know what the minimum value of the product of all elements of the array would be, if he applies no more than k operations to that array

And this is not everything that could be improved to make problems clearer. I am nitpicking, but it is something that makes thing much harder to understand if done in almost every sentence. We all want to make Codeforces better, and all what I mean by this comment is that there are certainly ways to do that just by spending few minutes to review the problem statements before the contest. Otherwise, every time I read it in English, it turns into a hell of figuring out what the author meant.

I hope other people feel the same way too.

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

FreeEditorial

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

Test case 7 of E-Road To Home doesn't seem to satisfy the conditions of the question. Can Danil start singing at x=12 which is the end? If no, I am getting output of 4,but 5 is the answer. Can someone explains me this thing. Thank you.

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

    No, he would start singing at x=7 till x=12 hence answer is 5, he will not sing from x=0 to x=7 (t is 7).

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

where is editorial?

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

editorials please??

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

Excelent set of problems but with a missing editerial. :(

By the way, I think problem D is full of details which causes a mass of code with mountains of special cases. Anyone think it's good for a Codeforces problem or bad?

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

    You can solve it with 2 cases.Suppose you will change a1,then new product will be:

    so if you choose a1 the smallest number by absolute value,you have 2 cases,if then you add x else subtract x.

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

      Thanks a lot for your solution of Problem D. Maybe I have made an inappropriate example...

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

WHERE IS TH EDITORIAL???

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

when is 'soon'?????? :(

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

Editorial pls

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

Can anyone give detailed solution for problem C,Div 2

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

    And different ways to solve this problem please. I understood the way using dp as suggested by Pixar using dfs and dp using pathLength. What are other ways to solve problem. Full discription please.

    → Reply