Codeforces Round #411 Editorial

Revision en1, by saliii, 2017-05-05 08:33:09

We were waiting several weeks tp setting this contest and hope the problem was good enough.

I will write the full editorial in the few next days, now some hints and short solutions exist here.

805A - Fake NP


805B - 3-palindrome


805C - Find Amir / 804A - Find Amir


805D - Minimum number of steps / 804B - Minimum number of steps


805E - Ice cream coloring / 804C - Ice cream coloring


There were some opinion about this sentence of the problem:

Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.

A subgraph S of a graph G is a graph whose set of vertices and set of edges are all subsets of G. And according to this definition, the subgraph can also be empty as a subset of vertices and edges.

A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected. This definition means that the null graph and singleton graph are considered connected, while empty graphs on 2 ≤ n nodes are disconnected.

All of these definitions were from valid articles and it seems more logical. How ever, I should apologize all of the participants because of bad sample tests when some of articles and books didn't accept my opinion.

805F - Expected diameter of a tree / 804D - Expected diameter of a tree


804E - The same permutation

Tags 411, codeforces round #411, tutorial, tutorials


  Rev. Lang. By When Δ Comment
en16 English saliii 2017-05-07 15:39:24 704
en15 English saliii 2017-05-06 20:37:54 1217 Tiny change: 'صان \ پر \نشد ** تا' -> 'صان \ پر \ نشد ** تا'
en14 English saliii 2017-05-06 19:59:34 6 Tiny change: '\sqrt(n) \log(n) +' -> '\sqrt(n) \cdot \log(n) +'
en13 English saliii 2017-05-06 19:58:26 53
en12 English saliii 2017-05-06 10:37:39 2978
en11 English saliii 2017-05-06 09:21:22 41 Tiny change: 'al:805D]\n_**To DO...**_\n\nTime C' -> 'al:805D]\n\nTime C'
en10 English saliii 2017-05-05 23:42:40 20699 Tiny change: 'We were wa' -> ' We were wa'
en9 English saliii 2017-05-05 18:11:59 196 (published)
en8 English saliii 2017-05-05 18:05:07 198 Tiny change: ':804A]\n[toturial:805C]' -> ':804A]\n[tutorial:805C]' (saved to drafts)
en7 English saliii 2017-05-05 17:16:48 6 Tiny change: 'e trivial upper-bound s' -> 'e trivial lower-bound s'
en6 English saliii 2017-05-05 16:21:21 6 Tiny change: 'a trivial upper-bound f' -> 'a trivial lower-bound f'
en5 English saliii 2017-05-05 14:40:04 47 Tiny change: 'oiler>\n\n' -> 'oiler>\n\n\nSolutions\n==================\n_**TO DO...**_'
en4 English saliii 2017-05-05 14:38:16 25 Tiny change: 'st here.\n\n[problem' -> 'st here.\nHints\n------------------\n[problem'
en3 English saliii 2017-05-05 14:33:54 38 Tiny change: 'ough.\n### Events' -> 'ough.\n#### Events'
en2 English saliii 2017-05-05 14:33:21 6426 Tiny change: 'tion. So $\choose{2}{n}$\n</spoi' -> 'tion. So $n \choose{}$\n</spoi' (published)
en1 English saliii 2017-05-05 08:33:09 3119 Initial revision (saved to drafts)