Not getting it... how to start, where to learn... plz help...

sorry for the bad english…
yesterday i was at at the august cookoff… as i m a beginner i was first searching for the easier question… i found that “Chef and The Divisibility Queries” - http://www.codechef.com/COOK37/problems/DIVQUERY is a easy question… well this was the first time i was actively participating in the event…
so i get to ideone to compile my code then… it took a long but after around 40 mins i was there with my code… i thought this will be my first successful submission… i submitted my code but i was disappointed :frowning: beacude of “time limit exceeded” error… my code was correct… then afterwards when the contest was over i looked for the submissions of the other contestants…

my code was like this

#include<stdio.h>
#define x 100001

int main()
{
int n,a[x],q,c=0,i,l,k,r;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}

while(q--)
{
c=0;
scanf("%d%d%d",&l,&r,&k);
for(i=l;i<=r;i++)
{
if(a[i]%k==0)++c;
}
printf("\n%d",c);
}

return 0;
}   


in c language...

and the submission of ACrush was this…

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)

const int maxn=100100;

int n;
int a[maxn];
int m;
int s[maxn],t[maxn],q[maxn];
int prev[maxn];
vector<int> g[maxn];
bool visited[maxn];
int c;
int p[maxn],e[maxn];
int pos;

void generate(int d,int x)
{
	if (d==c) 
	{
		if (visited[x]) g[x].push_back(pos);
		return;
	}
	for (int i=0;i<=e[d];i++)
	{
		generate(d+1,x);
		x*=p[d];
	}
}
int solve(vector<int>& a,int key)
{
	if (key<=0) return 0;
	int h=-1,t=SIZE(a);
	for (;h+1<t;)
	{
		int m=h+(t-h)/2;
		if (a[m]>key) t=m;
		else h=m;
	}
	return t;
}
int main()
{
#ifdef _MSC_VER
	freopen("input.txt","r",stdin);
#endif
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++) scanf("%d",&a[i]);
	for (int i=0;i<m;i++) scanf("%d%d%d",&s[i],&t[i],&q[i]);
	memset(visited,false,sizeof(visited));
	for (int i=0;i<m;i++) visited[q[i]]=true;
	memset(prev,255,sizeof(prev));
	for (int i=2;i<maxn;i++) if (prev[i]<0)
		for (int j=i;j<maxn;j+=i)
			prev[j]=i;
	for (int i=0;i<n;i++)
	{
		int key=a[i];
		c=0;
		for (;key>1;c++)
		{
			p[c]=prev[key];
			e[c]=0;
			for (;key%p[c]==0;key/=p[c]) e[c]++;
		}
		pos=i+1;
		generate(0,1);
	}
	for (int i=0;i<m;i++)
		printf("%d\n",solve(g[q[i]],t[i])-solve(g[q[i]],s[i]-1));
	return 0;
}

now my question

as i am a beginner i have no idea that i have to go that much deep for a simple problem… how do they do it??

how to develop this much logical thinking ??

suggest me any book which focuses on the deep thinking… i already have “intro to algos by th cormen, rivest etc” - how much this book will help??

thank you in advance…

@jaksparo >> Yes the problem was simple, but to arrive at a solution working within Time Limit was not.
Your solution is known as a brute force solution, and the time limit was set in such a manner so that such solutions won’t pass. You needed some faster optimization(s).

You should read the editorial for the problem http://discuss.codechef.com/questions/21662/divquery-editorial , as far as this particular problem is concerned.

1 Like

thanks @bugkiller

Before writing the code you should compute the approximate maximum no of instructions your code will be executing depending on the complexity of your code. And then decide whether this complexity may pass in given time limit or you need a better solution. About 10^7 instructions can be executed in 1 sec on codechef.
But your code is O(n) for 10^5 test cases for n<=10^5.
=> it will execute 10^10 instructions in worst case.
=> 1000 seconds on codechef in worst case.
Have a look at this

2 Likes

@jaksparo Start, practicing first with easy problems in practice section of codechef and on other sites like codeforces. Along with it, learn algorithms either form books or online. Then, start competing. And, yes most of the problems are set in the manner than brute force approach won’t pass. You have to came with better approach with optimization.

And read tutorials after contest finishes, you surely learn new things.

PS: Don’t follow top coders solution they are too complex to understand even for intermediate programmers.

First you need some practice to get familiar with environment…

Once I write some list, where you can start :wink:

http://discuss.codechef.com/questions/3154/a-newbie-can-anyone-help-me?page=1#3158

thank you buddies :slight_smile:

yes…right…

//