algorithms

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

problem.txt (2767B)


      1 B. WOW Factor
      2 time limit per test1 second
      3 memory limit per test256 megabytes
      4 Recall that string a
      5  is a subsequence of a string b
      6  if a
      7  can be obtained from b
      8  by deletion of several (possibly zero or all) characters. For example, for the string a
      9 ="wowwo", the following strings are subsequences: "wowwo", "wowo", "oo", "wow", "", and others, but the following are not subsequences: "owoo", "owwwo", "ooo".
     10 
     11 The wow factor of a string is the number of its subsequences equal to the word "wow". Bob wants to write a string that has a large wow factor. However, the "w" key on his keyboard is broken, so he types two "v"s instead.
     12 
     13 Little did he realise that he may have introduced more "w"s than he thought. Consider for instance the string "ww". Bob would type it as "vvvv", but this string actually contains three occurrences of "w":
     14 
     15 "vvvv"
     16 "vvvv"
     17 "vvvv"
     18 For example, the wow factor of the word "vvvovvv" equals to four because there are four wows:
     19 
     20 "vvvovvv"
     21 "vvvovvv"
     22 "vvvovvv"
     23 "vvvovvv"
     24 Note that the subsequence "vvvovvv" does not count towards the wow factor, as the "v"s have to be consecutive.
     25 
     26 For a given string s
     27 , compute and output its wow factor. Note that it is not guaranteed that it is possible to get s
     28  from another string replacing "w" with "vv". For example, s
     29  can be equal to "vov".
     30 
     31 Input
     32 The input contains a single non-empty string s
     33 , consisting only of characters "v" and "o". The length of s
     34  is at most 106
     35 .
     36 
     37 Output
     38 Output a single integer, the wow factor of s
     39 .
     40 
     41 Examples
     42 InputCopy
     43 vvvovvv
     44 OutputCopy
     45 4
     46 InputCopy
     47 vvovooovovvovoovoovvvvovovvvov
     48 OutputCopy
     49 100
     50 Note
     51 The first example is explained in the legend.
     52 
     53 ---
     54 
     55 - a is a subsequence of b iff a can be created by removing elements from b
     56 - wow factor := number of subsequences == "wow"
     57 - we use vv as a stand in for w
     58 - vvvv gives us three ways to make w's (always # of v's - 1)
     59 - each string is made of only v's and o's
     60 
     61 ---
     62 
     63 examples:
     64 
     65 vvvovvv
     66 
     67 vv_ovv_
     68 vv_ov_v
     69 vv_ovv_
     70 vv_ov_v
     71 
     72 in each example, we may take a v (or skip it), take another v (or skip it), and if we already have 2 v's then we may take the next o, ..., and after we've taken a o, we may take up to two more v's.
     73 
     74 string size is at most 10**6 = 100_000
     75 
     76 a naive approach would be evaluating, basically, 2**n selections if all elements are v's
     77 
     78 the state is as follows:
     79 
     80 - s(fvc,oc,svc)
     81     - fvc == first v count (0->2)
     82     - oc == o count (0->1)
     83     - svc == second v count (0->2)
     84 - s(ct)
     85     - ct ranges from 0->5
     86         - vv o vv
     87             - when ct == 5, we have found one
     88         - when ct == 4 or 3, we can take a 4
     89         - ...
     90 
     91 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
     92 
     93 ---
     94 
     95 vvovooovovvovoovoovvvvovovvvov