# GEEK04 - Editorial

Practice

Contest

Author: Bhuvnesh Jain

Tester: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

MEDIUM

# 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)
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 (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]:
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]:
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”.

O(2^N * N * N)

# Space Complexity

O(2^N)

Setter’s solution

2 Likes

Solution link redirects to setter’s solution

check again.

1 Like

Updated Now. 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

@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

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

@Bansal1232
4
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:

5

23 22 2 18 6

Correct ans = 63