Dreamoon's code with comment added by me


  • 2
    F

    Really awesome and difficult to understand for idiot as me

    #include <bits/stdc++.h>
    #define SZ(X) ((int)(X).size())
    #define ALL(X) (X).begin(), (X).end()
    #define REP(I, N) for (int I = 0; I < (N); ++I)
    #define REPP(I, A, B) for (int I = (A); I < (B); ++I)
    #define RI(X) scanf("%d", &(X))
    #define RII(X, Y) scanf("%d%d", &(X), &(Y))
    #define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
    #define DRI(X) int (X); scanf("%d", &X)
    #define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
    #define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
    #define RS(X) scanf("%s", (X))
    #define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
    #define MP make_pair
    #define PB push_back
    #define MS0(X) memset((X), 0, sizeof((X)))
    #define MS1(X) memset((X), -1, sizeof((X)))
    #define LEN(X) strlen(X)
    #define PII pair<int,int>
    #define VI vector<int>
    #define VL vector<long long>
    #define VPII vector<pair<int,int> >
    #define PLL pair<long long,long long>
    #define VPLL vector<pair<long long,long long> >
    #define F first
    #define S second
    typedef long long LL;
    using namespace std;
    const int MOD = 1e9+7;
    const int SIZE = 1<<15;
    int dp[SIZE];
    void update(int &x,int v){
        if(x==-1||x>v)x=v;
    }
    class Solution {
        public:
            int minStickers(vector<string>& stickers, string target) {
                // init dp array to -1, means invalid value
                // if (1<<pos)& (index of dp array)==1, target[pos] is satisfied, else not
                // dp[index] means to fill target on all positions of 1 of index, minimum stickers needed,
                // for example, for 0b101, means target[0], target[2] is satisfied
                MS1(dp);
                // to fill an empty string, need 0 stickers
                dp[0]=0;
                int n=SZ(target);
                // count of  all subset of n letters of target is 1<<n
                int N=1<<n;
                REP(i,N){
                    // dp[i] is invalid, can't expand it by adding more stickers
                    if(dp[i]==-1)continue;
                    // for each sticker
                    REP(j,SZ(stickers)){
                        // try apply sticker[j] to dp[i]
                        int now=i;
                        // for each letter of stickers[j]
                        REP(k,SZ(stickers[j])){
    
                            // for every position of target, if it's not set and == stickers[j][k]
                            // set that position in now, remember to break after finding match because each letter of sticker can be used only once
                            REP(r,n){
                                if((now>>r)&1)continue;
                                if(target[r]==stickers[j][k]){
                                    now|=1<<r;
                                    break;
                                }
                            }
                        }
                        // update dp array for result after applying sticker[j] on dp[i[
                        update(dp[now],dp[i]+1);
                    }
                }
                return dp[N-1];
            }
    };
    
    

  • 0
    L

    @feng.peng.3597 said in Dreamoon's code with comment added by me:

    #define MS1(X) memset((X), -1, sizeof((X)))
    #define LEN(X) strlen(X)
    #define PII pair<int,int>
    #define VI vector<int>
    #define VL vector<long long>

    How did you get to know what code he wrote in the contest???


  • 0

    Hi @lixuchen, I just found this out yesterday... click on the following link to go to the contest ranking. This displays rows of users' contest rank in descending order ( i.e. Dreamoon is on top ). Then click on the </> icon under column Q4.

    https://leetcode.com/contest/leetcode-weekly-contest-53/ranking


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.