Commented Solutions to Codeforces Round #364

Правка en1, от Noble_Mushtak, 2016-07-28 19:11:53

All solutions are based on the official editorial. I might start doing this for one or two editorials every month starting now because writing alternate solutions for 701C and 701D and writing a solution for 701E (could not figure out on my own) really helped me understand the problems better. Thanks!

701A — Cards

Their explanation is pretty straight-forward, so here's the solution.

701B — Cells Not Under Attack

Here, I deviate from the editorial in two ways:

  • Because I am using C and do not have set, I instead mark rows and columns as attacked in an array of bools and count the number of attacked rows and columns as I go along.
  • Their formula is n·n - cnt where cnt = szY·n + szX·n - szX·szY. This gives us n·n - szY·n - szX·n + szX·szY = (n - szX)(n - szY). I use the latter in my solution.

Here is my solution for this problem.

701C — They Are Everywhere

The confusing part of their answer is that they're not really clear about when they're talking about looping through the different types of letters in s or all of the letters in order. Here is my implementation of their solution.

701D — As Fast As Possible

Here is my binary search solution with comments. The problem with their explanation here is it's out of order, they never actually show their equation for what I called x, their variable posM convoluted their formula for x, and they never actually solve for what I called y but instead briefly mentions to account for the bus going back.

701E — Connecting Universities

I think the way they explained 701E pretty well other than the fact that lv is unnecessary since lv  =  1 for all v. However, it is missing A LOT of detail if you're not so good at working with trees. Here's my implementation of the editorial solution.

Теги #364, editorial, solutions

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский Noble_Mushtak 2016-07-29 04:23:26 8 fixed link
en7 Английский Noble_Mushtak 2016-07-29 04:22:50 197 added link to tarjan's bridge algorithm
en6 Английский Noble_Mushtak 2016-07-29 04:18:38 888 added proof of correctness to 701F
en5 Английский Noble_Mushtak 2016-07-29 03:47:00 114 added conditional on coming
en4 Английский Noble_Mushtak 2016-07-29 03:43:53 23 explained 701D issues better
en3 Английский Noble_Mushtak 2016-07-29 03:41:46 23 fixed 701E title
en2 Английский Noble_Mushtak 2016-07-29 03:36:09 989 finished problems from Div. 2 (published)
en1 Английский Noble_Mushtak 2016-07-28 19:11:53 2532 Initial revision (saved to drafts)