What will be the recursive solution for this

1

I know it’s embarrassing to ask such a easy question.
But what will be the recursive solution for this question.
https://codeforces.com/contest/253/problem/B

My approach:

 static int dir(int[] a, int i, int j) {
    int s = 2 * a[i] - a[j];
    if (s >= 0)
        return 0;
    else
        return min((1 + dir(a, ++i, j),(1 + dir(a, i, --j));
}

What is wrong with this solution?

2

Lets try this, I will make you realize the error yourself.

  • What does dir do? What does this function represent to you?
  • Is it dp if we are not storing states?
  • What is my state in dp? By state I mean variables (and their meaning/what-they-represent).
  • What is my transition? If you are at a state what next states you can go to?
1 Like
3

I have not memoize this solution as of now. Array ‘a’ is already, I have taken two pointers one pointing at last index and other at 0 index, as array is already sorted j index will be pointing to greatest element and i index will be pointing to first index
so for every index we have choice whether to take ‘i’ index element as smallest or not, if not I increments the i by +1 this goes for ‘j’ index as well.
In a way I’m trying all the combinations.

In this TC -

10

39 9 18 13 6 16 47 15 1 24

the o/p is 5

But my approach return 3

4

I get your approach, that you sort the array and then play with 2 pointers.

BTW - return min((1 + dir(a, ++i, j)) + (1 + dir(a, i, --j))); I believe it should be a comma instead of plus? What min function is this that it accepts just one argument? XD

Lets convert your answer to the following:

  • What are states?

    • The variables i,j represent state. i will point to the current minimum element we can discard, j points to current maximum element we can discard. Hence, my state has 2 independent variables (i,j). With this in mind, dp[i][j] will represent the solution for subarray [i,j].

  • What are my transitions?

    • I can either discard either the element at i or the element at j. So my next states can be (i+1,j) or (i,j-1).
    • So that makes the transitions correct as well, as we will take the one providing minimum value to answer.

I think its that min typo maybe. Can you share your full code?

1 Like
5

Yes that’s what I mean, it’s so stupid of me of not checking what I’m writing.
This is exactly my code is doing.

This is the full code

    import java.util.*;
import java.io.*;

class Test {
    static int dir(int[] a, int i, int j) {
        int s = 2 * a[i] - a[j];
        if (s >= 0)
            return 0;
        else
            return Math.min((1 + dir(a, ++i, j)), (1 + dir(a, i, --j)));
    }

    public static void main(String[] args) throws IOException {
//        Scanner input = new Scanner(new File("input.txt"));
//        PrintWriter out = new PrintWriter(new File("output.txt"));
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        int x = (2 * a[0] - a[n - 1]);
        System.out.println(dir(a, 0, n - 1));
    }
6

In your code, look at -

return Math.min((1 + dir(a, ++i, j)), (1 + dir(a, i, --j)));

Change the ++i to i+1 and similarly for j, because if you use ++i, the i for next function call also gets incremented. Meaning, after the ++i in first dir call, the i in second dir call is actually i+1.

4 Likes
7

:no_mouth:

I’m dumb.