11155 - Be Efficient

[Karim]

Can anyone tell me whats the idea of this problem

cause i am getting TLE

thanks

[emotional blind]

try to find out order M solution, which i did in contest.

[emotional blind]

Actually my algorithm was theta(N+M).

[Karim]

my algorithm is trying all subsets and check if divisible by m

i think O( n ^ 2)

[emotional blind]

thats why you got TLE

[paulmcvn]

[rio]

Getting WA..
Is sum 0 considered as Multiple of M?

What would be the result for sequence

Code: Select all

1 0 1 0 0 

with M = 2.

With considering sum 0 as Multiple of M, it will be 6.

Code: Select all

({1,0,1},  {0},  {1,0,1,0}, {1,0,1,0,0},  {0,0},  {0})

Without considering sum 0 as Multiple of M, it sould be 3.

Code: Select all

({1,0,1}, {1,0,1,0}, {1,0,1,0,0})

Which is right ? (maybe both wrong...)

[rio]

Ooops. I found my mistake and got AC.
I was assuming A <= M. Be carefull...
Anyway, it seems sum 0 sould be consider as Multiple of M.

ADD: I think paulmcvn post might be a little spoiler.

[emotional blind]

ADD: I think paulmcvn post might be a little spoiler.

yes, I agree.

[nut]

It seems right but I can't find the bug.

Code: Select all

#include <iostream>

#define MAXN 10000

using namespace std;

long long t, cc, a, b, c, m, n, i, r, res;
long long x[MAXN];
long long s[MAXN];
long long mod[MAXN];


int main()
{
  cin >> t;
  for (cc=0; cc<t; cc++)
    {
      cin >> a >> b >> c >> m >> n;
      x[0] = a;
      for (i=1; i<n; i++)
	  x[i] = ((x[i-1] * b + c) % m) + 1;

      s[0] = x[0];
      for (i=1; i<n; i++)
	s[i] = (s[i-1] + x[i]) % m;

      for (i=0; i<MAXN; i++)
	mod[i] = 0;

      for (i=0; i<n; i++)
	mod[s[i] % m]++;

      res = 0;
      for (i=0; i<m; i++)
	res += (mod[i]*(mod[i]-1) / 2);

      cout << "Case " << cc+1 << ": " << res << endl;
    }
  
  return 0;
}

[cypressx]

just add 'mod[0]++;' after res=0

[artie]

First, generate the sequence x like the problem description
Then, generate the sequence s,
where s = x[0] + x[1] + ... x
While computing, you can set s = (s[i-1] + x) % m; , because we only deal with the remainder modulo m

For each 0<=r<m, count the number of s, so that s % m = r
That means, you have to iterate through s, and set
mod[s % m]++;

Moreover, set mod[0]++;

Then, the result is sum ( mod*(mod[i] - 1) div 2, i=0..m-1)

That's simply because each subsequence can be represented as s[i] - s[j] for some i,j.

Would you please give a detailed explanation about sum ( mod[i]*(mod[i] - 1) div 2, i=0..m-1) formula? I can't get it

[rio]

Feel this thread too SPOILic ...

>paulmcvn
Please remove or edit your post. It's just not only me that feeling it spoilic.
>nut
Don't forget removing your code after AC.
>artie
Don't quote a post that might be spoilic

-----
(Is there a English term "spoilic" ..? Sory for my lack of English)

[temper_3243]

First, generate the sequence x like the problem description
Then, generate the sequence s,
where s = x[0] + x[1] + ... x
While computing, you can set s = (s[i-1] + x) % m; , because we only deal with the remainder modulo m

For each 0<=r<m, count the number of s, so that s % m = r
That means, you have to iterate through s, and set
mod[s % m]++;

Moreover, set mod[0]++;

Why should this be done ?

Then, the result is sum ( mod*(mod[i] - 1) div 2, i=0..m-1)

That's simply because each subsequence can be represented as s[i] - s[j] for some i,j.[/quote]
Would you please give a detailed explanation about sum ( mod[i]*(mod[i] - 1) div 2, i=0..m-1) formula? I can't get it

I don't understand this quite why it should be done. rationale behind this

[helloneo]

nC2 = n*(n-1)/2

The formula you're wondering above has come from it..

The reason we do this is also explained here..

That's simply because each subsequence can be represented as s - s[j] for some i,j

and mod[0] is kind of special because mod[0] itself can be the sequence we're looking for..