ONEZERO : faster algorithm

Discussion on all problems hosted at SPOJ

ONEZERO : faster algorithm

Postby darklord » Sun Nov 12, 2006 22:07

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

Postby vinaye » Sat Mar 10, 2007 04:26

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

Postby TripleM » Sat Mar 10, 2007 05:45

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

:(

Postby abcc » Sat Jun 09, 2007 21:01

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

Postby uau » Sun Jun 10, 2007 01:19

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

Postby chandan_google » Thu Apr 30, 2009 05:36

@ 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
chandan_google
 
Posts: 11
Joined: Wed Sep 24, 2008 16:09
Location: INDIA

Re: ONEZERO : faster algorithm

Postby akshaykulkarni » Wed Jul 28, 2010 13:38

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

Postby gooey_kablooie » Wed Jul 28, 2010 15:51

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

Postby akshaykulkarni » Fri Jul 30, 2010 18:53

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

Postby gooey_kablooie » Mon Aug 02, 2010 07:16

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

Postby akshaykulkarni » Tue Aug 03, 2010 12:02

Yeh Thanks,
That helped me a lot.
akshaykulkarni
 
Posts: 11
Joined: Wed Nov 04, 2009 19:48

Re: ONEZERO : faster algorithm

Postby hasan » Fri Aug 06, 2010 09:17

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.
User avatar
hasan
 
Posts: 190
Joined: Sun Sep 13, 2009 11:45
Location: Dhaka, Bangladesh

Re: ONEZERO : faster algorithm

Postby scofield23 » Wed Jan 05, 2011 13:31

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

Postby leppy » Wed Jan 05, 2011 17:04

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: 6021
Joined: Fri Aug 01, 2008 18:06

Re: ONEZERO : faster algorithm

Postby scofield23 » Wed Jan 05, 2011 19:24

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

Return to ProblemSet Archive

Who is online

Users browsing this forum: Google [Bot] and 1 guest