GEEK04 - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

Difficulty

MEDIUM

Prerequisites

Recursion, Bitmasks, Dynamic Programming.

Problem

Find the minimum time taken to cross the river by N people if we can allow almost 2 people to use a boat such that the rowing time is equal to the minimum of the rowing time of both the people. Note that, slowing rowing time is given by larger integers.

Explanation

First of all, any type of greedy algorithm will only pass the first subtask and not any other. As the constraints are small and greedy solution will not work, we will try to come up with a dynamic programming solution.

Let us assume we denote the side where all the persons are initially standing by left and their destination, i.e. where they want to reach by right.

The first observation is that we will always try to send 2 people in the boat. This is because the slower person rowing time will then not contribute to the answer. The next observation is that once few people have crossed the river and reached “right”, the boat will be brought to the left side by the person whose rowing time is the minimum among the persons at the right side. Next is that we can represent each person by a “bit-mask”. The “left” and “right” bitmask denote that if the {i}^{th} bit is one, then the {i}^{th} person is present there else he is not present. The last observation is that the person can be present either in the “left” side or “right” side, not both ways. Thus, we only care about “left” side masks. The “right” mask can be calculated from the “left” ones, by setting the bits to 1 which are not present in “left”.

With all these observations, we try to build a recursive solution as follows: (in the code, “turn” means, whether we send people from right to left or reverse)


	//call with recurse((2^n)-1, 0)
	void recurse(LEFTMASK, turn):
	if (LEFTMASK == 0):
		return 0		//we transferred all the people
	RIGHTMASK = ((2^n)-1) ^ LEFTMASK
	if (turn == 1):		//we want to transfer people to the left
		min_row = infinity, person = -1
		for i in [0 .. n-1]:
			if (RIGHTMASK & (2^i)):
				if (min_row > row[i]):
					min_row = row[i]
					person = i
		return row[person] + recurse(LEFTMASK ^ (2^person), turn ^ 1)
	else:				//we want to transfer people to the right
		if (number of set bits in LEFTMASK == 1):
			//only 1 person is left)
			for i in [0 .. n-1]:
				if (LEFTMASK & (2^i)):
					return row[i] + recurse(left ^ (2^i), turn ^ 1)
		else:
			//try every pair of people by sending them to right)
			ans = infinity
			for i in [0 .. n-1]:
				for j in [i+1 .. n-1]:
					if ((LEFTMASK & (2^i)) && (LEFTMASK & (2^j)):
						val = max(row[i], row[j])
						val += recurse(LEFTMASK^(2^i)^(2^j), turn ^ 1)
						ans = min(ans, val)
			return ans

To optimise the above code for the full score, we can use dynamic programming so that each state is visited only once. This is also known as “top-down DP” or “recursion with memoization”.

Time Complexity

O(2^N * N * N)

Space Complexity

O(2^N)

Solution Links

Setter’s solution

2 Likes

Is there anyone who had solved this question with bottom-up DP?

1 Like

@likecs

In the last sub-task N can be up to 20 and the value of ((2^N)NN) is 419430400(>4e8) which doesn’t work within the given time limit(2 secs) and again test cases are there which can be up to 3. Time complexity of my solution is also O((2^N)NN) but it is giving TLE for the last sub-task and I wasted 3 hours trying to optimize my solution. I literally shocked after seeing the Time complexity provided in the editorial. The best submission works in 0.00 secs and i want to see that submission.Please make all the submissions public.

1 Like

@Bansal1232
could you please explain how the answer to the input:
4
1 2 5 8

is 15 and not 17.??

@admin the practice links for every problem in this contest are invalid. The page exists but says “Problem is not visible now. Please try again later.”

In contrast to the claim in the tutorial I think that there is a greedy solution.

Maybe I am wrong, but at least my solution passes all test cases and my random case generator does not find a case where my output and the output of setter solution differs.

My solution runs in O(N \log(N))

Idea:

  1. Sort the times (Here is N\log(N) needed - remaining steps are linear)
  2. while there are more than 3 people on the left side Ship the slowest two people to the right by
  • either the fastest person and the slowest person go to the right, the fastest goes to the left (two times)
  • or the fastest TWO persons ride to the right, the fastest goes back, the slowest two people go right, the second fastest goes left
  1. Now only 1, 2 or 3 persons are left
  2. The fastest person rides to the right (with one of the remaining persons if there is any)
  3. if there is still a person on the left side the fastest goes back to the left and then goes right with the remaining person.
4 Likes

Solution link redirects to setter’s solution

check again.

1 Like

Updated Now. :slight_smile:

Why the solution of other programmers are still hidden?

The practice link is not working

1 Like

The solution you provided is indeed incorrect. It’s showing wrong answer in some of the test cases

I understand your frustuation. But Atleast don’t call someone dumb!! have some decency brother

2 Likes

How did you submitted it Because I am not able to open practice link

Check for this input:

4

1 2 5 8

Correct ans = 15

  1. 1 and 2 will go --> 2
  2. 1 will return --> 3
  3. 5 and 8 will go --> 11
  4. 2 will return --> 13
  5. 1 and 2 will go --> 15

Check it properly


My code is outputting only 15

Check for this one:

5

23 22 2 18 6

Correct ans = 63

Your answer = 75

Try this https://ideone.com/Dqjupr