11087 - Divisibility Testing

[Sumon]

I got 3 seconds with read(0, buf, 1024*1024) and a linear-time algorithm. It also helps not to store the numbers that you read. Read them one at a time and throw them away immediately.

Can anyone send the code segment where this read() function has been used and the data has been processed?? Please help me giving necessary info's for using this function like required header file and whatever it requires. I am waiting.

[Rainy Day]

read system call reads up to n bytes of data from the file associated with the file descriptor f1 & places them in the data area buf . u can learn more reading any book about system programming in Linux or Unix , there's a lot of thing to learn other then acm.


code:

#include<unistd.h>
int main()
{
char buf[128] ;

int Read ;
Read=read(0,buf,128) ;
if( Read <0)
write(2,"Read error\n",20);
if( write(1,buf,Read)!=Read)
write(2,"Write error\n",20) ;
exit(0) ;
}
I ran this program at Fedora 3 using gcc . I think u can easily understnd it.

[nymo]

What is the linear time algo. to find the number of pairs? Can someone give some hint? ... thanks.
[EDIT] I get the idea from MIB, thanks. ... should have exploited the fact that (a + b) % k = ( a % k + b % k ) % k

[hi!man!]

Can anyone help me?
I use Nazmul Quader Zinnuree's method
I got WA many times
or someone can give me critical cases?

Code: Select all

Aced

[EDIT]found a stupid mistake[/EDIT]

[lord_burgos]

someone can give me critical cases?

please

Code: Select all

# include <stdio.h>
# include <string.h>

char set;

long long hash[1000];
long long dup[1000];
int cmb(int num, int k){ return ( (num % k) + k ) % k; }
char flag[20000001];

int min(int a , int b){ return a < b ? a : b; }
int max(int a , int b){ return a > b ? a : b; }

main(){
  int casos, x,  y, num, searching, n, k, z;
  long long res, cont;
  for( scanf("%d", &casos) , set = 1; set <= casos && scanf("%d %d", &n, &k) != EOF; set++){
    memset(hash, 0, sizeof(hash));
    memset(dup, 0, sizeof(dup));
    for(x = 0 ; x < n ; x++) {
      scanf("%d", &num);
      if(flag[ num + 10000000] < set * 2){ flag[ num + 10000000] = set*2; hash[cmb( num , k)]++; }
      else if(flag[ num + 10000000] == set * 2){ flag[ num + 10000000] = set*2 + 1; dup[cmb( num , k)]++; }
    }
    res = 0;
    for(x = 0; x < k; x++){
      cont = 0;
      searching = cmb( k - cmb( x, k ) , k);
      if(searching > x) continue;
      if( x != searching ) cont += hash[x] * hash[searching];
      else {
        cont += hash[x] * (hash[x] - 1) / 2;
        cont += dup[x];
      }
      res += cont;
    }
    printf("Case %d: %lld\n", set, res);
  }
  return 0;
}

[windows2k]

I used that method and got WA
Please, help!

Your program fails on the input

Code: Select all

1
2 16
4 4

Hope it helps

[mak(cse_DU)]

I solved just keep tracking Frequency of number mod K.
Surely (negative number) mod K is positive.
so need a array of size 501.
My solution is O(N).

NB: No need hashing, save number after modulo by K.
Some Random input output:

Input:

Code: Select all

10
42 468
-166 3445 -7880 2498 -2440 -3546 9470 1053 -609 -2213 3749 -2090 -1295 -177 3721 3233 -8043 -632 -2859 4892 989 3009 -2570 1385 -2097 -95 -2822 -1018 6751 -719 348 182 98 6616 3641 -839 -980 3905 845 7006 -5870 6916 
67 377
-2377 4505 3303 3999 4036 -3612 3718 -5019 -7226 1671 -713 -3724 -2148 441 1204 -1415 696 525 -2412 -1919 1979 6200 5217 536 916 6670 3170 7370 -3964 -7549 -4367 1476 4476 -2755 -1691 7107 1051 7087 -4935 3554 -748 -545 8354 575 4149 5184 3547 -1946 -1520 3112 7660 -1165 2165 5386 -2307 -6701 -3307 1484 -4649 4963 2495 5216 3235 2287 2710 -1250 -1064 
15 4
2248 -3160 -9216 -483 8791 852 -3150 6246 1859 -1467 1767 6927 7645 3568 4217 
29 147
1476 442 9727 2428 -117 -8329 -5678 -4919 3503 4363 90 -5866 3173 -6388 -1168 4417 3897 5662 4860 8900 2015 -1468 8647 -6324 870 -3115 -2071 -7915 -2035 
40 424
283 4158 -4888 6917 -3002 2881 2181 -1794 -3279 6413 645 3523 -42 1132 104 887 -3443 -1237 -4336 -3663 2974 4968 5085 707 385 -147 7229 -3356 4096 -5127 -3548 -1850 -1118 567 -3423 2063 3490 3460 4213 -6237 
88 298
-659 5503 -905 3207 -5378 1586 703 -2098 -381 -8949 -1120 -6429 -88 -306 8350 5936 -4836 827 1439 -4900 -598 3951 4229 4735 -3554 1071 5894 4882 -3644 4905 2085 -1633 -7446 -2033 -5287 -866 4253 1855 9349 -715 2055 796 6078 5103 -3002 3701 -3097 1940 -4473 476 -2330 -6996 -1914 4704 8240 864 -367 4866 -1575 4089 4833 -6813 1380 5358 277 -381 -457 7033 1369 -3774 6951 2032 -4391 2865 -7593 479 -3278 4338 -2660 -7731 5169 6066 -5492 -126 9505 -5979 -2456 294 
30 66
-2373 -7559 -4909 -6150 -318 -2912 -431 124 -724 -2781 1737 81 -2757 2566 -6366 -4649 -308 3422 -3548 -422 -541 -4897 3563 -5529 6414 5581 -2228 5000 1680 6734 
25 179
-6691 5623 -9273 803 2208 -3915 7417 -662 -6448 -405 6908 845 39 1911 786 -8424 -6413 3083 4674 3167 3295 -2007 3934 -3074 4889 
14 175
-5476 -8468 4221 223 -2367 -3758 3943 -8711 528 2440 2101 -1442 3343 6839 
90 241
-3378 6706 887 -7414 -4455 3436 -1119 -149 -64 -4893 1838 -7167 -1132 -3493 4534 2345 -5675 -2263 448 1278 -3340 2065 -1193 2798 896 -5369 -1550 -1515 3259 306 -4054 368 246 -1452 -537 9066 3456 5106 -4190 -6319 3753 5809 -1853 4224 -4524 6564 -2509 -11 592 4386 -646 -6947 -931 4622 162 4946 -3124 -4180 1744 -4301 -9186 9282 529 -4405 -5180 1604 3098 -873 -116 389 2614 -1549 8040 4028 540 -2036 -3254 -3221 -331 2047 -976 -1896 3081 8120 -5540 -105 -3903 -1773 2734 1341 

Output:

Code: Select all

Case 1: 0
Case 2: 6
Case 3: 27
Case 4: 1
Case 5: 4
Case 6: 8
Case 7: 5
Case 8: 2
Case 9: 1
Case 10: 17