### tom's blog

By tom, 5 years ago,  Comments (42)
 » Problem A:Ad hoc.Problem F:Use multiple Dijkstra's algorithms for every letter of text. As a starting vertex for ith iteration use fields with text[i - 1] and computed distance. For first iteration starting point is at (0, 0) and distance 0.
•  » » F had a rather strict time limit and some (not all) solutions that used Dijkstra got TLE.F can actually be nicely implemented as a single breadth-first search.
•  » » » My Dijkstra's solution passed time limits with 2s. reserve. Can you elaborate on that?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   Yes, I didn't take part in the Finals, but I solved Problem F using BFS. Precalculate for each letter, its neighboring letter when pressing each of the four arrow keys. This can be done with a single loop over the board for each direction. For the sake of simplicity, add '*' to the string (the final Enter). Solve the problem using BFS. At each state, we only care about the following: Position on the board and current letter on the string. This can be represented with 3 integers {i, j, k}. At each state, we have four choices (the arrow keys). If at any moment we are at a position that contains the current letter we're processing, we go from {i, j, k} to {i, j, k + 1} with one extra movement (pressing the key). Additionally, of course, we should have an array Di, j, k representing the distance to each state. We have r * c * |S| possible states and four possible choices for each state, which gives us a maximum of 50*50*10000*4 = 100M operations, very comfortable for the time limit.
 » 5 years ago, # | ← Rev. 2 →   :)
 » I don't know about exact solutions but in yesterday's live streaming, some analysis and solution approach was given in between the telecast. Youtube link Hope this helps...
 » As an extension, If someone can clip these analysis snippets and upload them seperately !!
•  » » AFAIK, this will quite probably be done in the near future by the official ICPC channel. And if it isn't, we still have the sources of those recordings somewhere :)
 » Problem C went straight over my head. I have no clue why the construction in the video is working :/ I am familiar with the basic maximum-flow problem (as given in CLRS) but don't know how minimum cost is playing it's role here.Here is what I understood, a unit flow into a vertex means that one catering team is serving an event and in addition to a capacity, each edge has been given a cost per unit flow. Now, If we try to achieve maximum flow with minimum cost, how does this ensure that all 'N' events will eventually be catered in the first place? Can't flow can take any arbitrary path from source to sink? Why is it necessary that maximum flow must be used to achieve minimum cost? Is it not possible that we have an optimal solution that doesn't have a flow of 'K' and still gives a us a minimum cost? Can there be more than one catering team at a particular node at a given time? Could someone please give a more detailed explanation? I don't find the problem to be trivial :/
•  » » 5 years ago, # ^ | ← Rev. 3 →   Here's how I solved it: build a suitable weighted bipartite graph incrementally, for each x, find the value M[x] of the cheapest matching with exactly x edges (by always applying the cheapest augmenting path) the smallest of the values M[N-K] through M[N-1] gives you the solution First, imagine you want to use exactly N teams. The cost is obvious: it's the sum of all distances start-location (i.e., the sum of the second row of the input file). This will be called the basic solution.Now, imagine you want to use exactly F teams fewer (i.e., use exactly N-F teams). What is the cheapest way to do it?Well, exactly F times we need to send a team from some party location to some other party location. Compared to the basic solution, how much will we save if we send a team from party X to party Y? That's easy: We have to pay the cost from X to Y, but not the cost from headquarters to Y, so we save the difference of those two.Now, imagine a bipartite graph where each partition has N vertices (one for each party). For each X < Y there will be an edge from vertex X in the left partition to vertex Y in the right partition, and the weight of this edge will be the amount we save by sending a team from party X to party Y.Clearly, if you are sending a team from X1 to Y1 and also sending a team from X2 to Y2, then X1 must be distinct from X2 and Y1 must be distinct from Y2. Hence, any valid way of using N-F teams corresponds to a matching of size F in our bipartite graph. And therefore, the cheapest way to do so is the minimum weight matching with exactly F edges.(Note that in the above situation it might be the case that Y1=X2. In other words, the same team gets sent to multiple parties.)And that's it. As we get to use 1 through K teams, we are interested in minimum weight matchings that consist of N-K through N-1 edges.
•  » » » First, imagine you want to use exactly N teams. The cost is obvious: it's the sum of all distances start-location.I cannot find why it is impossible to carry equipment using client which was already served. Is it clear from the problem statement?
•  » » » » It is possible to carry equipment from one party to another. Finding the optimal cost of doing so is the actual problem we are solving here. I'm doing that later using the min cost matching, others are doing it using the mincost maxflow.In the part of my solution you are quoting I'm just computing the cost of one special case: the one where each party is served by a different team. (This special case may not even be a valid solution.)
•  » » » » » Let's see, the actual question is:Why is impossible for two equipments to start by the same party?It is not clear enough in the problem statement the fact that an equipment can be carried to one party only if this party has not been served by other equipment.
•  » » » » » » Yes, this was ambiguous. As far as I know, the only global clarification during the contest was the announcement that this is not allowed.
•  » » Problem C: I constructed the graph this way: Consider the N+1 locations as nodes. Construct an edge from Source to Location 1, with capacity=K, and cost=0. Construct edges from Source to Locations [2..N] with capacity=1, and cost=0. Call the Source as Layer 1, and this set of locations as Layer 2. Consider a Layer 3, with N+1 nodes. We can consider Layer 2 to be Input Nodes and Layer 3 to be Output Nodes. As per input given in the problem, construct edges from Layer 2 to Layer 3 with cost(i, i + j) Construct edges from Layer 3 to Sink with capacity=1 and cost=0. Perform min cost max flow on this graph.
•  » » » did you got AC with this method? seems pretty wrong to me, especially where you just pump flow 1 to all nodes [2...N]
•  » » » » Yes, I got AC.
 » 5 years ago, # | ← Rev. 2 →   For problem L, Do we need to take care of floating point precision issue? May be something like multiplying all the probabilities with 10^2.Edit: I tried solving the problem and it worked without need of any special care. Can anyone help me how can we prove that there won't be any precision loss in the solution?
 » Can any one explain complete solution of H and E? I saw the video but its not that clear to me.
 » Who can explain the answer in the first sample of problem I?
 » Misof,regarding problem L/Weather, could you explain how you arrived at 12k equivalence classes? I assume you mean for n = 20. Do you mean classes of symbol words that have the same number of each weather letter (RSFC)? In this case, I am only able to identify 1771 of them, listed here: http://pastebin.com/ZK0seLyV
•  » » You are correct, I was wrong. I also get only 1771 now. I probably accidentally used 40 instead of 20 when doing the calculation seconds before the broadcast :)
•  » » » Thank you. May I ask a follow-up question. How exactly do you compute the Huffman on the equivalence classes? I've tried a number of attempts without success.For instance, in testcase 1, the optimal Huffman tree encodes the string "CS" as 000 (3bits) but the string "SC" as 0111 (4bits), even though they have the same probability of occurring. How do you account for that?
•  » » » » 5 years ago, # ^ | ← Rev. 7 →   There is ways to divide sequence of 20 days into 4 groups. Why? Consider 23 empty places in a row. We want to put 3 walls in three different places. It gives us 4 segments separated by walls and their lenghts are our four numbers with sum equal to 20.
•  » » » » » Thanks — I'm not confused about why there are only 1771 classes — I'm asking how to process those classes when computing the Huffman tree. In the Huffman tree, each class ends up as a combination of multiple subtrees whose numbers of leaves add up to the numbers of elements of that equivalence class. I'm wondering how to find those efficiently. Is there another insight that is needed here?
•  » » » » If you have 15 nodes, each with probability 0.001, you will have 7 nodes, each with probability 0.002, and 1 node with probability 0.001. Then, the single remaining node will get paired with something else.Here's my AC code if you want to take a look: http://ideone.com/ZhvoD1
•  » » » » » Ah, of course. I had made the mistake of dissolving each equivalence class into nodes/subtrees once it reaches the head of the heap/queue, but this is of course not necessary since if you simply insert an equivalence class with probability 2*pp and sz//2 into the queue.
•  » » 5 years ago, # ^ | ← Rev. 2 →   .
 » Misof, I am intrigued by your comments about H, Qanat.I solved it by writing down the cost function in terms of xi and taking its partial derivatives. Setting the partial derivative to zero yields a recursion of xi + 1 in terms of xi and xi - 1, and then I used a binary search to find x1.Specifically, where k = h / w as in your presentation and x0 = 0 and xn + 1 = w for convenience.You say you would instead use a numerical method — could you elaborate more on how that would be useful? You could solve a system of 10,000 equations with 3 variables each, but that would require that you implement some kind of sparse solver; and in any event, with the equations as given, finding x1 with a binary search seems kind of obvious. Which numerical method that should converge reasonably quickly were you thinking of?Also, I tried using the method of gradient descent on the cost function with a line backtracking search. This works for small n, but fails to converge in time for large n as I expected.