harshraj22's blog

By harshraj22, history, 5 years ago, In English

I was trying BoggleScore problem from topcoder. I tried dp approach, saving answer to each substring at each cell. I am getting WA, and can't understand why. Can anyone help me ? Here is my code :

#include<bits/stdc++.h>
using namespace std;

#define ll long long int

long long int mod = 1e13,hashi=1;
const int N = 3e5+5;
vector<ll> dp[6][6];
unordered_map<string,ll> mp;

ll getHash(string s){
    if(mp[s] != 0)
        return mp[s];
    mp[s] = hashi++;
    return mp[s];
}

vector<string> grid;

ll obtain(ll i,ll j,string s){

    // termination case, if i or j is out of grid
    if(i<0 || j<0)
        return 0;
    else if(i>=4 || j>=4)
        return 0;
    ll hsh = getHash(s);
    
    if(s.size()==0)
        return dp[i][j][hsh] = 0;
    else if(grid[i][j] != s[0]){
        return dp[i][j][hsh] = 0;
    }

    if(dp[i][j][hsh] != -1){
        return dp[i][j][hsh];
    }

    else if(s.size()==1 && grid[i][j] == s[0]){
        return dp[i][j][hsh] = 1;
    }

    dp[i][j][hsh] = 0;
    s = s.substr(1,(ll)s.size()-1);

    for(int ii=-1;ii<2;ii++){
        for(int jj=-1;jj<2;jj++){
            if(ii == 0 && jj == 0)
                continue;
            dp[i][j][hsh] += obtain(i+ii,j+jj,s);
            dp[i][j][hsh] %= mod;
        }
    }    

    return dp[i][j][hsh]%mod;
}

long long int solve(vector<string> &input){
    ll ans = 0;
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            for(auto s:input){
                ans += obtain(i,j,s)*s.size()*s.size();
                ans %= mod;
            }
        }
    }
    return ans%mod;
}

class BoggleScore{
    public:
        ll bestScore(vector<string> grd, vector<string>input){
            for(int i=0;i<6;i++){
                for(int j=0;j<6;j++)
                    dp[i][j].resize(N,-1);
            }

            mp.clear(); grid = grd;
            return solve(input);
        }

};

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By harshraj22, history, 5 years ago, In English

Can anyone explain me the solution of XOMMON problem from codechef. I looked at many successful submissions, though don't understand why we sort the pair of int, pair and then do dp calculations. Also, I wonder why my approach is incorrect .

My approach: for every index,store the max length of subseq and corresponding xor val. To find the same for any index(say i), loop through each index less than the current one (say j), and see if the xor of two,is >= the xor stored at the lower index(j). If it is, look if length of subseq formed exceeds the length stored at i, if yes update xor val and len at i, if it is same, see if xor of two numbers is less than that stored at i, if yes again update. finally the answer should be the max element of the array len.

Full text and comments »

  • Vote: I like it
  • -3
  • Vote: I do not like it