2019 TCO Round 1B

There are still many interesting DP questions on Topcoder, but it would be great if there were more editors (what are you going to do…)

Solution link

EllysSki

The 250 question is too easy.

EllysTeleport

The 500 question was a question I originally asked when I was interviewing a certain company, and there was a possibility of encountering a loop.

2->1->5->6->7->8->5 is the case.

After thinking about it for a while, I first checked whether this point was on a loop and recorded the length of the loop.

Then scan it again and that’s it.

As far as the current problem is being dealt with, there will be no break down at all. Intellectual issues.

Of course, I just $N^2$ here.

ll val[100005],nxt[100005];
int fa[100005];

class EllysTeleport {
public:
   
    int getMax(int N, int H1, int A, int B, int P, int Q, int M) {
        val[1] = H1;
        repp(i,2,N) {
            val[i] = (val[i-1]*A+B)%M;
        }
        sort(val+1,val+N+1);
        repp(i,1,N) {
            nxt[i] = i-1;
        }
        int ans = 0;
        memset(fa,-1,sizeof(fa));
        repp(i,1,N) {
            int cnt = 0;
            int x = i;
            while(x!=0&&fa[x]!=i) {
                ++cnt;
                fa[x]=i;
                x=nxt[x];
            }
            ans = max(ans,cnt);
        }
        return ans;
    }
}t;

EllysPearls

The meaning of the question 1000 is that each point has a color, and points of the same color are required to be placed together. Ask how many times the current order of these points needs to be changed.

The question explanation says that if 15 usually appears, consider bitmask dp. And this dp is actually very classic. It is [0,1] that indicates whether the current color has been added to the set and whether it has been considered. Then the color at the last position is recorded and it is over.

int n;
vector<int>v;
int dp[55][16][1<<16];
class EllysPearls {
    public:

    int dfs(int ind,int col, int state) {

        if(ind>=n) {
            return 0;
        }
        if(dp[ind][col][state]!=-1) {
            return dp[ind][col][state];
        }
        int ans = 1 + dfs(ind+1,col,state);
        if(v[ind] == col) {
            ans = min(ans, dfs(ind+1,col,state));
        }
        if(!((1<<v[ind]) & state)) {
            ans = min(ans, dfs(ind+1,v[ind],((1<<v[ind])|state)));
        }
        dp[ind][col][state]=ans;
        return ans;
    }

    int getMin(int N, int M, vector <int> pearls) {
        memset(dp,-1,sizeof(dp));
        n = N;
        v = pearls;
        return dfs(0,M+1,0);
    }
}t;

It happened to be the May Day holiday here recently, so I didn’t go home. I miss my parents very much and think about the decisions I have made independently over the years. Don’t know what to say either. I just hope that I will keep working hard. Please keep working hard.

One day, let them. . . Be proud of me. . .