10567 - Helping Fill Bates

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10567 - Helping Fill Bates

Post by Dreamer#1 » Thu Oct 23, 2003 8:30 pm

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
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:

Post by marian » Thu Oct 23, 2003 10:58 pm

I have successfully solved it by binary search.

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

Post by Dreamer#1 » Thu Oct 23, 2003 11:26 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.

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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Oct 24, 2003 1:48 am

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:

Post by Whinii F. » Fri Oct 24, 2003 7:23 pm

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.
JongMan @ Yonsei

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Oct 24, 2003 8:30 pm

Allocate memory as you go..

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu » Fri Oct 24, 2003 10:45 pm

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.

Post by koala » Fri Apr 02, 2004 9:35 am

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

Post by minskcity » Wed Apr 07, 2004 6:14 am

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

Post by subbu » Thu Apr 08, 2004 1:47 pm

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

Post by Eather » Wed Jul 27, 2011 8:08 pm

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

Post by brianfry713 » Thu Mar 27, 2014 11:03 pm

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

Post by brianfry713 » Fri Apr 11, 2014 10:40 pm

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
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

Post by moxlotus » Thu Dec 11, 2014 8:49 am

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

Post by brianfry713 » Thu Dec 11, 2014 10:17 pm

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
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 105 (10500-10599)”