## 10567 - Helping Fill Bates

Moderator: Board moderators

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

### 10567 - Helping Fill Bates

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.

Dreamer
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
I have successfully solved it by binary search.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
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.

Dreamer
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Keep in mind there's only 52 characters.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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.

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Allocate memory as you go..

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am
I keep getting WA.. in 0.5 sec.

Could somebody give me some tricky I/O.

Thx.

koala
New poster
Posts: 7
Joined: Sun Mar 28, 2004 9:41 am
Location: Tsinghua University, Peking, P.R.China
Contact:

### To Whinii F.

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Whinii F. wrote: 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
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am
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
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

### Re: 10567 - Helping Fill Bates

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10567 - Helping Fill Bates

Input:

Code: Select all

``````a
1
a
``````
AC output:

Code: Select all

``````Matched 0 0
``````
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10567 - Helping Fill Bates

Input:

Code: Select all

``````GbAKfQMoTUzeoUAIcKBiqNdiSdZOReKaBRIJDDeFpPvENgAmUEifQTxQmcmvtAlxtmtobFiOEDbtcRIzsgGyeJcHQylOmiwYxfbnISwSNfLtbskpAlZhyTciDSioOlBizDVInqnIpjqkfgYkkxbBHFTQrjyORnnqpETFCyAhQBnUozjADQoAKPQEqXwOBNdMUICDKaRjLNAwSrxiJgbbDOIEgGXnMNjflIWAOYOuYfflBfxGAzaBpNeBKxDiMsDuqcuhFpGNBHxnfVjOMVWrbozBNLZyipoVYIxZkJOosqCALfxbvTMsfjlzbzfPVtZsHpESlhDExLHWyZNZGQYYOjoBVQoIGQcSGUvqberDTqLxIRFuusKaMeLRgnhOBCqUOCWNlNFdPgdPdnqHveqcnZYgTMlDXnzSINsdhbhWabOewzqrTbwuMmHytVfvUarmzwwAREZGdECNyHiblfssWiApRnWTnkyenttrhmrMzhZQDLqnFMtP
50
bZxGsxtYAOsZfwMrkvc
vFaQtmponNZRWonLycMxRXtYzGZti
qqXvMeAySEcJ
DuyTCFPeQraVlOUJ
dHaSyKrbTWBnzjesQZTNfCaqLxWa
ljZpSXvRvw
StBcnPVubhwgOLBl
HgqMaVDSu
RQomtKiepwqMkWTPMSLsGF
LTYsxPvrtl
OGVMFnL
VKjsceRygXIcTAHfdBOTHQQP
PmqwBWbZfgHiqxyiJqVo
nPsxPMlGquWWCoodeUcBW
iMBlVVEzMxx
frZDJcWeIDmdRShUGLMwJqLmczWIo
XDbxDfxTSuS
HRytdms
BCloHVuOXxxKiuupHeVccHofV
uOTWmkFNzEkNRnIJF
BfehkBNquhosDFur
WfElvGPAjZWIBGjjYJJTUmcyqRvb
haTlruiJpOvTvPKM
oTQpbNMtQERNq
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
``````
Check input and AC output for thousands of problems on uDebug!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 10567 - Helping Fill Bates

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

Code: Select all

``AC``
Last edited by moxlotus on Sun Dec 14, 2014 3:55 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10567 - Helping Fill Bates

Input:

Code: Select all

``````LnDWlKGqyeiKHqmnaanmEXhnsAUYAtkMkrmYGcJULEiktyORzyQDSLaiBVtvnsDcXqYocXjTvyyeORkzxbjostsQEFkSjUghJAzKcvqLCBbOiKCvcIMyvMhkpBiGainqBvsEPEPLEYdHyhtEAJXIIMdgjvMTUzbjHwKtRVddKEfkbOpGTDibFXBZdKejikWywVAiwQkmZzVLfdpsFtonllyoxfVZPDgrNSqrMaDKdXHCbccUIWwBrVTYZwUfFgFbpnMvtZBKYLgqFVZAwDEotMPzFiFXWxsNOBrUGJElwXVQsRodXXvbBBuTIWqAcvYWcmpCZaTqQjbPDxiZOnDwUcUsFUnMwWcvLwYUTjRCIgiQEmlcSMVNGdEXEKZuqoSYTDUcscPJgkxksRtZECWDOnkBUVvjIZUQeAZrOVFOkwsuKHweSDKJDYDmBXqZRGFTOuvBMkqGhozBxGvEYnGVongZbReseHAMmVPQaNBADeNmxThAIQqG
50
trdmzKHXzkARyqxYmzlNi
rIdEHfkWwsvQUboRgaHZuWEYBTCKS
gZXoHIquTXRpuDvAiQ
hjxwdiQMyegXbIPBFcTSTr
DHCrhC
ESwSCAkZJhRjjJpDpETq
TXtzKWsliWRRyhyjBHjZpyWozHFHG
emwEiTBDpZObro
ENPYpUmfEuRh
QUSNtJpXuvHzWObFnafaeHJcdY
zzzWUGvDNp
LrppJosufCXVdYuvlVMpeSogEv
qLlSRXxuopKjwDCmrttRnSQvf
pOv
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
``````
Check input and AC output for thousands of problems on uDebug!