July 12, 2019 Problem of the Week: On Math & Logic

This week, we’ll analyze the division 1, level one problem from SRM 700 (sponsored by Booz Allen Ham),  “FindingFriend”

The summary of the problem statement is as follows –

Your friend competes in an online contest. This contest has N rooms, each with X contestants per room. You are given the rank of your friend and each room’s leader’s rank. 

Your task is to determine the number of possible rooms that your friend might have been assigned to for the contest.

Now, let’s take an example.

Let’s say there are 5 rooms, and each room has 6 contestants. Let’s also consider the rank of our friend to be 10. 

Let’s consider the leaders of each room to have the global ranks [1, 2, 3, 6, 8].

Now, if our friend’s rank is 10, they may belong to any of the 5 possible rooms. 

The reason we can make this assertion is that their rank must be greater than the rank of the leader of the room they were assigned to.

In this case, the leaders of each room have a lower rank and therefore pose no issue.

However, this is just one potential scenario.

Consider the situation where the leaders of each room are [1, 4, 7, 8, 10].

Here, since our friend’s rank matches a certain leader’s rank, and since ranks are uniquely assigned to each contestant, we know that the leader who has the same rank as our friend is our friend themselves! This means that there’s only one possibility here.

That makes our second scenario.

But our solution isn’t yet complete.

Consider the following scenario, where the number of rooms is 5, and the contestants per room are 4, and the leader ranks are [1, 5, 9, 13, 17]. Let’s say our friend’s rank was 18.

What do you think our answer should be here?

Note here, that there’s only one possible solution where:

Room 1: Ranks 1, 2, 3, and 4.

Room 2: Ranks 5, 6, 7 and 8.

Room 3: Ranks 9, 10, 11 and 12.

Room 4: Ranks 13, 14, 15 and 16.

Room 5: Ranks 17, 18, 19 and 20.

Why? Because, for example, if rank 4 and rank 5 swapped rooms, then note that the leader of room 2 changes. 

This implies that the configuration of rooms can’t be freely changed, and only a certain configuration of the room is valid, under some cases.

Defining these cases in a general sense, we can say that a certain set of rooms are fixed in terms of their configuration if they “fill” up all ranks until that index.

Here’s what that means – In the above example, note that room 3’s leader had a rank of 9. And all leaders in front of room 3 had leaders whose ranks were greater than 9.

This means that the first 8 ranks were in room 1 and room 2.

And this implies that the top 8 ranks have been already assigned, meaning if our friend’s rank is greater than 8, their room cannot be in either room 1 or room 2.

This way, we can eliminate rooms that cannot include our friend’s rank, and accordingly update our answer.

Note that the input provides the leader rank vector in an unsorted manner, so it’s important to sort the list before proceeding as mentioned above.

The fastest solution was by Silver_Soul who solved this in under 8 minutes, and whose submission is available here – https://community.topcoder.com/stat?c=problem_solution&cr=40172809&rd=16821&pm=14166