12081 - Reduced ID Numbers

All about problems in Volume 120. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

AnGeLoSo
New poster
Posts: 8
Joined: Tue Oct 11, 2005 1:47 am

NWERC Problem F

Post by AnGeLoSo » Sun Nov 13, 2005 11:10 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Re: NWERC Problem F

Post by Per » Mon Nov 14, 2005 12:56 am

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".
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
New poster
Posts: 8
Joined: Tue Oct 11, 2005 1:47 am

Post by AnGeLoSo » Mon Nov 14, 2005 1:22 am

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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Nov 14, 2005 7:35 am

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

AnGeLoSo
New poster
Posts: 8
Joined: Tue Oct 11, 2005 1:47 am

Post by AnGeLoSo » Mon Nov 14, 2005 10:15 am

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Nov 14, 2005 11:12 am

AnGeLoSo wrote: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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Mon Nov 14, 2005 6:38 pm

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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

AnGeLoSo
New poster
Posts: 8
Joined: Tue Oct 11, 2005 1:47 am

Post by AnGeLoSo » Mon Nov 14, 2005 10:01 pm

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Nov 15, 2005 5:55 am

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
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue Nov 15, 2005 2:42 pm

AnGeLoSo 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!:)
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).
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

AnGeLoSo
New poster
Posts: 8
Joined: Tue Oct 11, 2005 1:47 am

Done!

Post by AnGeLoSo » Tue Nov 15, 2005 2:55 pm

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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

memset

Post by ayon » Wed Nov 16, 2005 7:51 am

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...
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Nov 16, 2005 9:35 am

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
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Wed Nov 16, 2005 11:56 am

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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Wed Nov 16, 2005 12:16 pm

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.

Post Reply

Return to “Volume 120 (12000-12099)”