ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1078. Segments

Please help me...WA #1 ;((((((((((((
Posted by NoX 16 Nov 2005 22:25
I can`t understand why my program has Wrong Answer on test #1...
Here is my program:
program z1078;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
        maxn=500;

type
        tSeg=record
                x,y:integer;
        end;
        tMyEl=record
                value:array[1..maxn]of boolean;
        end;

var
        n,i,j,k:integer;
        seg:array[1..maxn]of tSeg;
        m:array[1..maxn,1..maxn]of boolean;
        flag:boolean;
        el,maxel:tMyEl;
        color:array[1..maxn]of boolean;
        maxcount:integer;
        l:array[1..maxn]of integer;


procedure SIG(v,count:integer;el:tMyEl);
var
        i:integer;

begin
        el.value[v]:=true;
        color[v]:=true;
        if count>maxcount
         then
          begin
                maxcount:=count;
                maxel:=el;
          end;
        for i:=1 to n do
         begin
                if m[v,i] and not color[i]
                 then
                  SIG(i,count+1,el);
         end;
end;

procedure SortThis(n:integer);
var
        min,s,j,imin:integer;

begin
        for s:=1 to n-1 do
         begin
                min:=l[s];
                imin:=s;
                for j:=s+1 to n do
                 if (seg[l[j]].y-seg[l[j]].x)<(seg[l[imin]].y-seg[l[imin]].x)
                  then
                   begin
                       imin:=j;
                       min:=l[j];
                   end;
                l[imin]:=l[s];
                l[s]:=min;
         end;
end;

begin
        readln(n);
        for i:=1 to n do
         readln(seg[i].x,seg[i].y);
        for i:=1 to n do
         for j:=1 to n do
          m[i,j]:=false;
        for i:=1 to n do
         begin
                for j:=1 to n do
                 begin
                        if (seg[j].x>seg[i].x) and (seg[j].y<seg[i].y)
                         then
                          m[i,j]:=true;
                 end;
         end;
        maxcount:=0;
        for i:=1 to n do
         begin
                for j:=1 to n do
                 el.value[j]:=false;
                for j:=1 to n do
                 color[j]:=false;
                SIG(i,1,el);
         end;
        writeln(maxcount);
        j:=0;
        for i:=1 to n do
         if maxel.value[i]
          then
           begin
                inc(j);
                l[j]:=i;
           end;
        SortThis(j);
        for i:=1 to j-1 do
         write(l[i],' ');
        writeln(l[j]);
        readln;
end.

Please... Help me
Re: Please help me...WA #1 ;((((((((((((
Posted by Bluejack 05-2 Team 17 Nov 2005 08:47
I think it is DP problem.
I use Longest Decreasing  SubSequence(LDS).

-First sort the point coordinate by y value(ascending)
-Then do LDS normally by x value

O(N^2) it's enough to get AC from this problem.