### Vovuh's blog

By Vovuh, history, 23 months ago, translation, ,

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 dans 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

•
• +269
•

 » 23 months ago, # |   +24 30 September
•  » » 23 months ago, # ^ |   +26 Oh, sorry, my mistake. Fixed.
 » 23 months ago, # |   -55 Why unusual time? :/ The previous timings were way better.
 » 23 months ago, # | ← Rev. 2 →   -36 Unfortunately, this round will be conflict with Jordan-cpc :/
•  » » 23 months ago, # ^ |   -21 Hi. Sorry for my bad English.
 » 23 months ago, # | ← Rev. 2 →   +98 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.
 » 23 months ago, # |   +154 "Unusual" is the new usual.
•  » » 23 months ago, # ^ |   +15 You won the Internet. :D
 » 23 months ago, # |   +87 wish to see a programming contest not a hacking contest :D
•  » » 23 months ago, # ^ |   +8 I think hacking contest is interesting~
•  » » » 23 months ago, # ^ |   +49 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.
•  » » » » 23 months ago, # ^ |   +8 sorry,I didn't read carefully.
•  » » » 23 months ago, # ^ |   -24 but there is no hack in the programming competitions like ICPC or IOI
•  » » 23 months ago, # ^ |   +7 I think some pretests are little bit weak :<
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +7 the pretest of the last 4 or 5 contests were too weak
•  » » » » 23 months ago, # ^ |   +4 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!
•  » » » » » 23 months ago, # ^ |   +24 the pretest of problem A and B should be stronger~
•  » » » » » 23 months ago, # ^ |   +20 there is someone hacked 16 people on problem A last contest he took points like the points on problem E :\
•  » » 23 months ago, # ^ | ← Rev. 2 →   -29 if you hack a person once, you would not say this again =)
 » 23 months ago, # | ← Rev. 6 →   +11 bad round PS : one of my friend has comment it when we has class, sorry author :((
 » 23 months ago, # | ← Rev. 2 →   +33 one's day may be night for others. so we should appreciate this "unusual" time.
 » 23 months ago, # | ← Rev. 3 →   -56 my best friens Danil dans Sagunov also for help in preparing the roundwhat does "friens" mean??UPD: fixed.
•  » » 23 months ago, # ^ |   +50 thanks, fixed
 » 23 months ago, # | ← Rev. 3 →   -40 good luck
 » 23 months ago, # |   -56 why unusual man ? I hate to miss contests
 » 23 months ago, # |   +1 salamare problems sorted in order of their difficulty?
•  » » 23 months ago, # ^ |   +3 Usually they do, but it is still recommended to read all the problems, just in case.
 » 23 months ago, # | ← Rev. 2 →   +4 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.
 » 23 months ago, # |   0 Looking forward to the contest =D
 » 23 months ago, # |   +21 Round 374. 374 = 2 × 11 × 17 , Sphenic Number
•  » » 23 months ago, # ^ |   0 Nice Observation.
 » 23 months ago, # |   +25 I hope the platform will be stable today. Currently there are 7+ pages of pending submissions....
•  » » 23 months ago, # ^ |   +8 Seems better now :)
 » 23 months ago, # |   +7 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.
•  » » 23 months ago, # ^ |   +16 In my opinion, the active contest should have significantly higher priority on the queue than practice.
•  » » » 23 months ago, # ^ |   +7 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.
 » 23 months ago, # |   -76 Hit like if you think your rate will be increased today :v
•  » » 23 months ago, # ^ |   -45 then Hit Like if you think your rate will be decreased today :v
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +23 An old trick for getting upvote , stop it or you will get downvotes again!
 » 23 months ago, # |   +3 I hope that I have become better.
 » 23 months ago, # |   +9 Score distribution ?
 » 23 months ago, # |   0 Auto comment: topic has been updated by dans (previous revision, new revision, compare).
 » 23 months ago, # |   +12 After reinstalling windows, I am unable hack in firefox. Click
•  » » 23 months ago, # ^ |   +4 i think you need to update your adobe flash playeri have faced the same problem also
•  » » 23 months ago, # ^ |   +4 use chrome!
 » 23 months ago, # |   -8 the cool trick in div2 A is that you shouldn't test all samples on your code :v
•  » » 23 months ago, # ^ |   0 May I know why ?
 » 23 months ago, # |   0 Quick question, if I can't get pretests passed for anything I submitted, I'm still eligible for rating drop, right?
•  » » 23 months ago, # ^ |   0 Yes, You're eligible for rating drop if you have submitted at least once
•  » » » 23 months ago, # ^ |   0 Okay ;_;
•  » » » » 23 months ago, # ^ |   0 Sorry :(
•  » » 23 months ago, # ^ |   +5 not only drop bro :) extreme drop :P
•  » » » 23 months ago, # ^ |   0 Okay ;_;
•  » » » 23 months ago, # ^ |   +5 I can either keep attempting A and B under time constraints, or I can try to level up. My ratings will get dropped extremely(-130 this time) but it is one of those things you gotta do if you want to improve yourself(I hope) :)
 » 23 months ago, # |   +26 So codeforces allows submit the same code now?
•  » » 23 months ago, # ^ |   0 how same code get 15 ms as well as 31 ms??
•  » » 23 months ago, # ^ |   0 That apparently counted as resubmitting twice... Isn't that a bit of a problem?
•  » » 23 months ago, # ^ |   0 I think you will get 50 point penalty for resubmitting.
•  » » » 23 months ago, # ^ |   +10 He's div1 so it's unrated for him
•  » » » » 23 months ago, # ^ |   0 Having fun then
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 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
 » 23 months ago, # |   0 Div2B hack?
•  » » 23 months ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ |   +1 they are pairwise distinct though, no?
•  » » » » 23 months ago, # ^ |   0 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."
•  » » » » » 23 months ago, # ^ |   0 I was very confused by this too
•  » » » 23 months ago, # ^ |   +8 The next n lines contains passwords, one per line — pairwise distinct non-empty strings consisting of latin letters and digits.
•  » » » 23 months ago, # ^ |   0 "pairwise distinct non-empty strings consisting of latin letters and digits."
•  » » » 23 months ago, # ^ |   0 The statement has said "pairwise distinct non-empty strings"
•  » » » 23 months ago, # ^ |   0 Its written passwords are distinct
•  » » » 23 months ago, # ^ |   0 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?
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 23 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 23 months ago, # ^ |   +3 But it is mentioned that the strings will be pairwise distinct & non-empty.
 » 23 months ago, # |   0 Nice contest.. Anyone can tell me how to solve problem D??
•  » » 23 months ago, # ^ |   +8 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.
•  » » » 23 months ago, # ^ |   +6 Can you prove that why choose smallest abs value and apply opration on it in first step is true ??
•  » » » » 23 months ago, # ^ |   +3 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)
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 22 months ago, # ^ |   0 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?
 » 23 months ago, # |   +2 How to solve C guys?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 23 months ago, # ^ |   +5 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.
 » 23 months ago, # |   0 Is there a special algorithm to do C? I kept getting time limit with a breadth and depth first search.
•  » » 23 months ago, # ^ |   +4 I was on the same boat for a while. The trick (for me, at least) was topological sorting.
•  » » » 23 months ago, # ^ |   +3 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.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +5 Do a topological sort of vertices. 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].
•  » » » 23 months ago, # ^ |   0 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...
•  » » » » 23 months ago, # ^ | ← Rev. 7 →   +17 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 → 4 1 → 2 4 → 2 4 → 3 2 → 3 2 → 5 2 → 6 3 → 5 3 → 6 5 → 6
•  » » » » » 23 months ago, # ^ | ← Rev. 4 →   0 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... 
•  » » » » » » 22 months ago, # ^ |   0 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.
•  » » » » » » » 22 months ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » » » » » 22 months ago, # ^ | ← Rev. 4 →   +5 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).
•  » » » » » » » » » 22 months ago, # ^ |   0 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: 
•  » » » » » » » » » 22 months ago, # ^ | ← Rev. 2 →   +5 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: 21115101Feel free to ask any questions about the code.
•  » » » » » » » » » 22 months ago, # ^ |   0 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?
•  » » » » » » » » » 22 months ago, # ^ | ← Rev. 3 →   +5 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).
•  » » » » » » » » » 22 months ago, # ^ |   0 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.com/contest/721/submission/21047724
•  » » » » » » » » » 22 months ago, # ^ | ← Rev. 3 →   0 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 245435090So, 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
•  » » » » » » » » » 22 months ago, # ^ |   0 Your code made 17M iterations, mine did 3M. And yours is 30x faster somehow.http://codeforces.com/contest/721/submission/21168815
•  » » » » » » » » » 22 months ago, # ^ |   0 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.
•  » » » » » » » » » 22 months ago, # ^ |   0 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.
•  » » » » » » » » » 22 months ago, # ^ | ← Rev. 4 →   0 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.
•  » » » » » » » » » 22 months ago, # ^ |   0 Look at this: 2117200917835090 operations and only 265ms!The only difference I see is that there are no HashMaps and no TreeMaps.
•  » » » » » » » » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ |   0 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.
•  » » » » 22 months ago, # ^ | ← Rev. 7 →   +5 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.
•  » » » » » 22 months ago, # ^ |   0 Thankyou so much! Very nicely explained :)
 » 23 months ago, # |   +1 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 :|
•  » » 23 months ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ |   0 No i meant n**2 only. However on my first submit it had taken like 260mb of memory so i reduced one of them to unsigned short to just make it through mle. http://codeforces.com/contest/721/submission/21031777
 » 23 months ago, # |   +15 Did someone experience problem with lack of memory in Div2C?This is the first time it happened to me.
•  » » 23 months ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ |   +4 Me too. But it wasn't necessary to store that much memory. Use map instead of arrays as there are only 5000 edges.
•  » » » » 23 months ago, # ^ |   +1 @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)
•  » » 23 months ago, # ^ |   +1 I did, could have probably optimized memory complexity but I chose to just make stuff shorts instead of long longs and ints.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +5 I solved it using int dp[5000][5000][2] and it didn't give me MLE
 » 23 months ago, # |   -10 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.
•  » » 23 months ago, # ^ |   0 For which problem?
•  » » » 23 months ago, # ^ |   +1 A
 » 23 months ago, # |   +20 I was surprised that so many people solved C
•  » » 23 months ago, # ^ |   0 yes I was also surprised. It made me wonder if I was too complicated or not. Anymay I could not finish in time...
•  » » 23 months ago, # ^ |   0 Pretests are extremely weak. My bogus solution using Dijkstra with weights as {cities not visited, time taken} got accepted on pretests. It is easy to create anti test.
•  » » 23 months ago, # ^ |   0 There was a similar problem a few months ago on topcoder: DoubleWeights.
•  » » 23 months ago, # ^ |   0 well it seems only 600 really solved it...
•  » » » 23 months ago, # ^ |   0 587.
•  » » » 23 months ago, # ^ |   0 which means I will gain ratings instead of losing :D
 » 23 months ago, # |   +1 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
 » 23 months ago, # |   0 problem B hacking Test Case please?
 » 23 months ago, # |   +24 what's an unexpected verdict?
•  » » 23 months ago, # ^ |   -18 It's a verdict that is unexpected.
•  » » » 23 months ago, # ^ |   +18 wow that was unexpected
•  » » » » 23 months ago, # ^ |   +15 Judge shocked, Yukimai rocked
•  » » 23 months ago, # ^ |   0 And it becomes an unsuccessful now:)maybe small bugs
 » 23 months ago, # |   0 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
 » 23 months ago, # |   -21 Hhmmm...seems odd daneshvar_a accepted C and D at 1:58 and 1:59.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +9 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.
•  » » » 23 months ago, # ^ |   -7 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.
•  » » » 23 months ago, # ^ |   +7 Now it's really ODD.all your submissions were skipped :|
 » 23 months ago, # |   0 could anyone explain why the following code fails (TLE)? 21035958
 » 23 months ago, # |   0 In the last three contest Div 2C is a DP problem...Seems like its time to start practicing DP
•  » » 23 months ago, # ^ |   +13 DP is a great concept and I think it fits nicely into Codeforces rounds
 » 23 months ago, # |   +2 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.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +9 dp[i][j] is min time to get to i after visit j node,and it will get MLE if you use long long
•  » » 23 months ago, # ^ |   +9 a guy in my room use DFS but he had passed the pretests
•  » » » 23 months ago, # ^ |   +1 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.
•  » » 23 months ago, # ^ |   0 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.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +5 21049347 is my solution using DFS and it's Accepted, after the contest though :(Let me know if you have any doubts :)
•  » » » 23 months ago, # ^ |   0 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 :)
•  » » » » 23 months ago, # ^ |   0 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 :)
 » 23 months ago, # |   0 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...
•  » » 23 months ago, # ^ |   0 What was the hack?
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 Just a simple case. 7 2 a b cd dc abc acd acc accand the ans:15 22 good luck..
•  » » 23 months ago, # ^ |   +1 So as Div2D... I just realized I made a very, very foolish mistake.
•  » » » 23 months ago, # ^ |   0 Are there any of us that didn't handle negative test cases?;D
 » 23 months ago, # |   0 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...
 » 23 months ago, # | ← Rev. 2 →   0 My B solution got hacked, What would be the problem with that code? http://codeforces.com/contest/721/submission/21032401
•  » » 23 months ago, # ^ |   +6 you should get the sum of cnt[1~len-1],rather than count one by one.
•  » » » 23 months ago, # ^ |   0 Can you explain a little bit more please?
•  » » » » 23 months ago, # ^ | ← Rev. 6 →   0 You divide every cnt with m and divide by 5, so for: 5 4 a b ab cd abc abcYou 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]
•  » » » » » 23 months ago, # ^ |   0 ohh.. Thank you..
•  » » » » 23 months ago, # ^ |   0 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.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +1 Here's a hack case for your code.6 3 ab ac abc abd abcd abcf abcdThe 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)
 » 23 months ago, # | ← Rev. 2 →   +1 Expecting lots of hacks(System testing failure) on 2nd question. No pretest to bound best part of question passwords
 » 23 months ago, # |   0 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
•  » » 23 months ago, # ^ |   0 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.
 » 23 months ago, # |   0 How would O(N^2logN) gets TLE in 3 sec, problem C -_-
•  » » 23 months ago, # ^ |   -9 that's about 3*10^8 repetitions, you should never have that many.
•  » » » 23 months ago, # ^ |   0 it got AC now with a little more optimization but still O(N^2logN) 21043948very strict TL -_-
•  » » » » 23 months ago, # ^ |   0 I think the intended solution is O(nm)
•  » » 23 months ago, # ^ |   +6 solved C with Dijkstra , it took 623 ms better check your code
•  » » » 23 months ago, # ^ |   +6 139 ms lol.
•  » » » » 23 months ago, # ^ |   +6 62 ms lol
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +3 Can you give hint about your approach? I used DFS. Got 78ms and 1200KB memory (memory seems to be too less!)
 » 23 months ago, # | ← Rev. 2 →   +15 I see about 1100 people passed pretest on C but about 600 accepted, why ??
•  » » 23 months ago, # ^ |   -12 I think too very strict in memory constraints .....
•  » » 23 months ago, # ^ |   0 Because of DP
•  » » 23 months ago, # ^ |   +3 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)
•  » » » 23 months ago, # ^ |   0 I saw your solutions , similiar memory used any idea why mine exceeded ?
•  » » » 23 months ago, # ^ |   0 same
•  » » 23 months ago, # ^ |   +3 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 - Дополни граф). (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.
 » 23 months ago, # |   0 http://codeforces.com/contest/721/submission/21030275 Memory Limit exceeded in 33 test case ... :| I saw some solutions with similiar limits ... unfair !
•  » » 23 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » 23 months ago, # ^ | ← Rev. 2 →   -6 you should use priority_queue instead of queue , your code is about O(n^3)
•  » » » 23 months ago, # ^ |   0 Do you mean memory or time ?
 » 23 months ago, # | ← Rev. 3 →   -13 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 ) !
•  » » 23 months ago, # ^ |   +19 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.
•  » » » 23 months ago, # ^ |   0 sorry brother , updated my comment didn't know that your country follows such strict policies .
 » 23 months ago, # |   0 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??
•  » » 23 months ago, # ^ |   0 maxi+=mm[str.size()]; this part . you ought to add mm[str.size()] -1 . Later d incrementation after the 5sec calculation.
•  » » 23 months ago, # ^ |   0 You should not use cin and getchar/scanf when ios::sync_with_stdio(false) is being used.
•  » » » 23 months ago, # ^ |   0 Why it is bad? And when i should use this code?
 » 23 months ago, # | ← Rev. 2 →   0 I received a really strange Runtime Error on problem B and am not able to identify the reason.What is wrong here? 21044715I suspect the error is on the first sort after playing with the answers that Codeforces give me.
•  » » 23 months ago, # ^ |   0 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 RETry changing true to false in the last line of comparing function, I think this will work.
•  » » » 23 months ago, # ^ |   0 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?
•  » » » » 23 months ago, # ^ |   0 Yes in the first case sort will think that a = b.
•  » » » » » 23 months ago, # ^ |   0 I see. Thanks a lot for the help!
•  » » » » 23 months ago, # ^ |   0 Yes. If a < b and b < a are both false, then it just means that a = b for this comparing function.
•  » » » » » 23 months ago, # ^ |   0 I see. Thanks a lot for the help!
 » 23 months ago, # |   +33 Is something is wrong with the ratings? I think all three should be "Became Candidate Master"
•  » » 23 months ago, # ^ |   +3 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.
 » 23 months ago, # |   -28 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
•  » » 23 months ago, # ^ |   +11 Perhaps it's because he's familiar with crosswords from his own country (just geuessing XD)
•  » » 23 months ago, # ^ |   +11 the logic portion is only the 'solve()' function. Everything else was prewritten.
 » 23 months ago, # |   0 Auto comment: topic has been updated by P1kachu (previous revision, new revision, compare).
 » 23 months ago, # |   0 Why this code gives http://codeforces.com/contest/721/submission/21026545 gives runtime error while http://codeforces.com/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 functionbool comp( const string&a, const string&b){ if(a.length()<=b.length()) return true; else return false;}Can someone help what is the problem when i am using the above comparator function and thus causing the runtime error ?
•  » » 23 months ago, # ^ |   0 Same as above, there must be no two elements such that comp(a, b) =  = true and comp(b, a) =  = true.
•  » » » 23 months ago, # ^ |   0 Thank you !! Got it :)
•  » » 23 months ago, # ^ |   +18
•  » » » 23 months ago, # ^ |   0 Thank you !! Forgot to take note of these things :)
•  » » » 23 months ago, # ^ |   0 Thank you !! Then how should I sort it in non-decreasing order of length ?
•  » » » 23 months ago, # ^ |   -6 relax
 » 23 months ago, # |   0 http://codeforces.com/contest/721/submission/21035009 the following submission of the second question i.e. password ,my solution got accepted in the pretests however during the system check it got a wrong answer on pretest 14 ,here the number of unsuccessful password attempts are 5 and one for correct the answer should've been 6 ,since there is a penalty after 6 wrong submissions.Could any one please explain it. Thank you
 » 23 months ago, # |   +9 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 ? -_-
 » 23 months ago, # |   +1 I got Skipped, can you tell me why ?
•  » » 23 months ago, # ^ |   +14
 » 23 months ago, # |   +16 kudos to the author for the awesome contest, where even 4th question was well in reach! looking forward to more rounds from your side @P1kachu
 » 23 months ago, # | ← Rev. 3 →   0 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?
•  » » 23 months ago, # ^ |   +3 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.
•  » » » 23 months ago, # ^ |   0 Oh Okay I get it , I wish I never saw this :D . BTW can you answer the second question?
 » 23 months ago, # |   +20 66 test cases of a problem and the one your code gets WA on, 66Life is hard
 » 23 months ago, # |   -13 why so serious to down vote my comments !?
•  » » 23 months ago, # ^ |   +4 I feel sorry for you. Lol :)
 » 23 months ago, # | ← Rev. 2 →   -16 Can you guys help me with some debugging tips? How do you efficiently debug big codes? How do you quickly find out which part of the code has the problem?
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 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
•  » » » 23 months ago, # ^ |   -6 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.
 » 23 months ago, # |   0 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?
•  » » 23 months ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ |   0 Ok, but it doesn't explain the difference between 200ms and 3000ms. For example, here is another Java Map implementation that passes under 200ms: http://codeforces.com/contest/721/submission/21033441
•  » » 23 months ago, # ^ | ← Rev. 2 →   +7 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.
•  » » » 23 months ago, # ^ |   0 Thanks, I now got a 600ms solution using a modified version of Bellman-Ford.
 » 23 months ago, # |   0 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 :/
•  » » 23 months ago, # ^ |   0 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) ?
•  » » » 23 months ago, # ^ |   0 You have to finish the journey in the showplace n.
•  » » » 23 months ago, # ^ |   0 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
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 oh god...Thanksmy problem was quite different :/
 » 23 months ago, # |   +16 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..
 » 23 months ago, # |   0 can someone explain why this MLE?
 » 23 months ago, # |   0 can someone tell me whats wrong with my D solution? http://codeforces.com/contest/721/submission/21054178here 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.
 » 23 months ago, # |   0 I'm looking forward to the solution... The problem E was a little bit hard for me. :D
 » 23 months ago, # |   0 I have no idea why did my code failed on test case 50... Can anyone help point it out?http://codeforces.com/contest/721/submission/21056370
•  » » 22 months ago, # ^ |   +3 Because you were failing at this test case [Even I did] :- 5 3 3 5 5 5 -3 -3 
 » 23 months ago, # | ← Rev. 2 →   +3 .
 » 23 months ago, # |   +4 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.
•  » » 23 months ago, # ^ |   0 lol
 » 23 months ago, # |   +15 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.
•  » » 23 months ago, # ^ |   0 How did you even realize that adding comment would fix it? :o
•  » » » 23 months ago, # ^ |   0 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.
•  » » » » 23 months ago, # ^ |   0 Is there any way we can contact codeforces team to tell us what exactly that RunTimeError is?
•  » » » » 23 months ago, # ^ |   0 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!
 » 23 months ago, # |   +3 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 :((
 » 23 months ago, # |   +10 where is the editorial??
 » 23 months ago, # |   +28 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 lengthsJust when Vanya will have entered enters the correct password, he is immediately authorized on to the siteBut 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 thatVanya 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 arrayAnd 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.
»
23 months ago, # |
-8

# FreeEditorial

 » 23 months ago, # |   0 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.
•  » » 23 months ago, # ^ |   0 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).
•  » » » 23 months ago, # ^ |   0 Thank you..I just missed that case
 » 23 months ago, # |   +10 where is editorial?
 » 23 months ago, # |   +5 editorials please??
 » 23 months ago, # |   0 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?
•  » » 23 months ago, # ^ |   +3 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.
•  » » » 22 months ago, # ^ |   0 Thanks a lot for your solution of Problem D. Maybe I have made an inappropriate example...
 » 22 months ago, # |   +5 WHERE IS TH EDITORIAL???
•  » » 22 months ago, # ^ | ← Rev. 3 →   +5
•  » » » 22 months ago, # ^ |   0 Thanks you very much
 » 22 months ago, # |   +2 when is 'soon'?????? :(
 » 22 months ago, # |   +3 Editorial pls
 » 22 months ago, # |   0 Can anyone give detailed solution for problem C,Div 2
•  » » 22 months ago, # ^ |   +2 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.