12081 - Reduced ID Numbers

[AnGeLoSo]

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!

[Per]

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

No, you will not. This is indeed the indended solution, and I doubt there is anything better.

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.

[AnGeLoSo]

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

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

I can't think a way of doing it quicker!!

[Observer]

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

[AnGeLoSo]

Hmmm, I don't undestand your idea! Could you put an example of how does your algorithm work? You can use the second test input for example.

Thanks!

[Per]

I'm trying this on http://acmicpc-live-archive.uva.es/nuevoportal/ but it takes more than 10 seconds!!

You have an array size issue. The answer can be a lot bigger than 305.

[Eduard]

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.

[AnGeLoSo]

Hi!

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!:)

[mf]

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.

[Eduard]

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!:)

It's not so slow because for finding all divisors I'm making

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

[AnGeLoSo]

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:

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

[ayon]

Hi, i have 2 questions about memset.

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;

Here runtime is O(l*m*n); but if i use

Code: Select all

memset(a, true, 100*100*100*sizeof(bool));

what would be the runtime? still O(l*m*n) or simply O(1)?

If i have a structure as below:

Code: Select all

struct data
{
      int n;
      char c;
      double f;
} p[100];

How to set all 100 elements of p to {10, 'a', 3.33} using memset?

thanks in advance...

[little joey]

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:

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

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:

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

[ayon]

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:

Code: Select all

int a[1000];
memset(a, 0, 1000*sizeof(int));

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:

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

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

[Krzysztof Duleba]

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.