Hi! I'm just amazed about this algorithm! My previous O(N^3) implementation take 0.624 and 508 KB with my best efforts to reduce runtime. When I submitted the Manacher's one, the runtime dropped down to 0.015 and 2376 KB!! Just google it. It's a very easy and efficient O(N) algorithm. That's all you need to solve this problem. No more than 30 lines of code.

Can anyone please tell me in tabular form what is are the values of answers for the above values. My algorithm is almost right and it is calculating accurately as far as I know but it is always responding No on test # 2. Please help!!! I am stuck and dissappointed.... :(

What is the test 18? I really don't understand it... I wrote solution with ternary search, and I think that there is problem with accuracy of calculations. Have anybody this problem?

P.S. Sorry for my bad english :)

The following code is failing the test case 3, I have used linked-list to store the data in as a stack. Below is the code for reference, can you tell me where I am going wrong. Thank you.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<math.h>
#include<assert.h>

typedef unsigned long long _ull;
typedef unsigned int _uint;

typedef struct _link_list {
    _ull _number;
    struct _link_list*_next;
} _list;

void _makenode(_list**,_ull);
void _insertnode(_list**,_list*);

int main(int argc,const char*argv[]) {
    _ull _val;
    _list *_head,*_temp;
    _head = _temp = NULL;
    while(true) {
        fscanf(stdin,"%lld",&_val);
        assert(_val>=0);
        if(feof(stdin)) break;
        _makenode(&_head,_val);
    }
    while(_head) {
        _temp = _head;
        fprintf(stdout,"%0.4lf\n",sqrt(_head->_number));
        _head = (_head->_next);
        free(_temp);
    }
    return 0;
}

void _makenode(_list**_ptr,_ull _data) {
    _list*_node = malloc(sizeof(_list));
    (_node->_number) = _data;
    (_node->_next) = NULL;
    _insertnode(_ptr,_node);
}

void _insertnode(_list**_ptr,_list*_node) {
    if(!(*_ptr)) (*_ptr) = _node;
    else {
        (_node->_next) = (*_ptr);
        (*_ptr) = _node;
    }
}

Try testcases
12 11
1
12 10
2
100 7
7
20 7
2
1000 1
26
10000 1
37
10000 13
25
100 25
8

Can you please explain what this problem is asking?

Input:
10 2
8 8
Output:
6

Input:
10 3
8 8 8
Output:
4

Can you explain how the output is changing? What's the logic/intuition behind this? Please explain in details.

What is test 7?

[code deleted]

Edited by moderator 19.11.2019 23:08

#include <iostream>
#include <string>
using namespace std;
int main()
{
    int n,i,k=2;
    string s;
    cin>>n;

    for (i=1;i<=n;++i)
    {
        getline(cin,s);
        if (s.find("+")!=string::npos)
        k+=2;

        else
        ++k;
    }

    if (k==13)
    ++k;

    cout<<k*100;

    return 0;
}

Edited by author 16.06.2019 18:08

Edited by author 16.06.2019 18:08

Is it special test? I have no idea, what is wrong with my implementation.

Hello! I`ve got a code, equations must be right, but the result is different from sample. I don`t know what the problem is. Please, help!! My result is 45,28, whereas the sample`s one is 52,04.

static void Main(string[] args)
        {
            const double D = 6875;
            const double pi = 3.1415926535897932384626433;
            string trash;
            char[] separators = new[] { ' ', '^', '"', '\''};
            /* double shipx, shipy, shipz, icex, icey, icez; */
            for (int i = 0; i < 3; i++)
                trash = Console.ReadLine();
            var shipLat = Console.ReadLine().Split(separators);
            var shipLong = Console.ReadLine().Split(separators);
            trash = Console.ReadLine();
            var iceLat = Console.ReadLine().Split(separators);
            var iceLong = Console.ReadLine().Split(separators);
            trash = Console.ReadLine();

            double phi1 = (int.Parse(shipLat[0]) + (int.Parse(shipLat[1]) + int.Parse(shipLat[2]) / 60) / 60) * (pi / 180);
            double phi2 = (int.Parse(shipLong[1]) + (int.Parse(shipLong[2]) + int.Parse(shipLong[3]) / 60) / 60) * (pi / 180);
            if (shipLat[3] == "SL") phi1 = -phi1;
            if (shipLong[4] == "WL") phi2 = -phi2;

            double L1 = (int.Parse(iceLat[0]) + (int.Parse(iceLat[1]) + int.Parse(iceLat[2]) / 60)/60) * (pi / 180);
            double L2 = (int.Parse(iceLong[1]) + (int.Parse(iceLong[2]) + int.Parse(iceLong[3]) / 60)/60) * (pi / 180);
            if (iceLat[3] == "SL") L1 = -L1;
            if (iceLong[4] == "WL") L2 = -L2;

            double ans = Math.Acos(Math.Sin(phi1) * Math.Sin(L1) + Math.Cos(phi1) * Math.Cos(L1) * Math.Cos(L2-phi2));
            double dist = ans * D/2;

            Console.Write("The distance to the iceberg: ");
            Console.WriteLine("{0:0.00}", dist);
            if (100.00 - dist > 0.005) Console.WriteLine("DANGER!");
        }

I just cin every string and then solve using it. 0.156 accepted

1 1
1 1
1

the answer must be "NO", not "YES"

Edited by author 27.04.2007 09:34

If its not a multy eadge and it is a bridge, then it increase the number of pieces by one otherwise the pieces amount left same. Am I right?

#include<iostream>
#include<string.h>
#include<deque>
#include<stdio.h>
using namespace std;
int main()
{
    string node;
    cin >> node;
    int one,two;
    one = 0;
    two = 1;
    int pre = 0;
    for(int i = 0;i < node.size();i++)
    {
        if(node[i] == '!')
        continue;
        if(node[i] == node[i+1])
        {
            node[i] = node[i+1] = '!';
            one = pre;
            if(i+2 < node.size())
            two = i+2;
            while(one> 0 && two < node.size())
            {
                while(one > 0 && node[one] == '!')
                one--;
                if(node[one] == node[two] )
                {
                    node[one] = node[two] = '!';
                    one--;two++;
                }
                else
                break;
            }
        }
        else
        pre = i;

    }

   for(int i = 0;i < node.size();i++)
   {
       if(node[i] != '!')
       cout << node[i];
   }

}

Wrong answer    1 test

#include <iostream>
using namespace std;

int main()
{
    int n, i, x, max;
    int mas[1000];

    cin >> n;
    max = 0;
    for (i = 0; i < n; i++)
    {
        cin >> mas[i];
    }
    max = mas[0] + mas[1] + mas[2];
    x = 1;
    for (i = 1; i < n; i++)
    {
        if (mas[i] + mas[i + 1] + mas[i + 2] > max)
        {
            max = mas[i] + mas[i + 1] + mas[i + 2];
            x = i + 1;
        }
    }
    cout << max << ' ' << x + 1 << endl;
    system("pause");
    return (0);
}

#include <iostream>

using namespace std;

int main()
{
    int a[1000];
    int n=0,s,sx=0,m=0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int u=1;u<n-1;u++){
            s=a[u]+a[u+1]+a[u+2];
            if(s>sx){
                sx=s;
                m=u+1;
            }}
    if (n==3){
        sx=a[0]+a[1]+a[2];
        m=2;
    }
    cout << sx << " " << m << endl;
}