## ONEZERO : faster algorithm

Discussion on all problems hosted at SPOJ

### ONEZERO : faster algorithm

I got ONEZERO accepted but with very poor timelimit = 7s

many top coders have solved it in <1s , so it seems they probably use faster algo rather
than just faster I/O.

the algorithm which I used is quite crude
find remainders of 10^n using modular exponentiation
and just check all sums of remainders , we get solution when sum is divisble by n .

does anybody know a better algo for this problem.

Thanx ,
darklord

Posts: 4
Joined: Thu Nov 09, 2006 19:06

yeah, seems like i used an almost similar algorithm. I could get it run in 5.37 sec, using 21MB memory.I am curious about the algorithm they used.
You may wonder what happens to earth when everyone could compete!
vinaye

Posts: 154
Joined: Fri Jul 28, 2006 21:26
Location: India

I guess it depends on what you mean by 'check all sums of remainders'. I used the same outline as you mentioned, and solved it in 0.92s.
I just used a BFS..
TripleM
Global Moderator

Posts: 1142
Joined: Tue Nov 29, 2005 01:40

### :(

My algo is the same and i tried to do a bfs for every node (10,100,1000...) and the program times out. I tried dfs with the same result..
I couldn't think of a way to optimise the bfs. Any hint on how to optimise it?
I just used a BFS..

Does that mean just one BFS for one node alone???
abcc

Posts: 14
Joined: Sun Apr 22, 2007 15:37

The simplest way is to keep the set of all possible remainders of n-digit numbers, then add to that x+10^n for each existing element x to get the set for n+1 and so on until you get a zero. If you implement that efficiently you can get a time of about 0.2 seconds. To get 0.01 seconds (or 0.00, if that actually is possible) you need to make it a little bit smarter.
uau

Posts: 25
Joined: Mon Oct 03, 2005 18:20

### Re: ONEZERO : faster algorithm

@ tripleM
can u explain how to model this problem on a graph i cant figure it out.

Is there a DP solution also possible.
challenge the limits

Posts: 11
Joined: Wed Sep 24, 2008 16:09
Location: INDIA

### Re: ONEZERO : faster algorithm

Hi friends,
I am getting TLE in this problem when I use strings to store the answer. But when I used long long int to store answer Judge gives wrong answer as expected.
I am not getting how to optimise my prog to AC. Please help me or give me some hints so that i can solve my problem.
Code: Select all
`#include<queue>#include<iostream>#include<stdio.h>#include<vector>#include<algorithm>#include<string.h>using namespace std;typedef struct{   int mod;   unsigned long long ans;}node;const unsigned long long a=1;const unsigned long long b=10;void bfs(int n){   int dp[20100];   memset(dp,0,sizeof(dp));   queue<node> q;   node t1,t2,t3;   t1.ans=a;   t1.mod=1%n;   q.push(t1);   dp[t1.mod]=1;   while(!q.empty())   {      t2=q.front();      q.pop();      if(t2.mod==0)      {         printf("%llu\n",t2.ans);         break;      }      t3.mod=((b*t2.mod)%n);      if(dp[t3.mod]==0)      {         dp[t3.mod]=1;         t3.ans=(t2.ans*b);         q.push(t3);      }      t3.mod=((b*t2.mod+a)%n);      if(dp[t3.mod]==0)      {         dp[t3.mod]=1;         t3.ans=(t2.ans*b+a);         q.push(t3);      }   }}int main(){   int tc;   scanf("%d",&tc);   int n;   while(tc--)   {      scanf("%d",&n);      bfs(n);   }   return 0;}`
akshaykulkarni

Posts: 11
Joined: Wed Nov 04, 2009 19:48

### Re: ONEZERO : faster algorithm

You can do it without storing the answer as strings. Just store the lengths, remainder and parents. As the string is composed entirely of 0s and 1s you can print a 1 then fill the difference in lengths between current node and its parent with zeros. You have to construct the remainder network properly. If you check the previous post by uau you can understand the idea I am coming up with.
gooey_kablooie

Posts: 229
Joined: Wed Feb 25, 2009 12:54

### Re: ONEZERO : faster algorithm

First of all thanks for the reply.
Sorry but I couldn't understand what you said in this post and the above by uau.
Please, Can you be more explantive.(by a example)
akshaykulkarni

Posts: 11
Joined: Wed Nov 04, 2009 19:48

### Re: ONEZERO : faster algorithm

What uau means by his post is that keep a set of all numbers having ones and zeros only such that for a given n all the numbers of the set leave different remainders when divided by n. Now if your set contains 0, 1, 10, 11 the next numbers can be obtained by adding 100 to all the numbers in the set. So the next numbers can be 100, 101, 110, 111. You have to keep repeating till you obtain the number whose remainder is 0. I hope now my earlier post will be easier to understand.
gooey_kablooie

Posts: 229
Joined: Wed Feb 25, 2009 12:54

### Re: ONEZERO : faster algorithm

Yeh Thanks,
That helped me a lot.
akshaykulkarni

Posts: 11
Joined: Wed Nov 04, 2009 19:48

### Re: ONEZERO : faster algorithm

akshaykulkarni wrote:Yeh Thanks,
That helped me a lot.

Instead of the actual numbers, you can just store the mod values, (from these values, states can be easily deduced). So, you have only 0 to n-1 different states.

hasan

Posts: 190
Joined: Sun Sep 13, 2009 11:45

### Re: ONEZERO : faster algorithm

Still getting TLE.. please suggest a Optimization Technique ..

Code: Select all
`#include<iostream>#include<queue>#include<string.h>using namespace std;struct node{       int rem;       string n;};void BFS(int n){    queue <node> q;        bool visited[201000];        memset(visited,false,sizeof(visited));    node temp1,temp2,temp3;    temp1.n="1";    temp1.rem=1%n;    visited[temp1.rem]=1;    q.push(temp1);    while(!q.empty()){                      temp2=q.front();                      q.pop();                      if(temp2.rem==0){                                       cout<<temp2.n<<endl;                                       return ;                      }                      temp3.rem=(temp2.rem*10)%n;                      if(!visited[temp3.rem]){                                              visited[temp3.rem]=1;                                              temp3.n=temp2.n+"0"; // case 1                                              q.push(temp3);                      }                                            temp3.rem=(temp2.rem*10+1)%n; // case 2                      if(!visited[temp3.rem]){                                                visited[temp3.rem]=1;                                              temp3.n=temp2.n+"1";                                              q.push(temp3);                      }    }}                                              int main(){    int n,t;    scanf("%d",&t);    while(t--){               scanf("%d",&n);               BFS(n);    }    return 0;}`
Last edited by scofield23 on Wed Jan 05, 2011 19:22, edited 1 time in total.
scofield23

Posts: 15
Joined: Thu Oct 28, 2010 01:01

### Re: ONEZERO : faster algorithm

I suggest you read the other posts in this topic. Based on your code you haven't read any of them.
leppy
Global Moderator

Posts: 6731
Joined: Fri Aug 01, 2008 18:06

### Re: ONEZERO : faster algorithm

sir ,
could you be more specific in determining the problem. Still unable to get..
scofield23

Posts: 15
Joined: Thu Oct 28, 2010 01:01

Next