Unofficial Editorial for Atcoder ABC 191

Revision en6, by Naithani, 2021-02-07 12:10:50

Problem A :

The ball is invisible for time: [S, T], which means it will be invisible for the section: [S*V, T*V]. To hit the ball by Akoi D must not lie in this section, that means D should be less than S * V or greater than T * V

Link to my code

Problem B:

Just a straight forward implementation, print those numbers which are not equal to X.

Link to my code

Problem C:

Key Point: There are no white cells inside the polygon of black cells, so, you can assume the polygon as a contiguous block of black cells, whose sides we have to find.

To find sides: For every black cell X, check its adjacent (left, right, up & down) cels (let's say each cell Y), we have to check the followings:

  1. If Y is black then it doesn't contribute to the answer.

  2. If Y is white, then check whether that edge is already added or not. If it is not added then add this side to the answer.

To check some side is added or not, you can use loops or maintain some data structure like set (in C++). I've used the set in my code.

Link to my code

Problem D:

Consider a vertical line that passes through the center of the circle (h, k). Iterate on the integer points (let say each point P) of that line such that those points lie inside the circle i.e. points: (h, k-r) to (h, k+r), r is the radius of the circle. For each point P, find the number of integer points on the left and right of P such that they lie inside the circle.

To find the number of points you can use the binary search.

NOTE: Maintain the precisions.

Link to my code

Problem E:

You can rephrase the problem statement to: for each node find the least weighted cycle or say it is impossible. To find the least weighted cycle one can use Dijkstra's algorithm. For each node s, find the shortest path to other nodes, and then go to those nodes and check for the cycle with the least weighted path.

Link to my code

Thanks :)

Tags abc191, #editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Naithani 2021-02-07 12:10:50 0 (published)
en5 English Naithani 2021-02-07 12:09:33 1 Tiny change: 'n\n\nThank :)\n' -> 'n\n\nThanks :)\n'
en4 English Naithani 2021-02-07 12:09:16 446 Tiny change: '92353)\n\n' -> '92353)\n\n\nThank :)\n'
en3 English Naithani 2021-02-07 11:56:32 1140 Tiny change: ' answer.\n2. If `Y' -> ' answer.\n\n2. If `Y'
en2 English Naithani 2021-02-07 11:05:08 227
en1 English Naithani 2021-02-07 10:53:58 577 Initial revision (saved to drafts)