## 11155 - Be Efficient

Moderator: Board moderators

Karim
New poster
Posts: 7
Joined: Sun Sep 24, 2006 4:11 pm

### 11155 - Be Efficient

Can anyone tell me whats the idea of this problem

cause i am getting TLE

thanks

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
try to find out order M solution, which i did in contest.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Actually my algorithm was theta(N+M).

Karim
New poster
Posts: 7
Joined: Sun Sep 24, 2006 4:11 pm
my algorithm is trying all subsets and check if divisible by m

i think O( n ^ 2)

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
thats why you got TLE

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm
Last edited by paulmcvn on Wed Jan 24, 2007 9:34 am, edited 2 times in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
rio wrote:ADD: I think paulmcvn post might be a little spoiler.
yes, I agree.

nut
New poster
Posts: 4
Joined: Sat Nov 11, 2006 3:43 pm

### why WA?

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
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

artie
New poster
Posts: 8
Joined: Sun Dec 31, 2006 11:56 am
Location: Russia
paulmcvn wrote: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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am
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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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..