vjudge7701's blog

recursion problem
By vjudge7701, history, 3 years ago, In English

in this problem : https://codeforces.me/gym/104493/problem/A i know it is very slow to solve it using recursion but i want to know the solution using recursion to understand dp solution well here is my code it is WA2 : 

int n;
int a[N] ;
ll sum=0;
ll mx=0;

int fr[11] ;
bool ok(int r){
    ll x = a[r] ;
    while(x > 0){
        fr[x%10]++;
        x/=10;
    }
    for(int i=0;i<10;i++){
        if(fr[i] > 2)return 0;
    }
    return 1;
}
void del(int r){
    ll x = a[r] ;
    while(x > 0){
        fr[x%10]--;
        x/=10;
    }
}
bool vis[N] ;
void rec(int r){
    if(r == n){
        mx  = max(mx , sum) ;
        return  ;
    }
    if(ok(r)){sum+=a[r];vis[r]=1;}
    else (del(r));
    rec(r + 1) ;
    if(vis[r]){sum-=a[r] ; vis[r]=0;del(r);}
    rec(r+1);

}
void solve(){
    cin >> n;
    for(int i=0;i<=n;i++)vis[i]=0;
    sum = mx = 0 ;
    for(int i=0;i<10;i++)fr[i]=0;
    for(int i=0;i<n;i++)cin>>a[i];
    rec(0);
    cout<<mx<<"\n";
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Seems ok, just use long long array to store a.

Also, I propose (to make the code structure better) to make changes to sum and vis only inside corresponding functions (ok and del). The function should perform a certain self-sufficient work, and in your case adding a weight to the set is done with if (ok) { sum += a[r], vis[r] = 1; } else del(r);. It is not an atom, the bigger code is, the easier is to have a mistake somewhere. For example, I consider the following structure much better.

void del(int r) // update fr, sum, vis for a[r]

bool add_and_check(int r) // update fr, sum, vis for a[r]; return 1 if all is ok, 0 if fr[d] > 2 for some d.

bool add(int r) {
  bool ok = add_and_check(r);
  if (ok) return 1; // added succesfully
  del(r);
  return 0; // a[r] was not added, fail (but fr, sum, vis are up to date)
}
→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Do you have idea how to solve it using dp recursion

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Your recursion is of kind

      void rec(...) {
  if (i == n) mx = max(mx, sum), return;
  do some updates, go into recursion
}

      You can add memoization to avoid going into the same state more than one time, like in the following. 

      void rec(...) {
  if (already_was_in_that_state()) return;
  remember_current_state();
  if (i == n) mx = max(mx, sum), return;
  do some updates, go into recursion
}

      In your case, the variables that define current state are r, fr, sum, vis. There are two much of them to remember them all, so we would do some clever things.

      1. vis in fact is not needed, for fixed r we ask only vis[r]. That's the key idea of dynamic programming -- forget the information from previous steps, that doesn't affect the answer in the future. Here, vis[i] for i <= r indicates, whether i-th weight was taken, or not, and it doesn't affect our choice in the future. vis[i] for i > r is always false.

      2. I don't know, how to say it in general case, but here you don't need sum too. It doesn't affect your choice (whether we can take a next weight or not). It affects the answer, but nevertheless, it just adds something to it.

        What I want to say is that you can write the function in a style that it doesn't know sum, but returns the optimal answer to the suffix a[r+1..n]. Then if sum is sum for a[1..r] and ans is best choice for a[r+1..n], you can set mx = max(mx, sum + ans).

      With those two changes, you have a recursion with relatively few parameters, and you can remember answer for all of them:

      ll rec(int r) { // the only parameters, that answer depends on are `r` and `fr`.
  if (already_calculated(r, fr)) return ans(r, fr);
  if (r == n) return 0; // the answer is sum, 0 needs to be added
  ll ans = 0;
  do some updates, update `ans` with going into recursion.
  update_ans(r, fr); // if `ans` is better than current ans for `r, fr`, than update.
}

      To store the best ans for a current state you should use any data structure — multi-dimensional array or map. Map is easier (you can replace fr with vector, than use map<pair<int, vector<int>>, int> memo like this memo[{r, fr}] = ans), but it adds extra log factor to the complexity, so the solution might be too slow.

      Note that the total number of states is not so big. For correct states fr[d] = 0,1,2, therefore the total number of states is no more than $$$3^{10} \cdot n$$$. It should fit in the limits.

      → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i solved it using dp and here is my solution if you need any help with it ask me XD

here

→ Reply