ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1273. Tie

why wa on test#7? Help
Posted by LeXuS[Alex Kalugin] 12 Jul 2004 01:27
{\$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
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.
Greedy doesn't work :)
Posted by Vlad Veselov [PMG17, Vinnitsa - KNU, Kiev] 12 Jul 2004 18:31
Try test
5
5 3
4 6
2 4
3 1
7 5
You can remove second and third ties.
Re: Greedy doesn't work :)
Thanks! I Understand...
Just use DP (-)
Posted by Dmitry 'Diman_YES' Kovalioff 12 Jul 2004 21:32
Re: Just use DP (-)
Posted by LeXuS[Alex Kalugin] 12 Jul 2004 23:47
what is DP?
Dynamic programing :) (-)
Posted by Dmitry 'Diman_YES' Kovalioff 13 Jul 2004 12:10
Re: Dynamic programing :) (-)
Posted by LeXuS[Alex Kalugin] 13 Jul 2004 14:58
ok...
Help me with test 7!
Posted by UMC (SSAU) 3 Dec 2007 19:32
#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