Lewin's blog

By Lewin, history, 8 years ago, In English
Viscious Keyboard
Valued Keys
Voltage Keepsake
Volatile Kite
Vulnerable Kerbals
Varying Kibibits
Verifying Kingdom
Tutorial of VK Cup 2017 - Round 2
  • Vote: I like it
  • +63
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Fast editorial! Great!

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Div1B can be solved in O(n*log(D)) by binary searching on d. For a particular d if a line passes through the circles with centre i,i+1,i+2 and radius d then concave polygon can be formed. My submission

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

"First, we can make only one angle of the polygon nonconvex." Why?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We dont need more.

    If we can find 3 non-consecutive vertices of polygon moved for some D so that it becomes nonconvex, we can find 3 consecutive vertices of this polygon that being moved for the same D also make it nonconvex. If some vertex can become unconvex with some other vertex after moving them, it will also become unconvex with all of the vertices that are between them after moving these vertices for the same or lower D.

»
8 years ago, # |
Rev. 3   Vote: I like it -19 Vote: I do not like it

nice

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

In my impression, Div1 A is tough to solve in some language such as Java and C#. See this (26436569). It is almost same as expected solution. However, it failed at case 71.

I want to know whether this problem can be solved or not.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

    I got the same error so that means...probably not. Maybe test case 71 should not be counted for some languages?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Hi guys, quickly check out accepted solutions here http://mirror.codeforces.com/contest/801/status

      and filter by Java | accepted | Problem C

      we can learn something from how accepted Java solutions solved it.

      Take care

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        After looking through different solutions, they all look identical to mine besides some names, nothing big.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        After slowly making changes in my code until it works, this is what I came to:

        I was calculating the amount of time a device would need the charger for to stay alive , so I was using Math.max(0, (b[i] — a[i] * time)/p) and compared the total to time.

        What you were doing was using the required power as in the amount of energy per second the charger would need to have all of the devices living a.k.a. using Math.max(0, (a[i] — b[i]/time)) and comparing that to p.

        There are also other people who calculate the overall energy with Math.max(0,a[i]*time-b) and comparing that to time*P. This is what the editorial used.

        The only difference that caused power to work is that the numbers that are being worked with are smaller, meaning no calculation error. Thinking purely mathematically, all three way would work, but since the computer is not perfect at math, only one way works in practice.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        To get rid of the errors in calculations with fractional numbers, try to avoid multiplications/divisions with double values. Instead do the mul/div operations with integers and leave only comparisons to doubles. In my solution, I check only t <= sumB/ (sumA - p). sumA and sumB are the sums of those a[i] and b[i] for which t > b[i]/a[i]. Therefore all multiplication and division occurs with integers.

        Second thing worth-mentioning is that you can take high value in binary search to be a power of two. That would help to get integer values for t, most of the time.

        Hope, this helps.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same problem. setting the high value in binary search to 1e10 + 10 passes Test #71, but fails in Test #73. Setting it to 1e10 + 20, passes #73 but fails in #80 in my solution. Can't get further than that.

    Judges should clarify this issue.

»
8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Cool)) All the titles of the problems are "V... K..."
P.S. Ранее условия и названия, в частности, были прочитаны на русском языке.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In D we shouldn't consider f(S) >= x as numbers, but rather as a vector of digits (what is currently not specified).

»
8 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

In div2C, I think the max answer can be at most around 10^10... The max answer will be generated by a case like:

100000 99999

1 100000

1 100000

........

........

1 100000

Could you verify?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Yes. It can be proved in this manner. Since p & a(i)'s are integers, this essentially means the sum of a(i)'s at t = 2sec < sum of a(i)'s at t = 1sec because p < sum of a(i)'s. This means sum of a(i)'s will decrease by atleast 1 after each second.
    Therfore maximum answere possible = sum of all a(i)'s in the start which is nothing but (10 ^ 5) * (10 ^ 5).

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I have a question concerning problem Div.2 C:

Why is the maximum answer 1e14?

I had trouble finding the upper limit in the contest so I ended up putting it 1e20 or more, I solved it.

Any help is appreciated.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    in the worst case, p + 1 = sum of all a[i]. In that case, you need sum of all b[i] seconds to run out of energy

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In that case, the maximum answer is less than 1e14.

      Sum of all b[i] is 1e10. Therefore if the upper bound for binary search was 1e10, it would be fairly enough to solve the problem.

      Please correct me if I'm wrong.

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        yes of course it's 10^10. My solution has it's upper bound at 1e11 and still pass the system test

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I didn't participe but I read tasks...

I have questions for both A and B div 1. I would submit same solutions as written in editorial but some parts are not clear at all to me — they are intuitive but again I would like to hear proof.

1.In A task when time needed to charge all devices is smaller than searched time — can you show construcktive algorithm of charging everything on way that none of devices will be empty during this period ?

2.For B task. Why are we making always non-convex polygon, maybe sometime is more optimal to make polygon with edge intersections ?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If sum of demands <= p then this means you can come back to charge the same device after 1 second and it wouldn't have lost all of the charge.
    Let's suppose it the device starts charging from device 1 then device 2 .... device n and repeat. For each device i it gives it a(i) charge i.e. which can support it for 1 second
    Now since p > sum of all a(i)'s this essentially means it will be back at device 1 for the same charging cycle in <= 1sec and will re charge each device before it has fully drained all of it's charge of previous cycle.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey I didn't get it completely what you are saying! Can you explain in a bit detail ?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What part you didn't understand?

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How much time do you spend supplying i'th device?

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The time sufficient such that ith device garners a(i) amount of charge. SO the time in seconds will be a(i) / p seconds.

            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              But this way of charging devices is not working on this testcase

              3 15

              2 1

              5 1

              8 1

              You charge a first device 2/15 seconds. While you're charging amount of energy of the third device will be negative because 2*8/15 is bigger than 1

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have similar doubts on problem A. Here are my thoughts. You don't really need a constructive algorithm to prove that the devices are alive. If you think of it like conservation of energy (charge) — As long as the charger can supply energy of P*T which is greater or equal to the charge required by all devices, an infinitesimally small charge persists on each device.

    I don't know if this is right. Any help is appreciated. Thanks!

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2 C , what happens wrong when I compare the answer to the upper bound used in binary search for the infinity case? WA : 26437983 AC : 26438358

»
8 years ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

Easy ac with long double on cpp. Easy tl/wa with bigdecimal/double on java. Nice ;)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone please help me out in Div2 C problem. I don't know why i keep getting WA on test 31. I guess the problem might be lying in the error bound. Code: 26438641

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer for 31 is -1. Don't use a certain time to determine if it is going on forever. Just check if the sum of the power usages is less than or equal to P.

»
8 years ago, # |
Rev. 4   Vote: I like it +26 Vote: I do not like it

For Division 2 C, I did everything the editorial said and even now, I am getting a .0003 error on test case 71. I can't seem to do better no matter what. Does anyone know why? Code: 26438965

Also, when I used BigDecimal, I got runtime error on testcase 10.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Crisp and clear explanations in the editorial.

»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

In div1a (772A - Voltage Keepsake), you can use fewer runs of binary search by using the trick described by Um_nik in his blog: http://mirror.codeforces.com/blog/entry/49189?locale=en. It wasn't necessary today but it allowed making a program much faster (/ more precise). But please note that this thing has nothing to do with Java issues in this particular problem.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why there is not a fixed value for infinity .. like 1e10 or anything else (limits) in problem C

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you are asking why there isn't a value where you can safely say that the power will last forever, then their actually is, 1e14 + 1

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please elaborate on why the upper limit is 1e14 + 1?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For 772A Voltage Keepsake, isn't Xi = max(0,T*ai — bi)?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you're right, because we want the power to be charged, so Xi = max(0, T * a — b) seems just what we need.

    P.S.: it must be a mistake, the author's code uses Xi = max(0, T * a — b).

»
8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Hello:

  1. In 772A - Voltage Keepsake how are you able to assume that the maximum for binary search is 1014? Where does this maximum come from?

  2. Also in the tutorial for 772A - Voltage Keepsake, you say Xi = max(0, bi - T * ai), however in your example code you write: ld need=max(0.0L, (imid-exhaust[i])*a[i]); Upon my own testing, I believe the condition in the code is right, and it should be updated to Xi = max(0, T * ai - bi).

Thanks

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Hello, I think I just (partially) figured out the answer to my question #1 (why is the maximum 1014). Feel free to correct me if I am wrong.

    The largest time is produced if the power of the charger is one less than the sum of all the charges needed by the devices (if ).

    EDIT: It does not seem that 1e14 is the lowest possible upper bound though... I'm not sure why it was chosen... see my other comment below for more info

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you elaborate on why we multiply those two numbers 1e9 * 1e5 ? it is the maximum TIME we seek after all.

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In Div1-D, the inclusion-exclusion approach, how to calculate the modified f(x) function?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I have a solution with inclusion-exclusion .

    You can see details Here ! 26449626

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do these array mean in your solution: cnt, sum, sq, g?

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        let S[i] : be the multiset of numbers which all of them has following condition :

        for every x in S[i]:

        for every k , kth digit of x is greater or equal than kth digit of i.

        now :

        sum[i] is equal to sum of these elements.

        sq[i] is equal to sum of squares of this elements.

        g[i] is equal to the answer(the thing that question want!) for all of the subset of S[i]

»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Can anyone please describe the solution of Div1 C with more details .

»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In div 1 C how do we create the edges in a suitable time?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    the condition that we have an edge(directed) (u, v) :

    gcd(u, m) | v , that's equal to gcd(u, m) | gcd(v, m)

    so , replace each i , with gcd(i ,m),

    now you want a path that each number is divisor of the next number .

    you can do it with a simple dp .

    see this solution for more details ! 26435471

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thx man that helped! :)

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you explain for me why gcd(u, m) | v, that's equal to gcd(u, m) | gcd(v, m) ?

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        suppose that d = (u, m), d|v

        so d|u, d|m, d|v

        so d|m, d|v

        so d|(v, m)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E/div2: there are two directed edges between two nodes i and j if and only if gcd(n, i) = gcd(n, j). Can anyone give a proof of this?

Any help is appreciated.

Sory for my poor English.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we can prove that, exist x make ix ≡ j modn if and only if gcd(n, i)|gcd(n, j)

    if ix ≡ j modn, gcd(n, j) = gcd(n, kn + ix) = gcd(n, ix). apparently, gcd(n, i)|gcd(n, j);

    the other way, if gcd(n, i)|gcd(n, j), then exist x make gcd(n, ix) = gcd(n, j), and j = ix + kn, too.

    so if there are two directed edges between i and j, and then gcd(n, i)|gcd(n, j) and gcd(n, j)|gcd(n, i), so, gcd(n, i) = gcd(n, j);

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In problem B, why do we only need to consider every 3 consecutive points? What I did was that, for each point, I took its distance from all line segments such that atleast one endpoint of that segment is adjacent to the given point.

eg. A=(0,0), B=(1000,500), C=(1001,500), D=(1000,-500)
Here, distance from A to line BC is less than distance from A to line BD.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am also having difficulty with the proof of correctness.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In this case, the optimal answer is actually the distance from point B to line AC.

    I guess the difficulty may be when the projection of the point doesn't lie in the segment. In that case, I think we can claim that's never an optimal solution, and doesn't need to be considered.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, in this case, that is true. But in general, can we say that given three consecutive vertices A, B and C, there can never exist some vertex D such that distance from B to line AD is less than distance from B to line AC and that this is the final answer?

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in div1E , how does the checker check if the tree in output is isomorphic to the tree in input?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Tree hashing. For example computing the centroid of the tree, then we can hash the subtrees by imagining the subtree as a bracket subsequence, and for each internal node, we sort the subtrees oriented from it by hash value.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Here's my checker implementation: https://pastebin.com/N5nLQUrH

    I just compute the bracket sequence, and don't do any hashing.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My dear!I have got at least 15 WA on div2 C!!!it's on the test 71 or 74 ,Could you please give me some suggestions?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    cause it's a valid point of time to make all devices alive with 0 units of power, you didn't consider that.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks Lewin for that fast and well prepared tutorial, nice contest BTW.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

801C - Voltage Keepsake why the max answer is 1e14 ?

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    It's not. The maximum answer is 1010.

    Let's say I have 105 devices, each uses 1 unit of charge per second, and starts with 105 units of charge. The charger is p = 99999. The answer should be 1010.

    Edit: this scenario is the same as test #66.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah I consider it as 1e10 as p has to be strictly less than the summation of the consumption and it's max val 1e5*1e5 ...but I got confused with 1e14 at the tutorial , thanks bro.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem C why the sum suply of these bi more than p ,than output -1?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It is if the sum of a[i]s is less than or equal to P, then the output is -1. The idea is that the total voltage will always increase through time.

»
8 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

div 1 B can be solved in O(n): We can draw a line through the nearest two points with a given point, and it is easy to see that the answer is half the length of the perpendicular from the point to this line (and we have three options to draw a straight line through two of the three points). That is, the problem is reduced to the search for a minimum of three heights of triangles formed by every three neighboring points. /// Мы можем провести прямую через ближайшие с данной точкой две точки, и нетрудно убедиться, что ответом будет половина длины перпендикуляра от точки к этой прямой (причём у нас есть три варианта провести прямую через две из трех точек). То есть задача сводится к поиску минимума из трёх высот треугольников, образованных каждыми тремя соседними точками. /// http://mirror.codeforces.com/contest/772/submission/26468460

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

The upper bound is 1e10, not 1e14.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2-D, firstly I used Heron's formula to get triangular's area but repeatedly got wrong answer. After fixxing it by calculating with vector property, I got accepted.

Is it dangerous to use heron's formula in calculating triangular's area usually??

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here, and I guess it is just the language precision in floating number that causes.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone explain this line of the code given in the editorial for 772C — Vulnerable Kerbals:

    int print = (long long) b * my_pow(a, cnt_coprime, m) % m;
    print = (long long) print * my_gcd(m, nxt) / my_gcd(m, previous) % m;

Thanks in advance :)

UPD: DONE.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help explain in B. Volatile Kite if i am using int for coordinates of the vertex i am getting wrong answer but using double AC,in input they are integer