What's Test 9?

I saw, that Test 9:
7
1 3
2 5
2 5
4 7
6 9
6 9
8 10

My answer:
3
1 3
4 7
8 10

What's correct answer?

My program runs any tests from other topics perfectly, but something is wrong with the task 1. Sounds like madness.

Edited by author 24.02.2022 23:04

Edited by author 24.02.2022 23:05

What is test #3??

I got WA in first test. I checked my program using a lot of compiler and in first test my program outputs is correct.

my code id:9308865

Hello. My program passes all tests from the forum, but I still get WA6.

I do brute force

First, I go through all the elements that are to the right of the current one, then everything that is to the left

can anyone have any tests?

here is y code is needed:

#include <iostream>

using namespace std;

int n, result = 0, sizeHelpArray = 0, sizeAnswerArray;
int line[100][2], helpArray[100][2], answerArray[100][2];

//initialization and sorting on the left border
void Init()
{
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> line[i][0] >> line[i][1];
        if (line[i][0] > line[i][1])
            swap(line[i][0], line[i][1]);
    }

    for (i = 0; i < n; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (line[j][0] < line[i][0])
            {
                swap(line[i][0], line[j][0]);
                swap(line[i][1], line[j][1]);
            }
            if(line[j][0] == line[i][0])
                if (line[j][1] < line[i][1])
                {
                    swap(line[i][0], line[j][0]);
                    swap(line[i][1], line[j][1]);
                }
        }
    }
}

//adding a segment to the temporary answer

void AddInHelpArray(int index)
{
    sizeHelpArray++;
    helpArray[sizeHelpArray][0] = line[index][0];
    helpArray[sizeHelpArray][1] = line[index][1];
}

//to record the best current result

void copyInAnswerArray()
{
    int i;
    for (i = 0; i < sizeHelpArray + 1; i++)
    {
        answerArray[i][0] = helpArray[i][0];
        answerArray[i][1] = helpArray[i][1];
    }
}

void sortAnswerArray()
{
    for (int i = 0; i <= sizeAnswerArray; i++)
    {
        for (int j = i + 1; j <= sizeAnswerArray; j++)
        {
            if (answerArray[j][0] < answerArray[i][0])
            {
                swap(answerArray[i][0], answerArray[j][0]);
                swap(answerArray[i][1], answerArray[j][1]);
            }
            if (answerArray[j][0] == answerArray[i][0])
                if (answerArray[j][1] < answerArray[i][1])
                {
                    swap(answerArray[i][0], answerArray[j][0]);
                    swap(answerArray[i][1], answerArray[j][1]);
                }
        }
    }
}

void Solve()
{
    int i, x, tmp = 1, currentPoint;
        //starting from the first element ..
    for (x = 0; x < n; x++)
    {
        sizeHelpArray = 0;
        tmp = 1;
        memset(helpArray, 0, sizeof(helpArray));
                //I write the current element to an auxiliary array
        helpArray[sizeHelpArray][0] = line[x][0];
        helpArray[sizeHelpArray][1] = line[x][1];
        currentPoint = line[x][1];
                //Checking items to the right of the current one
        for (i = x + 1; i < n; i++)
        {
            if (line[i][0] >= currentPoint)
            {
                tmp++;
                currentPoint = line[i][1];
                AddInHelpArray(i);
            }
        }


        currentPoint = line[x][0];
        int border;
        border = line[x][0];
        bool first = true;
                //Checking items to the left of the current one
        for (int j = 0; j < x; j++)
        {
            if (line[j][1] <= currentPoint && first)
            {
                tmp++;
                currentPoint = line[j][1];
                AddInHelpArray(j);
                first = false;
            }
            else if (first == false && line[j][0] >= currentPoint && line[j][1] <= border)
            {
                tmp++;
                currentPoint = line[j][1];
                AddInHelpArray(j);
            }
        }
                //If the result is better than the previous one, then I save it.
        if (tmp > result)
        {
            result = tmp;
            copyInAnswerArray();
            sizeAnswerArray = sizeHelpArray;
        }
    }

    sortAnswerArray();
    cout << result << endl;
    for (int i = 0; i <= sizeAnswerArray; i++)
        cout << answerArray[i][0] << " " << answerArray[i][1] << endl;
}

int main()
{
    Init();
    Solve();
    return 0;
}

Edited by author 02.04.2021 07:26

Edited by author 02.04.2021 07:26

Edited by author 02.04.2021 07:37

Edited by author 02.04.2021 07:37

6
1 5
2 6
3 7
4 8
5 9
6 10

WHY answer is:
2
1 5
5 9
I think [2;6] and [3;7] have common interior point such as 3, 4, 5, 6.

Does anyone know the 8th test?

Solved both tasks with the same algorithm. Think this task is over-valued.

Edited by author 26.10.2016 20:59

If you're doing a greedy solution and you're sorting by the rightmost endpoints (B_i), you need to sort with the leftmost endpoints as second key. That is, if B_i == B_j, the shortest segment of i and j goes first in the list.

This basically means that longer segments are kept, so for inputs:

3
3 5
1 5
5 6

You would get result
2
1 5
5 6

instead of
2
3 5
5 6

which means you get a bigger covering of the set but the problem statement didn't mention this requirement.

Edited by author 24.12.2014 21:07

Change "left" to "remaining" since it would otherwise indicate "the opposite of right" which is confusing

Is there somebody who can give me input data for test #2?

Edited by author 03.11.2013 17:06

This problem is quite easy.You can sort the "end node",and then use the greedy algo to solve the program.

What's Test 9?

My algo is:
Search the segment with more intersections and delete it (repeat while the segment got 0 intersections)
Is it wrong?

I got AC, but on test:

6
0 30
10 70
20 80
40 110
90 130
120 140

my AC program output:
2
0 30
90 130

but answer must be:
3
0 30
40 110
120 140

Please tell me the reason or give me the t4,thank you!
This is my program:
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int n,result=0,xia=0,rxia;
int line[110][2],era[110][2],fera[110][2];
void init()
{
  int i,j;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
  {
    scanf("%d %d",&line[i][0],&line[i][1]);
    if(line[i][0]>line[i][1])
      swap(line[i][0],line[i][1]);
  }
  for(i=1;i<n;i++)
    for(j=i+1;j<=n;j++)
    {
      if(line[j][0]<line[i][0])
      {
        swap(line[i][0],line[j][0]);
        swap(line[i][1],line[j][1]);
      }
      if(line[j][0]==line[i][0])
        if(line[j][1]<line[i][1])
        {
          swap(line[i][0],line[j][0]);
          swap(line[i][1],line[j][1]);
        }
    }
}
void jilu(int i)
{
  xia++;
  era[xia][0]=line[i][0];
  era[xia][1]=line[i][1];
}
void copyera()
{
  int i;
  for(i=1;i<=xia;i++)
  {
    fera[i][0]=era[i][0];
    fera[i][1]=era[i][1];
  }
}
void solve()
{
  int i,x,temp=1,now;
  for(x=1;x<=n;x++)
  {
    xia=0;
    temp=1;
    memset(era,0,sizeof(era));
    xia++;
    era[xia][0]=line[x][0];
    era[xia][1]=line[x][1];
    now=line[x][1];
    for(i=x+1;i<=n;i++)
      if(line[i][0]>=now)
      {
        temp++;
        now=line[i][1];
        jilu(i);
      }
    if(temp>result)
    {
      result=temp;
      copyera();
      rxia=xia;
    }
  }
  printf("%d\n",result);
  for(i=1;i<=rxia;i++)
    printf("%d %d\n",fera[i][0],fera[i][1]);
}
int main()
{
  init();
  solve();
  return(0);
}

Thank you very much!!!

maybe you forgot to write how many lines should be saved.
sorry for my poor English

My english ability is very poor!So I can't express correctly~I feel very sorry.
    About this problem,I have tried many data.But I am sorry I can't found that anything is wrong.Next I will give my code,I hope somebody can help me,or give me some hints.Thank you very much~
#include "stdio.h"
#include "malloc.h"
int main()
{
  int amount,i,j;
  int **endpoint;
  int *flag,temp;
  int max,index = -1;
  int condition = 0,count = 0;
  int test = 0;
  scanf("%d",&amount);
//  if(amount <= 0 || amount >= 100)
//  {
 //   return 0;
 // }
  endpoint = (int **)malloc(sizeof(int*) * amount);
  flag = (int *)malloc(sizeof(int) * amount);
  for( i = 0;i < amount;i ++)
  {
    endpoint[i] = (int *)malloc(sizeof(int) * 2);
  }
  flag = (int *)malloc(sizeof(int) * amount);
  for( i = 0;i < amount;i ++ )
  {
    scanf("%d%d",&endpoint[i][0],&endpoint[i][1]);
    if( endpoint[i][0] == endpoint[i][1] || endpoint[i][0] > 999 || endpoint[i][0] < -999 || endpoint[i][1] > 999 || endpoint[i][1] < -999)
    {
       return 0;
    }
    flag[i] = 0;
     if(endpoint[i][0] > endpoint[i][1])
     {
         temp = endpoint[i][0];
         endpoint[i][0] = endpoint[i][1];
         endpoint[i][1] = temp;
     }
  }
  //排序
  for(i = 0; i < amount - 1 ;i ++)
  {
      for(j = i + 1;j < amount;j++)
      {
         if(endpoint[i][0] > endpoint[j][0])
         {
           temp = endpoint[i][0];
           endpoint[i][0] = endpoint[j][0];
           endpoint[j][0] = temp;
           temp = endpoint[i][1];
           endpoint[i][1] = endpoint[j][1];
           endpoint[j][1] = temp;
         }
      }
  }
  while(condition != 0 || count == 0 )
  {
      condition = 0;
      test = 0;
   for(i = 0;i < amount;i ++)
   {
   if(endpoint[i][0] !=0 || endpoint[i][1] != 0)
     {
     for(j = 0;j < amount;j ++)
     {
       if(endpoint[j][0] !=0 || endpoint[j][1] != 0)
       {
        if(endpoint[i][0] > endpoint[j][0] && endpoint[i][0] < endpoint[j][1] )
        {
         flag[i] += 1;
       }
       else if(endpoint[i][0] <= endpoint[j][0] && endpoint[i][1] >= endpoint[j][1] )
       {
           if(i != j && ( endpoint[i][0] != 0 || endpoint[j][0] != 0 ))
             flag[i] += 1;
       }
       else
       {
         if(endpoint[i][1] > endpoint[j][0] && endpoint[i][1] < endpoint[j][1])
         {
           flag[i] += 1;
         }
       }
      }
     }
    }
  }
  max = flag[0];
  index = 0;
  condition += flag[0];
  flag[0] = 0;
  for( i = 1 ;i < amount;i ++ )
  {
      condition += flag[i];
    if(max < flag[i])
    {
        max = flag[i];
        index = i;
    }
    flag[i] = 0;
  }
    if(index != -1 && condition != 0 )
    {
       endpoint[index][0] = 0;
       endpoint[index][1] = 0;
    }
    count ++;
 }
  printf("%d\n",amount - count + 1);
  for(i = 0 ;i < amount;i ++)
  {
      if(endpoint[i][0] != 0 || endpoint[i][1] != 0)
      {
         printf("%d %d\n",endpoint[i][0],endpoint[i][1]);
      }
  }
  return 0;
}

If you have a problem - WA4 - consider sorting input, not output

for example:

5
1 5
3 6
1 3
9 6
4 2

answer
3
1 3
3 6
6 9

I WA at Test 4.
Who can tell me what the test 4 is?

Edited by author 04.04.2010 10:48