Discussion @ 1273. Tie @ Timus Online Judge

Yu YuanMing DP can AC in O(n^2)......but waht algo can AC in O(nlogn)? [1] // Problem 1273. Tie 9 Oct 2004 20:59

kirill_SSAU619 WA#1 // Problem 1273. Tie 31 Oct 2010 14:25

Aleksander If you have WA#3 [1] // Problem 1273. Tie 17 Mar 2010 00:10

Alexander Akimenko ssau 6108 test [1] // Problem 1273. Tie 21 Mar 2010 15:37

nick's_name wa7 // Problem 1273. Tie 4 Oct 2009 16:21

Лелик how can it be solved for nlogn? [4] // Problem 1273. Tie 14 May 2005 15:56

Gheorghe Stefan I think K is too small [5] // Problem 1273. Tie 8 Sep 2004 16:43

Emil Please help anybody(What a ucking tests are there??) // Problem 1273. Tie 1 Mar 2008 00:13

Lepilin Max SSAU 619 How accepted 1273??? // Problem 1273. Tie 15 Jan 2008 19:16

UMC (SSAU) Need tests! It brakes on 7-th test! // Problem 1273. Tie 3 Dec 2007 19:35

LeXuS[Alex Kalugin] why wa on test#7? Help [7] // Problem 1273. Tie 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
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.

Vlad Veselov [PMG17, Vinnitsa - KNU, Kiev] Greedy doesn't work :) [6] // Problem 1273. Tie 12 Jul 2004 18:31

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.

KIEV_lyceum_№145 (Grinenko,Kalugin,Ryjouk) Re: Greedy doesn't work :) [4] // Problem 1273. Tie 12 Jul 2004 19:32

Thanks! I Understand...

Dmitry 'Diman_YES' Kovalioff Just use DP (-) [3] // Problem 1273. Tie 12 Jul 2004 21:32

LeXuS[Alex Kalugin] Re: Just use DP (-) [2] // Problem 1273. Tie 12 Jul 2004 23:47

what is DP?

Dmitry 'Diman_YES' Kovalioff Dynamic programing :) (-) [1] // Problem 1273. Tie 13 Jul 2004 12:10

LeXuS[Alex Kalugin] Re: Dynamic programing :) (-) // Problem 1273. Tie 13 Jul 2004 14:58

ok...

UMC (SSAU) Help me with test 7! // Problem 1273. Tie 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

Sandro (USU) Problem 1273 "Tie" has been rejudged (+) [1] // Problem 1273. Tie 24 Nov 2006 14:26

Trần Quang Chung WA#9 // Problem 1273. Tie 10 Jun 2006 21:53

Alexey I didn't expect me to be so stupid! I even don't know how to organize DP! // Problem 1273. Tie 10 Jun 2006 17:30

Виктор Крупко (wa5) give me wrong test. PLEASE. [5] // Problem 1273. Tie 17 Aug 2005 00:05

Jiang Xu What the heck is wrong with this stupid problem? [4] // Problem 1273. Tie 16 Jul 2005 03:08

Нищий Наглец Who can give me some GOOD tests I got Wa7! I thinck my program GOOG! but Wa7 // Problem 1273. Tie 29 Jul 2005 04:34

Тёма и Серёжа I got AC [1] // Problem 1273. Tie 28 May 2004 19:37

hey, dude! How did you do it in O(n^2). I only know n^3 =( [1] // Problem 1273. Tie 4 Apr 2005 14:56

Sandro And what about this test? [4] // Problem 1273. Tie 31 Jan 2005 15:42

Discussion of Problem 1273. Tie