With help of my friend that was just looking at maximums index sequense and found an idea, finally, I got AC. Some hints: 1) Find an idea to calculate next maximum indices from previous ones: all the maximum's indices can be obtained from previous ones in such ways: i = s*2 + 1; or i = s*2 - 1; or i = s*4 + 1; or i = s*4 - 1; for example f(21)=8 is maximum for 21<=n<=34 so 21 = 2*11-1, where 11 is one of previous maximums indices. And so on using all the formulas above. but 2*11+1 = 23 is not a maximum index. so we have to cancel this number (23). 2) Learn to calculate f(n) in O(logn) 3) Generate all maximums indices (about 1500). You can store them in heap to get an access to the smallest maximum index. 4) than read n and just search for it in maximums index array. P.S. who can prove the first and the main idea? If you can, please post here you proof. How did you invent it? Edited by author 05.07.2009 22:51 It seems that only test s*2 - 1 and s*4 - 1 is OK. I've tested by bruteforce program in range [0, 20000000]. I will try it. Edited by author 15.10.2016 08:24 This is exactly how my accepted program runs. Suppose i is a maximum index, i = 2*i1+1, i2 = i1+1, then either 1) i1 is even, at least one of i1/2, i2 is a maximum index; or 2) i2 is even, at least one of i2/2, i1 is a maximum index. But I don't know how to prove it. Thus candidate indices from 2^n to 2^{n+1} can be generated from calculated maximum indices from 2^{n-2} to 2^n. Suppose we want to calculate max({A * a[i] + B * a[i + 1], A * a[i + 1] + B * a[i]}) for i = 0..n-1 (in this problem A = 0, B = 1). Then answer(A, B, n) = max(answer(max(A, B), A + B, n/2), A * a[n - 1] + B * a[n], B * a[n - 1] + A * a[n]), so it can be solved recursively. That's very clever! How did you come up with this idea? It's been 2.5 years, so I don't remember clearly, but as far as I remember, I tried expanding formulas to find a simple formula for max. I didn't find such a formula, but I noted that the problem can be parametrized and expanded formulas fit that parametrization well. I think that most people trying to solve this problem will try to deal with two problems, they are: 1. How to calculate a[n] fast? 2. How to find those n that a[n] is the maximum in [1...n]? Here is my method. 1. Calculating a[n] (without calculating a[1...n-1]). Directly calculation will lead to a long time. But, after some observation, I found that: a[4n] = a[n] a[4n + 1] = a[2n] + a[2n + 1] = 2a[n] + a[n + 1] a[4n + 2] = a[n] + a[n + 1] a[4n + 3] = a[n] + 2a[n + 1] So, a[4n] to a[4n + 3] could be presented as the linear form of a[n] and a[n + 1]. We will soon realise that, a[2^k n] to a[2^k n + (2^k - 1)] could also be presented as linear form of a[n] and a[n + 1]. So, pre-calculation is done to calculate all the linear forms of a[65536n] to a[65536n + 65535]. This will take about O(65536 * 2) time. After this pre-calc, calculation for any number K will go very fast. 2. Finding the maximum. After listing some of the 'maximum index', we found that: 1 3 5 9 11 19 21 35 37 43 ...... Maybe my math is not so good, so I could not find so useful properties in the array, but I noticed one thing: ------------------------------------------------------------------------------------------ Every 'maximunm index' could be presented as its max 2-power and some former 'maximum index'. ------------------------------------------------------------------------------------------ Sorry for my poor English, let's take a look at the examples: 1 3 = 2 + 1 5 = 4 + 1 9 = 8 + 1 11 = 8 + 3 19 = 16 + 3 21 = 16 + 5 35 = 32 + 3 37 = 32 + 5 43 = 32 + 11 ...... So, we just need to use every 2^k number to ITERATE the list of 'maximum index'. As the list is of size O(Log N), the algo runs quite fast. With above methods, I got AC in 0.046 sec. Well, if my algo is too stupid for you, don't hesitate to post your algo here. Have fun and good luck. I've solved 1079,but this problem...Is any trick there? Edited by author 01.09.2007 22:19 I think, the only trick here - to have creative brains :) I thihk that unhelpful to wait when creativeness come to us. That it should try to solve as can. For exampple, let n to be strong number if a[n]>max(0<=i<=n-1) a[i]. It is evidence that having strong numbers precalculated and if their number rather small then the problem will be solved easily. This is list of strong numbers in 1000: 3 1 1 5 1 0 1 9 1 0 0 1 11 1 0 1 1 19 1 0 0 1 1 21 1 0 1 0 1 35 1 0 0 0 1 1 37 1 0 0 1 0 1 43 1 0 1 0 1 1 69 1 0 0 0 1 0 1 73 1 0 0 1 0 0 1 75 1 0 0 1 0 1 1 83 1 0 1 0 0 1 1 85 1 0 1 0 1 0 1 139 1 0 0 0 1 0 1 1 147 1 0 0 1 0 0 1 1 149 1 0 0 1 0 1 0 1 165 1 0 1 0 0 1 0 1 171 1 0 1 0 1 0 1 1 277 1 0 0 0 1 0 1 0 1 293 1 0 0 1 0 0 1 0 1 299 1 0 0 1 0 1 0 1 1 331 1 0 1 0 0 1 0 1 1 339 1 0 1 0 1 0 0 1 1 341 1 0 1 0 1 0 1 0 1 555 1 0 0 0 1 0 1 0 1 1 587 1 0 0 1 0 0 1 0 1 1 595 1 0 0 1 0 1 0 0 1 1 597 1 0 0 1 0 1 0 1 0 1 661 1 0 1 0 0 1 0 1 0 1 683 1 0 1 0 1 0 1 0 1 1 If you can find algo for their generation you will winner. Now I can't. But it,s evident for me that for their binary expansions fulfil next lows: 1) numbers of 0 and 1 are equal or with difference 1; 2) 1 and 0 alternates exept for last two 1. I can generate such number sets combinatorically ang strong numbers will be among them. By the way, number of strong numbers really very small/ For example, until 200000 thei number is 114. Edited by author 20.09.2007 12:08 I also noticed this feature (and even some more strong), but it didn't help me to solve the problem... Thank you for your help!I'll think about it.Now with your help I've idea.Ostalnoe,po-moemu,delo tehniki. Edited by author 20.09.2007 18:42 It's quite easy to see the pattern. It's a bit different for odd and even number of digits (excluding leading zeroes), but there IS a pattern, and it's quite simple to program. If you still can't find the pattern inside base-2 representation (I could do that), write it base-4 - it's more evident there and easier to code. Even if you cannot find strict pattern, you may find some weaker pattern which includes all of strong indices and probably some more. Of course, this will lead to O(log^2(N)) solution because you will have to test each of such indexes as you don't know which of them is actually a strong one, but still it should be AC. My algo generates strong indices ONLY, and it does so only for N/2..N interval. The biggest goes to the answer. N<65536 are brute-forced special cases (too few digits). Yes I found the pattern in binary and got AC (0.078, 140KB) (no precompute), for strong indices only, and only generate them starting with 2^(floor(log2(n))). The pattern holds lower than 65536 so you can set the brute force threshold lower for faster execution time. (I have a special case for finding the maximum if it occurs below my starting point). This has been a fascinating problem to solve, thank you to the authors. Edited by author 20.09.2012 23:38 One way to solve this problem has something to do with binary representation and fibonacci sequence.. or tree traversal on odd numbers. I received incomparable pleasure of solving this problem. Vladimir, Thanx. :) I submitted my program to 1079 and get AC. It at least shows that my ALGO work for small data. By the way, my answer for 10^18 is 2504730781961 Is it right? Maybe the 'int64' or some problems like this make me WA. Could you please tell me why? I am confused. Thanks in advance. Well, sorry to ADMIN. I have found my mistake and now I have AC. BTW, my answer for 10^18 is correct. I HAVE ACCEPTED WITHOUT PRECALCULATE!!!!!!!!!! MY PROG SOLVE THIS PROBLEM FOR 0.046 ms AND USE 650 kb. I think, that limitation must be bigest: For Example 10^180. Yes, there are some solutions that may fit TL without precalc. Ilay Grebnov's first (Pascal) solutions, for example. There is absolutely no need to increase N. Edited by moderator 13.07.2006 13:09 The goal of limitation 10^18 is to prevent bruteforce solution, but to give a freedom of any other ways of solving. Besides with 10^18 you do not need to use long arithmetics. You can create new problem "Maximum. Version 3"!!! I can give you my solution idea or my prog. If you want, give me your e-mail. Thanks My e-mail is cpp_student@163.com Can you tell me your Idea? yydjtc1990@gmail.com THX.. Can you give me your idea and solution? thank you very much! my email: 547841181@qq.com or jaryn_lin@foxmail.com Last line before Sample: corResponding I've passed with O(TLogN) but I can't solve with O(T). Please help me with the algorithm O(T). My email is : phongpdnkptnk_4ever@yahoo.com I've solved this problem, but in quite a sophisticated way. How did you solve it? May write here or at nick@inbox.ru, using goryinyich as the nick. What is test#1 or test #2?I've solved 1079,but my program gives Crash on #1 test in 1396. Please answer/Thank!!! Edited by author 28.07.2007 22:21 It is only ont test in this problem Please I need any tips why I am having WA#1. My solution was accepted at 1079 and it is O(logN) solution. May be some subtle issues with the compiler and __int64 stuff? I cannot debug on my computer because it does not have __int64. Try to use unsigned long long... Nice task... I really like it... Not very difficult, but not simple too <Editted> Edited by author 21.03.2007 15:34 I have AC Edited by author 01.10.2006 05:51 This problem is the same as 1079 “Maximum” but with bigger limitations. Edited by author 10.05.2006 19:37 The problem is just added, so it may be easily modified. Let it be more than 10000 lines in input - so that the TL would be strict enough and my solution get TLE ;) Edited by author 11.05.2006 12:21 Burunduk1, please, resubmit your solution for N < 10^18. I will use your solution to generate new tests ;-) Edited by author 11.05.2006 15:31 This code will get WA with N < 10^18. Guess why? And for N < 10^17 ? Try to change "__int64" to "unsigned __int64". Please, give me my AC solution!!! (to sk1@hotbox.ru) I modified it (of course without backup) and now it doesn't pass second test. (or you've already added new tests?) PS: This ability (to view submitted solutions) is useful. And now there is only one test I see... (know the same solution gets WA 1) The bug was in this: I calculated F[i] int 32-bit integer. Do you use any precalculations? My solution consists of only precalc. I calculate all different maximums on [1..x] where x is any integer between 1 and 10^18. I see... And why you haven't got AC? I have found O(logN) solution in one book. Very nice idea. As far as I know solution of this problem in O(logN) can be found in Shens book... Edited by author 22.09.2006 00:57 Edited by author 22.09.2006 00:57 Edited by author 22.09.2006 02:01 |
|