Before contest

Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

16:07:57

Register now »

Codeforces Round #504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)

16:07:57

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | OO0OOO00O0OOO0O0…O | 3280 |

3 | Syloviaely | 3274 |

4 | Um_nik | 3248 |

5 | Petr | 3233 |

6 | fateice | 3230 |

7 | mnbvmar | 3096 |

8 | anta | 3053 |

9 | FizzyDavid | 3050 |

10 | LHiC | 3047 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 164 |

2 | rng_58 | 161 |

3 | tourist | 160 |

4 | Petr | 153 |

5 | csacademy | 151 |

6 | Swistakk | 150 |

7 | Vovuh | 145 |

7 | Um_nik | 145 |

9 | Nickolas | 142 |

10 | PikMike | 140 |

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/17/2018 01:27:03 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

Solution link is not open for us.

Fixed.

Thanks:)

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

Fixed.

Last equality in

D:aV_{xj}-V_{yi}=aV_{xi}-V_{yi}.I think that's wrong because

V_{yi}in both sides looks pretty suspicious.Oh, try now it is fixed now

another solution for C: have a set of pair of

partial sumandindex of any a(i)andSthat shows how many warriors died so we putS = S + k(i)then ifS >= nthen we putS = 0else we get a lower_bound of(s).(sorry for bad English)

## 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];

}

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

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

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

iff (

V_{xi},V_{yi}) = (V_{xj},V_{yj})But, for example, one ghost moving with

V= (2, 0) will be parallel with another one withV= ( - 2, 0). Isn't it (V_{xi},V_{yi}) =k* (V_{xj},V_{yj}) the condition?We will not count those in the first place not that

aV_{x}-V_{y}for the first is 2afor second is - 2aunless a is 0, in which they will actually collide. here a >=1

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

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!!! :(

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

Here's a useful link explaining the same.

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

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.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:

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

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

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

Problem D is very amazing. Parameters: b, x[i], y[i] are useless for solving 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.

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

to

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

Oh thanks for pointing it out.

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?

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.

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

necessarycondition 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

sufficientcondition for collision of two ghosts ?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.

thanks for reply, I have understood the proof. But that's only

necessaryfor 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 . :) .

actually

aV_{ix}-V_{iy}=aV_{jx}-V_{jy}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.

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 ?

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 .Were you able to prove sufficiency ? Even I am getting the same doubt.

check below, in reply of Jakube's reply .

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

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.

a*V_{xi}-V_{yi}=a*V_{xj}-V_{yj}(III) is not a sufficient condition.Think of it this way. From the first equation

X_{0i}+V_{xi}T=X_{0j}+V_{xj}T(I) you can computeT. So if you pick this computedT, then the first equation (I) is satisfied, and if additionally (III) is satisfied, then also the second equationa*X_{0i}+b+V_{yi}T=a*X_{0j}-b+V_{yj}T(II) is satisfied (becausea* (I) - (III) = (II)).Notice, if you can't compute

Tfrom (I), then you can compute it from (II), and make the same proof, just with (I) and (II) swapped.And if you cannot compute

Tfrom both (I) and (II), then there is no solution at all.So two ghosts meet, whenever you can compute

T(which is equivalent toV_{i}≠V_{j}), and (III) is satisfied.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 .

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

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

975C - Осада Вальгаллы

Codeforces Round #478 (Div. 2)

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.

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

They meet at

t= - 1.thanx

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

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.

Problem E

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

Link

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

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

I assume you mean "how to make sure that ghosts with

parallelvelocities are not counted".The only case when two ghosts have equal respective (

aV_{x}-V_{y}) 'sandparallelV's is when the two velocities are equal. So, you can compute the answerincludingparallel velocities and then at the end subtract 2 times the number of pairs with equal velocities.Hmm..i get it .Thank you

The E problem is not friendly with the accuracy.

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

w(ﾟДﾟ)w

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

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.