maksay's blog

Codeforces Beta Round #62
By maksay, 14 years ago, translation, In English
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 rng_58!
Announcement of Codeforces Beta Round 62
  • Vote: I like it
  • +134
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +13 Vote: I do not like it
nice problem set :)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What is the approach to solve Problem B?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    Binary search on answer
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Use binary search to find the answer. Just count amount of removed power and check if it's enough.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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 that
    1) 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 
    → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
Can you please elaborate it
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    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
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Wait a second, my rating increased from 1993 to 2165, is this a bug?
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Alright, it's back to 1821 :-/
Seems like it's being fixed.
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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?
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
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_ANSWER
Input
2
1 2 0 0 6
Output
-1 -1
Answer
0 0
Checker Log
wrong 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?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    "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."
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    "-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.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    "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.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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 =/
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
your output must be "-1 -1", when there is no state that hold all the limit's.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
how to solve problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    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 states

    And each state may iterate from 0 to 5 (maximum capacity of an edge), so multiply by 6. 12.825.540

    Which 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/xjL2jTS4

    I 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.
    → Reply
14 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it
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.100000000
Verdict: WA
quote 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.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any hint for problem D ? 
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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..)
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      EDIT:  NO, that is wrong :( .  see rng_58's solution. :)
      → Reply