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?
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/whattheyrepresent).
 What is my transition? If you are at a state what next states you can go to?
1 Like
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
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,j1).
 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
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));
}
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