I'm using KMP I don't know why I get TLE?



#include <iostream>



int main(int argc, const char * argv[]) {

    long long int NumofChars;
    long long int finAns=-1;

    scanf("%lld",&NumofChars);

    char lettersS[2*NumofChars];
    char lettersT[NumofChars];
    char letter_tmp;





    for (long long int i=0;i<NumofChars;i++)
    {
        scanf(" %c",&letter_tmp);
        lettersT[i]=letter_tmp;
    }

    for (long long int i=0;i<NumofChars;i++)
    {
        scanf(" %c",&letter_tmp);
        lettersS[i]=letter_tmp;
        lettersS[i+NumofChars]=letter_tmp;
    }




    long long int prefix[NumofChars];
    prefix[0]=0;
    prefix[1]=0;

    long long int pi=0;
    long long int pj=1;

    while(pj<NumofChars-1)
    {
        if(lettersT[pi]==lettersT[pj])
        {
            prefix[pj+1]=prefix[pj]+1;

            pi++;
            pj++;

        }
        else
        {

            pi=0;
            if(lettersT[pi]==lettersT[pj])
            {
                prefix[pj+1]=1;

                pi++;
                pj++;


            }
            else
            {
                prefix[pj+1]=0;

                pj++;

            }

        }
    }







    finAns=-1;

    long long int i=0;
    while(i<NumofChars)
    {


        long long int Matchcount=0;
        long long int j_init=0;
        for (long long int j=j_init;j<NumofChars;j++)
        {
            if(lettersS[i+j]==lettersT[j])
            {
                Matchcount++;
            }
            else
            {
                if(j-prefix[j]>0)
                {
                    i=i+j-prefix[j];
                    j_init=prefix[j];

                }
                else
                {
                    i++;
                }

                break;
            }
        }


        if(Matchcount==NumofChars)
        {
            finAns=i;

            break;
        }
    }
    std::cout<<finAns;
    return 0;
}

Whoever thought of this problem haven't fried steaks in real life.

The only way to get an acceptable solution to 1820 is to cook the steaks somewhat similar to this order:
Minute 1: St1A, St2A
Minute 2: St1B, St3A
Minute 3: St2B, St3B
(where there are three steaks: St1, St2 and St3, and each having side A and side B).

The problem with this is:
After St2A side is cooked, it will be taken off the heat and cool down for one minute before cooking the other side, thus in the end the steak will be less cooked than stake 1 and 3. That's all sorts of wrong, you'll be ruining a good steak!

:-D

For those who get TLE #17 try to use scanf/printf instead of cin/cout

Explain me please, why if n=4, the answer is 204.
I get 2513.

Here is my code:
-----
[The code was here]
-----
I've got the point. Thank you.

Edited by author 17.07.2011 18:48

/*
    Machine: Class4_B2
    System: Windows7 SP1 32bit
*/
[code deleted]

Edited by moderator 19.11.2019 23:15

what's different between undefined and 3?
can you help me?

I use Tonelli-Shanks algo,but i got WA#2.By now I had read all te topic but hadn't found the error.Please give me some hints or cases.
the key code:

int inverse(int a, int m)//thr inverse element of a(modulo m);
int quickpower(int a, int n, int m)//a^n(modulo m);
void sqrt(int a, int p)
{
    if(p==2)
    {
        cout << 1 << endl;
        return;
    }
    if(quickpower(a,(p-1)/2,p)!=1)
    {
        cout << "No root" << endl;
        return;
    }
    int s, t = 0, b = 0, i, j, x, y, inv, N;
    for (s = p - 1; !(s & 1); s /= 2) t++;
    inv = inverse(a, p);
    x = quickpower(a, (s + 1) / 2, p);
    for (N = 2; quickpower(N, (p - 1) / 2, p) == 1; N++);
    for (i = t - 2; i >= 0; i--)
    {
        b = b ? b*b%p : quickpower(N, s, p);
        y = x*x%p*inv%p;
        for (j = 1; j <= i; j++) y = y*y%p;
        if (y != 1) (x *= b) /= p;
    }
    if (2 * x < p) cout << x << " " << p - x << endl;
    else cout << p - x << " " << x << endl;
    return;
}

Deleting this post... had to hack another solution. Still don't see what was wrong with the original approach... must have been some kind of parsing issue with the input.

Edited by author 08.02.2015 09:36

I am sure that my program is right, but i get WA on test 16.
Do somebody know this test or can say something interesting?

a "for"-loop in python for integers 1 <= i <= 10^18 needs a lot of time. Is there a way to avoid to do such a huge for-loop?


Edited by author 21.01.2015 20:28

hi everybody! i have wa 5 but i don't understand my mistake. can anybody who knows some tests help me?

#include <iostream>

int main()
{
 long int i, n, m, z, s, k, a[16000], l, r, mid;
 std::cin >> n;
 k=0;
 for (i=0; i<n; i++)
 {
  std::cin >> z;
  if ((i!=0) && (z!=a[k]))
  {
   a[k]=z; k++;
  }
  if (i==0)
  {
   a[k]=z; k++;
  }
 }
 n=k-1;
 std::cin >> m;
 s=0;
 k=0;
 for (i=0; i<m; i++)
 {
  l=0; r=n; k=0;
  std::cin >> z;
  if ((z>a[0]) && (z<a[n]))
   while ((l<r) && (k<n-1))
   {
    k=k+1;
    mid=(l+r)/2;
    if (a[mid]>z)
     r=mid;
     else if (a[mid]<z)
     l=mid;
     else if (a[mid]==z)
      break;
   }
  else if ((z==a[0]) || (z==a[n]))
   s++;
  if ((a[mid]==z) && (mid!=0))
   s++;
 }
 std::cout << s;
}

#include<iostream>

using namespace std;

int main()
{
    int k, n, S =0;
    cin >> k >> n;

    if (k, n >= 1 && k, n <= 100) {
        int  *A = (int*)malloc(n*sizeof(int));
        for (int i = 0; i < n; i++) {
            cin >> A[i];
            if (!(A[i] >= 0 && A[i] <= 100))
                break;
        }
        for (int i = 0; i < n; i++)
            S += A[i] - k;
        cout << S << endl;
    }
        return 0;
}

Edited by author 05.02.2015 20:02

Вот мой код. показывает Runtime на 4 тесте. не могу разобраться из-за чего.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication4
{
    class Program
    {
        static void Main()
        {
            bool sol;
            string s = Console.ReadLine();
            string[] sp = s.Split(' ');
            int n = int.Parse(sp[0]);
            int m = int.Parse(sp[1]);
            int q = n + 1;
            int q2 = n + 2;
            int p1, p2, p3;
            int[, ,] mas = new int[q2, q2, q2]; // основной массив для работы.
            for (int i = 0; i < m; ++i)   // заполнение массива с клавиатуры.
            {
                string a = Console.ReadLine();
                string[] b = a.Split(' ');
                int[,] c = new int[1, 3]; // интовый массив вводимой строки

                for (int j = 0; j < 3; ++j)
                {
                    c[0, j] = int.Parse(b[j]);
                    if (j == 2)           // когда массив с заполняется, вынимаем индексы и цены.
                    {
                        p1 = c[0, 0];
                        p2 = c[0, 1];
                        p3 = c[0, 2];
                        mas[p2, p1, 0] = p3; // заполняем 0-ой слой основного массива ценами.
                    }
                }
            }
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= n; ++j)
                {
                    sol = true;

                    for (int k = 1; k <= n; ++k)
                    {
                        if (mas[k, i, 0] == 0 & mas[k, j, 0] == 0)
                        {
                            mas[j, i, q] = 0;
                            sol = false;
                        }
                        else
                        {
                            if (mas[k, i, 0] <= mas[k, j, 0] & mas[k, i, 0] != 0)
                            {
                                mas[j, i, k] = mas[k, i, 0];
                            }
                            else
                            {
                                mas[j, i, k] = mas[k, j, 0];
                            }
                            if (mas[j, i, q] < mas[j, i, k])
                            {
                                if (sol) { mas[j, i, q] = mas[j, i, k]; }
                            }
                        }
                    }
                    if (mas[0, 0, 0] == 0)
                    {
                        mas[0, 0, 0] = mas[j, i, q];
                    }
                    else
                    {
                        if (mas[j, i, q] > 0)
                        {
                            if (mas[0, 0, 0] >= mas[j, i, q])
                            {
                                mas[0, 0, 0] = mas[j, i, q];
                            }
                        }
                    }
                }
            }



            if (mas[0, 0, 0] < 1)
            {
                Console.WriteLine("No solution");
            }
            else
            {
                Console.WriteLine(mas[0, 0, 0]);
            }
            Console.ReadKey();
        }
    }
}

any hints???

Если изменить правило 2(если n делится на k) и вместо k умножить на 1, то все заработает.

Определение 1. n!!…! = n(n−k)(n−2k)…(n mod k), если n не делится на k; n!!…! = n(n−k)(n−2k)…1, если n делится на k (знаков ! в обоих случаях k штук).

Если что-то не получается, пишите вк: https://vk.com/evgeniy_baskov.
Разберемся:)

who knows what the meaning of set of numbers is???
is it true that the user must specify how many numbers must be taken?

Edited by author 03.02.2015 23:09