Rollo's blog

By Rollo, 2 months 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  

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution link is not open for us.

»
2 months 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! :)

»
2 months 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.

»
2 months 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)

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

    define ll long long

    define f(i,n) for(ll i=0;i<n;i++)

    vector B;//prefix sum vector ll p;//for partial ll check=0; ll cnt=0;

    ll fun(ll k){ ll ind=lower_bound(B.begin(),B.end(),k+p)-B.begin(); //cout << ind << "....lower_bound" << endl; if( B[ind]-p==k ) { //cout << "Exact" << endl; check=1; }else{ //cout << "Not Exact" << endl; check=2; } return ind; } int main(){ ll n,q; cin>>n>>q; ll a[n],k[q]; f(i,n) cin>>a[i]; f(i,n) cin>>k[i];

    B.pb(a[0]);
    for(ll i=1;i<n;i++){
        B.pb(B[i-1]+a[i]);
    }
    
    //f(i,n) cout << B[i]<<" ";pn;
    
    p=0;
    ll ans=0;
    f(i,q){
        if( k[i] >= (B[n-1]-p) ){
            ans=n;
            p=0;
        }else{
            ll ind = fun(k[i]);
            if( check==1 ){
                ans = n-ind-1;
            }else if( check==2 ){
                ans = n-ind;
            }
            p+=k[i];
        }
        cout << ans << endl;
    }
    return 0;

    }

    can you help me?? I am getting WA on 4th test case.. :(

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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)

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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

    • »
      »
      »
      6 weeks 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????

»
2 months 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!!! :(

  • »
    »
    7 weeks 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.

»
7 weeks 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.

  • »
    »
    7 weeks 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.

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

      No I am not ignoring that. For the test case suggested by you the solution comes out correctly as 2 1.

      I am re-calculating the factor at each step. So I am not ignoring the case when the current index warrior is still alive.

  • »
    »
    7 weeks 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

    • »
      »
      »
      7 weeks 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. :)

      • »
        »
        »
        »
        7 weeks 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!

»
7 weeks 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.

»
7 weeks 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.

  • »
    »
    7 weeks 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 :)

»
7 weeks 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?

  • »
    »
    7 weeks 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.

»
7 weeks 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 ?

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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 . :) .

      • »
        »
        »
        »
        7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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 ?

        • »
          »
          »
          »
          »
          7 weeks 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 .

          • »
            »
            »
            »
            »
            »
            7 weeks 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.

        • »
          »
          »
          »
          »
          7 weeks 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 ?

      • »
        »
        »
        »
        7 weeks 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.

  • »
    »
    7 weeks 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.

    • »
      »
      »
      7 weeks 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 .

    • »
      »
      »
      6 weeks 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????

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it
»
7 weeks 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.

  • »
    »
    6 weeks 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????

»
7 weeks 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. :)

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone simply explan me of problem C. i reading the problem statement in a big while but I still dont understand what they want in this problem. It will be better if you tell me details based on the test cases examples.

Thanks in advance.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
.
»
6 weeks 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

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

may i ask what do u mean by mask in problem A, and the word 'exit' is a typo right ?

»
6 weeks 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??

  • »
    »
    6 weeks 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.

»
5 weeks 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

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

Can anyone help me with my solution to problem C? It is failing on test case #4 but only the first number is different for some reason: I output 999 while they output 1000, but everything after that looks like the same. Does anyone know why this might be the case? Am I missing an edge case or something? Thanks. Submission here: 39276012

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

    Never mind, got it to work in case anyone is interested: 39277335. It was an edge case indeed, when I did k = k-1 and then b = k-1 b was really k-2, I need to be more careful. Also needed to use long vs. int.