Show all threads Hide all threads Show all messages Hide all messages | optimization | Grandmaster | 1452. Pascal vs. C++ | 23 Dec 2020 04:00 | 2 | How can i improve my O(n ^ 2 * logN) time and O(n * n) memory too pass all tests? int n, y[2004], index = 1, maximum = 1, rati; pair<int, int> x[2004]; map<int, int> s[2004]; int main() { cin >> n; for(int i = 0; i < n; i++){ cin >> x[i].first; x[i].second = i; y[i] = 1; } sort(x, x + n); for(int i = 1; i < n; i++) { for(int j = 0; j < i; j++){ if(y[i] < s[j][x[i].first - x[j].first] + 2 && x[i].first - x[j].first != 0){ y[i] = s[j][x[i].first - x[j].first] + 2; if(maximum < y[i]){ index = i; maximum = y[i]; rati = x[i].first - x[j].first; } } s[i][x[i].first - x[j].first] = s[j][x[i].first - x[j].first] + 1; } } cout << maximum << "\n"; int val = x[index].first, i; cout << x[index].second + 1 << " "; for(i = index - 1; i >= 0; i--) { if(val - x[i].first == rati && rati != 0) { val = x[i].first; cout << x[i].second + 1 << " "; } } return 0; } You can use a hashmap instead of a red-black tree to get AC. Just remember to use the __gnu_pbds::cc_hash_table (header <ext/pb_ds/assoc_container.hpp>) as it's about 3 times faster than the std::unordered_map. | Is there actually an O(N^5) solution? | PrankMaN | 1452. Pascal vs. C++ | 1 Jun 2020 14:26 | 1 | I've tried to come up with solution from the story part of the problem, but the worst algorithm I came up with is O(N^4). Is there an O(N^5) algorithm? | WA 1 | aslan7470 | 1452. Pascal vs. C++ | 12 Jan 2020 15:48 | 2 | WA 1 aslan7470 14 Mar 2015 01:44 On #1 test my program output: 4 4 5 1 6 with code: cout<<4<<endl<<4<<" "<<5<<" "<<1<<" "<<6 but get wrong answer. Why? Re: WA 1 Alikhan Zimanov 12 Jan 2020 15:48 Because the first test is NOT the same as the sample | Probably weak tests | Sirko | 1452. Pascal vs. C++ | 25 Feb 2017 08:03 | 1 | My AC solution runs about 10 seconds for test case 1, 2, ...., 2000 on my laptop (it's an old one, though, maybe that's the reason). | A good solution found on the net | wangbicheng1 | 1452. Pascal vs. C++ | 8 Nov 2015 09:43 | 1 | | WA3 ??? | hailoc12 | 1452. Pascal vs. C++ | 13 Apr 2015 23:17 | 1 | Can somebody give me some hints on Test 3 ? I get WA but don't know why. I 've run all other test in the forum and it gives right answer | WA 6.... | Pushkar Mishra | 1452. Pascal vs. C++ | 22 Jan 2014 11:18 | 2 | WA 6.... Pushkar Mishra 21 Mar 2013 10:02 Can anybody suggest me the 6th test case? В натуре спотыкается.В чем соль? Где зарыта собака? Edited by author 22.01.2014 11:56 | Help! WA#5! | wyyyl | 1452. Pascal vs. C++ | 30 Nov 2013 21:00 | 3 | Who can give me some tests(include#5) or hints? Try this test 16 1 3 4 5 7 9 10 11 12 13 14 16 18 19 21 22 The answer is 8 1 3 5 7 10 12 14 16 Hope it helps! Edited by author 30.11.2013 21:02 | WA 1 but right answer!!! | Wasdek | 1452. Pascal vs. C++ | 16 Nov 2013 15:36 | 3 | On #1 test my program output: 4 6 1 5 4 but get wrong answer. Why? Your progression is decreasing (9 7 5 3), which contravenes the problem statement: "You should take a maximal number of different elements from this sequence which are successive terms of some increasing arithmetical progression." Thank you, i'll correct my mistake | ADMINS!!! WRONG TEST!!! | Alexander Prudaev | 1452. Pascal vs. C++ | 13 Nov 2013 20:04 | 18 | test #1 6 7 0 0 0 0 0 my program output "2\n1 2" but gets WA#1 yes, you are right my cheat program: var N; begin readln(N); readln(N); readln(N); if (N=0) then 10 div 0 else InfinityRecursion end. of course, read(N); i am in despair. it work! test it! at least once for sample input it write sample output. i don't use any random, but it gets WA1 //code deleted Edited by author 13.06.2006 23:27 ht[heap[hp].nexN&0x7FF]=hp++; //It's wrong! ht[heap[hp].nexN&0x7FF]=hp++; //It's wrong! why it's wrong? it's equivalent line: ht[heap[hp].nexN&0x7FF]=hp; hp++;
ht[heap[hp].nexN&0x7FF]=hp; hp++; //It's right! and after finding of all mistakes, you get the TLE#6... 6 1 2 3 4 5 6 3 1 1 2 3 1 2049 4097 Edited by author 11.06.2006 05:08 я извиняюсь, мне просто не сказать этого по английски :) я запостил не ту версию программы, в этой есть баги. да не в этом дело я написал программу которая даёт правильный ответ на sample#1 причём даже в той же последовательности выводит номера. моя программа даёт ответ: 4 4 5 1 6 но проверяющая система выносит вердикт: WA#1 я закомментировал вывод ответа и написал в конце printf("4\n4 5 1 6"); такая программа получает WA2 вопрос: как такое может быть, что одна программа получает WA2, а вторая WA1 я не однократно проверил что программы на этот sample выдают один и тот же ответ может быть причина в том, что я вывожу числа так: for (i=0;i<chetotam;i++) printf("%d ",int_ar[i]); мешает лишний пробел? это глупо, и маловероятно. перед выводом нет перевода строки. больше мне ничего в голову не приходит На всякий случай убери лишний пробел, моя АС прога не выводит его... Your solution is verified by a checker written by Ilya Grebnov, and no one still claimed it works wrong. I want you to send me both you WA(1) and WA(2) solutions for investigation. If some bug in the checker is found I will fix it. My e-mail for Russian-speaking programmers is dimanyes@mail.ru sent. I write a new program - WA12 :) I send. You forgot about? I have nothing to say. Everything is ok on my Borland C++ Builder compiler. You must contact with Vladimir Yakovlev to investigate this problem because he is C++ programmer. I have forwarded your mail to him. can you give me his e-mail? you know my, sent it. Your program works wrong on sample input. Test it with other compiler. For example, with Intel C++ Compiler 7.0 I have only Visual Studio 6 & 2005 in this IDE my program writes right answer I have same problem. On 1 test my program output: 4 6 1 5 4 but WA1. Why? | Solution | Carbon | 1452. Pascal vs. C++ | 12 Aug 2013 04:17 | 6 | Sorry for my impudence but my AC program has O(N^2*ln(N)) and takes 234 ms with GREAT optimization (and with memory too). Your solutions (by velocity characteristics) has O(N^2) difficulty and O(N) memory. First, we should watch all differences between elements (O(N^2)) and then find greatest sequence (O(ln(N))). In process of finding such sequence we should know all differences (O(N^2) memory). Am I mistaken in something? Could you tell me, in what destination I should think to get quick solution. I have thought up O(N^2) algo! Now time is 0.109 ms. But it eats O(N^2) memory:( Edited by author 28.07.2016 15:40 I only store N minimal differences, initially a1-a0,a2-a1,...,a(n-1)-a(n-2) (given a0..a(n-1) sorted sequence). Store it in heap (pyramide), get top (minimal) difference and change it from a(j)-a(i) to a(j+1)-a(i) and push down to the heap's bottom. My N*N*logN runs in 0.125 | Алгоритм. Быстродействие O(N^2), память O(N) | aslan7470 | 1452. Pascal vs. C++ | 30 Mar 2013 22:41 | 1 | Ьудем рассматривать все возможные разности (в виде i-начало, j-конец, i<j) в порядке возрастания. Но запоминать и сортировать их все нет нужды, чтобы получить их, воспользуемся идеей сортировки слиянием: N последовательностей a(2)-a(1)...a(N)-a(1), a(3)-a(2)...a(N)-a(2) итд, их можно "слить" за O(N^2). Опять-таки, сливать все сразу не надо, надо выделить подряд идущую группу равных элементов (их не более N) и сохранить в промежуточный массив, далее работать с ними, потом брать следующую группу и так пока все сливаемые последовательности не закончатся. Первую группу, где величина разности=0, ессн-но не обрабатываем Остается из группы k<=N разностей выделить макс.членов арифм.прогрессии, т.е. чтобы конец одной разности = началу другой. Используем массив размера N, где для каждого эл-та исходного массива храним счетчик = длине оканчивающегося в нем куска прогрессии. Первому эл-ту присваиваем счетчик=0. Одним проходом по группе разностей расставляем счетчики (учитывая что разности изначально сортированы по i-начало в ходе слияния), счетчик[разность.конец]=счетчик[разность.начало]+1, в том же проходе запоминаем наибольший счетчик и последний эл-т, из которых за O(N) легко восстановить всю последовательность. Итого на группу O(k) действий, а в сумме O(N^2) | How to read input data in Pascal? | Iosif inf-10 | 1452. Pascal vs. C++ | 6 Feb 2013 14:08 | 1 | My prog got TLE on test 8 I found that on test 8 about 0.2 sec my program spend on reading input data. Here the part of code ( this part takes about 0.2 sec on test 8 - I checked it many times) ... Readln(N); for i:=1 to N do begin A[i].p:=i; Read(C); A[i].V:=C; end; ... Could you please explain how it should be done? Edited by author 06.02.2013 14:09 Edited by author 07.02.2013 01:22 Edited by author 07.02.2013 01:22 | WA3 | Ig | 1452. Pascal vs. C++ | 30 Jul 2012 09:20 | 2 | I have WA#3ю Please give me test Re: WA3 HappyPerson 30 Jul 2012 09:20 | Crash <acces violant> on test 3! Pls help | Roman Furko | 1452. Pascal vs. C++ | 17 Jun 2011 01:41 | 1 | Why Crash (acces violant) I use vector < map <int,int> > ! Are the problem in it? P.S Sorry for my bad English #include <cstdio> #include <vector> #include <algorithm> #include <map> #include <iostream> #include <cstdlib> using namespace std; struct neww{ int x,n; }; int abss(int x) { if (x>=0) return x; else return (-x); } bool funcsort(neww a, neww b) { if (a.x < b.x) return true; else return false; } int main() { int n,i,j,x,maxn; neww a[2200]; scanf("%d",&n); vector < map <int,int> > b(12000); vector < map <int,int> > pi(12000); vector < map <int,int> > pj(12000);
for (i = 0; i < n; ++i) { scanf("%d",&a[i].x); a[i].n = i + 1; } sort(a,a+n,funcsort); if (n == 1) { printf("1\n"); printf("%d\n",1); exit(0); }
for (i = n - 1; i >= 0; --i) { for (j = n - 1; j > i; --j) if (a[j].x-a[i].x > 0) { b[i][a[j].x-a[i].x] = max(b[i][a[j].x-a[i].x],b[j][a[j].x-a[i].x] + 1); if (b[i][a[j].x - a[i].x] = b[j][a[j].x-a[i].x] + 1) { pi[i][a[j].x-a[i].x] = j; pj[i][a[j].x-a[i].x] = a[j].x - a[i].x; } } } maxn = 0; int numb,ost; for (i = 0; i < n; ++i) for (j = i; j < n; ++j) if (b[i][abss(a[i].x - a[j].x)] > maxn) { maxn = b[i][abss(a[i].x-a[j].x)]; numb = i; ost = abss(a[i].x - a[j].x); } printf("%d\n",maxn+1); printf("%d",a[numb].n); while (maxn) { int nm = pi[numb][ost]; int ot = pj[numb][ost];
printf(" %d",a[nm].n);
numb = nm; ost = ot; --maxn; } printf("\n");
} Edited by author 17.06.2011 01:42 | please. Help me!! | {AESC USU} Dembel | 1452. Pascal vs. C++ | 4 Jan 2011 21:48 | 4 | I have TLE#12 on C++ and TLE#10 on Pascal but my solution O(N^2*logN) Please help me.give me any test with TLE. Edited by author 11.03.2007 11:45 I have the same problem. TLE. can anybody explain my O(N^2) algo? gsaghinadze@yahoo.com near O(N^2) algo is with use of hashing to avoid binary search. I'd used standard .net Dictionary<int, int> class for this, and got AC. | note for WA#11 | hoan | 1452. Pascal vs. C++ | 4 Jan 2011 18:55 | 1 | try this test: 2 1 2 i know the anwer for test #11 is 2. GOOD LUCK!!! | WA #9 | Chalyshev Vladimir [cmd] | 1452. Pascal vs. C++ | 26 Aug 2010 08:30 | 2 | WA #9 Chalyshev Vladimir [cmd] 11 Apr 2007 19:40 Anybody, can tell me what the test 9? when I got WA 9, my solution doesn't work on test: 8 0 2 4 6 8 9 10 11 | WA 8:((( | THE_SCORPION | 1452. Pascal vs. C++ | 2 Feb 2010 00:09 | 2 | Why WA 8? Please help me ! I tested my programm many times, but did'not find a mistake. Maybe someone tell me where is wrong or give me same test. Sorry for my bad english. Here is my code: program Project2; {$APPTYPE CONSOLE} uses windows; type din=array of longint; type IntMas=array[1..2000] of longint; var mas,mas2:din; pre,rez:intMas; n,i,dlin,dlin2,kol,u,y,save,KOLM,a,b,sr,MAX,num,del,l,r:longint; f:text; // lMas:array[1..2000,1..2000] of longint; DELTA:array[0..1000000000] of boolean; T:BOOLEAN; t1,t2,t3,t4:_SYSTEMTIME; procedure sort(var d,d2:din;var l:longint); var dlin,dlin2:longint; mas2,mas3,Dmas2,Dmas3:din; begin t:=false; dlin:=l div 2; dlin2:=l-dlin; setlength(mas2,dlin+1); setlength(Dmas2,dlin+1); for i:=1 to dlin do mas2[i]:=d[i]; for i:=1 to dlin do Dmas2[i]:=d2[i]; setlength(mas3,dlin2+1); setlength(Dmas3,dlin2+1); for i:=1 to dlin2 do mas3[i]:=d[i+dlin]; for i:=1 to dlin2 do Dmas3[i]:=d2[i+dlin]; if dlin>1 then begin sort(mas2,Dmas2,dlin); end; if dlin2>1 then begin sort(mas3,Dmas3,dlin2); end; kol:=0; i:=1; u:=1; L:=dlin+dlin2; while kol<l do begin if mas2[i]<mas3[u] then begin inc(kol); d[kol]:=mas2[i]; d2[kol]:=Dmas2[i]; if i+1<=dlin then inc(i) else begin for y:=u to dlin2 do begin d[kol+y-u+1]:=mas3[y]; d2[kol+y-u+1]:=Dmas3[y]; end; break; end; end else begin inc(kol); d[kol]:=mas3[u]; d2[kol]:=Dmas3[u]; if u+1<=dlin2 then inc(u) else begin for y:=i to dlin do begin d[kol+y-i+1]:=mas2[y]; d2[kol+y-i+1]:=Dmas2[y]; end; break; end; end end; //sort() end; begin {assign(f,'input.txt'); reset(f);} readln({f,}n); setlength(mas,n+1); setlength(mas2,n+1); for i:=1 to n do begin read({f,}mas[i]); mas2[i]:=i; end; t:=false; if n>1 then sort(mas,mas2,n); rez[1]:=1; kolM:=1; DELTA[0]:=true; for i:=1 to n do for u:=i+1 to n do if not DELTA[mas[u]-mas[i]] then begin del:=mas[u]-mas[i]; DELTA[del]:=true; num:=mas[u]; num:=num+del; kol:=2; pre[1]:=mas2[u]; pre[2]:=mas2[i]; l:=u; r:=n; while true do begin if mas[l]=num then begin inc(kol); pre[kol]:=mas2[l]; num:=num+del; l:=l; r:=n; // break; end; if mas[r]=num then begin inc(kol); pre[kol]:=mas2[r]; num:=num+del; l:=r; r:=n; // break; end; if (mas[r]<>num) and(mas[l]<>num) then begin if ((abs(r-l)=1) or (abs(r-l)=0)) then begin if kol>kolM then begin for l:=1 to kol do rez[l]:=pre[l]; kolm:=kol; end; break; end; if mas[(l+r)div 2]<num then l:=(l+r)div 2 else r:=(l+r)div 2; end; end; end; writeln(kolM); for i:=1 to kolM do begin write(rez[i]); write(' '); end; //readln;
end. 9 1 3 5 11 2 3 4 7 9 answer: 6 1 2 3 8 9 4 | WA46 | Carbon | 1452. Pascal vs. C++ | 9 Apr 2007 17:43 | 1 | WA46 Carbon 9 Apr 2007 17:43 My solution cannot pass test 46. Tell me, please, what special in this test? |
|
|