belowthebelt's blog

November Clash 2016
By belowthebelt, history, 8 years ago, In English

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!

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Text Editor and Registration System?

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

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The problem can be solved by using a simple map in around 18 lines. See below comment.

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

    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:

    15
lebron10
lebron11
lebron
lebron1
lebron
lebron2
lebron3 
lebron4
lebron5
lebron6
lebron7
lebron8
lebron9
lebron9
lebron10

    Output: 

    lebron10
lebron11
lebron
lebron1
lebron0
lebron2
lebron3
lebron4
lebron5
lebron6
lebron7
lebron8
lebron9
lebron90
lebron100
    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What was the approach for the problem Furthest Vertex?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply