| ENG RUS | Timus Online Judge |
Discussion of Problem 1081. Binary Lexicographic Sequence>>> i solved dp[i] - the number of sequences of length i [2] // Problem 1081. Binary Lexicographic Sequence 21 Oct 2021 00:48 Ivan Re: i solved dp[i] - the number of sequences of length i [1] // Problem 1081. Binary Lexicographic Sequence 23 Jan 2022 01:33 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 So Sui Ming Re: i solved dp[i] - the number of sequences of length i // Problem 1081. Binary Lexicographic Sequence 6 Apr 2024 22:41 dp[i][1] = dp[i - 1][1] is wrong, should be: dp[i][1] = dp[i - 1][0] Sergey AC with this formula [5] // Problem 1081. Binary Lexicographic Sequence 9 Oct 2011 01:01 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) daftcoder [Yaroslavl SU] Re: AC with this formula // Problem 1081. Binary Lexicographic Sequence 16 Oct 2011 17:46 INSANE! htzfun Re: AC with this formula // Problem 1081. Binary Lexicographic Sequence 1 May 2012 17:44 I don't want to live in this world anymore. Md. Taufique Hussain Re: AC with this formula // Problem 1081. Binary Lexicographic Sequence 3 Jun 2013 13:32 wow!!!! you probably made an easy thing too complicated. Shubh Srivastava Re: AC with this formula // Problem 1081. Binary Lexicographic Sequence 24 May 2018 00:24 Looks like you're using golden ratio to calculate Fibonacci Hristo Nikolaev (B&W) Re: AC with this formula // Problem 1081. Binary Lexicographic Sequence 18 Apr 2023 17:54 Way too complicated. I solved entirely using bitwise operations and an array with the first 64 Fibonacci numbers. motoras Admins, cannot submit any kind of rust solution for this problem [1] // Problem 1081. Binary Lexicographic Sequence 21 Feb 2019 15:24 I get, Runtime error (non-zero exit code), even if I send a program such: fn main() { println!("{}",-1); } motoras Re: Admins, cannot submit any kind of rust solution for this problem // Problem 1081. Binary Lexicographic Sequence 21 Feb 2019 16:16 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)" 4llower How to solve this tusk? // Problem 1081. Binary Lexicographic Sequence 9 Apr 2018 15:50 CaCO3 nice problem // Problem 1081. Binary Lexicographic Sequence 22 Dec 2017 08:10 it's cooooooool Husan please help! I have WA10! Give me some tests [2] // Problem 1081. Binary Lexicographic Sequence 6 Mar 2008 19:36 Posazhennikov Maksim Re: please help! I have WA10! Give me some tests [1] // Problem 1081. Binary Lexicographic Sequence 16 Jul 2013 01:35 1 10 S.Ged Re: please help! I have WA10! Give me some tests // Problem 1081. Binary Lexicographic Sequence 25 Sep 2016 17:31 it could be useful if the poor guy is not dead already Bobur TLE#5, how can i solv this with fibonachchi, [6] // Problem 1081. Binary Lexicographic Sequence 23 Mar 2008 16:22 i solved, but my algo so slow, how can i solve this problem faster, sorry for my english. thx! PersonalJesus Re: TLE#5, how can i solv this with fibonachchi, [5] // Problem 1081. Binary Lexicographic Sequence 17 Apr 2008 17:16 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. Bobur Re: TLE#5, how can i solv this with fibonachchi, // Problem 1081. Binary Lexicographic Sequence 7 May 2008 18:53 thanks a lot, i think i can find it!! Bobur now, i've AC too!! [1] // Problem 1081. Binary Lexicographic Sequence 8 May 2008 18:49 cookie Re: now, i've AC too!! // Problem 1081. Binary Lexicographic Sequence 11 Sep 2009 07:48 wow i feel good ¬¬_.'[smoke] ty for the idea † SiriuS † [TWYT Union] Re: TLE#5, how can i solv this with fibonachchi, // Problem 1081. Binary Lexicographic Sequence 18 May 2014 16:12 Tnk u. Ur hint is very helpful. I got AC! Mewtwo Re: TLE#5, how can i solv this with fibonachchi, // Problem 1081. Binary Lexicographic Sequence 25 Jul 2016 13:18 PersonalJesus wrote 17 April 2008 17:16 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 Sherxon WIUT What is Test 6? [1] // Problem 1081. Binary Lexicographic Sequence 11 Feb 2015 11:33 Please give me test 6? Mewtwo Re: What is Test 6? // Problem 1081. Binary Lexicographic Sequence 25 Jul 2016 13:09 Sherxon WIUT wrote 11 February 2015 11:33 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 aslan7470 WA 8 // Problem 1081. Binary Lexicographic Sequence 16 Mar 2015 15:21 Please, send me test 8 Haile What's up with test #6 ? // Problem 1081. Binary Lexicographic Sequence 18 Nov 2013 14:46 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 Freezing Sun Accepted [3] // Problem 1081. Binary Lexicographic Sequence 22 Aug 2009 07:57 AC at 0.015 145 KB :) Al-Xorazmiy Re: Accepted // Problem 1081. Binary Lexicographic Sequence 8 Oct 2010 16:05 arif1122 Re: Accepted [1] // Problem 1081. Binary Lexicographic Sequence 3 Apr 2012 13:13 AC @ .015 and 112KB :) PrankMaN Re: Accepted // Problem 1081. Binary Lexicographic Sequence 24 Mar 2013 15:05 The same, AC 0.015 and 112 KB rrpai Crash why ? [6] // Problem 1081. Binary Lexicographic Sequence 29 Dec 2006 11:18 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. Peter Huggy Re: Crash why ? // Problem 1081. Binary Lexicographic Sequence 20 Mar 2007 13:13 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! WangKaixiang Re: Crash why ? // Problem 1081. Binary Lexicographic Sequence 8 Aug 2008 09:37 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?~:) WangKaixiang Re: Crash why ? // Problem 1081. Binary Lexicographic Sequence 8 Aug 2008 09:40 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?~:) WangKaixiang Re: Crash why ? // Problem 1081. Binary Lexicographic Sequence 8 Aug 2008 09:40 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?~:) WangKaixiang Re: Crash why ? // Problem 1081. Binary Lexicographic Sequence 8 Aug 2008 09:51 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~~~ barry Re: Crash why ? // Problem 1081. Binary Lexicographic Sequence 22 Jul 2012 08:12 maybe....-1 imereli WA7 // Problem 1081. Binary Lexicographic Sequence 6 Jul 2012 00:23 do you have any idea about this test? vongang Help ! What's the meaning of this problem ??? [1] // Problem 1081. Binary Lexicographic Sequence 9 Oct 2011 08:43 Silent_coder Re: Help ! What's the meaning of this problem ??? // Problem 1081. Binary Lexicographic Sequence 27 Jan 2012 23:56 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 > :) Sandro (USU) Problem 1081 "Binary Lexicographic Sequence". New tests were added. (+) [2] // Problem 1081. Binary Lexicographic Sequence 14 Mar 2007 14:22 74 authors lost AC after rejudge. mariami [Freeuni] Re: Problem 1081 "Binary Lexicographic Sequence". New tests were added. (+) [1] // Problem 1081. Binary Lexicographic Sequence 15 Sep 2011 03:00 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 Sandro (USU) Re: Problem 1081 "Binary Lexicographic Sequence". New tests were added. (+) // Problem 1081. Binary Lexicographic Sequence 15 Sep 2011 13:43 I've added these tests, but you seem to be the only author who doesn't pass them. :) ENick(TNU) test#1 [2] // Problem 1081. Binary Lexicographic Sequence 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 Steven Re: test#1 [1] // Problem 1081. Binary Lexicographic Sequence 19 Apr 2010 06:51 I think you forget this:"Write −1 if the number K is larger than the number of valid sequences" remdy21 Re: test#1 // Problem 1081. Binary Lexicographic Sequence 26 Jul 2010 17:01 thanks a lot bobchennan Give advices to the person who has WA#1 [1] // Problem 1081. Binary Lexicographic Sequence 7 May 2009 17:57 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 FaLLeN Re: Give advices to the person who has WA#1 // Problem 1081. Binary Lexicographic Sequence 24 Jun 2009 23:30 Ops, he already found decision=) Edited by author 24.06.2009 23:32 hhh help me // Problem 1081. Binary Lexicographic Sequence 12 Mar 2009 16:10 #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 Alias (Alexander Prudaev) what's wrong? [1] // Problem 1081. Binary Lexicographic Sequence 15 Mar 2007 18:34 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 Yashar Abbasov Re: what's wrong? // Problem 1081. Binary Lexicographic Sequence 17 Jan 2008 09:59 you forgot about -1. When k is bigger than all possible sequences then the answer is -1 Juri Krainjukov I don't understand what's wrong . [4] // Problem 1081. Binary Lexicographic Sequence 1 Dec 2002 03:16 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 Juri Krainjukov I found my mistake!!! [3] // Problem 1081. Binary Lexicographic Sequence 1 Dec 2002 03:40 Georgiy Savchenko Re: I found my mistake!!! [2] // Problem 1081. Binary Lexicographic Sequence 5 Feb 2007 03:03 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 Georgiy Savchenko Re: I found my mistake!!! [1] // Problem 1081. Binary Lexicographic Sequence 6 Feb 2007 04:27 Finally found out the problem. When you solve this problem take a look to overflows! Peter Huggy Re: I found my mistake!!! // Problem 1081. Binary Lexicographic Sequence 13 Mar 2007 12:53 Georgiy Savchenko wrote 6 February 2007 04:27 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).
|