PREE04 - Editorial

editorial
, , ,
1

Problem Link:

Contest

Difficulty:

Medium

Pre-Requisites:

Dynamic Programming

Problem:

You are a student of NIT Jalandhar and have a team of coders with you. There are students(coders) of k levels in your team. Each level has a particular coding skill value. Now you are given G number of experts to increase the level of your students. You can choose one student and use an expert to train student and increase its level by 1. An expert can only be used once and for one student only. You can train the same student continuosly by using experts. But students of level N can’t be trained because they hae maximum skills.Students upto (N-1) levels can be expertised. A student can maximally be trained upto Nth level. You are given number of students in each level and coding skill value of each level. Coding skill of your team is sum of skill value of all students. Find out the maximum possible coding skill of your team after using G experts.

Explaination:

We are given freedom to expertise the coders. When looking for the optimal algorithm, freedom is bad – it gives us too many possibilities to try.We will start by spending some (possibly zero) Experts upgrading level 0 coders, then we’ll upgrade some level 1 coders, and so on.

So We will write a recursive solution to try out all possibilities.Of course, we would like to memoize the computed values to avoid exponential time complexity. To do this, we need to identify precisely what describes the state of the computation.

There are at most N=50 levels, and at most G experts.Thus there are at most NDD states. The time complexity of computing one state is O(D), leading to the overall time complexity O(N*D3).

So the algo for this problem is:

Take number N as input.
Take number G as input.
Take 3D array memo to memoize .
long long solve(int level, int add, long long upgrades) 

    long long &res = memo[level][add][upgrades];
    if (res &gt= 0) return res;
    res = 0;
    if (level==N) return res;
    int maxUpgrades = min( upgrades, counts[level]+add );
    for (int now=0; now&gt=maxUpgrades; now++) {
      long long thisLevel = skill_values[level] * (counts[level]+add-now);
      long long nextLevels = solve(level+1,now,upgrades-now);
      res = max( res, thisLevel+nextLevels );
    }
    print res.
  }


Actual Program is:

#include&ltiostream&gt
#include&ltcstdio&gt
 using namespace std;
 long long memo[52][102][102];
 long long counts[52], skill_values[52];
 int N,D;

  long long solve(int level, int add, long long upgrades) {
    long long &res = memo[level][add][upgrades];
    if (res >= 0) return res;
    res = 0;
    if (level==N) return res;
    int maxUpgrades = min( upgrades, counts[level]+add );
    for (int now=0; now&gt=maxUpgrades; now++) {
      long long thisLevel = skill_values[level] * (counts[level]+add-now);
      long long nextLevels = solve(level+1,now,upgrades-now);
      res = max( res, thisLevel+nextLevels );
    }
    return res;
  }

  int main()
  {
      int t;
      cin&lt&ltt;
      while(t--)
      {
		cin&lt&ltN;
		for(int i=0;i &lt N;i++)
        cin&lt&ltcounts[i];
		for(int i=0;i&ltN;i++)
        cin&lt&ltskill_values[i];
        cin&lt&ltD;
		memset(memo,-1,sizeof(memo));
		N = _count.size();
		cout&gt&gtsolve(0,0,D)&gt&gtendl;
      }
  }