11127 - Triple-Free Binary Strings

vinay · Post by **vinay** » Sun Oct 15, 2006 2:56 pm

what algo to use ...

I think somee dp...

any hint about it and the algo complexity...

sclo · Post by **sclo** » Wed Oct 18, 2006 2:16 am

I can't see the dp yet. Can it be backtracking?

vinay · Post by **vinay** » Wed Oct 18, 2006 2:23 am

some one hhelp on this topic...

no reponses yet

sclo · Post by **sclo** » Wed Oct 18, 2006 2:24 am

I'll try backtracking.

vinay · Post by **vinay** » Wed Oct 18, 2006 2:27 am

do respond if accepted...

thanks in advance..

sclo · Post by **sclo** » Wed Oct 18, 2006 2:52 am

I got AC.

Whether or not you get TLE will depends how fast you can do the following.
Input:

Code: Select all

30 ******************************

Output:

Code: Select all

Case 1: 230800

vinay · Post by **vinay** » Wed Oct 18, 2006 3:33 am

what is ur algo...???

rushel · Post by **rushel** » Wed Oct 18, 2006 8:37 am

Its a simple backtracking and u have to check triples efficienty.

suppose u have string S so far in backtracking and s is a suffix of S and |s| should be multiple of 3. use this idea.

thanks

vinay · Post by **vinay** » Wed Oct 18, 2006 5:46 pm

it tle's.....
here is my code...

how can i improve upon it??

Code: Select all

edit: ACC  :)

sclo · Post by **sclo** » Wed Oct 18, 2006 7:40 pm

the way that you use stl string makes it tle. You keep passing string as argument to your functions, which is slow. You don't need to pass any string as argument, just keep it simple and working directly with a char array is enough.

vinay · Post by **vinay** » Wed Oct 18, 2006 8:07 pm

thanks ...
its AC in 1.682 secs..

strings are really very slow....
i need to minimize thrie usage

coolguy · Post by **coolguy** » Thu Jan 04, 2007 1:39 am

im getting TLE in this problem. any possible optimization u want me to consider. i used backtracking. here is the code:

GOT AC

CODE DELETED

thank you

Jan · Post by **Jan** » Thu Jan 04, 2007 3:10 pm

You are checking the validity after calculating a full sequence. Try to check the validity while calculating a sequence.

Input:

Code: Select all

30 000***************************
0

Output:

Code: Select all

Case 1: 0

You will see the output instantly if your code is alright.

coolguy · Post by **coolguy** » Fri Jan 05, 2007 3:25 am

Jan wrote:

You are checking the validity after calculating a full sequence.

this is not right. i did check for validity after putting every character. my problem was that i didn't check the validity efficiently. my code for checking the validity was naive, now i changed it and got ac in around 3 seconds. thank you anywayz for your reply Jan.
BYE

OJ Board

11127 - Triple-Free Binary Strings

11127 - Triple-Free Binary Strings

algo

getting TLE

about tle in 11127 triple binary string