Codeforces Round #532 (Div. 2) — Editorial

21 month(s) ago, # ^ |

← Rev. 2 →

+12

For D,

Let us solve this question assuming that the king is at the centre of the board at (500, 500). (If it is not at the centre, then we need around at max 499 steps to reach it as it could have been at the corner.)

Once you are at the centre, consider the four newly created divisions (or quadrants) of the board. Choose the 3 divisions which do not have the minimum number of rooks. By doing this you ensure that the combination of these 3 divisions has atleast 666 * 3/4 >= 499 rooks otherwise you have not chosen the top 3 divisions correctly (basic pigeon hole principle).

From now, just move the king away from the section with the minimum rooks ( < 499 in any case) along the diagonal (this ensures that rows and cols are handled together).

Keep doing this till the corner. You are bound to get a check by a rook as no. of steps required to reach corner from the centre is 499 and from php we know that there are atleast 499 rooks there.

Eg. 1. king at 999,999

move king to 500,500
let quadrant IV have minimum rooks (167). So quads I, II, III have 499 rooks combined.
while going towards 0,0 (top left point inside quad II), we will end up checking from rows 500 to 1 and cols 500 to 1 simultaneously while going towards the top left diagonal.
since no. of steps to reach the diagonal is at max 499 and we know that there are 499 rooks in these 3 quads, we will get a check(mate) for sure.

NOTE: I may be off with the numbers by 1 or 2..but i hope you get the point. All of this will occur in less than 1000 steps

A good question it sure is.

→ Reply

21 month(s) ago, # ^ |

← Rev. 2 →

There is one corner case you need to handle, which is if rooks are on the king's diagonals. You will need to go the nearest row and col together to eliminate the rook as you cannot eat it. I'll fix and share a code with good comments soon

→ Reply

Code: https://codeforces.com/contest/1100/submission/48345032

21 month(s) ago, # ^ |

I have tried to comment as much as I could Have a look

Java 8: 48414117

→ Reply

atlasworld

21 month(s) ago, # |

hello den2204 2nd example :

gives us k = 3 ;

so our top order will be (2-->1) (4--->3) , so while removing edges with weights <=k , we actually disconnects the graph . And how will you decide the priority between 2 and 3 or 2 and 4 .

in the above example 1-->3 has wt. 3 , so how to check this in above topolozical order ?

→ Reply

TadijaSebez

21 month(s) ago, # |

+56

F can be solved in O((n + q)logC).

System tests for D are too weak. My submission that moves king to the center and then allways moves it to the same corner passed system test.

Code: https://codeforces.com/contest/1100/submission/48362464

→ Reply

vladalos

21 month(s) ago, # ^ |

Can you shortly explain your solution for F?

→ Reply

TadijaSebez

21 month(s) ago, # ^ |

+25

It's very similar to the standard Gaussian elimination with xors. The difference is that when adding new element to the structure, if we already have an element with the same highest bit, then we keep one with the highest index in the array and continue the process with the other.

→ Reply

twangal

21 month(s) ago, # ^ |

Actually you can serve queries online if you precompute and store the linear basis for each position.

→ Reply

21 month(s) ago, # |

← Rev. 8 →

+48

Good Explanation for C

the Radius of the innar circle = R and radius of the outer circle = r by connect the center point of the innar circle with two center points of the other consective small circles , the angle (a) = 360 / n and the traingle is Isosceles triangle from the cousine law we will reach

#include "bits/stdc++.h"
using namespace std;
const long double PI = acos(-1);
int main()
{
  int n , R;
  cin>>n>>R;
  cout<<fixed<<setprecision(7)<<sin(PI / n) / (1 &mdash; sin(PI / n));
}

→ Reply

21 month(s) ago, # ^ |

Abdo_kamr see this

→ Reply

giorgosgiapis

21 month(s) ago, # ^ |

Nice explanation. One could also note that the polygon formed by connecting the centers of adjacent outer circles is a regular n-gon inscribed in a circle of radius R + r.

→ Reply

21 month(s) ago, # ^ |

thank's bro . great observation

→ Reply

_Shravann_

21 month(s) ago, # ^ |

But , how would you deduce the value of 'r' (or the radius of the outer circle) from that sir ???. I couldn't get your point

→ Reply

giorgosgiapis

21 month(s) ago, # ^ |

From basic geometry we know that side length of a regular n-gon with circumradius R' is $\text{[math]}$ . In our case we observe that the side length of our polygon is 2r (r is unknown) and that the circumradius is R + r. Therefore, we get that $\text{[math]}$ and solve for r.

→ Reply

_Shravann_

21 month(s) ago, # ^ |

That's really awesome sir !!! Thanks a lot !

→ Reply

usernameson

21 month(s) ago, # ^ |

Another approach is to note that if you cut the triangle in your diagram in half (bisect the angle a) you have a right angle triangle where the hypotenuse is the line connecting the centres of the big circle and little circle. This gives $\text{[math]}$ .

→ Reply

baudelaire

21 month(s) ago, # ^ |

Thank you very much! This helped me a lot.

→ Reply

_Evoiz_

21 month(s) ago, # ^ |

← Rev. 2 →

why (r+r)^b ? it's (r+r)^2 and how you get second equation ? i think it will be (2*r)^2 = 2 * (R+r)^2 *(1-cos(a))

→ Reply

21 month(s) ago, # ^ |

Sorry , it's ^2 not b I has a mistake while typing in the second equation try to take (R + r)^2 as a common factor and you will get (2r)^2 = (R + r)^2 * (1 — cos(a))

→ Reply

_Evoiz_

21 month(s) ago, # ^ |

← Rev. 2 →

let say x=(R+r)^2 then: x+x-2*x * cos(a) take x as common factor will be x*(1+1+2*cos(a)) then: x*(2+2*cos(a)) take 2 as common factor from(2+2*cos(a)) it will be x * 2 * (1-cos(a) )

→ Reply

_Evoiz_

21 month(s) ago, # ^ |

for more let R=2 , r=3 , cos(a)=1/2=0.5; the res for first one will be 25 + 25 — 2 * 5 * 5 * 0.5=25 but in you second one will be 25 * 0.5=12.5

→ Reply

21 month(s) ago, # ^ |

Sorry , I has reviewed my solution . see the new update of the photo :)

→ Reply

bhuvnesh97

21 month(s) ago, # ^ |

I think there is one more easy way to do it.. draw the perpendicular from the common point of both outer circle(seen from fig) or equivalently can say bisector of angle a and it will pass through center of the inner circle and after this you can apply simple sin(ang)=r/(r+R) where r=radius of small circle ,R radius of outer circle and ang will be PI/N it all can be easily proved so no worry.. i did it same way during contest and it will work.

→ Reply

bhuvnesh97

21 month(s) ago, # ^ |

easy explanation

→ Reply

Bug_Debug

21 month(s) ago, # ^ |

Why angle is PI/n?.Please explain. Where PI 3.14159

→ Reply

http://codeforces.com/contest/1100/submission/48402367

21 month(s) ago, # ^ |

no , PI here equal 180 not 3.14

→ Reply

Mackenzie

21 month(s) ago, # ^ |

Why it can't solve just clearing 'R' in the 6th step? Without apply the trigonometric identity...

→ Reply

JonnyDavies

20 months ago, # ^ |

I know it's been a while since this contest but this solution for 1100C how does this result in the radius of the outer circle?

scanf("%lf%lf",&n,&r);
db sn=sin(3.1415926535897/n);

printf("%.10lf\n", sn * r / (1 - sn) );

Specifically the final equation -> (sn * r) / (1 — sn). I understand that the first statement calculates the angle of the inner circle. Could someone explain or send me a link to some theory in how this results to the outer circle radius?

→ Reply

Romansp

21 month(s) ago, # |

why D is falling? I just can not understand, plz help

→ Reply

bartkaw

21 month(s) ago, # ^ |

while(kx!=500&&ky!=500)

Should be || instead &&.

→ Reply

Romansp

21 month(s) ago, # ^ |

Thank!

→ Reply

NoTiNGeM

18 months ago, # ^ |

I had same problem and used your solution and got AC but can't understand why || works and && doesn't. can you explain?

→ Reply

olpetOdessaONU

21 month(s) ago, # |

← Rev. 2 →

-9

I think, author's solution for D is wrong. For example, put the king to the center, put 333 rooks to positions 1 1, 2 2, 3 3,... 333 333, and other 333 rooks to positions 999 999, 998 998, 997 997,... In such case the king has no chance to win.

I tried to find additional restrictions in the task, excluding such an example, but don't see it. Am I wrong?

UPD: Thank you, guys, you are right

→ Reply

neal

21 month(s) ago, # ^ |

+17

Just head straight to (999, 1) and you'll win.

→ Reply

filippos

21 month(s) ago, # ^ |

← Rev. 3 →

You can move from (500, 500) to (1, 999). It will take you 499 steps while the opponent would have to move 666 rooks

→ Reply

21 month(s) ago, # |

← Rev. 2 →

Could somebody explain the time complexity of the hull method in F please?

I am seeing a O((nlog(n) + q)log²C) time complexity, with the recurrence

T(n) = O(n)log²C + T(n / 2) + T(n / 2)

→ Reply

RobeZH

21 month(s) ago, # ^ |

← Rev. 3 →

There are two parts. The first part is answering the queries, and the second part is divide-and-conquer itself. We should see them as seperate parts.

For the first part, each query costs log²(C), which is the time of combining the left basis and the right basis, so answering the total q queries will cost $\text{[math]}$

For the second part, calculating the left basis list and the right basis list both costs $\text{[math]}$ , so the recurrence will be $\text{[math]}$ . Then $\text{[math]}$

So totally the complexity will be something like $\text{[math]}$ .

→ Reply

21 month(s) ago, # ^ |

The part about the queries don't confuse me. Ignoring the O(logC) components.

You mentioned that the recurrence is:

$\text{[math]}$ with the solution T(n) = O(nlogn)

But they have reported the time complexity as O(n).

→ Reply

RobeZH

21 month(s) ago, # ^ |

I am trying to understand you.

What do you mean by But they have reported the time complexity as O(n). ?

→ Reply

21 month(s) ago, # ^ |

Oh, thanks for being so patient.

In the last line of the editorial they have written:

Complexity is O((n + q)log²C) or O(nlog²C + q).

This has an O(n) term, but no O(nlog(n)) term, and that is what I meant by

But they have reported the time complexity as O(n).`

I feel that they should have a O(nlogn) term in the complexity.

→ Reply

RobeZH

21 month(s) ago, # ^ |

Yes. I think so too.

→ Reply

(https://codeforces.com/contest/1100/submission/48425126)

21 month(s) ago, # ^ |

den2204 could you take a look at this?

→ Reply

den2204

21 month(s) ago, # ^ |

More strictly, complexity of first solution is $\text{[math]}$ , because we can add vector to hull in time proportional to the size of the basis — $\text{[math]}$ .

→ Reply

MagicSpark

21 month(s) ago, # |

An International Grandmater(djq_cpp,He is only 13!!!!) told me there are answer code for problem F on the Internet.I copy the code and get accepted(I didn't take part in the contest.).So F is a problem appeared before.That's really bad!!!Submittion 48412606

→ Reply

TooNewbie

21 month(s) ago, # |

+13

Problem D 091 there: http://olympiads.win.tue.nl/imo/soviet/RusMath.html

→ Reply

bhuvnesh97

21 month(s) ago, # |

← Rev. 2 →

-26

→ Reply

brdy

21 month(s) ago, # ^ |

+26

Seriously dude, it is test case 1. Don't expect other people to help you debug when you haven't put in the effort.

→ Reply

21 month(s) ago, # |

← Rev. 2 →

Why first solution fails and second one passes for E?

First solution

Code

while(!q.empty()){
    int s=q.front();
    q.pop();

    for(auto t:v[s]){
        in[t]--;
        if(!in[t]){
            deg[t]=deg[s]+1;
            q.push(t);
        }
    }
}

vector<int>sol;
for(int i=1;i<=m;i++){
    if(e[i].w<=k){
        if(deg[e[i].from]>deg[e[i].to])sol.push_back(i);
    }
}

Second solution

Code

int cnt=0;
while(!q.empty()){
    int s=q.front();
    q.pop();
    deg[s]=++cnt; //difference is here

    for(auto t:v[s]){
        in[t]--;
        if(!in[t]){
            q.push(t);
        }
    }
}

vector<int>sol;
for(int i=1;i<=m;i++){
    if(e[i].w<=k){
        if(deg[e[i].from]>deg[e[i].to])sol.push_back(i);
    }
}

→ Reply

bigbigbigcat111

21 month(s) ago, # ^ |

← Rev. 5 →

The order(deg) of every vertex need to be different!

There can be CIRCLE in the edges connected those vertexs with same order.

→ Reply

21 month(s) ago, # ^ |

I don't really get it

→ Reply

bigbigbigcat111

21 month(s) ago, # ^ |

← Rev. 3 →

consider input below,

→ Reply

21 month(s) ago, # ^ |

Thanks :)

→ Reply

21 month(s) ago, # ^ |

For such a case, how do you figure out which link to reverse? Obviously you cannot give answer as 1 2 3 for vertices (graph is adjacency list implementation)

→ Reply

bigbigbigcat111

21 month(s) ago, # ^ |

Besides, how to post part of the submission?

→ Reply