Class : UnsortedSequence
Method : getUnsorted
Simple enough.
Approach.
1. sort the array in ascending order
2. Check from the last element, and find a second largest element.
3. Let the index of the second largest element i. Switch arr[i] with arr[i+1]
class UnsortedSequence {
public:
vector <int> getUnsorted(vector <int>);
};
vector <int> UnsortedSequence::getUnsorted(vector <int> s) {
vector<int> emp;
int N = s.size();
if(N == 1) return emp;
sort(s.begin(), s.end());
if(s[0] == s[N-1]) return emp;
for(int i = N-2; i >= 0; i--)
if(s[N-1] != s[i])
{
swap(s[i+1], s[i]);
return s;
}
return emp;
}
DIV2 - 500
Class : NoRepeatPlaylist
Method : numPlaylists
There are two approaches, both of which are used during the contest.
One was used by _peanut (http://community.topcoder.com/stat?c=problem_solution&rm=311364&rd=14724&pm=11774&cr=23010876)
and another was used by vexorian (http://community.topcoder.com/stat?c=problem_solution&rm=311312&rd=14724&pm=11774&cr=22652965)
Although _peanut's solution looks simpler and easier to code once you understand dp relation, I prefer vexorian's approach because
1. His approach is simpler to understand.
2. His approach is easier to code.
_peanut's approach
Logic
1 <= i <= P , 1 <= j <= N
dp[i][j]
= number of ways to make a playlist whose length == i using
j different songs
= add a new song + add an already added song
= (number of ways to make a playlist whose length == (i-1) using
(j-1) different songs) * (number of avilable new songs)
+ (number of ways to make a playlist whose length == (i-1) using
j different songs) * (number of already added songs whose
previously appearance is at least M songs away from position j)
=dp[i-1][j-1] * (N - (j - 1))
+ dp[i-1][j] * max(j-M, 0)
Ans
= dp[P][N]
= number of ways to make a playlist whose length == P
using N different songs
It is hard to understand max(j-M,0) at first sight.
j is the number of different songs used at position[1...i-1].
We want to add one of songs from postion[1..i-1] to position i.
If M == 0, we can use any one of j songs.
Let's see what happens when M == 1.
This means we cannot use songs from position (i-1).
Any one of j songs can be at that position.
So we can use only (j - 1) songs.
Expand this logic to M == M, and we can use (j-M).
Notice that if M >= j, we cannot add any existing song to position i
because we have not used enough different songs.
Base
dp[0][0] = number of ways to make an empty playlist using 0 song.
= 1
Actual code
int NoRepeatPlaylist::numPlaylists(int N, int M, int P) {
ll dp[P+1][N+1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1ll;
for(int i = 1; i <= P; i++)
for(int j = 1; j <= N; j++)
dp[i][j] = ( (dp[i-1][j-1] * (N - (j-1))) % mod + (dp[i-1][j] * max(j-M,0)) % mod ) % mod;
return dp[P][N];
}
vexorian's approach
Logic
He used classic dynamic programming approach : recursive function + memoizattion.
Define recursion
long long rec(int idx, long long extra, long long mustPlay)
= If you are choosing (idx)th song,
and have "extra" number of already played songs to choose from,
and "mustPlay" number of not-played songs to choose from,
how many ways can you make playlist?
Memoization
mem[idx][extra][mustPlay] = result of rec(idx, extra, mustPlay)
Code
typedef long long ll;
class NoRepeatPlaylist {
public:
int numPlaylists(int, int, int);
};
ll mod = 1000000007;
ll mem[101][101][101];
int last;
int margin;
ll rec(int idx, ll extra, ll mustPlay)
{
ll& res = mem[idx][extra][mustPlay];
if(idx == last+1)
{
//successfully played all songs
if(mustPlay == 0)
return 1ll;
//should play all songs at least once. Unsuccessful
return 0ll;
}
if((idx - 2) >= margin) extra+=1ll;
if(res == -1)
{
res = 0;
if(mustPlay > 0)
{
res = (res + mustPlay * rec(idx+1, extra, mustPlay-1)) % mod;
}
if(extra > 0)
{
res = (res + extra *rec(idx + 1, extra - 1 , mustPlay)) % mod;
}
}
return (res % mod);
}
int NoRepeatPlaylist::numPlaylists(int N, int M, int P) {
last = P;
margin = M;
memset(mem, -1, sizeof(mem));
return rec(1, 0ll, (ll)N);
}
DIV2 - 1000
Class : KingdomReorganization
Method : getCost
Logic
We need to build a MST out of the given tree(s) defined by vector<string> kingdom.
So in a sense, we are building a MST.
However, the MST we want needs to follow below rule
: Always prefer keeping existing edges (defined by kingdom[i][j] == '1') to building new edges.
So, assuming we are building a MST from scratch (with no edges at all), how can we force our MST to use edges defined by kingdom?
We can do it by setting cost of existing edges negative, which will be always lower than building new edges and therefore force any greedy algorithm to choose existing edges.
So setting cost of existing edges negative will give us MST we want.
However, how do we cover the cost of going from" the given tree defined by vector<string> kingdom " to an empty MST? In other words, above procedure will destroy all existing roads and rebuild a few of them, and rebuilding sounds like a waste because we are wasting cost of (destroy[i][j] + build[i][j]) when we should be wasting 0 cost by not destroying it in the first place.
We can solve this issue by setting build[i][j] = -(destroy[i][j]).
I will use Kruskal's algorithm to solve this.
class KingdomReorganization {
public:
int getCost(vector <string>, vector <string>, vector <string>);
};
struct edge
{
int from;
int to;
int cost;
edge(int f, int t, int c): from(f) , to(t), cost(c) {}
};
int getEdgeCost(char ch)
{
if('A' <= ch && ch <= 'Z')
return (ch - 'A');
if('a' <= ch && ch <= 'z')
return ((ch - 'a') + 26);
cout<<"This line should never be reached"<<endl;
return -100;
}
bool sortEdge(edge a, edge b)
{
if(a.cost < b.cost) return true;
return false;
}
int KingdomReorganization::getCost(vector <string> kingdom, vector <string> build, vector <string> destroy) {
int N = kingdom.size();
int destructCost = 0;
int createCost = 0;
vector<edge> edges;
REP(i,0,N)
REP(j,(i+1),N)
{
if(kingdom[i][j] == '1')
{
destructCost += getEdgeCost(destroy[i][j]);
edges.push_back(edge(i,j,-(getEdgeCost(destroy[i][j]))));
}
else
{
edges.push_back(edge(i,j, getEdgeCost(build[i][j])));
}
}
/*
Kruskal's algorithm.
Sort edges in ascending order.
Go through each edge, see if it makes a cycle.
If yes, skip this edge.
If no, add this edge to MST
*/
sort(edges.begin(), edges.end(), sortEdge);
vector<int> setID;
REP(i,0,N)
setID.push_back(i);
for(int i=0; i < edges.size(); i++)
{
edge cur = edges[i];
if(setID[cur.from] != setID[cur.to])
{
int oldID = setID[cur.to];
createCost += cur.cost;
for(int j=0; j < N; j++)
if(setID[j] == oldID)
setID[j] = setID[cur.from];
}
}
return (createCost + destructCost);
}
No comments:
Post a Comment