recursion problem - Codeforces

Блог пользователя vjudge7701

recursion problem

Автор vjudge7701, история, 3 года назад, По-английски

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";
}

vjudge7701
3 года назад
5

Комментарии (4)

Показать архивные | Написать комментарий?

LeoPro

3 года назад, скрыть # |

← Rev. 2 →

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

→ Ответить

vjudge7701

3 года назад, скрыть # ^ |

Do you have idea how to solve it using dp recursion

→ Ответить

LeoPro

3 года назад, скрыть # ^ |

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.

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

→ Ответить