algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (2000B)


      1 #include <vector>
      2 #include <iostream>
      3 
      4 // the state is as follows:
      5 // 
      6 // - s(fvc,oc,svc)
      7 //     - fvc == first v count (0->2)
      8 //     - oc == o count (0->1)
      9 //     - svc == second v count (0->2)
     10 // - s(ct)
     11 //     - ct ranges from 0->5
     12 //         - vv o vv
     13 //             - when ct == 5, we have found one
     14 //         - when ct == 4 or 3, we can take a 4
     15 //         - ...
     16 // 
     17 // this gives us an upper bound of 5 * size which is at worst 500_000, a reasonable number of stated assuming limited computation per state
     18 
     19 using namespace std;
     20 
     21 long long solve(string& input, char found, int idx, vector<vector<long long>>& memo) {
     22 
     23     if(found == 5) {
     24         return 1;
     25     }
     26 
     27     if(idx == input.size()) {
     28         return 0;
     29     }
     30 
     31     if(memo[found][idx] != -1) {
     32         return memo[found][idx];
     33     }
     34     
     35 
     36     long long res = 0;
     37 
     38     // we may only use v's that are adjacent
     39     // if the prior was a v, but current isn't, we skip
     40     if(found != 1 && found != 4) {
     41         res += solve(input, found, idx+1, memo);
     42     }
     43 
     44     char current = input[idx];
     45 
     46     switch (found) {
     47         case 0:
     48             if(current == 'v') {
     49                 res += solve(input,found+1, idx+1, memo);
     50             }
     51             break;
     52         case 1:
     53             if(current == 'v') {
     54                 res += solve(input,found+1, idx+1, memo);
     55             }
     56             break;
     57         case 2:
     58             if(current == 'o') {
     59                 res += solve(input,found+1, idx+1, memo);
     60             }
     61             break;
     62         case 3:
     63             if(current == 'v') {
     64                 res += solve(input,found+1, idx+1,memo);
     65             }
     66             break;
     67         case 4:
     68             if(current == 'v') {
     69                 res += solve(input,found+1, idx+1,memo);
     70             }
     71             break;
     72     }
     73 
     74     memo[found][idx] = res;
     75     return res;
     76 }
     77 
     78 int main() {
     79     string input;
     80     cin >> input;
     81 
     82     vector<vector<long long>> memo (5, vector<long long> (input.size(), -1));
     83 
     84     cout << solve(input,0,0, memo) << endl;
     85 }