TopCoder Open 2012 - Round 1C

Level One - PasswordXGrid


Source Code

1:  long long PasswordXGuessing::howMany(vector <string> V) {  
2:         
3:    int N = V.size();  
4:    int M = V[0].size();  
5:    int res = 0;  
6:      
7:    for(int w=0; w < M; w++)  
8:    {  
9:      for(char ch = '0'; ch <= '9'; ch++)  
10:      {  
11:        bool isValid = true;  
12:        string ans = V[0];  
13:        ans[w] = ch;  
14:          
15:        for(int i=0; isValid && i < N; i++)  
16:        {  
17:          int diff = 0;  
18:            
19:          for(int j=0; j < M; j++)  
20:            if(V[i][j] != ans[j]) diff++;  
21:            
22:          if(diff != 1) isValid = false;  
23:        }  
24:        if(isValid) res++;  
25:      }  
26:    }  
27:      
28:    return res;  
29:  }  
30:    

Level Two - PasswordXGuessing


Source Code

1:    
2:  const int maxN = 45;  
3:  int dp[maxN][maxN];  
4:  int vert[maxN][maxN];  
5:  int hori[maxN][maxN];  
6:    
7:  int PasswordXGrid::minSum(vector <string> H, vector <string> V) {  
8:    
9:    int R = H.size();  
10:    int C = H[0].size()+1;  
11:      
12:    memset(dp, 0, sizeof(dp));  
13:    memset(hori, 0, sizeof(hori));  
14:    memset(vert, 0, sizeof(vert));  
15:      
16:    for(int i=0; i < R; i++)  
17:      for(int j=0; j < C-1; j++)  
18:        hori[i][j] = H[i][j] - '0';  
19:      
20:    for(int i=0; i < R-1; i++)  
21:      for(int j=0; j < C; j++)  
22:        vert[i][j] = V[i][j] - '0';  
23:    
24:    for(int i = R-1; i >= 0; i--)  
25:      for(int j= C-1; j >= 0; j--)  
26:        dp[i][j] = max(hori[i][j] + dp[i][j+1], vert[i][j] + dp[i+1][j]);  
27:    
28:    return dp[0][0];  
29:    
30:  }  

Level One - PasswordXPalindrome


Source Code

1:  int PasswordXPalindrome::minSwaps(string pwd) {  
2:      
3:    int N = pwd.size();  
4:    int res = 0;  
5:    bool soloChk = false;  
6:    for(int i = 0; i < N/2; i++)  
7:    {  
8:      if(pwd[i] == pwd[N-1-i]) continue;  
9:      bool found = false;  
10:      for(int j=i+1; !found && j < N-1-i; j++)  
11:        if(pwd[i] == pwd[j])  
12:        {  
13:          swap(pwd[j], pwd[N-1-i]);  
14:          res++;  
15:          found = true;  
16:        }  
17:      if(!found)  
18:      {  
19:        if(N%2 == 1 && !soloChk)  
20:        {  
21:          swap(pwd[i], pwd[N/2]);  
22:          res++;  
23:          soloChk = true;  
24:          i--;  
25:        }  
26:        else if(pwd[i] != pwd[N-1-i])  
27:          return -1;  
28:      }  
29:    }  
30:       return res;  
31:  }