Discussion @ 1013. K-based Numbers. Version 3 @ Timus Online Judge

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; Andrew Hoffmann aka SKYDOS [Vladimir SU] 15 Aug 2010 20:19

maybe your long arithmetics works too slow.
what base are you using when performing adding/multiplying? what about algo?

Edited by author 15.08.2010 20:20

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; Info 16 Aug 2010 12:46

Edited by author 16.08.2010 12:46

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; T_be_GP 16 Aug 2010 12:47

// 1012.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <deque>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int SZ = 1000;

class verylong
{
private:
deque<char>vlstr;
int vlen;
verylong multdigit(const int) const;
verylong mult10(const verylong) const;
public:
verylong() : vlen(0)
{ vlstr[0]='\0'; }
verylong(const char s[SZ])
{ strcpy(vlstr, s); vlen=strlen(s); }
verylong(const unsigned long n)
{
sprintf(vlstr, "%lu", n);
_strrev(vlstr);
vlen=strlen(vlstr);
}
void putvl() const;
void getvl();
verylong operator + (const verylong);
verylong operator * (const verylong);
verylong operator - (const verylong);
};
//--------------------------------------------------------------

void verylong::putvl() const
{
char temp[SZ];
strcpy(temp,vlstr);
cout << _strrev(temp);
}
//--------------------------------------------------------------
void verylong::getvl()
{
cin >> vlstr;
vlen = strlen(vlstr);
_strrev(vlstr);
}
//--------------------------------------------------------------
verylong verylong::operator + (const verylong v)
{
char temp[SZ];
int j;

int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int carry = 0;
for(j = 0; j<maxlen; j++)
{
int d1 = (j > vlen-1)   ? 0 : vlstr[j]-'0';
int d2 = (j > v.vlen-1) ? 0 : v.vlstr[j]-'0';
int digitsum = d1 + d2 + carry;
if( digitsum >= 10 )
{ digitsum -= 10; carry=1; }
else
carry = 0;
temp[j] = digitsum+'0';
}
if(carry==1)
temp[j++] = '1';
temp[j] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator - (const verylong v)
{
char temp[SZ];
    int j, p=0, r=0;

    int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
    p = maxlen - 1;
    int carry = 0;

    for(j=0; j<maxlen; j++)
    {
        int d1 = (j > vlen-1) ? 0 : vlstr[j] - '0';
        int d2 = (j > v.vlen - 1) ? 0 : v.vlstr[j] - '0';
        int digitdif = d1 - d2 - carry;
        if(digitdif < 0)
        { digitdif += 10; carry = 1; }
        else carry = 0;
        temp[j] = digitdif + '0';
    }
    temp[j] = '\0';

    return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator * (const verylong v)
{
verylong pprod;
verylong tempsum;
for(int j=0; j<v.vlen; j++)
{
int digit = v.vlstr[j]-'0';
pprod = multdigit(digit);
for(int k=0; k<j; k++)
pprod = mult10(pprod);
tempsum = tempsum + pprod;
}
return tempsum;
}
//--------------------------------------------------------------
verylong verylong::mult10(const verylong v) const
{
char temp[SZ];
for(int j=v.vlen-1; j>=0; j--)
temp[j+1] = v.vlstr[j];
temp[0] = '0';
temp[v.vlen+1] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::multdigit(const int d2) const
{
char temp[SZ];
int j, carry = 0;
for(j = 0; j<vlen; j++)
{
int d1 = vlstr[j]-'0';
int digitprod = d1 * d2;
digitprod += carry;
if( digitprod >= 10 )
{
carry = digitprod/10;
digitprod -= carry*10;
}
else
carry = 0;
temp[j] = digitprod+'0';
}
if(carry != 0)
temp[j++] = carry+'0';
temp[j] = '\0';
return verylong(temp);
}

int main()
{
    verylong a[180], s[180];
    unsigned long n, i, k;
    scanf("%d", &n);
    scanf("%d", &k);

    a[0] = (n-n);
    s[0] = (k-1);

    for(i=1; i<n; i++)
    {
        s[i] = (verylong)k * s[i-1];
        s[i] = s[i] - a[i-1];
        a[i] = s[i-1] - a[i-1];
    }

    s[n-1].putvl();
    return 0;
}

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; T_be_GP 17 Aug 2010 22:00

waiting....

T_be_GP wrote 16 August 2010 12:47

// 1012.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <deque>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
const int SZ = 1000;

class verylong
{
private:
deque<char>vlstr;
int vlen;
verylong multdigit(const int) const;
verylong mult10(const verylong) const;
public:
verylong() : vlen(0)
{ vlstr[0]='\0'; }
verylong(const char s[SZ])
{ strcpy(vlstr, s); vlen=strlen(s); }
verylong(const unsigned long n)
{
sprintf(vlstr, "%lu", n);
_strrev(vlstr);
vlen=strlen(vlstr);
}
void putvl() const;
void getvl();
verylong operator + (const verylong);
verylong operator * (const verylong);
verylong operator - (const verylong);
};
//--------------------------------------------------------------

void verylong::putvl() const
{
char temp[SZ];
strcpy(temp,vlstr);
cout << _strrev(temp);
}
//--------------------------------------------------------------
void verylong::getvl()
{
cin >> vlstr;
vlen = strlen(vlstr);
_strrev(vlstr);
}
//--------------------------------------------------------------
verylong verylong::operator + (const verylong v)
{
char temp[SZ];
int j;

int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
int carry = 0;
for(j = 0; j<maxlen; j++)
{
int d1 = (j > vlen-1)   ? 0 : vlstr[j]-'0';
int d2 = (j > v.vlen-1) ? 0 : v.vlstr[j]-'0';
int digitsum = d1 + d2 + carry;
if( digitsum >= 10 )
{ digitsum -= 10; carry=1; }
else
carry = 0;
temp[j] = digitsum+'0';
}
if(carry==1)
temp[j++] = '1';
temp[j] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator - (const verylong v)
{
char temp[SZ];
    int j, p=0, r=0;

    int maxlen = (vlen > v.vlen) ? vlen : v.vlen;
    p = maxlen - 1;
    int carry = 0;

    for(j=0; j<maxlen; j++)
    {
        int d1 = (j > vlen-1) ? 0 : vlstr[j] - '0';
        int d2 = (j > v.vlen - 1) ? 0 : v.vlstr[j] - '0';
        int digitdif = d1 - d2 - carry;
        if(digitdif < 0)
        { digitdif += 10; carry = 1; }
        else carry = 0;
        temp[j] = digitdif + '0';
    }
    temp[j] = '\0';

    return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::operator * (const verylong v)
{
verylong pprod;
verylong tempsum;
for(int j=0; j<v.vlen; j++)
{
int digit = v.vlstr[j]-'0';
pprod = multdigit(digit);
for(int k=0; k<j; k++)
pprod = mult10(pprod);
tempsum = tempsum + pprod;
}
return tempsum;
}
//--------------------------------------------------------------
verylong verylong::mult10(const verylong v) const
{
char temp[SZ];
for(int j=v.vlen-1; j>=0; j--)
temp[j+1] = v.vlstr[j];
temp[0] = '0';
temp[v.vlen+1] = '\0';
return verylong(temp);
}
//--------------------------------------------------------------
verylong verylong::multdigit(const int d2) const
{
char temp[SZ];
int j, carry = 0;
for(j = 0; j<vlen; j++)
{
int d1 = vlstr[j]-'0';
int digitprod = d1 * d2;
digitprod += carry;
if( digitprod >= 10 )
{
carry = digitprod/10;
digitprod -= carry*10;
}
else
carry = 0;
temp[j] = digitprod+'0';
}
if(carry != 0)
temp[j++] = carry+'0';
temp[j] = '\0';
return verylong(temp);
}

int main()
{
    verylong a[180], s[180];
    unsigned long n, i, k;
    scanf("%d", &n);
    scanf("%d", &k);

    a[0] = (n-n);
    s[0] = (k-1);

    for(i=1; i<n; i++)
    {
        s[i] = (verylong)k * s[i-1];
        s[i] = s[i] - a[i-1];
        a[i] = s[i-1] - a[i-1];
    }

    s[n-1].putvl();
    return 0;
}

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; AYUBXON UBAYDULLAYEV (TUIT of IT) 11 Jan 2012 18:34

Here is my simple program
//////////
#include<iostream>
using namespace std;
int main()
{
int a[2000]={0},b[2000]={0},c[2000]={0};
int g,n,k,i,j,m=1,t=2000;
cin>>n>>k;
a[t-1]=1; b[t-1]=k-1;
for(i=2;i<=n;i++)
{
    g=0;
    for(j=t-1;j>=t-m;j--)
    {
     c[j]=a[j]+b[j];
     c[j]=c[j]*(k-1)+g;
     if (c[j]>9) {g=c[j]/10; c[j]=c[j]%10; }else g=0;
     a[j]=b[j]; b[j]=c[j];
    }
    if (g!=0)
    {
        m++;
        b[t-m]=g; c[t-m]=g;
    }
}
for(j=t-m;j<t;j++) cout<<c[j];
}

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; Mher Asatryan (YSU) 22 Feb 2013 07:40

it's amazing ... bravo!

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; tiancaihb 19 Aug 2010 13:17

Hi, I think the major problem is operator *. You seem to use vlen of verylong objects store the intermediate value. That's not a good idea, as 10-based long algorithm already has the risk of TLE, let alone that staff. Try not to use multy10 but to store intermediate value in a char array instead. I can send you my code (in C). btw, VC2010 compiler says it doesn't allow using deque as an argument of strxxx. How did you pass compilation with this code?

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; tiancaihb 19 Aug 2010 13:23

You don't necessarily use *. + is enough. And quicker.
I've tested. It works in this way very fast. Remember to enlarge array.

Edited by author 19.08.2010 13:36

Edited by author 19.08.2010 13:46

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; T_be_GP 19 Aug 2010 14:08

My int main algo is right or not?

I wrote it in VC 2010.
You must wipe out #include "stdafx.h"
and main function must be int main()

Edited by author 19.08.2010 14:10

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; T_be_GP 19 Aug 2010 14:16

my mail:

johnterryr@mail.ru

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; tiancaihb 19 Aug 2010 14:52

I think algo all right. But it won't compile if using deque. After changing it into char[5000] it works, producing the same answer for 1800,10 as mine. However, for input 10,2 the output is 089, I don't know why. I'll send you my program later this evening.

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; T_be_GP 19 Aug 2010 15:56

yes i wanted change answers like that into 89 , But i sent it and AC.And i didn't take care of it after AC,

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; tiancaihb 19 Aug 2010 16:11

Sent. See email for detail.

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; T_be_GP 19 Aug 2010 16:14

thanks

Re: I have done 1009 and 1012. BUt in 1013 my progs are very slow for input n = 1800, k = 10; Marius Žilėnas 24 Oct 2013 17:10

Do not make recursive calls, instead use a register of 3 values, f(N-1), f(N-2) and the one you are calculating: f(N). Then calculate all values from i=2 to N and use register. This reduces memory requirements :), makes the code for this problem faster.

Discussion of Problem 1013. K-based Numbers. Version 3