12081 - Reduced ID Numbers
Moderator: Board moderators
NWERC Problem F
Problem F: Reduced ID Numbers
T. Chur teaches various groups of students at university U. Every U-student has a unique Student Identification Number (SIN). A SIN s is an integer in the range 0 ≤ s ≤ MaxSIN with MaxSIN = 106 − 1. T. Chur finds this range of SINs too large for identification within her groups. For each group, she wants to find the smallest positive integer m, such that within the group all SINs reduced modulo m are unique.
Input
On the first line of the input is a single positive integer N, telling the number of test cases (groups) to follow. Each case starts with one line containing the integer G (1 ≤ G ≤ 300): the number of students in the group. The following G lines each contain one SIN. The SINs
within a group are distinct, though not necessarily sorted.
Output
For each test case, output one line containing the smallest modulus m, such that all SINs
reduced modulo m are distinct.
Sample input
2
1
124866
3
124866
111111
987651
Sample output
1
8
----------------------------------------------------------------
This is NWERC's problem F. If you try to solve it by generating values for m starting with the number of students and checking you don't get repeated values for the reduced SINs you will get "Time Limit Exceded".
How can you solve this problem in a quicker way?
Thanks!
T. Chur teaches various groups of students at university U. Every U-student has a unique Student Identification Number (SIN). A SIN s is an integer in the range 0 ≤ s ≤ MaxSIN with MaxSIN = 106 − 1. T. Chur finds this range of SINs too large for identification within her groups. For each group, she wants to find the smallest positive integer m, such that within the group all SINs reduced modulo m are unique.
Input
On the first line of the input is a single positive integer N, telling the number of test cases (groups) to follow. Each case starts with one line containing the integer G (1 ≤ G ≤ 300): the number of students in the group. The following G lines each contain one SIN. The SINs
within a group are distinct, though not necessarily sorted.
Output
For each test case, output one line containing the smallest modulus m, such that all SINs
reduced modulo m are distinct.
Sample input
2
1
124866
3
124866
111111
987651
Sample output
1
8
----------------------------------------------------------------
This is NWERC's problem F. If you try to solve it by generating values for m starting with the number of students and checking you don't get repeated values for the reduced SINs you will get "Time Limit Exceded".
How can you solve this problem in a quicker way?
Thanks!
Re: NWERC Problem F
No, you will not.AnGeLoSo wrote:This is NWERC's problem F. If you try to solve it by generating values for m starting with the number of students and checking you don't get repeated values for the reduced SINs you will get "Time Limit Exceded".

Note that you need to check for repeated values in O(N), or at least O(N log N). O(N^2) will be too slow.
Yeah, I think you are right. I kept the repeated "reduced SINs" in a boolean array and had to put it all to false each time I tried a new modulo.
I'm trying this on http://acmicpc-live-archive.uva.es/nuevoportal/ but it takes more than 10 seconds!!
I can't think a way of doing it quicker!!
I'm trying this on http://acmicpc-live-archive.uva.es/nuevoportal/ but it takes more than 10 seconds!!
Code: Select all
#include <iostream>
using namespace std;
int main()
{
int num_casos;
int num_estudiantes;
int SIN[320];
int SIN_reducido;
int resultado[305];
int estudiante;
int modulo;
int caso;
int condicion = 1;
cin >> num_casos;
for (int caso=0; caso<num_casos; caso++)
{
cin >> num_estudiantes;
for (estudiante = 0; estudiante < num_estudiantes; estudiante++)
cin >> SIN[estudiante];
for (modulo = num_estudiantes; 1; modulo++)
{
for (estudiante = 0; estudiante < num_estudiantes; estudiante++)
{
SIN_reducido = SIN[estudiante] % modulo;
if (resultado[SIN_reducido] == condicion) break;
else resultado[SIN_reducido] = condicion;
}
condicion++;
if (estudiante >= num_estudiantes) break;
}
cout << modulo << endl;
}
return 1;
}
Hmm... my algorithm is different from yours. My idea is: given two ID's A and B, where A <> B. For what m would we have the relation A = B (mod m)? Clearly A <> B (mod m) for all m > |A-B|. But what about for m < |A-B|?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
You have an array size issue. The answer can be a lot bigger than 305.AnGeLoSo wrote:I'm trying this on http://acmicpc-live-archive.uva.es/nuevoportal/ but it takes more than 10 seconds!!
Hello.
I solved this problem in some other way.
If A%m must be unique for all i<=n then |a-a[j]|%m<>0 for all i,j<=n; i<>j!
From this I get n*(n-1)/2 numbers and find all their divisors,and then find first number what isn't divisor of any of this numbers.
This got AC, but isn't fast!
Eduard.
I solved this problem in some other way.
If A%m must be unique for all i<=n then |a-a[j]|%m<>0 for all i,j<=n; i<>j!
From this I get n*(n-1)/2 numbers and find all their divisors,and then find first number what isn't divisor of any of this numbers.
This got AC, but isn't fast!
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
Hi!
I've just got accepted with this code:
It took a bit more than 9 seconds, so I'm not happy because there are submission that took 0.5 seconds!! Anybody can post a 0.5 seconds algorithm and explain it??
Thanks!
PS: Eduard, i don't know why u got accepted solving the problem using that algorithm! Perhaps I'm wrong, but I think mine is quicker (you know, generating n*(n-1)/2 numbers, then finding their divisors and cheking what number doesn't divide any id...) and I got T.L.! Anyway, thanks a lot for your answer!:)
I've just got accepted with this code:
Code: Select all
#include <iostream>
#include <set>
using namespace std;
int main()
{
int num_casos;
int num_estudiantes;
int SIN[320];
int SIN_reducido;
set<int> resultado;
int estudiante;
int modulo;
int caso;
int tamanio;
cin >> num_casos;
for (int caso=0; caso<num_casos; caso++)
{
cin >> num_estudiantes;
for (estudiante = 0; estudiante < num_estudiantes; estudiante++)
cin >> SIN[estudiante];
for (modulo = num_estudiantes; 1; modulo++)
{
resultado.clear();
for (estudiante = 0; estudiante < num_estudiantes; estudiante++)
{
tamanio = resultado.size();
SIN_reducido = SIN[estudiante] % modulo;
resultado.insert(SIN_reducido);
if (tamanio == resultado.size()) break;
}
if (estudiante >= num_estudiantes) break;
}
cout << modulo << endl;
}
return 1;
}
It took a bit more than 9 seconds, so I'm not happy because there are submission that took 0.5 seconds!! Anybody can post a 0.5 seconds algorithm and explain it??
Thanks!
PS: Eduard, i don't know why u got accepted solving the problem using that algorithm! Perhaps I'm wrong, but I think mine is quicker (you know, generating n*(n-1)/2 numbers, then finding their divisors and cheking what number doesn't divide any id...) and I got T.L.! Anyway, thanks a lot for your answer!:)
I have 0.354 sec. A very straightforward solution, with just one little trick:
Instead of a boolean array to mark which numbers were generated, I use an array
of integers (initially filled with zeroes) and a counter. Instead of cleaning
the array every time I test another modulus, I just increment the counter. To test
whether a number was generated I compare the array's element with the counter.
Instead of a boolean array to mark which numbers were generated, I use an array
of integers (initially filled with zeroes) and a counter. Instead of cleaning
the array every time I test another modulus, I just increment the counter. To test
whether a number was generated I compare the array's element with the counter.
It's not so slow because for finding all divisors I'm makingAnGeLoSo wrote: PS: Eduard, i don't know why u got accepted solving the problem using that algorithm! Perhaps I'm wrong, but I think mine is quicker (you know, generating n*(n-1)/2 numbers, then finding their divisors and cheking what number doesn't divide any id...) and I got T.L.! Anyway, thanks a lot for your answer!:)
Sum(sqrt(|a-a[j]|)) for all i,j<=n i<>j
operations.Put all divisors in an array of size 10^6.(ex. if 20 is divisor then a[20]=1 else a[20]=0).Then just make 10^6 operations to find the first a=0!It works 1.5sc(Pascal).
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
Done!
Hi!
The idea I was using was the correct one (instead of a boolean array to mark which numbers were generated, using an array of integers and a counter). The problem I had was the array size as Per said before, and the variable "caso", which was defined twice.
This is the correct code:
Thanks to everybody!!
The idea I was using was the correct one (instead of a boolean array to mark which numbers were generated, using an array of integers and a counter). The problem I had was the array size as Per said before, and the variable "caso", which was defined twice.
This is the correct code:
Code: Select all
#include <iostream>
using namespace std;
int main()
{
int num_casos;
int num_estudiantes;
int SIN[320];
int SIN_reducido;
int resultado[1000000];
int estudiante;
int modulo;
int caso;
int condicion = 1;
cin >> num_casos;
for (caso=0; caso<num_casos; caso++)
{
cin >> num_estudiantes;
for (estudiante = 0; estudiante < num_estudiantes; estudiante++)
cin >> SIN[estudiante];
for (modulo = num_estudiantes; 1; modulo++)
{
for (estudiante = 0; estudiante < num_estudiantes; estudiante++)
{
SIN_reducido = SIN[estudiante] % modulo;
if (resultado[SIN_reducido] == condicion) break;
else resultado[SIN_reducido] = condicion;
}
condicion++;
if (estudiante >= num_estudiantes) break;
}
cout << modulo << endl;
}
return 1;
}
Thanks to everybody!!
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
memset
Hi, i have 2 questions about memset.
Here runtime is O(l*m*n); but if i use
what would be the runtime? still O(l*m*n) or simply O(1)?
If i have a structure as below:
How to set all 100 elements of p to {10, 'a', 3.33} using memset?
thanks in advance...
Code: Select all
bool a[100][100][100];
for(i = 0; i < l; ++i)
for(j = 0; j < m; ++j)
for(k = 0; k < n; ++k)
a[i][j][k] = true;
Code: Select all
memset(a, true, 100*100*100*sizeof(bool));
If i have a structure as below:
Code: Select all
struct data
{
int n;
char c;
double f;
} p[100];
thanks in advance...
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
My advise would be: never use memset() on anything but strings. Better still: never use it at all. Like gets() it is a dangerous function that tempers directly with memory without the necessary checks.
It can lead to surprising results to the newbie (and the not so attentive leet) programmer. Try:and be surprised. It converts the second argument, an int, to a byte and fills memory with it. The outcome is implementation dependent.
The iterative way to initialise an array is (almost) as fast as memset if you realy want to initialise the whole array. But in most cases (like in programming problems) you only have to initialise a part of the array for each input case, and then the iterative method will be much faster.
To initialise an array of structures, you can use a const of the struct type you use. In your case:
It can lead to surprising results to the newbie (and the not so attentive leet) programmer. Try:
Code: Select all
#include <stdio.h>
#include <string.h>
int main(){
int i;
int a[10];
memset(a,1234567,10*sizeof(int));
for(i=0;i<10;i++) printf("%d\n",a[i]);
return 0;
}
The iterative way to initialise an array is (almost) as fast as memset if you realy want to initialise the whole array. But in most cases (like in programming problems) you only have to initialise a part of the array for each input case, and then the iterative method will be much faster.
To initialise an array of structures, you can use a const of the struct type you use. In your case:
Code: Select all
#include <stdio.h>
struct data{
int n;
char c;
double f;
} p[100];
struct data const INITDATA={10,'a',3.33};
int main(){
int i;
for(i=0;i<100;i++) p[i]=INITDATA;
/* to see that it works: */
for(i=0;i<100;i++) printf("%d %c %lf\n",p[i].n,p[i].c,p[i].f);
return 0;
}
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
Hi little joey, thank you very much for your advice. i didn't know about the surprising result of memset. But i tried some input-output and found something about memset. memset works perfectly for string and bool. and for int or double it can initialize the array with 0. code like:
works perfectly within O(1) time(of course faster than initialize by loop).here i can mention that, in the last online contest there was a problem named "reduced ID number":
http://online-judge.uva.es/contest/data ... et/p5.html
i submitted the code below:
and got TLE(not within 3 seconds), but i changed the two lines with memset, i got accepted within 0.6sec(or something nearby).
sorry for my long story...
Ishtiak Zaman
Code: Select all
int a[1000];
memset(a, 0, 1000*sizeof(int));
http://online-judge.uva.es/contest/data ... et/p5.html
i submitted the code below:
Code: Select all
#include <stdio.h>
#include <string.h>
bool num[1000009];
void main()
{
int test, tc, i, n, m, a, x[309], flag;
scanf("%d", &test);
for(tc = 0; tc < test; ++tc)
{
scanf("%d", &n);
for(i = 0; i < n; ++i)
scanf("%d", &x[i]);
for(m = n; ; ++m)
{
for(i = 0; i < m; ++i) // this two lines
num[i] = false; //
flag = 0;
for(i = 0; i < n; ++i)
{
a = x[i] % m;
if(num[a])
{
flag = 1;
break;
}
num[a] = true;
}
if(flag == 0)
break;
}
printf("%d\n", m);
}
}
sorry for my long story...
Ishtiak Zaman
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program
----------------
the world is nothing but a good program, and we are all some instances of the program
-
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
No, memset doesn't work in O(1). It's just a few times faster than the loop.
I don't agree with little joey. I use memset a lot, you just have to know what the second argument is of char type. memset is not like gets, in fact it's a very nice function. But, like many other C features (pointers, direct memory management, etc.) it requires some knowledge and practice. little joey is an old-school Pascal programmer and he might not like that.
sizeof on arrays works fine, so instead of memset(a, true, 100*100*100*sizeof(bool)) you can write memset(a, true, sizeof(a)). Note that it won't work with pointers.
I don't agree with little joey. I use memset a lot, you just have to know what the second argument is of char type. memset is not like gets, in fact it's a very nice function. But, like many other C features (pointers, direct memory management, etc.) it requires some knowledge and practice. little joey is an old-school Pascal programmer and he might not like that.
sizeof on arrays works fine, so instead of memset(a, true, 100*100*100*sizeof(bool)) you can write memset(a, true, sizeof(a)). Note that it won't work with pointers.