ONEZERO : faster algorithm

[darklord]

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 ,

[vinaye]

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.

[TripleM]

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..

[abcc]

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???

[uau]

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.

[chandan_google]

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

Is there a DP solution also possible.

[akshaykulkarni]

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;
}


[gooey_kablooie]

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.

[akshaykulkarni]

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)

[gooey_kablooie]

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.

[akshaykulkarni]

Yeh Thanks,
That helped me a lot.

[hasan]

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.

[scofield23]

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;
}



[leppy]

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

[scofield23]

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