Odin-'s blog

Codeforces Round #478 (Div. 2), Editorial
By Odin-, 7 years ago, In English
Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution

Tutorial is loading...

Solution

  • Vote: I like it
  • +85
  • Vote: I do not like it

Comments Comments (51)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution link is not open for us.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm not allowed to see the solutions. Could you please fix it? I'm very interested in the solution of problem E. Thanks! :)

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

Last equality in D : aVxj - Vyi = aVxi - Vyi.

I think that's wrong because Vyi in both sides looks pretty suspicious.

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

another solution for C: have a set of pair of partial sum and index of any a(i) and S that shows how many warriors died so we put S = S + k(i) then if S >= n then we put S = 0 else we get a lower_bound of(s).

(sorry for bad English)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In question D. How to check two point will be parallel?

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

    if they are moving in the same direction with the same speed.

    iff (Vxi, Vyi) = (Vxj, Vyj)

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

      But, for example, one ghost moving with V = (2, 0) will be parallel with another one with V = ( - 2, 0). Isn't it (Vxi, Vyi) = k * (Vxj, Vyj) the condition?

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

        We will not count those in the first place not that

        aVx - Vy for the first is 2a for second is  - 2a

        unless a is 0, in which they will actually collide. here a >=1

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

Only triangle in sample in problem E? I didn't realize that the non-weighted mean of all points is not the center of mass(but it holds for triangles) the whole night!!! :(

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

    This is a fairly non-trivial fact and I wasn't aware of it either !

    Here's a useful link explaining the same.

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

Can someone please tell me why my code is wrong for problem Div2 C? — 37830313

I first calculated the sum of all the strengths of the warriors in the array sum[x]. Next what I have is a value as factor which is calculated based on the solution of previous round. factor basically tells us what value from the sum array is to be subtracted while calculating the index for next round.

start tells us what part of sum we need to consider for this round.

C1:- If the ceil search returns -1 then all the warriors are dead. Reset factor to 0 and start to 0.

C2:- If the ceil search returns a valid index and value at that index is equal to the one we need, then I set the start as index+1 i.e the index for next ceil search and the factor is calculated. Otherwise set the start as index (because this warrior is still alive) and corresponding factor is again calculated.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You have to search such value which is sum of arrows until all warriors dead. When all warriors are dead, reset the value to 0 and repeat the previous step. Your approach is not considering about remaining helath of warrior (which is warrior[index]) in C2.

    Ex) warriors : 3 2

    arrows : 2 2

    After first arrow is shoot, first warrior still has 1 hp. Your code might be ignoring it.

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

    Hi! The problem is in one of the last lines, when you check if(index-1<0). If that is true, you assign factor = firenow. What if factor wasn't zero? You discard all the arrows that were shooted before. I changed it to factor += firenow and got AC. You can check my submission 37843897 :)

    Your code fails for cases like:

    2 3
10 10
3 3 5

    because it returns 2 2 2, but it should return 2 2 1.

    PD: there are easier ways to code binary search (if you really don't want to use upper_bound, which is even easier) :P

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

      Yes, my code does not follow a very clean approach, and probably this is why I overlooked this case.

      Anyways, thank you for helping in figuring out my mistake. :)

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

        You are welcome! If you want, you can check my submission to see how to solve this problem using upper_bound: 37846073. Bye!

        → Reply
»
7 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Problem D is very amazing. Parameters: b, x[i], y[i] are useless for solving it.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please point out why this code does not work 37820945 while this code gets accepted 37840088 ,all i have changed is use vector instead of array. The non working code got stuck in some test cases and outputs only -1 for each query after a while.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Hi! The first one fails because of the arguments you are passing to upper_bound. You are using positions [1...n] of the array a, so a[n+1] has garbage. Remember that binary search assumes the array is sorted, but a[n+1] can be lower than a[n] (we don't know what value is stored in there), so upper_bound probably does some strange things.

    I changed

    cpos = upper_bound(a , a+n+2, at + a[ppos-1]) - a;

    to

    cpos = upper_bound(a , a+n+1, at + a[ppos-1]) - a;

    and got AC. You can check my submission here: 37843999 :)

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to solve problem E by maintaining a transformation matrix T. Whenever I get a type-one query I multiply the Transformation matrix by 3 matrices, (translation, rotation, translation back) according to the rotation of the centroid around the fixed point.

But it seems that as I multiply a lot of doubles, the precision is lost. So did someone manage to solve it with the same idea but in a more precise way?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Yes, I could (using long longs though). However, I needed to move the first point to (0, 0) for more precise computation of the center of mass.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I m bit confused in theoretical proof of D question.

We assumed that two ghosts are colliding, then we found the observation that a*Vix — Viy = a*Vjx — Vjy. Means, This is the necessary condition for two ghosts to collide. But nowhere we have proven that it is sufficient codition for two ghosts to collide.

Pls, can someone prove that a*Vix — Viy = a*Vjx — Vjy is also sufficient condition for collision of two ghosts ?

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

    It is the condition for two ghosts to collide, we found the time of collision on x axis and then checked if it is the same on y axis.

    This is how to check if two moving points will meet or not.

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

      thanks for reply, I have understood the proof. But that's only necessary for two ghosts to collide.

      Initially you have assumed that two ghosts are colliding , and that's why we are comparing their corresponding X and Y co-ordinates.

      but, Can we prove it reverse ? If we are given a*Vix — Viy = a*Vjx — Vjy , then prove that those two will always collide. that's what I am looking for . :) .

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

        actually aVix - Viy = aVjx - Vjy is wrong because it also counts the ghosts that "meet in infinity (speaking physics here)".

        Other words it will consider the ghosts that have the same velocity and the same direction to collide after . thats why we can not start from it as it is a wrong premise that needs modification.

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

          okay fine, let's say,,, we added constrain that

          aVix - Viy = aVjx - Vjy where ( Vix != Vjx ) , now is it possible to proof that this is sufficient condition ?

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

          I am asking for proof, becuase, I had found the observation

          aVix - Viy = aVjx - Vjy , during the contest, but I was not able to proof that it is also sufficient, that's why I am curious, if I was missing something .

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

            Were you able to prove sufficiency ? Even I am getting the same doubt.

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

              check below, in reply of Jakube's reply .

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

          I didn't exactly understand what you mean by counting ghosts that "meet in infinity". Do you mean parallel ghosts ?

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

        a*Vix-Viy = a*Vjx — Vjy plus the condition Vi!=Vj is equivalent to the system of equations that describe a collision. Equivalence gives us both necessity and sufficiency.

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

    a * Vxi - Vyi = a * Vxj - Vyj   (III) is not a sufficient condition.

    Think of it this way. From the first equation X0i + VxiT = X0j + VxjT   (I) you can compute T. So if you pick this computed T, then the first equation (I) is satisfied, and if additionally (III) is satisfied, then also the second equation a * X0i + b + VyiT = a * X0j - b + VyjT   (II) is satisfied (because a * (I) - (III) = (II)).

    Notice, if you can't compute T from (I), then you can compute it from (II), and make the same proof, just with (I) and (II) swapped.

    And if you cannot compute T from both (I) and (II), then there is no solution at all.

    So two ghosts meet, whenever you can compute T (which is equivalent to Vi ≠ Vj), and (III) is satisfied.

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

      thanks,Now I understand it :).

      when we are given a * Vxi - Vyi = a * Vxj - Vy , we can say that at some time 'T', two ghosts will have same 'X' co-ordinate.

      When, two ghosts, have same 'X' co-ordinate, at time T, that at that time, we can prove that they will have same 'Y' co-ordinate as well.

      This is what I missed during the contest :(...

      Nice solution btw. Jakube . :) . thanks a lot .

      → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Video solution to Problem C Valhalla Siege: https://youtu.be/YuBz1keibrM

975C - Valhalla Siege
Codeforces Round 478 (Div. 2)

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

There's some cool geometric theory that I'm fairly sure is equivalent to what you've written for D, but at the same time is (in my opinion) very interesting and easy to miss if you just arrive at the solution through algebra.

We know that in a normal 2D plane, two non parallel lines will cross at some point. But, because of this extra time parameter, two ghosts won't necessarily cross if their intersection occurs at different times for each one. We can actually represent this geometrically by treating time as a third Euclidean dimension (i.e. Make it the z-axis). If we do that, then two intersections on this 3D Euclidean space correspond to actual ghost collisions.

Now, we notice that for two ghosts to collide, the plane spanned by their paths in 3D and the ax+b line is the same! That means we really only have to look for unique planes created by each ghosts' 3D path and the line up at time T, and count collisions for anything that isn't parallel in that plane. I'm pretty sure this boils down to calculating the exact quantities you've listed in your editorial, but I thought it was super cool how you can think about this as planes in 3D.

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

    case :

    2 1 0

    -1 -1 -1

    1 1 1

    output :2

    in this 2 ghost position (-1,-1) and (1,1), at t=1 , their position (-2,-2) ans (2,2)

    so how they collide????

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found solution to problem A very interesting. I didn't use bitmasks in the contest but applied it after I read the solution on here.

Here is the GitHub of all my solutions to this contest, in case anybody wants to refer them. :)

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E

I'm getting WA on test #4. Couldn't find the bug myself. Help needed.

Link

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, how does your solution for problem d make sure that ghosts with antiparallel velocities are not counted??

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I assume you mean "how to make sure that ghosts with parallel velocities are not counted".
    The only case when two ghosts have equal respective (aVx - Vy) 's and parallel V 's is when the two velocities are equal. So, you can compute the answer including parallel velocities and then at the end subtract 2 times the number of pairs with equal velocities.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The E problem is not friendly with the accuracy.

I can't pass the problem without replacing double with long double.

w(ﾟДﾟ)w

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

For D, my submission 51768572 got Accepted but it gets a WA on 

2 1 0
1 2 4
2 1 2

(it outputs -2 when the answer is 0) so maybe you should add that case.

My other solution 51767265 that also got Accepted gets WA on

2 1 0
1 2 2
2 1 1
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

54444361 please some one tell me the error it is working alright with all the possible test cases I can think of PROBLEM -C

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D , Lest's two ghost g1 and g2 having velocity vector v1 and v2 respectively. 1. If v1 and v2 are not parallel then always g1 and g2 should meet at some point. 2. If v1 and v2 are parallel then they should never meet (or always be together but problem says at given moment no two ghost are together).I can't figure out what I'm missing.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, instead of center of mass, I keep track of the hinge co-ordinates. But it doesn't pass due to precision issues. Should there really be so much loss here ? Code

→ Reply