Solution of LOJ3089

Posted on Edited on In Comments:

Problem Statement

link to loj.ac

Main Ideas

The Answer looks like a product of different items under a sqrt, therefore a basic tecnique is to use ln.

After this, calculation of product is changed to calculation of sum, which looks like:

Now the problem is to seek the maximum average value of gem sequences that match the model string.

When a problem of strings contains ONE model and MANY patterns, AC Automaton should come to one’s mind at once!

We build the AC Automaton for the model string, and do dynamic programming on it, thus the problem should be solved.

MIND that each node on the AC Automaton should inherit all the information of its ancestors on the fail-pointer tree.

When a problem that asks for minimize/maximize the average for a certain set of values, Linear Programming should come to one’s mind at once!

Assume that the average for the current set of model strings is $C$, it is obvious that we can do binary search to determine its value.

Then if there is a set of {w} that results in an average larger than $C$, the following expression should be true:

Now we can use the sign of the largest possibel to determine if the current is the answer.

The benefit of this algorithm is that we can delete one dimension of our DP on the AC Automaton, thus the Complexity is divided by

We assume represents this state: iteration on the first characters of the model string has been finished, and the pointer on AC Automaton is at node

If the next character of the model string is fixed, we simply update the value for ,

else we’ll have to update all values of

For more Details, refer to the code

Copy Code


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/*------------------------------
Author: Orion545
Date: 2019/05/16
Time: 157 min
------------------------------*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<queue>
#include<cmath>
#define ll long long
using namespace std;
inline int read(){
    int re=0,flag=1;char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') flag=-1;
        ch=getchar();
    }
    while(isdigit(ch)) re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re*flag;
}
int n,m;double w[1510];
char a[1510],s[1510][1510];
int ch[1510][10],cntn=0,num[1510],fail[1510];
double sum[1510];
//AC Automaton
inline void insert(int x,int len){
    int i,cur=0,tmp;
    for(i=1;i<=len;i++){
        tmp=s[x][i]-'0';
        if(!ch[cur][tmp]) ch[cur][tmp]=++cntn;
        cur=ch[cur][tmp];
    }
    num[cur]++;sum[cur]+=w[x];
}
queue<int>q;
inline void build(){
    int i,u,v;
    for(i=0;i<10;i++){
        if(!ch[0][i]) continue;
        q.push(ch[0][i]);fail[ch[0][i]]=0;
    }
    while(!q.empty()){
        u=q.front();q.pop();
        num[u]+=num[fail[u]];
        sum[u]+=sum[fail[u]];
        for(i=0;i<10;i++){
            v=ch[u][i];
            if(v) fail[v]=ch[fail[u]][i],q.push(v);
            else ch[u][i]=ch[fail[u]][i];
        }
    }
}
//Dynamic Programming
double dp[1510][1510];
int from[1510][1510][2],endpos;
inline bool check(double mid){
    int i,j,k,son;
    for(i=0;i<=n;i++) for(j=0;j<=cntn;j++) dp[i][j]=-2e20;
    for(i=0;i<=cntn;i++){
        sum[i]-=mid*(double)num[i];//cut the value according to binary search process
    }
    dp[0][0]=0;
    for(i=1;i<=n;i++){
        for(j=0;j<=cntn;j++){
            if(dp[i-1][j]==-2e20) continue;
            if(a[i]!='.'){//character is fixed in original S
                son=ch[j][a[i]-'0'];
                if(dp[i][son]<dp[i-1][j]+sum[son]){
                    dp[i][son]=dp[i-1][j]+sum[son];
                    from[i][son][0]=j;//record the source of the maximum value
                    from[i][son][1]=a[i]-'0';//record the corresponding character
                }
            }
            else{//character is unfixed
                for(k=0;k<10;k++){
                    son=ch[j][k];
                    if(dp[i][son]<dp[i-1][j]+sum[son]){
                        dp[i][son]=dp[i-1][j]+sum[son];
                        from[i][son][0]=j;
                        from[i][son][1]=k;
                    }
                }
            }
        }
    }
    int pos=0;
    for(i=1;i<=cntn;i++) if(dp[n][i]>dp[n][pos]) pos=i;
    for(i=0;i<=cntn;i++) sum[i]+=mid*(double)num[i];//repair the value cut
    endpos=pos;return dp[n][pos]>0;//determine if largest value is over zero
}
char re[1510];
int main(){
    n=read();m=read();int i;
    scanf("%s",a+1);
    for(i=1;i<=m;i++){
        scanf("%s",s[i]+1);
        w[i]=read();
        w[i]=log((double)w[i]);
        insert(i,strlen(s[i]+1));
    }
    build();
    double l=0,r=log(1e9+7),mid,ans=0;
    while(r-l>1e-6){//binary search
        mid=(l+r)*0.5;
        if(check(mid)) ans=mid,l=mid;
        else r=mid;
    }
    check(ans);
    for(i=n;i>=1;i--){//get the answer string
        re[i]=from[i][endpos][1]+'0';
        endpos=from[i][endpos][0];
    }
    for(i=1;i<=n;i++) putchar(re[i]);
    putchar('\n');
}

0%