Show all threads Hide all threads Show all messages Hide all messages | Simulation Time Complexity | taodaling | 1777. Anindilyakwa | 3 Aug 2023 13:18 | 1 | Let's assume delta is the difference between the nearest number in our set. Then we can approve delta will decrease by half (at least) in every 2 rounds. So the simulation will be executed at most 2log 10^18 time, it's about 120. | Small Hints | irinaguseva | 1777. Anindilyakwa | 25 Jul 2021 21:52 | 1 | 1) Try writing an algorithm for finding the minimum difference in a list first (list.sort() method may come in handy) 2) Think of how the usage of sets and lists may assist you in determining whether we have doublets in your list 3) Use counters for finding the number of iterations in your cycle Enjoy :) Edited by author 25.07.2021 21:52 Edited by author 25.07.2021 21:52 | Explanation of the worst case and the idea for solution. | grinrag | 1777. Anindilyakwa | 1 Oct 2019 13:54 | 1 | We have got 3 distinct number, A < B < C. Let's imagine that the minimum difference Z = (C - B) goes between numbers A and B, closer to B, so new sequence will be A < Z < B < C. And the next minimum difference Y = (B - Z), goes between A and Z, closer to Z, A < Y < Z < B < C and so on. You see Y + Z = B, Z + B = C, the next number in the sequence (in order from left to right) is equal to the sum of current and previous members (looks like Fibonacci numbers). Now try to find the sequence with described property. Look at the example: 1 4 6 10 16 26 ... We can continue this sequence until the last two members will be 519390993822245170 and 840392281454979346. Their sum is more than 10^18. It takes only 83 iterations to build this sequence. The test case would be: 1 519390993822245170 840392281454979346 So, in the worst case, the number of iteration N < 100. The naive algorithm, when we just put the minimum diff to the array and sort it again will work. The time complexity will be O(N^2 log N). Edited by author 01.10.2019 14:24 | WA#18 | Tural Vugar Gulmammadov | 1777. Anindilyakwa | 13 Dec 2018 21:41 | 8 | WA#18 Tural Vugar Gulmammadov 9 Oct 2010 16:21 Can someone give me test #18??? Or give me some tests and answers??? Re: WA#18 Tural Vugar Gulmammadov 9 Oct 2010 17:03 For: 75000000000000000 50000000000000000 25000000000000000 answer is 2 (1 ≤ x1, x2, x3 ≤ 10^18) Try to use int64 Re: WA#18 Tural Vugar Gulmammadov 9 Oct 2010 20:22 Thanks, but i have already use int64/ but i dont know where's my error... :( I have submitted it more than one times with int64, but again and again I got WA on test19, however, same source code in Java using BigInteger was accepted at once. 45 1 12 You can have problems with sorting your array it was helped me. Good luck, bro! Edited by author 13.12.2018 21:43 Edited by author 13.12.2018 21:43 | WA #19 | FrostCode | 1777. Anindilyakwa | 13 Dec 2018 21:41 | 2 | WA #19 FrostCode 29 Aug 2013 16:46 I didn't find a mistake in my program. And what is the test #19? I'am confused( 45 1 12 it was helped me. Good luck, bro! | Are the tests strong enough? | dntnhan | 1777. Anindilyakwa | 27 Aug 2018 01:56 | 2 | I use unsigned long long and STL vector with very simple algorithm: store x1, x2, x3 in the vector, then find the minimal diffenrence and push it in the vector (repeat the process until minimal difference is 0). I got AC. I suppose that the tests are not strong enough. I wonder whether there is any test whose output is very large since I don's believe vector can store too many elements. P/S: I'm a beginner so I'm very glad to study from all of you :-)! The simulation works in O(logN), so your solution is correct | Hint | Amil Khare | 1777. Anindilyakwa | 17 Sep 2017 19:27 | 1 | Hint Amil Khare 17 Sep 2017 19:27 Hello, So initially I thought there might some cases like there are in questions regarding divisors, range, odd, even etc. However, there wasn't any such case. I tried simulating the above problem for a = 1-20, b =1-20, c= 1-20. The maximum possible answer was 3 and minimum was 3 so I was sure simulation was enough. I tried my best to derive some relation but was unable to do so. So in this way, you could think about solving the problem and just simulate the whole process to solve it. | Solved it by simulation. | Mahilewets | 1777. Anindilyakwa | 21 Jun 2017 18:16 | 1 | After we add new pile Z of stones if there is new pair of piles X and Y such that |X-Y| is minimal that either X=Z or Y=Z. So, just add nee pile and recalculate new pair of piles such that the difference between stones count is minimal in O(n) where n is tje number of piles present now. | WA#17 and WA#18 Test Examples and Tips | KOTnt | 1777. Anindilyakwa | 28 Feb 2015 01:46 | 2 | Try these tests on big input data: 1000000000000000000 999999999999999990 999999999999999999 3 1000000000000000000 10 500000000000000000 3 1000000000000000000 500000000000000000 250000000000000000 2 Tips: 1. Remember, that you should not only forget about using big types (for c++ it's long long int or __int64) but not forget to take big input data correctly. For example, if you will use scanf("%d", &i), it will not get correctly a big input digit. 2. If you use min function in you program to find the minimum of two digits, don't forget to initialize your min value variable with the maximum value your can input. For example, __int64 minInit = LLONG_MAX. If you have such problems, you will have incorrect answers on the second and third tests (you'll get 4 and 3 respectively) and you will have WA on the tests 17 (the first tip) and 18 (the second tip). Hi KOTnt, you helped a lot thank you ...!!! | WA #17 why? | Иван | 1777. Anindilyakwa | 17 Jun 2014 19:06 | 1 | #include <stdio.h> #include <stdlib.h> #include <unistd.h> #define True 1 #define False 0 #define N 15 #define MAX_DIFF 1000000000000000001 void print_a(unsigned long long a[N]) { int i; printf("\n----------------\n"); for (i = 0; a[i] != 0; i++) { printf("%llu\n", a[i]); } printf("\n--------------\n"); } void sort(unsigned long long a[N]) { int i, j, s_fl; unsigned long long tmp; for (i = 0, s_fl = True; s_fl == True; i++) { for (j = 0, s_fl = False; j < N-i-1; j++) { if (a[j] < a[j + 1]) { s_fl = True; tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } } } } int main(int argc, char *argv[]) { int i, j, c; unsigned long long prev, diff; unsigned long long max[N] = {0}; for (i = 0; i < 3; i++) scanf("%llu", &max[i]); sort(max);
for (j = 2, c = 0; max[j] != 0; j++, c++) { for (i = 0, diff = MAX_DIFF; max[i + 1] != 0; i++) { prev = max[i] - max[i + 1]; if (prev < diff) diff = prev; } max[j + 1] = diff; sort(max); // print_a(max); } printf("%d\n", c); return 0; } | give same tests please | Nikolay | 1777. Anindilyakwa | 21 Dec 2013 22:52 | 9 | 1 1 2 1 1 2 3 2 234 532 245 3 12345 87654 23456 4 1223456 8098887645 567321 4 12345 654345678 1234567890 5 Edited by author 05.07.2011 20:09 Hey Maria, Problem states that the input, consists of 3 space-separated pairwise DISTINCT integers so your first example doesn't satisfy conditions and hence, is useless. Regards, Sepehr thanks :) got AC after testing you input and fixing the program P.S. long in JAVA is enough!!!! Maria , for test number 4, I think the answer should be 3 : First aborigine brings a pile of 75309 ( 87654-12345 ) , the second aborigine also brings a pile of 75309 stones , because that's still the biggest difference , and the third points to the two equal piles. Correct me if I'm wrong! hopless dreamer, No, u r wrong. The FIRST aborigine will bring the pile of 64198 stones, becouse it's the LEAST. And the second aborigine will bring the pile of 64198 - 23456 = 40742 stones and so on. "Professor asked one of the aborigines to point at two piles with the MINIMAL difference of numbers of stones in them and tell what this difference is." Edited by author 06.07.2012 18:07 Edited by author 06.07.2012 18:07 | use unsigned long long for C++ | Valentin Pimenov | 1777. Anindilyakwa | 4 Aug 2013 20:53 | 2 | I didnt use ull & got AC. | WA#17 | RocBoy-D | 1777. Anindilyakwa | 6 Mar 2013 23:21 | 11 | WA#17 RocBoy-D 7 Aug 2012 19:15 #include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { unsigned long long *pa = (unsigned long long *)a, *pb = (unsigned long long *)b; return *(unsigned long long *)pa - *(unsigned long long *)pb; } int main() { unsigned long long arr[15000], min=1000000000000000000; int N=3, count=0, i; for(i = 0; i<N; i++) scanf("%llu", &arr[i]); while(min) { qsort (arr, N, sizeof(unsigned long long), cmp); for (i = 0; i<N-1; i++) if(arr[i+1] - arr[i]<min) min=arr[i+1] - arr[i]; arr[N++] = min; count++; } printf("%d", count); return 0; } Can anybody help me? Re: WA#17 Andrew Sboev [USU] 7 Aug 2012 21:07 Use __int64 instead of unsigned long long I changed. But I stil have WA#17 and time limit exceed. #include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } int main() { __int64 arr[100], min=1000000000000000000; int N=3, count=0, i; for(i = 0; i<N; i++) scanf("%I64d", &arr[i]); while(min) { qsort (arr, N, sizeof(__int64), cmp); for (i = 0; i<N-1; i++) if(arr[i+1] - arr[i]<min) min=arr[i+1] - arr[i]; arr[N++] = min; count++; } printf("%d", count); return 0; } Now I have WA#17 and crash(acces violation). Re: WA#17 Andrew Sboev [USU] 7 Aug 2012 22:29 Of course, you have crash :D Replace all number types to __int64, uncluding int. I changed: #include <stdio.h> #include <stdlib.h> int cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } int main() { __int64 arr[100], min=1000000000000000000, N=3, count=0, i; for(i = 0; i<N; i++) scanf("%I64d", &arr[i]); while(min) { qsort (arr, N, sizeof(__int64), cmp); for (i = 0; i<N-1; i++) if(arr[i+1] - arr[i]<min) min=arr[i+1] - arr[i]; arr[N++] = min; count++; } printf("%I64d", count); return 0; } But the same problem remain: WA#17 crasn(access violation) Re: WA#17 Andrew Sboev [USU] 8 Aug 2012 11:02 You didn't changed int cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } change to __int64 cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } #include <stdio.h> #include <stdlib.h> __int64 cmp(const void *a, const void *b) { __int64 *pa = (__int64 *)a, *pb = (__int64 *)b; return *(__int64 *)pa - *(__int64 *)pb; } int main() { __int64 arr[100], min=1000000000000000000, N=3, count=0, i; for(i = 0; i<N; i++) scanf("%I64d", &arr[i]); while(min) { qsort (arr, N, sizeof(__int64), cmp); for (i = 0; i<N-1; i++) if(arr[i+1] - arr[i]<min) min=arr[i+1] - arr[i]; arr[N++] = min; count++; } printf("%I64d", count); return 0; } No, it doesn't help. Re: WA#17 Andrew Sboev [USU] 8 Aug 2012 17:27 Oh,you have too small array size. Use STL vector do it greater. I don't know C++. I tried to change size of array, but I have time limit exceed. Edited by author 08.08.2012 18:32 # include <iostream> # include <vector> # include <algorithm> using namespace std; long long q; int main() { vector <long long> v(3),v1;
for(int i=0; i<3; i++) cin>>v[i];
while(1) { v1.clear();
q++;
for(int i=0; i<(int)v.size(); i++) { for(int h=0; h<(int)v.size(); h++) { if(i!=h) { int a=v[i]-v[h];
if(a>=0) v1.push_back(a); } } }
sort(v1.begin(),v1.end());
if(v1[0]==0) {break;}
v.push_back(v1[0]); } cout<<q; } | WA2 | Majo | 1777. Anindilyakwa | 29 Jan 2013 16:02 | 3 | WA2 Majo 20 Jan 2013 13:09 My program is right for this test. | test 33 | Arsen Babakhanyan (AUA) | 1777. Anindilyakwa | 16 Dec 2012 01:12 | 1 | test 33 Arsen Babakhanyan (AUA) 16 Dec 2012 01:12 What is in test 33 ? The same code with Scanner is accepted but with StreamTokenizer and BufferedReader is giving WA33. Very unexpected result!! O_O Edited by author 16.12.2012 10:56 | FOR ADMINs | AzizIO | 1777. Anindilyakwa | 21 Oct 2012 03:14 | 3 | Edited by author 21.10.2012 03:11 Edited by author 21.10.2012 03:11 I corrected my mistake!!! sorry for all ;) got AC! I had Crash 1!!! and solve in Java and found my mistake!!! | WA #17. Why? | Alla | 1777. Anindilyakwa | 28 Sep 2012 17:01 | 2 | Here is my code: #include <iostream> using namespace std; int x[200]; int compare (const void *a, const void *b) { return (*(int*)a - *(int*)b); } int main() { int r[200], a = 3; long min; bool z = false; for (int i = 0; i<3; i++) cin>>x[i]; for ( ; ; ) { qsort (x, a, sizeof(int), compare); min = 1000000000; for (int i = 0; i<a-1; i++) { r[i] = abs(x[i] - x[i+1]); if (r[i]<min) min = r[i]; } x[a] = min; for (int j = 0; j<a; j++) { if (x[j] == min) { z = true; break; } } if (z == true) break; a++; } printf("%d", a - 1); return 0; } Where is my mistake? Use long long instead of int | Use bigger types | vpro | 1777. Anindilyakwa | 29 Jun 2012 23:37 | 1 | For example, I got WA19 at first time. I changed real to extended and integer to longint and got AC. | WA33 | LostInSpace | 1777. Anindilyakwa | 30 Apr 2012 23:46 | 2 | WA33 LostInSpace 9 Apr 2012 13:14 пробовал разные способы вычисления, упираюсь в 33 тест. Какие есть мысли? try more ways reading longs | WA 19?? | KibiBit[KhAI] >> Dima | 1777. Anindilyakwa | 4 Feb 2012 16:55 | 1 | WA 19?? KibiBit[KhAI] >> Dima 4 Feb 2012 16:55 |
|
|