### maksay's blog

By maksay, 12 years ago, translation,
Hi everybody!

Today authors are me and Roman Iedemskyi (Shtrix). Big thanks for help in preparing problems to our teammate Iaroslav Tverdohklib, Artem Rakhov, Maria Belova and Dmitry Matov.

Hope you will enjoy the contest!

UPD: Congratulations to winner
Announcement of Codeforces Beta Round #62

• +134

 12 years ago, # |   +13 nice problem set :)
 12 years ago, # |   0 What is the approach to solve Problem B?
•  12 years ago, # ^ |   +2 Binary search on answer
•  12 years ago, # ^ |   0 Use binary search to find the answer. Just count amount of removed power and check if it's enough.
•  12 years ago, # ^ |   0 Let a and b be the number of accumulators with the biggest amount of energy and the smallest amount of energy. Initially a and b are 1. While a + b ≠ n move energy from the a accumulators with the most energy to b accumulators with the least energy such that1) the energy remained in the accumulators with the most energy equals to the energy of accumulators with the most energy from the remaining ones (n - a - b). In this case a increases with 1.2) the energy remained in the accumulators with the least energy equals to the energy of accumulators with the least energy from the remaining ones (n - a - b). In this case b increases with 1.Here my source code (in C++): http://pastebin.com/m9Xc9rjy
 12 years ago, # |   +2 Can you please elaborate it
•  12 years ago, # ^ |   +8 You can see that you never move the same "part" of energy twice in optimal solution. Otherwise why can't you move it to the final place from original place?So now if you guess what is the result, there are some accumulators that have some additional energy and some that need energy. There must be additional * (1-k/100) >= needed
 12 years ago, # |   +3 Wait a second, my rating increased from 1993 to 2165, is this a bug?
 12 years ago, # |   +3 Alright, it's back to 1821 :-/Seems like it's being fixed.
•  12 years ago, # ^ |   +3 NVM people, it's back to normal!
 12 years ago, # |   +1 I found some issue with Custom Test while this round.For Problem A, I wrote my code in Ruby and test it on Custom Test to see whether my code gets TLE.Custom Test reports 970ms as running time for worst input case(997 998 999 1000 0 31415), but my code failed on System test by TLE, though the failed case was just same as my case.Are there any difference between Custom Test and System test?Couldn't I trust running time on Custom Test?
 12 years ago, # |   +3 Hey, my solution fails system test 8 with error:Test: #8, time: 10 ms., memory: 1364 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWERInput2 1 2 0 0 6 Output-1 -1 Answer0 0 Checker Logwrong answer 1st numbers differ - expected: '0', found: '-1'although problem statement says:If there is no amount of fuel that can reach synchrophasotron, output "-1 -1".So there is no amount of fuel that can reach synch...whatever, (it is 0), but the correct output should be 0 0?
•  12 years ago, # ^ |   0 "The amount of fuel which will flow into synchrophasotron is not neccessary positive. It could be equal to zero if the minimum constraint of every pipe is equal to zero."
•  12 years ago, # ^ |   0 "-1 -1" and "0 0" are two different cases.In one there is amount of fuel equal to 0 that satisfies all conditions on pipes. (maximum, minimum, income=outcome for middle nodes).In other there is no amount of fuel that can satisfy them.
•  12 years ago, # ^ |   0 "If there is no amount of fuel that can reach synchrophasotron, output -1 -1" means that you should output "-1 -1" only if all conditions on capacities can not be satisfied simultaneously.There is a sentence in output section of the statement:The amount of fuel which will flow into synchrophasotron is not neccessary positive. It could be equal to zero if the minimum constraint of every pipe is equal to zero.
•  12 years ago, # ^ |   0 Lol, apparently I missed that sentence. If I change my flow cycle to start from 0 instead of 1 (which I did on purpose, because of the first one) my solution passes. Pretty stupid mistake =/
 12 years ago, # |   0 your output must be "-1 -1", when there is no state that hold all the limit's.
 12 years ago, # |   0 how to solve problem C?
•  12 years ago, # ^ |   +5 During the contest I thought that just a backtracking wouldn't be fast enough, but actually removing the memoization step turned up to be faster than the version with memoization, anyway, as I can only prove the complexity of the DP, I'll describe it.So, first notice that you have a very simple dag (directed acyclic graph). The idea is to process the edges in the natural order (for n=4 1->2;1->3;1->4;2->3;2->4;3->4) trying all possible flows for each edge from the minimum to the maximum. Now what are the constraints that must be satisfied when processing one edge:1) The amount of flow in the node of origin need to be at least the minimum required by the edge.2) After processing the last edge of a node the amount of flow in it must be equal to 0. It means that when you arrive in the last node all other nodes will have flow 0.Also note that a state is uniquely defined by the flow stored in each of the nodes and in which edge you are.So your state will be:The edge (easier represented by a pair (nodeorigin,nodedestination)).The amount of flow in each of the nodes.The minimization of the flow can be achieved iterating the initial flow in node 1 from 0 to 25 (5 edges of flow 5 in the worst case), and stopping as soon as you have a solution.The maximization of the cost is achieved because you try everything.Complexity proof:The maximum flow is 25, as state above. This flow must be distributed in the 6 nodes. So you can represent it as a string of  25 *'s and 5 commas, all permutations will represent a state. From combinatorial theory you'll have 30!/(5!*25!) = 142506.You need to multiply this value by 15 as you have 15 edges in the worst case. 2.137.590 statesAnd each state may iterate from 0 to 5 (maximum capacity of an edge), so multiply by 6. 12.825.540Which is a reasonable number. Of course you still have the overhead of the map to memoize it, but with this not so big values it won't be a problem. You could also take out several impossible states, as having flow stored in a node after processing it's last edge.You may check the implementation of this idea during the contest in: http://pastebin.com/xjL2jTS4I hope it is clear enough.Now, if anyone can give a reasonable explanation why the pure backtracking works fine it would be nice. Thank you in advance.
 12 years ago, # | ← Rev. 3 →   -9 I think condition of the problem B is incorrect (or checker):My response in test case 36 : 0.100001000;The correct answer is (mathematically, and from the jury): 0.100000000Verdict: WAquote from the condition: "The absolute or relative error response should not exceed 10  - 6 "As I understand it (this assumption), the standard checker, which compares to a strictly smaller.
 12 years ago, # |   0 Any hint for problem D ?
•  12 years ago, # ^ |   0 seemed easy to me..although i didn't submit..just see, how many leaf nodes are reachable from the node where "add" statement is given .Then add that many items to all the leaf nodes reachable.Simple :)    . (then to produce ans take average..)
•  12 years ago, # ^ |   +3 EDIT:  NO, that is wrong :( .  see rng_58's solution. :)