10567 - Helping Fill Bates

[Dreamer#1]

hello ppl,

to me this seems to be an algorithm specific problem but i couldn't figure out what algorithm to use, it would be really nice if someone can give me some hints on how to solve it without facing TLE.

thanks in advance

Dreamer

[marian]

I have successfully solved it by binary search.

[Dreamer#1]

thanks marian.

so it requires binary search. i'm pretty weak in binary search may be thats the reason i wasn't finding any way to solve it. never thought of binary search.

still i don't know how to apply binary search on this problem. can you help me a little more. this problem is the first of its kind to me. so you can understand why i'm having trouble in figuring out how to solve it with binary search.

it would be really nice of you to write a little on how your solution using binary search works.

thanks for you reply

Dreamer

[Larry]

Keep in mind there's only 52 characters.

[Whinii F.]

Hi, I just solved this problem with binary search but I am really curious about whether there might be an observation I am missing, which can lead to a simpler solution.

My solution is as follows: (Spoiler!!)

For the sequence S, keep an array COUNT of 52 elements for each of the letters S_i, where COUNT[i, l] means how many letter l s appeared before (and including) S_i.

So we take the first letter and we need the first location loc_1 where COUNT[loc_1][first_letter] >= 1. We can do this with binary search. And for the next letter, what we need is the first location loc_2 where COUNT[loc_2][next_letter] > COUNT[loc_1][next_letter].

My program repeats this process until all letters are found || there is no location that suffices the condition.

But, the array size is the problem because we have a million elements, so having an int[52] for all of the letters will cost 1000*1000*52*4 = approx. 200MB. So I made arrays only for letters S_i where i is divisible by 10. So this gives 20MB memory usage. After that I dynamically found each of the COUNT by linear search..

(A lengthy description, huh?)

So, are there anything better? It seems there can be something more simpler but I really don't know.

Thanks for a long read.

edit) There seems to be few types of memory usage: 20MB and 8MB majorly.

[Larry]

Allocate memory as you go..

[subbu]

I keep getting WA.. in 0.5 sec.

Could somebody give me some tricky I/O.

Thx.

[koala]

To Whinii F. :

Yes, there is a more simple method.

Let Pos[ch(Char),i(Longint)] be the position of i-th ch in S. Because Pos[ch,i]<Pos[ch,i+1], Binary Search can be used here, too.

Let Length(ch) be the length of array Pos[ch]. Obviously, Length('A')+Length('B')+...+Length('Z')+Length('a')+...+Length('z')=Length(S)<=10^6. So MLE can be avoided by using the procedure of Getmem in Pascal.

I am not a C user, but there must be a procedure similar to Getmem.

[minskcity]

It seems there can be something more simpler but I really don't know.

My algorithm (using sets and lower_bound ) is 5 lines and really simple, but uses 25Mb and 6 seconds...

[subbu]

to minskcity:

I am guessing you r doing the same thing as i am.

Try using the hint form of insertion into the set,to make it
constant time per insertion.

[Eather]

Im getting WA. Any test cases please??

Code: Select all

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<algorithm>
#include<set>
#include<cstdio>
#include<sstream>
using namespace std;

int pel(string s){string t;t=s;reverse(t.begin(),t.end());if(s==t)return 1;return 0;}
string toString(int n){ostringstream ost;ost<<n;ost.flush();return ost.str();}
int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
bool isprime(int m){if(m<2) return 0;for( int i=2; i*i<=m ; i++)if(m%i==0)return 0; return 1;return 0;}

# define __(array,w)   memset(array,w,sizeof array)
# define FOR(i, a, b) for (int i=a; i<b; i++)
# define REP(i, a) FOR(i,0,a)
# define all(c) (c).begin(), (c).end()
# define sz(x) x.size()
# define pb push_back
# define UNQ(s) {sort(all(s));(s).erase(unique(all(s)),s.end());}
# define rive(s) reverse(s.begin(),s.end())
# define out(a) cout<<#a<<" #"<<a<<endl;
# define caout(a) cout<<#a<<" "<<++a<<": ";

int main()
{
    string s;
    vector<string>vs,vt;

    map<char,long long>mp,mq,mpi;

    cin>>s;

    REP(i,26)
    {
        char c=i+'A';
        mp[c]=count(all(s),c);
    }
    REP(i,26)
    {
        char c=i+'a';
        mp[c]=count(all(s),c);
    }

    int many;
    cin>>many;

    while(many--)
    {
        string t;
        cin>>t;
        bool f=0;
        long long  up,low;
        REP(i,26)
        {
            char c=i+'A';
            mq[c]=count(all(t),c);
            if(mq[c]>mp[c])f=1;
        }
        REP(i,26)
        {
            char c=i+'a';
            mq[c]=count(all(t),c);
            if(mq[c]>mp[c])f=1;
        }
        bool e,g;e=0,g=0;
        REP(i,sz(s))
        {if(e==0 &&s[i]==t[0]){low=i;e=1;}
        else if(g==0 && s[i]==t[sz(t)-1]){up=i+mq[t[sz(t)-1]]-1;g=1;}if(e==1&&g==1)break;}

        if(f==1)cout<<"Not matched"<<endl;
        else cout<<"Matched "<<low<<" "<<up<<endl;
        mq.clear();

    }
    return 0;
}

[brianfry713]

Input:

Code: Select all

a
1
a

AC output:

Code: Select all

Matched 0 0

[brianfry713]

Input:

Code: Select all

GbAKfQMoTUzeoUAIcKBiqNdiSdZOReKaBRIJDDeFpPvENgAmUEifQTxQmcmvtAlxtmtobFiOEDbtcRIzsgGyeJcHQylOmiwYxfbnISwSNfLtbskpAlZhyTciDSioOlBizDVInqnIpjqkfgYkkxbBHFTQrjyORnnqpETFCyAhQBnUozjADQoAKPQEqXwOBNdMUICDKaRjLNAwSrxiJgbbDOIEgGXnMNjflIWAOYOuYfflBfxGAzaBpNeBKxDiMsDuqcuhFpGNBHxnfVjOMVWrbozBNLZyipoVYIxZkJOosqCALfxbvTMsfjlzbzfPVtZsHpESlhDExLHWyZNZGQYYOjoBVQoIGQcSGUvqberDTqLxIRFuusKaMeLRgnhOBCqUOCWNlNFdPgdPdnqHveqcnZYgTMlDXnzSINsdhbhWabOewzqrTbwuMmHytVfvUarmzwwAREZGdECNyHiblfssWiApRnWTnkyenttrhmrMzhZQDLqnFMtP
50
bZxGsxtYAOsZfwMrkvc
vFaQtmponNZRWonLycMxRXtYzGZti
XqzLVvzAdgosVIaX
qqXvMeAySEcJ
DuyTCFPeQraVlOUJ
dHaSyKrbTWBnzjesQZTNfCaqLxWa
ljZpSXvRvw
StBcnPVubhwgOLBl
HgqMaVDSu
RQomtKiepwqMkWTPMSLsGF
LTYsxPvrtl
OGVMFnL
VKjsceRygXIcTAHfdBOTHQQP
PmqwBWbZfgHiqxyiJqVo
nPsxPMlGquWWCoodeUcBW
jqAzaKQiyOzymBpOADiQQFmRJ
iMBlVVEzMxx
frZDJcWeIDmdRShUGLMwJqLmczWIo
XDbxDfxTSuS
HRytdms
BCloHVuOXxxKiuupHeVccHofV
uOTWmkFNzEkNRnIJF
BfehkBNquhosDFur
WfElvGPAjZWIBGjjYJJTUmcyqRvb
haTlruiJpOvTvPKM
oTQpbNMtQERNq
eHMXGadcPa
ynEU
HL
Xc
ebmQifRqQDH
SsMZBDVbQe
qwhtNjcfaCKdPjivsItRMC
hdTZRVeiefrsaldETBwuTnZkFcxW
j
knpuQdIjoMlvmLCJTuNygpUYvgeW
Hwl
jbXcfutmIAUGDNTOHBUlXdbiJbg
ljk
OVay
vW
LJICTDJWsoFfBautp
aFlwMWeWQzqxRIgBhA
yznRgQkklcIjcgUXS
HXMYVRXJaKnG
HuuIWqreQCVl
NutennQLGzAxGitBkfPWrtbSb
ClezoTBDhEjFRoOQgH
GmZyQxkSqtBtmRSOiyPydpg
ZICxTfaZ

AC output:

Code: Select all

Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Matched 87 367
Not matched
Matched 106 464
Matched 27 281
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Matched 185 415
Matched 87 466
Not matched
Not matched
Matched 18 431
Not matched
Not matched
Not matched
Not matched
Matched 83 171
Matched 87 106
Matched 185 257
Not matched
Not matched
Not matched
Not matched
Matched 137 137
Not matched
Matched 87 113
Not matched
Matched 62 139
Matched 27 283
Matched 42 226
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Matched 26 405

[moxlotus]

Got WA, but passed the test cases by brianfry.
I am wondering what am i missing here.

Code: Select all

AC

[brianfry713]

Input:

Code: Select all

LnDWlKGqyeiKHqmnaanmEXhnsAUYAtkMkrmYGcJULEiktyORzyQDSLaiBVtvnsDcXqYocXjTvyyeORkzxbjostsQEFkSjUghJAzKcvqLCBbOiKCvcIMyvMhkpBiGainqBvsEPEPLEYdHyhtEAJXIIMdgjvMTUzbjHwKtRVddKEfkbOpGTDibFXBZdKejikWywVAiwQkmZzVLfdpsFtonllyoxfVZPDgrNSqrMaDKdXHCbccUIWwBrVTYZwUfFgFbpnMvtZBKYLgqFVZAwDEotMPzFiFXWxsNOBrUGJElwXVQsRodXXvbBBuTIWqAcvYWcmpCZaTqQjbPDxiZOnDwUcUsFUnMwWcvLwYUTjRCIgiQEmlcSMVNGdEXEKZuqoSYTDUcscPJgkxksRtZECWDOnkBUVvjIZUQeAZrOVFOkwsuKHweSDKJDYDmBXqZRGFTOuvBMkqGhozBxGvEYnGVongZbReseHAMmVPQaNBADeNmxThAIQqG
50
trdmzKHXzkARyqxYmzlNi
rIdEHfkWwsvQUboRgaHZuWEYBTCKS
gZXoHIquTXRpuDvAiQ
hjxwdiQMyegXbIPBFcTSTr
DHCrhC
ESwSCAkZJhRjjJpDpETq
TXtzKWsliWRRyhyjBHjZpyWozHFHG
emwEiTBDpZObro
ENPYpUmfEuRh
QUSNtJpXuvHzWObFnafaeHJcdY
zzzWUGvDNp
LrppJosufCXVdYuvlVMpeSogEv
qLlSRXxuopKjwDCmrttRnSQvf
pOv
bbwmadRkdZkLWejIDzFrVyoaOUfo
TBZxpoqZTCOSQxhPrWJBvcmZt
jDpxCEsBioulSGjKjULnU
ozCpSyQ
qotSykXh
BwqSJHGscAOa
NhLya
nDNyycODtaScGnEhRSZblCig
GfZhKKzYXLIdpVM
soWaunuZsT
IdTtXYqqwxFNZsrwrWYqUrjq
PFmRA
dBwERT
mytUeAHcsmG
IiLpQVnGhaQfNLtqkcF
XqaPaapiICLFIrl
kNZjKayvHrbYXJRAvwyWSYxHLyOfFQ
SjAHH
Hsljzmk
pvzSWTAY
QmXaHojIOvQABleKoxZMoCWuIO
oBWySbsSfGDfDyGxLrG
YAeKxfsOSiPO
oDXVbQbrw
lPwvGZCfCW
LDtbydaNEIXVRgSkAT
xPQkSGUSVycNKYMrITmA
gMtcrRlcNRZsVwUTdJy
PEvmlssPsyGOGRUSPUWl
GuVXwMjgka
MFsOKMkJOeCvLKaFJuoHbnKvomfQKS
xOXYXjLFTA
TEWqDMKDWa
TWqhKOIkteOBPjGdkzQW
MvDIcScDqQqgthHOcljkWZL
bbfGogBf

AC output:

Code: Select all

Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Matched 120 259
Not matched
Not matched
Not matched
Not matched
Matched 7 456
Not matched
Not matched
Not matched
Not matched
Matched 24 447
Not matched
Matched 132 315
Matched 138 311
Matched 14 372
Not matched
Not matched
Not matched
Matched 52 160
Not matched
Matched 120 318
Not matched
Not matched
Not matched
Matched 67 425
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Not matched
Matched 80 478
Matched 71 325
Not matched
Not matched
Matched 81 251