Hello, Codeforces community!
Link: https://www.hackerearth.com/november-clash-16/
I want to invite all of you to participate in November Clash at HackerEarth. The contest is scheduled today, November 12. The contest duration is 24 hours, so there should be some comfortable time for every timezone. :)
There will be six tasks in the problemset. Five of them will be standard algorithmic problems with partial solutions allowed — you get points for every test that your solution passed. And the final task is an approximate problem — your score for this task depends on how good your solution is comparing to current best solution.
KuchumovIlya is the author of this problemset. He's done great job preparing the problem-set. And I hope you guys will enjoy the questions prepared. I_love_Tanya_Romanova worked on this contest as the tester and editorialist — he is responsible for taking care of the problems. And not surprisingly, he has done a commendable job for testing the problem-set. I hope you guys will not be disappointed.
Good luck!
I_love_Tanya_Romanova has a really tough job! I can't imagine how hard it is to stand statements like this one so often.
How to solve Text Editor and Registration System?
Registration System:
This problem can be solved by using a trie. Firstly, we have to check if the login is occupied or not. If it is not then we add its in the trie. If the login is occupied we have to add some suffix at the end of the login. In every node of the trie we maintain the shortest length of a suffix that gives a free login. It helps to look for the suffix fast.
For better understanding you can see this code.
The problem can be solved by using a simple map in around 18 lines. See below comment.
Coding registration system is simple but the toughest part of it was understanding the problem statement/ how the output was generated.
Here is my code for reference:Click
Sample I/O:
Input:
Output:
What was the approach for the problem Furthest Vertex?
Two things to observe:
1) In a tree, the furthest vertex for any node will be among the diameter's endpoints. I believe you know that, it is a very well known fact, you can prove it easily yourself.
2) Consider two trees with diameters (U,V) and (P,Q). No matter how we join them, the new tree's diameter will have its endpoints among {U,V,P,Q}. This can be proven using the previous observation.
Thanks..Got it.