| Show all threads Hide all threads Show all messages Hide all messages |
| i solved dp[i] - the number of sequences of length i | >>> | 1081. Binary Lexicographic Sequence | 6 Apr 2024 22:41 | 3 |
dp[i][j] - amount of i-digit numbers ending with j.
therefore we form 2d table dp[n][2]
then
dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
dp[i][1] = dp[i - 1][1]
It's not hard to see that dp[i][0] + dp[i][1] (i.e. number of all valid sequences) forms a fibonacci sequence.
dp[i][0] + dp[i][1] = 2*dp[i - 1][0] + dp[i - 1][1]
you can treat as f_n = 2*f_(n - 2) + f_(n - 3)
But still, I don't know how to solve this problem :)
Edited by author 23.01.2022 01:36
Edited by author 23.01.2022 01:37 dp[i][1] = dp[i - 1][1] is wrong, should be:
dp[i][1] = dp[i - 1][0] |
| AC with this formula | Sergey | 1081. Binary Lexicographic Sequence | 18 Apr 2023 17:54 | 6 |
I've used this formula to solve this problem:
a(n) = 2^(b(n)-1) + a(n - c(1+b(n)))
b(n) = -1+floor(log(((n+0.2)*sqrt(5)))/log((1+sqrt(5))/2));
c(0) = 0, c(1) = 1, c(n) = c(n-1) + c(n-2) I don't want to live in this world anymore. wow!!!! you probably made an easy thing too complicated. Looks like you're using golden ratio to calculate Fibonacci Way too complicated. I solved entirely using bitwise operations and an array with the first 64 Fibonacci numbers. |
| Admins, cannot submit any kind of rust solution for this problem | motoras | 1081. Binary Lexicographic Sequence | 21 Feb 2019 16:16 | 2 |
I get, Runtime error (non-zero exit code), even if I send a program such:
fn main() {
println!("{}",-1);
} If I paste the solution, in the submission text box, I am able to get an answer from the judge. If I uploaded I always get "Runtime error (non-zero exit code)" |
| How to solve this tusk? | 4llower | 1081. Binary Lexicographic Sequence | 9 Apr 2018 15:50 | 1 |
|
| nice problem | CaCO3 | 1081. Binary Lexicographic Sequence | 22 Dec 2017 08:10 | 1 |
|
| please help! I have WA10! Give me some tests | Husan | 1081. Binary Lexicographic Sequence | 25 Sep 2016 17:31 | 3 |
it could be useful if the poor guy is not dead already |
| TLE#5, how can i solv this with fibonachchi, | Bobur | 1081. Binary Lexicographic Sequence | 25 Jul 2016 13:18 | 7 |
i solved, but my algo so slow, how can i solve this problem faster,
sorry for my english.
thx! Lets consider the sequence for n=4:
0000
0001
0010
0100
0101
1000
1001
1010
Try to find a connection between the number of all sequences with length 4, those which begin with 0 and those which begin with 1. After that look "deeper" and "deeper" into each sequence and try to find a way to generate the k-th sequence. Sorry that I'm not telling you the algorithm directly, but the feeling when you discover it yourself is great :) (it's even greater when you get Acc from 1-st submition :P). I hope that you find this helpful. thanks a lot, i think i can find it!! wow
i feel good ¬¬_.'[smoke]
ty for the idea Tnk u. Ur hint is very helpful. I got AC! Lets consider the sequence for n=4:
0000
0001
0010
0100
0101
1000
1001
1010
Try to find a connection between the number of all sequences with length 4, those which begin with 0 and those which begin with 1. After that look "deeper" and "deeper" into each sequence and try to find a way to generate the k-th sequence. Sorry that I'm not telling you the algorithm directly, but the feeling when you discover it yourself is great :) (it's even greater when you get Acc from 1-st submition :P). I hope that you find this helpful. Thank u so much.... :) It really feels wow... :D |
| What is Test 6? | Sherxon WIUT | 1081. Binary Lexicographic Sequence | 25 Jul 2016 13:09 | 2 |
Please give me test 6? Try these Tests: Test 1: 43 999999999 Ans=>1010000100100001010101000001000101000100101 Test 2: 42 999999999 Ans=> -1 Test 3: 40 100000000 Ans=>0010101001010100001010000010101010000010 |
| WA 8 | aslan7470 | 1081. Binary Lexicographic Sequence | 16 Mar 2015 15:21 | 1 |
WA 8 aslan7470 16 Mar 2015 15:21 |
| What's up with test #6 ? | Haile | 1081. Binary Lexicographic Sequence | 18 Nov 2013 14:46 | 1 |
My damned solution keep giving WA on test 6 with C11. I tested on big numbers and every corner case (yes, it works with 1 1 -> '0', yes, it gives '-1' on 3 6, etc..)
Suggestions? What's in test 6?
The exact same algorithm in python gives AC.. (and it's not a bignum issue, I tested the C version with 43 and 10**9)
Edited by author 24.11.2013 01:26 |
| Accepted | Freezing Sun | 1081. Binary Lexicographic Sequence | 24 Mar 2013 15:05 | 4 |
The same, AC 0.015 and 112 KB |
| Crash why ? | rrpai | 1081. Binary Lexicographic Sequence | 22 Jul 2012 08:12 | 7 |
My java program crashes for this. I do not understand why. I tested for even big inputs and it is working fine for me in my machine. How do I know where it crashed ? No information is given by judge. Test 6 contains numbers on different lines (I suppose so). I have Crash in my C# program on this test. And now it is AC! I have the same trouble, also with java!
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
Above is like the A+B problem, I think it's right.
Any one can help me plz?~:) I have the same trouble, also with java!
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
Above is like the A+B problem, I think it's right.
Any one can help me plz?~:) I have the same trouble, also with java!
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
Above is like the A+B problem, I think it's right.
Any one can help me plz?~:) I know why crash!~
for the input:40 1000000000 no problem
what about this one: 1 1
I carsh because can't pass 1 1
But now AC~~~ |
| WA7 | imereli | 1081. Binary Lexicographic Sequence | 6 Jul 2012 00:23 | 1 |
WA7 imereli 6 Jul 2012 00:23 do you have any idea about this test? |
| Help ! What's the meaning of this problem ??? | vongang | 1081. Binary Lexicographic Sequence | 27 Jan 2012 23:56 | 2 |
You should print lexicographically kth sequence for length n
like for n=3
we have,
000 -- 1st
001 -- 2nd
010 -- 3rd
100 -- 4th
101 -- 5th
and for n=4
0000 - 1
0001 - 2
0010 - 3
0100 - 4
and so on.. you find kth sequence for length n :)
Hope it helps > :) |
| Problem 1081 "Binary Lexicographic Sequence". New tests were added. (+) | Sandro (USU) | 1081. Binary Lexicographic Sequence | 15 Sep 2011 13:43 | 3 |
74 authors lost AC after rejudge. I believe the tests are still weak. My solution which answers with "110...0" to "4 4", "5 6", "7 14", "8 22" got Accepted.
Edited by author 15.09.2011 03:00
Edited by author 15.09.2011 03:00 I've added these tests, but you seem to be the only author who doesn't pass them. :) |
| test#1 | ENick(TNU) | 1081. Binary Lexicographic Sequence | 26 Jul 2010 17:01 | 3 |
test#1 ENick(TNU) 28 Sep 2008 19:08 Please,take me a test#1.My program's output on example test are "000",but got WA#1 many times....(((
Edited by author 28.09.2008 19:09 I think you forget this:"Write −1 if the number K is larger than the number of valid sequences" |
| Give advices to the person who has WA#1 | bobchennan | 1081. Binary Lexicographic Sequence | 24 Jun 2009 23:30 | 2 |
It's very easy.
TEST#1 is a data which result is -1(It means "no answer").
I submit my program ,and accept!
Edited by author 07.05.2009 17:59 Ops, he already found decision=)
Edited by author 24.06.2009 23:32 |
| help me | hhh | 1081. Binary Lexicographic Sequence | 12 Mar 2009 16:10 | 1 |
#include <iostream>
using namespace std;
long long n,k,a[45],i=0,b[50],j,t=0,r=0,z,c[50];
int main()
{
cin>>n>>k; a[0]=1; a[1]=2; t=n;
for(i=2; i<=n; i++) a[i]=a[i-1]+a[i-2];
if(k>a[n]) { z=-1; cout<<z; return 0; }
else{ b[1]=b[2]=0; b[3]=1; b[4]=2;
for(i=5; i<=n; i++) b[i]=2*b[i-1]+1;
while(a[i]<=k) { i++; j=i; }
for(i=1; i<=j; i++) z+=b[i];
r=k+z-1;
while(r!=0) { c[t]=r%2; r/=2; t--; }
for(i=1; i<=n-t; i++) c[i]=0;
for(i=1; i<=n; i++) cout<<c[i];
return 0; }}
wa#2 |
| what's wrong? | Alias (Alexander Prudaev) | 1081. Binary Lexicographic Sequence | 17 Jan 2008 09:59 | 2 |
WA#9 But, Why? It' is right program!
int p = n;
for (int i = 0; i < n; i++)
{
if (f[p]>=k) s[i] = '0';
else
{
s[i] = '1';
k -= f[p];
}
p--;
}
s[n] = 0;
printf("%s\n",s);
f[1] = 1,
f[2] = 2,
f[i] = f[i-1]+f[i-2];
Edited by author 15.03.2007 18:38 you forgot about -1. When k is bigger than all possible sequences then the answer is -1 |
| I don't understand what's wrong . | Juri Krainjukov | 1081. Binary Lexicographic Sequence | 13 Mar 2007 12:53 | 5 |
I checked this program for all sequences n<= and it worked properly.
I don't see any reasons why it shouldn't work with another n.
[code deleted]
Edited by moderator 13.02.2007 20:54 I have approximately the same solution
And I'm having WA6
What can be wrong?
[code deleted]
Edited by author 05.02.2007 03:03
Edited by moderator 13.02.2007 20:54 Finally found out the problem. When you solve this problem take a look to overflows! Finally found out the problem. When you solve this problem take a look to overflows! I don't understand what overflow we can have. For N=43 the number of different sequences is equal to 1,134,903,170 (fits to int32). |
