sorry,I didn't read carefully.

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!

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

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.

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)

Consider that you have two elements a_i and a_j, |a_i| < |a_j|. Let m be the smallest number of operations required to change the sign of a_j. If you apply them to a_j, you will get two numbers, a_i and new a_j, and now |a_j| (the new one)  = m·x - |a_j|. If you apply all those m operations to a_i instead (there might be some better ways, but let's consider this), there will be new a_i: |a_i| (the new one)  = m·x - |a_i|, and a_j will remain unchanged. |a_j| > |a_i|, m·x - |a_i| > m·x - |a_j|, 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.

Sure.

Let's consider, for example, a DAG with 6 vertices: v₁, v₂, v₃, v₄, v₅, v₆.
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: v₁ is [ floor 1 ] and v₆ is [ floor 6 ], because we always gain access to all of the verices in a graph from vertex v₁ (we always gain access to the floors of a building through the first floor) and we end our travel in a graph in vertex v₆ (we cannot move further up from the floor 6).
Now, we base our decisions about correspondance of vertices v₂, v₃, v₄, v₅ and floors on the fact that if v₂ is some [ floor i] then all of the outgoing edges from v₂ 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

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 v_k. For example, it has 3 parent vertices: v₁, v₂, v₃. 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 v₁. At that moment, we update estimate of child vertex v_k.
On some other step of the algorithm we become sure in the estimate of v₂. Then we do the second update of the state of the vertex v_k.
And situation repeats for the vertex v₃.

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

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

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

Judge shocked, Yukimai rocked

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

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]

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.