CAN SOME ONE GIVE ME SOME TEST?

MY GMAIL: LIHE21327@GMAIL.COM

its a greedy+dp according to me

you should analyze the four scenario like

1. two increasing sequence :

     take two array . two array initially have only one value zero. then iterate over 2nd to nth element.

     if element > 1st and 2nd arrays last element
             then, 1st sequence last element > 2nd arrays last element then: (add element
                                                                  to the 1st array)
             otherwise (add element to the 1st array)
     otherwise   add it to the array whose last element < element

     (this is optimal ).

2. two decreasing sequence: approach greedily like 1st one

3. one increasing and one decreasing(1st element included in the increasing array):(try yourself)

4. one increasing and one decreasing(1st element included in the decreasing array):(try yourself)

for 3rd and 4th criteria , think greedily also.

The program is already installed in one computer.
Now, we need to install it in (N-1) computers.

abc
cba
6
aba
bab
2
abcabc
cba
5
abcbaabdca
abcada
1
abcabbaca
abcabbc
1

you can easily find the solution with O(nk^3)

but it will give u tle

after optimization with cumulative sum array it will be O(nk^2)

import java.util.Scanner;
public class Staircases {
      public static void main(String... args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        System.out.println(find_Q(N, N));
    }

      static int find_Q(int X, int Y) {
         int U = X-1;
         if(Y<X) {
         U = Y;
         if(Y == 0 || Y ==1)
         return 1;
         }
         if(Y<=1)
         return 0;
         int A = 0;
         for(int i = U; i > 0; i--)
          A += find_Q(i, Y-i);
         return A;
          }
}

I've implemented several approaches, ones calculate 1/4 of circle, another ones calculate 1/8 of circle. All of them works fine for R < 60000000. With R > 60millions there is a chance (and it increases with bigger R) 2 approaches can give different results. They use the same calculations (sqrt, ceiling). I also tried to implement 1/8 without float point numbers, by integers only. Same result with same difference. Maybe these "magic" numbers can help someone

r: 67250001 correct: 14208049816923164 diff: 12
r: 67250051 correct: 14208070944129524 diff: 4
r: 67250211 correct: 14208138551359320 diff: 4
r: 67250249 correct: 14208154608083608 diff: 8
r: 67250321 correct: 14208185031387396 diff: 16
r: 67250433 correct: 14208232356606236 diff: 4
r: 67250449 correct: 14208239117361224 diff: 4
r: 67250505 correct: 14208262780007696 diff: 4
r: 67250601 correct: 14208303344588340 diff: 8
r: 67250697 correct: 14208343909213316 diff: 4
r: 67250769 correct: 14208374332717888 diff: 4
r: 67250825 correct: 14208397995480888 diff: 4
r: 67250835 correct: 14208402220968636 diff: 4
r: 67251315 correct: 14208605045441340 diff: 8
r: 67251347 correct: 14208618567139620 diff: 12
r: 67251457 correct: 14208665047975948 diff: 4

Edited by author 07.04.2021 02:35

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

AC in 0.015 sec with dp
if u r better with math plz reply

Edited by author 07.04.2021 13:27

Edited by author 07.04.2021 13:27

Edited by author 07.04.2021 13:27

AA=0,AB=1,BA=2,BB=3
cnt[0]=no. of AA,cnt[1]=no. of AB...........

int sz=2;
if(last letter==A) szvalue=0;
if(last letter==B) szvalue=2;

define DP[cnt[0]+2][cnt[1]+2][cnt[2]+2][cnt[3]+2][sz];

dp 1,0,0,0,0=1; //for AA
dp 0,1,0,0,1=1; //for AB

Edited by author 05.05.2016 19:23

I had int n,i; and I had wa #10, then I changed them to long long and got ac, but I can't understand why I got wa10 with int n,i; where i and n can't exceed 10^6.

My algorithm is O(R) and i have AC

I got WA at #1 and I use line tree.
Now I've accepted!

Edited by author 07.03.2013 19:40

what is test5 look like?

Edited by author 02.04.2021 18:58

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

I've found dp[sum][last][k] as cnt of make sum with k numbers and last number is last, but calculation of this dp is too long, so i've just precalculated it. Can you give me a hint?