CodeChef INTEST Problem
21 views
Skip to first unread message
Praveen Kumar
Jun 22, 2011, 1:37:57 PM6/22/11
to theco...@googlegroups.com
Those who have solved the INTEST problem, please post your solutions in this thread.
Krishna Chaitanya
Jun 22, 2011, 2:40:10 PM6/22/11
to theco...@googlegroups.com
Hi here is my code for the problem.
#include<iostream.h>
#include<conio.h>
void main()
{
int n,k,ti,x=1,m=0;
cout<<"Enter two integers"<<endl;
cin>>n>>k;
while(x<=n)
{
cin>>ti;
if(ti%k==0)
{
m=m++;
}
x++;
}
cout<<m<<endl;
}
Regards
On Wed, Jun 22, 2011 at 11:07 PM, Praveen Kumar <pravee...@gmail.com> wrote:
Those who have solved the INTEST problem, please post your solutions in this thread.
Krishna Chaitanya
Jun 22, 2011, 2:59:57 PM6/22/11
to theco...@googlegroups.com
Hi this is my solution to the INTEST problem using Dev-C++.
#include<iostream>
using namespace std;
int main()
{
int n,k,ti,x=1,m=0;
cin>>n>>k;
while(x<=n)
{
cin>>ti;
if(ti%k==0)
{
m=m++;
}
x++;
}
cout<<m<<endl;
system("pause");
return(0);
}
Regards.
On Wed, Jun 22, 2011 at 11:07 PM, Praveen Kumar <pravee...@gmail.com> wrote:
Those who have solved the INTEST problem, please post your solutions in this thread.
Sharat
Jun 22, 2011, 4:10:03 PM6/22/11
to theco...@googlegroups.com
m=m++ is same as m++ so from now on use the latter one.
Praveen Kumar
Jun 23, 2011, 2:00:00 PM6/23/11
to theco...@googlegroups.com
The problem is quite straightward i.e to keep taking the n integer inputs and counting those which are divisible by 'k'.
So, the first solution that comes in everyone's mind is as given below (for those who are from C++ background).
#include<iostream>
using namespace std;
int main()
{
int n, k, t;
cin>>n>>k;
int count=0;
for(int i=0; i<n; i++)
{
cin>>t;
if (t%k==0)
{ count++;}
}
cout<<count<<endl;
return 0;
}
And if you submit this solution to the CodeChef, it times out i.e the execution time of this program exceeds the given time
restriction of 8sec. The reason for this is that the basic I/O functions in C++ also called the stream objects become very
slow with the increase in input size. A stream is basically an object from which a program can extract data and also can insert
data. The default mechanism for a program to take input is through the keyboard and C++ defines the 'cin' stream to access
the data or the characters you type in the keyboard. We can understand this in the way that it is the responsibility of the 'cin' stream
object to handle the keyboard input and pass it to the program. Similarly, the monitor is the default output for a program and the
program accesses it using the 'cout' stream object.
In any contest problem like as those on CodeChef, SPOJ etc, you will be asked to read from the standard input and write to standard
output which turns out to be 'cout' and 'cin' in the case of C++. Coming back to the INTEST problem, if you see the size : n,k<10^7 and t<10^9.
The stream operations tend to be slow with such large size inputs and the solution times out.
Coming to the rescue are the C standard I/O operations which are very fast. It must be remembered that C++ is an extension
of C and you can do whatever you could in C in C++. You just have to include the appropriate library headers.
We can use the C standard I/O operations in C++ by including the cstdio library. The standard input function in C is scanf(). scanf reads
formatted data from the standard input. Formatted data implies that you specify the structure of the input. For example, if we want to read
two integers separated by space in one go, its format would be "%d %d" where %d stands for an integer. If we wish to read a string and an
integer separated by a space, the format would be "%s %d".
The basic syntax of using scanf() is as below:
int number;
scanf("%d", &number);
Observe that we pass the reference to the number variable as the second parameter. The integer taken as input from the standard input
will be stored in the 'number' variable. You can read more about scanf here http://www.cplusplus.com/reference/clibrary/cstdio/scanf/
So, our modified program becomes;
#include<iostream>
#include<cstdio> //library containing the standard C I/O functions
using namespace std;
int main()
{
int n, k, t;
scanf("%d %d",&n,&k);//take the input and store them in n and k
int count=0;//initialize the counter variable
while(n--)
{
scanf("%d",&t)
if (t%k==0)//check if t is divisible by k
{ ++count;}
}
cout<<count<<endl;
return 0;
}
This program runs in 5.4 seconds.
So, you should keep in mind that whenever you encounter a problem which requires heavy I/O or large number
of I/O operations, you must use scanf and printf available in cstdio.
Please report if anywhere I have gone wrong or if the above solution can be optimised more.
Praveen
So, the first solution that comes in everyone's mind is as given below (for those who are from C++ background).
#include<iostream>
using namespace std;
int main()
{
cin>>n>>k;
int count=0;
for(int i=0; i<n; i++)
{
cin>>t;
if (t%k==0)
{ count++;}
}
cout<<count<<endl;
return 0;
}
And if you submit this solution to the CodeChef, it times out i.e the execution time of this program exceeds the given time
restriction of 8sec. The reason for this is that the basic I/O functions in C++ also called the stream objects become very
slow with the increase in input size. A stream is basically an object from which a program can extract data and also can insert
data. The default mechanism for a program to take input is through the keyboard and C++ defines the 'cin' stream to access
the data or the characters you type in the keyboard. We can understand this in the way that it is the responsibility of the 'cin' stream
object to handle the keyboard input and pass it to the program. Similarly, the monitor is the default output for a program and the
program accesses it using the 'cout' stream object.
In any contest problem like as those on CodeChef, SPOJ etc, you will be asked to read from the standard input and write to standard
output which turns out to be 'cout' and 'cin' in the case of C++. Coming back to the INTEST problem, if you see the size : n,k<10^7 and t<10^9.
The stream operations tend to be slow with such large size inputs and the solution times out.
Coming to the rescue are the C standard I/O operations which are very fast. It must be remembered that C++ is an extension
of C and you can do whatever you could in C in C++. You just have to include the appropriate library headers.
We can use the C standard I/O operations in C++ by including the cstdio library. The standard input function in C is scanf(). scanf reads
formatted data from the standard input. Formatted data implies that you specify the structure of the input. For example, if we want to read
two integers separated by space in one go, its format would be "%d %d" where %d stands for an integer. If we wish to read a string and an
integer separated by a space, the format would be "%s %d".
The basic syntax of using scanf() is as below:
int number;
scanf("%d", &number);
Observe that we pass the reference to the number variable as the second parameter. The integer taken as input from the standard input
will be stored in the 'number' variable. You can read more about scanf here http://www.cplusplus.com/reference/clibrary/cstdio/scanf/
So, our modified program becomes;
#include<iostream>
#include<cstdio> //library containing the standard C I/O functions
using namespace std;
int main()
{
scanf("%d %d",&n,&k);//take the input and store them in n and k
int count=0;//initialize the counter variable
while(n--)
{
scanf("%d",&t)
if (t%k==0)//check if t is divisible by k
{ ++count;}
}
cout<<count<<endl;
return 0;
}
This program runs in 5.4 seconds.
So, you should keep in mind that whenever you encounter a problem which requires heavy I/O or large number
of I/O operations, you must use scanf and printf available in cstdio.
Please report if anywhere I have gone wrong or if the above solution can be optimised more.
Praveen
Sharat
Jun 23, 2011, 2:53:17 PM6/23/11
to theco...@googlegroups.com
Hi
Good work done by Praveen. I hope the beginners will not have any problem in future in regard to io related things.
Anyways, I want to add a comment in regard to optimizing this code. scanf and printf are quite fast, in fact they handle 2.5mb data per sec but recently I got to know of another technique. It is usually used when the size of input is beyond 10 million cases(or characters if input is a sequence of strings). It uses something called buffer, where the whole input is taken at once and then its processed and then it is fed to the program. As of now we don't need it because scanf and printf will do the job.
The following code is for the interested reader. This code runs in only 0.78 secs. This is the magic of buffers.
//--------------header files-------------
#include<cstdio> // needed for input output i.e., scanf and printf
#include<cassert>// cassert is needed for fast input output
//-------global variables declared----------
int n,k,t,count; // variables are declared globally so that they can be used anywhere in the whole code
// global variables are automatically set to zero when declared
//--------code for fast io starts here----------------
const int MAX_SIZE = 100000000; //dont play around with MAX_SIZE as this is very important parameter.
// choose it carefully as this is the size of char array that will be created for pre-processing. If it is less than //what is needed then some of your test cases will be lost. So don't be kanjus when you set this size.
static char input[MAX_SIZE];
struct Scanner {
Scanner() {
int sz = fread(input, 1, sizeof(input), stdin);
assert(sz < MAX_SIZE - 1);
input[sz] = 0;
input[sz + 1] = 0;
curPos = input;
}
char* nextString(int& length) {
while (*curPos && *curPos <= ' ')
curPos++;
if (!*curPos)
return 0;
char* s = curPos;
while (*curPos && *curPos > ' ')
curPos++;
length = curPos - s;
*curPos++ = 0;
return s;
}
int nextInt() {
while ((*curPos < '0' || *curPos > '9') && *curPos != '-')
curPos++;
bool minus = *curPos == '-';
if (*curPos == '-') curPos++;
int res = 0;
while (*curPos >= '0' && *curPos <= '9') {
res = res * 10 + (*curPos) - '0';
curPos++;
}
return minus ? -res : res;
}
char* curPos;
};
//--------fast io function ends here--------------
//------------- main program starts---------------
int main()
{
Scanner sc;// now sc has access to the the buffer
n=sc.nextInt();//the first value is fed to n
k=sc.nextInt();// second to k
while(n--)
{
t=sc.nextInt(); // rest to t's
if(t%k==0) count++; // count is incremented whenever we have a multiple
}
printf("%d\n",count); // this prints the value of count
return 0;
}
//----------code ends here--------------------------
Regards
Sharat
P.S.: Don't use this technique if scanf and printf can do the job
Good work done by Praveen. I hope the beginners will not have any problem in future in regard to io related things.
Anyways, I want to add a comment in regard to optimizing this code. scanf and printf are quite fast, in fact they handle 2.5mb data per sec but recently I got to know of another technique. It is usually used when the size of input is beyond 10 million cases(or characters if input is a sequence of strings). It uses something called buffer, where the whole input is taken at once and then its processed and then it is fed to the program. As of now we don't need it because scanf and printf will do the job.
The following code is for the interested reader. This code runs in only 0.78 secs. This is the magic of buffers.
//--------------header files-------------
#include<cstdio> // needed for input output i.e., scanf and printf
#include<cassert>// cassert is needed for fast input output
//-------global variables declared----------
int n,k,t,count; // variables are declared globally so that they can be used anywhere in the whole code
// global variables are automatically set to zero when declared
//--------code for fast io starts here----------------
const int MAX_SIZE = 100000000; //dont play around with MAX_SIZE as this is very important parameter.
// choose it carefully as this is the size of char array that will be created for pre-processing. If it is less than //what is needed then some of your test cases will be lost. So don't be kanjus when you set this size.
static char input[MAX_SIZE];
struct Scanner {
Scanner() {
int sz = fread(input, 1, sizeof(input), stdin);
assert(sz < MAX_SIZE - 1);
input[sz] = 0;
input[sz + 1] = 0;
curPos = input;
}
char* nextString(int& length) {
while (*curPos && *curPos <= ' ')
curPos++;
if (!*curPos)
return 0;
char* s = curPos;
while (*curPos && *curPos > ' ')
curPos++;
length = curPos - s;
*curPos++ = 0;
return s;
}
int nextInt() {
while ((*curPos < '0' || *curPos > '9') && *curPos != '-')
curPos++;
bool minus = *curPos == '-';
if (*curPos == '-') curPos++;
int res = 0;
while (*curPos >= '0' && *curPos <= '9') {
res = res * 10 + (*curPos) - '0';
curPos++;
}
return minus ? -res : res;
}
char* curPos;
};
//--------fast io function ends here--------------
//------------- main program starts---------------
int main()
{
Scanner sc;// now sc has access to the the buffer
n=sc.nextInt();//the first value is fed to n
k=sc.nextInt();// second to k
while(n--)
{
t=sc.nextInt(); // rest to t's
if(t%k==0) count++; // count is incremented whenever we have a multiple
}
printf("%d\n",count); // this prints the value of count
return 0;
}
//----------code ends here--------------------------
Regards
Sharat
P.S.: Don't use this technique if scanf and printf can do the job
Praveen Kumar
Jun 23, 2011, 3:08:49 PM6/23/11
to theco...@googlegroups.com
0.78 secs!! AWESOME. It would be better if you could explain it to me line by line and the concept behind the buffer technique.
Also, I think that buffering the whole input will increase the memory footprint badly.
Praveen
Also, I think that buffering the whole input will increase the memory footprint badly.
Praveen
Reply all
Reply to author
Forward
0 new messages