Commented Solutions to Codeforces Round #364

Правка en7, от Noble_Mushtak, 2016-07-29 04:22:50

All solutions below are thoroughly commented and 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 solutions for 701E and 701F (could not figure out on my own) really helped me understand the problems better. Also, I'm sorry if the later solutions are more clunky; I'm not used to solving problems of that difficulty. 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. 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 only briefly mention that solutions must 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 lots of detail if you're not so good at working with trees. Here's my implementation of the editorial solution.

701F — Break Up

I could not understand from the editorial's explanation how to find the second edge in the case of two edges until I looked at the dfs2() function from this solution to 701F from Vosatorp, so thanks to them for this solution!

Basically, in our depth first search, if an edge from va to vb in path from s to t is unnecessary, then there will contain a cycle with vb and a vertex before vb in the path. This is because since the edge is unnecessary, there exists another path from s to t without that edge. Let vl be the vertex farthest along the original path that is before vb on this new path. and vr be the vertex closest to vb that is after it on this new path. Then, using the old path, we get to vb, then vr and using the new path, we get to vl. Thus, by this process, we have created a cycle with both vb and vl, proving our original point. Ergo, by contrapositives, edges where vb is not in any cycle with a previous vertex in the path are necessary.

This process seems to be a variation on [Tarjan's Bridge-Finding algorithm](https://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan.27s_Bridge-finding_algorithm) which I did not know before.

Other than that proof of correctness, everything else is pretty much explained in the comments of my re-writing of Vosatorp's solution in C, without vector.

700D — Huffman Coding on Segment

Coming when I have enough time/experience to understand the solution!

700E — Cool Slogans

Coming when I have enough time/experience to understand the 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)