| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| DP can AC in O(n^2)......but waht algo can AC in O(nlogn)? | Yu YuanMing | 1273. Шпалы | 11 май 2011 21:39 | 2 |
also DP....
It's obvious that LIS can be sloved in O(nlogn)... |
| WA#1 | kirill_SSAU619 | 1273. Шпалы | 31 окт 2010 14:25 | 1 |
WA#1 kirill_SSAU619 31 окт 2010 14:25 test 1?))
уже не надо
Edited by author 31.10.2010 14:28
Edited by author 31.10.2010 14:45
I have AC!!
Edited by author 31.10.2010 15:41 |
| If you have WA#3 | Aleksander | 1273. Шпалы | 1 апр 2010 22:59 | 2 |
Just write in your code:
...
scanf("%d",&n);
if (n == 0){
printf("0");
return 0;
}
...
When I write it I got AC
Good Luck :-) Thank you, I got AC too :) |
| test | Alexander Akimenko ssau 6108 | 1273. Шпалы | 23 мар 2010 20:21 | 2 |
test Alexander Akimenko ssau 6108 21 мар 2010 15:37 please give some tests, WA7 Re: test Alexander Akimenko ssau 6108 23 мар 2010 20:21 |
| wa7 | nick's_name | 1273. Шпалы | 4 окт 2009 16:21 | 1 |
wa7 nick's_name 4 окт 2009 16:21 I've tried all the tests mentioned here, and the output was correct. Still I have WA on test 7 var a,b,c,d: array [1..102] of integer; ind,n,i,j,k,z,v:integer; begin readln(n); k:=0; z:=0; for i:=1 to n do begin read(a[i]); readln(b[i]); if a[i]>b[i] then begin inc(z); d[i]:=1; end else d[i]:=0; end; if z>n div 2 then for j:=1 to n-1 do for i:=1 to n-1 do if d[i]>d[i+1] then begin v:=d[i]; d[i]:=d[i+1]; d[i+1]:=v; v:=a[i]; a[i]:=a[i+1]; a[i+1]:=v; v:=b[i]; b[i]:=b[i+1]; b[i+1]:=v; end; if z<n div 2 then for j:=1 to n-1 do for i:=1 to n-1 do if d[i]<d[i+1] then begin v:=d[i]; d[i]:=d[i+1]; d[i+1]:=v; v:=a[i]; a[i]:=a[i+1]; a[i+1]:=v; v:=b[i]; b[i]:=b[i+1]; b[i+1]:=v; end; repeat for i:=1 to n do c[i]:=0; for i:=1 to n do for j:=1 to n do if (((a[i]>a[j]) and (b[i]<b[j])) or ((a[i]<a[j]) and (b[i]>b[j]))) then c[i]:=c[i]+1; ind:=1; for i:=2 to n do if c[i]>c[ind] then ind:=i; a[ind]:=0; b[ind]:=0; if (c[ind]>0) then k:=k+1; until c[ind]=0; writeln(k); readln; end. |
| how can it be solved for nlogn? | Лелик | 1273. Шпалы | 29 авг 2009 15:50 | 5 |
I cant understand how it can be solved for nlogn. Help me
or I'll kill you! lelik! I know how But i won't saw cause rule is so stupid
please call me on 9 o'clock :)) what's your name? and how old are you? |
| I think K is too small | Gheorghe Stefan | 1273. Шпалы | 29 авг 2009 15:38 | 6 |
This could be done in K logK... why K is only 100? It's 100. And I didn't say that is ok, I just said that K could be 100.000 and still working. I agree with you
k log k is very simple :) |
| Please help anybody(What a ucking tests are there??) | Emil | 1273. Шпалы | 1 мар 2008 00:13 | 1 |
#include <iostream.h>
int main()
{int K,max;
cin>>K;
int **a=new int*[K];
for (int i=0;i<2;i++)
a[i]=new int[K];
for (int i=0;i<K;i++)
for (int j=0;j<2;j++)
cin>>a[j][i];
int *b=new int[2000];
for (int i=0;i<2000;i++)
b[i]=0;
for (int i=0;i<K;i++)
if (a[0][i]>a[1][i]) b[a[0][i]-a[1][i]]++;
else b[a[1][i]-a[0][i]+1000]++;
max=b[0];
for (int i=1;i<2000;i++)
if (b[i]>max) max=b[i];
cout<<K-max<<endl;
//cin>>K;
}
????? |
| How accepted 1273??? | Lepilin Max SSAU 619 | 1273. Шпалы | 15 янв 2008 19:16 | 1 |
|
| Need tests! It brakes on 7-th test! | UMC (SSAU) | 1273. Шпалы | 3 дек 2007 19:35 | 1 |
|
| why wa on test#7? Help | LeXuS[Alex Kalugin] | 1273. Шпалы | 3 дек 2007 19:32 | 8 |
{$R+}
var
a, b: array[1 .. 101] of longint;
y1, y2: array[1 .. 101] of longint;
j, k, i, n, max, ind: longint;
bn : boolean;
begin
read (n);
for i := 1 to n do read (y1[i], y2[i]);
repeat
bn := true;
for i := 1 to n - 1 do
for j := i + 1 to n do begin
if (b[i] = 0) and (b[j] = 0) then
if ((y1[i] > y1[j]) and (y2[i] < y2[j])) or
((y1[i] < y1[j]) and (y2[i] > y2[j])) or
(y1[i] = y1[j]) or (y2[i] = y2[j]) then
begin
bn := false;
inc (a[i]);
inc (a[j]);
end;
end;
max := 0;
for i := 1 to n do if a[i] > max then begin max := a[i]; ind := i; end;
if max > 0 then begin inc (k); b[ind] := 1; end;
for i := 1 to n do a[i] := 0;
until bn = true;
writeln (k);
end. Try test
5
5 3
4 6
2 4
3 1
7 5
Correct answer is 2, but your - 3.
You can remove second and third ties. #include <iostream>
using namespace std;
void main()
{
int y1[100];
int y2[100];
int n,i,q,u;
int ct[100];
int cty1[10000];
int cty2[10000];
int cr = 0,res = 0;
int spect[100];
cin >> n;
for(i = 0; i<n; i++)
{
cin >> y1[i];
cin >> y2[i];
ct[i] = 0;
}
for(i = 0; i<n; i++)
{
for(q = i+1; q<n; q++)
{
if ( ((y1[i]>=y1[q]) && (y2[i]<=y2[q])) || ((y1[i]<=y1[q]) && (y2[i]>=y2[q])) )
{
ct[i]++;
ct[q]++;
cty1[cr] = i;
cty2[cr] = q;
cr++;
}
}
}
while(cr!=0)
{
int max = ct[0];
int mid = 0;
int l = 0;
for(u = 0; u<n; u++)
{
if (ct[u]>max) { max = ct[u]; mid = u; }
}
for(u = 0; u<n; u++)
{
if (ct[u]==max) { spect[l] = u; l++; }
}
///////////
int mini = 10000;
int minid = spect[0];
for(u = 0; u<l; u++)
{
int cur = 0;
for(int y = 0; y<l; y++)
if (y!=u)
for(int o = 0; o<cr; o++)
if ( (cty1[o]==spect[u] && cty2[o]==spect[y]) || (cty2[o]==spect[u] && cty1[o]==spect[y]) ) cur++;
if (cur<mini) { minid = spect[u]; mini = cur; }
}
///////////
mid = minid;
for(i = 0; i<cr; i++)
{
if (cty1[i]==mid)
{
ct[cty2[i]]--;
if (i!=cr-1)
{
cty1[i] = cty1[cr-1];
cty2[i] = cty2[cr-1];
}
cr--;
i--;
} else
{
if (cty2[i]==mid)
{
ct[cty1[i]]--;
if (i!=cr-1)
{
cty1[i] = cty1[cr-1];
cty2[i] = cty2[cr-1];
}
cr--;
i--;
}
}
}
ct[mid] = 0;
res++;
}
cout << res;
cin >> res;
}
P.S. it works with
5
5 3
4 6
2 4
3 1
7 5 |
| Problem 1273 "Tie" has been rejudged (+) | Sandro (USU) | 1273. Шпалы | 12 дек 2006 01:33 | 2 |
Some new tests were added. 35 authors got WA. The next rejudge will take place if new tricky tests will be found.
Edited by author 24.11.2006 22:45 New rejudge has been finished. 22 submits lost AC verdict. Thanks to anus(USU) for idea of some good tests. |
| WA#9 | Trần Quang Chung | 1273. Шпалы | 10 июн 2006 21:53 | 1 |
WA#9 Trần Quang Chung 10 июн 2006 21:53 What is this. I'm WA on test 9. Help me |
| I didn't expect me to be so stupid! I even don't know how to organize DP! | Alexey | 1273. Шпалы | 10 июн 2006 17:30 | 1 |
I like DP, but now I cann't do it!
May be the weather is bed, that's why...
Please, help me!
Thanks. |
| (wa5) give me wrong test. PLEASE. | Виктор Крупко | 1273. Шпалы | 21 авг 2005 21:39 | 6 |
var
x,y:array[1..100] of integer;
b:array[1..100] of boolean;
i,n,otv:integer; ex:boolean;
procedure reflesh;
var
i,max,col,j,yd:integer;
begin
ex:=false;
for i:=1 to n do
if b[i] then
begin
col:=0;
for j:=1 to n do
if (i<>j) and b[j] then
begin
if (x[i]=y[i]) then break;
if (x[i]<y[i]) then
if ((x[j]>x[i]) and (y[i]>y[j])) then begin inc(col); yd:=j; end;
if (x[i]>y[i]) then
if ((x[i]>x[j]) and (y[i]<y[j])) then begin inc(col); yd:=j; end;
end;
if col=1 then begin inc(otv); b[yd]:=false; ex:=true; break; end;
end;
end;
begin
{ assign(input,'c:\test.txt');
reset(input);}
ex:=true;
readln(n);
fillchar(b,sizeof(b),true);
for i:=1 to n do readln(x[i],y[i]);
while ex do reflesh;
writeln(otv);
end. Try this
3
1 5
2 3
3 4
The right answer - 1.
You should use DP. I am very weak in the theory.
My algorithm not true.
Whether you can give me idea. (my mail xxvictorxx@mail.ru (if has overlooked))
you algo wrong.
You need use DP.
i got AC O(N^2/2) Re: MALADEZ Tolstobrov_Anatoliy[Ivanovo SPU] 21 авг 2005 21:39 |
| What the heck is wrong with this stupid problem? | Jiang Xu | 1273. Шпалы | 11 авг 2005 00:02 | 5 |
I've seen there are many WA's for this problem, even if you only need basic knowledge to solve it. Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define MAXN 101 typedef struct shit { int x, y; }; shit a[MAXN]; int N, i, j; int m[MAXN]; int cmp(shit a, shit b) { return a.x < b.x ? 1 : 0; } int main(void) { scanf("%d\n", &N); for (i = 0; i < N; i ++) scanf("%d %d\n", &(a[i].x), &(a[i].y)); sort(a, a + N, cmp); int ans = 1; m[0] = 1; for (i = 1; i < N; i ++) { m[i] = 1; for (j = 0; j < i; j ++) if (a[j].y < a[i].y && 1 + m[j] > m[i]) m[i] = 1 + m[j]; if (m[i] > ans) ans = m[i]; } printf("%d\n", N - ans); return 0; } "Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3..."
Oh yeah... I couldn't find bug in your source, but since I had many problems myself on this one I can send you my code. E-mail me on dporobic at gmail dot com . |
| Who can give me some GOOD tests I got Wa7! I thinck my program GOOG! but Wa7 | Нищий Наглец | 1273. Шпалы | 29 июл 2005 04:34 | 1 |
|
| I got AC | Тёма и Серёжа | 1273. Шпалы | 14 май 2005 16:09 | 2 |
I got AC Тёма и Серёжа 28 май 2004 19:37 If you want to know how to solve it, write me on shteynerserg@mail.ru |
| How did you do it in O(n^2). I only know n^3 =( | hey, dude! | 1273. Шпалы | 4 апр 2005 16:55 | 2 |
It also can be done in O(K * logK). O(N^2) is with DP, a classic problem (longest increasing subset) |
| And what about this test? | Sandro | 1273. Шпалы | 3 фев 2005 11:27 | 5 |
My AC solution with DP outputs 2 in this test:
6
0 3
1 0
2 2
3 5
4 1
5 4
But the correct answer is 3. Maybe this test should be added to the test set. I remember the optimal answer for sets of ties with numbers k..l for all k,l (for all segments).
The optimal answer Ans(k,l+1)= max(Ans(k,l),S+1), where S is the sum of optimal answers for all segments in k..l, that any tie of any of these segments doesn't intersect (l+1)th tie. (In the first case we delete (l+1)th tie, in the second case leave (l+1) and delete all ties, intersecting it.)
This algorith is not correct, because ties in the optimal solutions can intersect, so sum of the optimal solutions may not be solution at all. My test is the simple example of it. But this algorith gets AC, and this is very strange. |
