GEEK04 - Editorial

Problem Link



Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain




Recursion, Bitmasks, Dynamic Programming.


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.


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
	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)
			//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


Solution Links

Setter’s solution


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

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

1 Like

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


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

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


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

Check for this input:


1 2 5 8

Correct ans = 15

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

is 15 and not 17.??

  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:


23 22 2 18 6

Correct ans = 63

Your answer = 75

Try this

I hope this will work now.Also above logic is incorrect if row is not sorted before calling recurse I think.

The reason for this is that while calculating RIGHTMASK from LEFTMASK we assume that all elements not in LEFT are at right but for cases much smaller than (1<<n) we have not included that element and if not sorted this may use an element which was not at all considered

Your solution is working fine but i don’t know why it’s getting more time which will definitely time out in 2 sec.