NUMBERS - Editorial

editorial
, , , ,
1

Problem Link:

Practice

Contest

Difficulty:

CakeWalk

Pre-requisites:

Sorting

Explanation:

Sub tasks 1, 2, 3:

The constraints in these subtasks are designed in such a way that it is possible just to check every single person in O(N) time. This
way, the solution will look like: for every player check the fact that any other player’s number is not equal to the number of this
player and if it is so just check that this person’s number is minimal.

All the sub tasks:

If you sort all the players according to the numbers that they have said (obviously, in order from the smallest to the largest),
it’s easy to see that in order to check the uniqueness of any player’s number, it’s sufficient to look at the numbers of his
left and right neighbor in this sorted list. This way, we obtain O(N) solution after sorting and O(NlogN) solution for a single test case.

Setter’s solution:

Can be found here

Tester’s solution:

Can be found here

2

have look at my solutions here

  • First Solution
  • Second Solution

    • The only difference between them is I used structure instead of pair in the first solution, but the first solution was not accepted for many test cases please explain the funda behind this.

    3

    Can someone pls tell me why my solution was not accepted?
    Pls take a look
    http://www.codechef.com/viewsolution/3006113