| ENG RUS | Timus Online Judge |
Discussion of Problem 1863. Peaceful AtomIgorKoval(from Pskov) What is algo??? [6] // Problem 1863. Peaceful Atom 1 Nov 2011 00:06 Head-on solution have complexity O(2^40)=O(10^12). It's very slow. How do it faster? svr Re: What is algo??? [5] // Problem 1863. Peaceful Atom 1 Nov 2011 07:46 I used 40=30+20 First 20- memorization second 20 as 2^20=10000000- that normaly IgorKoval(from Pskov) Re: What is algo??? [4] // Problem 1863. Peaceful Atom 2 Nov 2011 02:34 Could you explain your solution more in detail? "First 20- memorization" What it mean in Russian? I understood that what we do with second 20. But can not understood that what we do with first 20. =) svr Re: What is algo??? [3] // Problem 1863. Peaceful Atom 2 Nov 2011 07:01 I meant that first 20 also as 2^20 or with brute force aproach, but result of first 20 we place in arr[1..1000000](memorization) sort arr than in second 20 use log-bin search in arr. IgorKoval(from Pskov) Re: What is algo??? [2] // Problem 1863. Peaceful Atom 3 Nov 2011 02:31 Thank you very much. You is good man! I got AC. =) Harkonnen Re: What is algo??? [1] // Problem 1863. Peaceful Atom 16 Aug 2022 08:33 It's a bit more complicated than that because you should care about rod not getting off the rails during the process as well, so you can't just pick arbitrary memorized sequence which gives suitable end-result, it also must stay within limits while it performs memorized shiftings. Looks like segment tree algo, not just plain binary search (or tests are very weak). P.S: Got AC with 0.5 sec and 44Mb, probably could've done better. For every 2^20 endings I track range of start values where it is suitable (i.e. fits for its entire internal history), then for every 2^20 beginnings (sorted) I track min/max of currently active segments via two heaps. Edited by author 16.08.2022 11:51 Harkonnen Re: What is algo??? // Problem 1863. Peaceful Atom 16 Aug 2022 12:17 P.P.S: Ah, I'm dumb! Memorizing first 20 leads to much easier algo when last 20 are brute-forced (not vice versa). 0.265 sec, 7 Mb. Yet, coding that monster from previous "P.S" was fun :) yyll very short, but MLE/TLE python solution // Problem 1863. Peaceful Atom 28 May 2022 09:37 n, s, k = map(int, input().split()) a = 1 << s for u in map(int, input().split()): a = a >> u | (a & (1 << n+1-u) - 1) << u print((a & -a).bit_length() - 1, a.bit_length() - 1) Kostyareh Why is WA14? // Problem 1863. Peaceful Atom 25 Sep 2021 21:46 Edited by author 29.09.2021 19:50 sherbina_evgeniy Test 1 [1] // Problem 1863. Peaceful Atom 27 Sep 2014 12:33 I got WA1 and I don't understand why. Give me some tests please. Tolstobrov Anatoliy[Ivanovo SPU] Re: Test 1 // Problem 1863. Peaceful Atom 6 Jan 2016 21:02 Test #1 describe into problem statement. 10 3 3 4 5 1 What it means, we have range [0, 10] and start position in 3. And have 3 shifts. First shift we can go from 3 to [-1, 7] as -1 not in range we have only [7] positions. Second shift we can go to positions [2, 12] as 12 not in range we have only [2] position. Third shift we can go to positions [1, 3] as all of them in range we have 2 possible final states 1 and 3, minimal of them 1 and maximal 3. Answer will be 1 3. Another test: 100 50 4 1 2 4 8 Possible positions on steps: 0) [50] 1) [49, 51] 2) [47, 49, 51, 53] 3) [43, 45, 47, 49, 51, 53, 55, 57] 4) [35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65] Answer will be 35 65 Wasdek WA3 and incorrect statement [1] // Problem 1863. Peaceful Atom 22 Jan 2014 20:38 My program get WA3, but work right on my tests. I can't find a mistake. Please, give me some tests. Also, why 0<=s<=n and n>0 ? Is it incorrect statement? ER Re: WA3 and incorrect statement // Problem 1863. Peaceful Atom 19 Jun 2014 12:38 For WA3, check how you initialize the global min and max depth. n > 0 is fine. n cannot be zero, but s can be. java707 Why WA#12? // Problem 1863. Peaceful Atom 1 Nov 2011 15:27 My program works in my cases. But i have WA#12. Why?
|