## 11155 - Be Efficient

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

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
Location: Bangladesh
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
Location: Bangladesh
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
Location: Bangladesh
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
Location: Bangladesh
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
Location: Madrid, Spain

### 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 = a;
for (i=1; i<n; i++)
x[i] = ((x[i-1] * b + c) % m) + 1;

s = x;
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
just add 'mod++;' after res=0
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 + x + ... 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++;

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 per aspera ad astra
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 + x + ... 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++;

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 is kind of special because mod itself can be the sequence we're looking for..