Shayan's blog

Codeforces Educational Round 172 (Div 2) — Video Tutorial
By Shayan, history, 25 hours ago, In English

Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.

2042A — Greedy Monocarp

Video

2042B — Game with Colored Marbles

Video

2042C — Competitive Fishing

Video

2042D — Recommendations

Video

2042E — Vertex Pairs (not complete)

Video

2042F — Two Subarrays

Video
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
21 hour(s) ago, # |
  Vote: I like it +28 Vote: I do not like it

could you post text tutorial, please? would be much more helpful.

→ Reply
»
19 hours ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

Why not posting text editorial first, then video tutorial later? Posting video tutorial first makes it look like you want to boost your Youtube view count to me.

→ Reply
  • »
    »
    16 hours ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Video tutorials aren't from contest authors.

    → Reply
  • »
    »
    14 hours ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Instead of yapping why not read the 'note' from the blog first?

    → Reply
  • »
    »
    13 hours ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    First look at the note then speak anything...don't speak something randomly because few people prefer video tutorial

    → Reply
»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Text tutorial proves to be much more convenience!!!!

→ Reply
»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Text tutorial first please, it'll be better.

→ Reply
»
10 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me was this contest unrated?? Why my rating haven't increased??

→ Reply
  • »
    »
    10 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For Div 3 and Educational Rounds, there is an open hacking phase which lasts 12 hours. After that, the round goes through system testing which takes another 2-3 hours. As you can see now, the round is about 80% done with system testing. After system testing is finished you should see your rating updated. I hope this helps.

    → Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is a text editorial??

→ Reply
»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Bro make a text tutorial that would be great.

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to get the answer in writing not video!How c?could someone answer my question?Thank you very much.

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The text editorial is provided by the authors of the round, which is not yet available. Video editorials are from third parties for those who prefer video over text.

    → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution for E — Vertex pairs:
https://codeforces.me/contest/2042/submission/294654766
- First we find the maximum vertex number needed. Which mean that if we connect all the vertices with index <= root, we get all number from 1 to n. (O(nlogn))
- Then reroot the tree from the maximum vertice, keep track of the parent of each node. So if we remove any vertice, the subtree will be disconnected from the root. (O(n))
- For 2 vertices with the same color, find the lowest common ancestor and mark it and its ancestors as must keep. Because if it is removed, the color will be lost and not satisfied the constraint. (O(n) or O(nlogn) defending on the implementation of LCA)
- For node from 2*n to 1, if the node is not removed and not must keep, we remove the subtree at the node. For each number written on the subtree, we find the other node with the same number and mark it and its ancestor as must keep. (O(n))
Total time complexity O(nlogn)

→ Reply