10567 - Helping Fill Bates
Moderator: Board moderators
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.
thanks in advance
Dreamer
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
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
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
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
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.
-
- 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!!)
(A lengthy description, huh?)
So, are there anything better? It seems there can be something more simpler but I really don't know.![:(](./images/smilies/icon_frown.gif)
Thanks for a long read.![:)](./images/smilies/icon_smile.gif)
edit) There seems to be few types of memory usage: 20MB and 8MB majorly.
My solution is as follows: (Spoiler!!)
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..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.
(A lengthy description, huh?)
So, are there anything better? It seems there can be something more simpler but I really don't know.
![:(](./images/smilies/icon_frown.gif)
Thanks for a long read.
![:)](./images/smilies/icon_smile.gif)
edit) There seems to be few types of memory usage: 20MB and 8MB majorly.
JongMan @ Yonsei
-
- 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.
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.
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10567 - Helping Fill Bates
Input:AC output:
Code: Select all
a
1
a
Code: Select all
Matched 0 0
Check input and AC output for thousands of problems on uDebug!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10567 - Helping Fill Bates
Input:AC output:
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
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!
Re: 10567 - Helping Fill Bates
Got WA, but passed the test cases by brianfry.
I am wondering what am i missing here.
![:(](./images/smilies/icon_frown.gif)
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.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 10567 - Helping Fill Bates
Input:AC output:
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
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!