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

Post by Karim » Sat Jan 20, 2007 6:47 pm

Can anyone tell me whats the idea of this problem

cause i am getting TLE

thanks

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Jan 20, 2007 7:13 pm

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Jan 20, 2007 7:18 pm

Actually my algorithm was theta(N+M).

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

Post by Karim » Sat Jan 20, 2007 7:25 pm

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

i think O( n ^ 2)

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Jan 20, 2007 7:32 pm

thats why you got TLE

paulmcvn
New poster
Posts: 34
Joined: Sat Nov 13, 2004 12:15 pm

Post by paulmcvn » Sun Jan 21, 2007 7:37 am

:wink:
Last edited by paulmcvn on Wed Jan 24, 2007 9:34 am, edited 2 times in total.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Jan 21, 2007 10:36 am

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...)

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Jan 21, 2007 10:52 am

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.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Jan 21, 2007 6:37 pm

rio wrote:ADD: I think paulmcvn post might be a little spoiler.
yes, I agree. :cry:

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

why WA?

Post by nut » Mon Jan 22, 2007 1:03 pm

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

Post by cypressx » Mon Jan 22, 2007 1:15 pm

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

artie
New poster
Posts: 8
Joined: Sun Dec 31, 2006 11:56 am
Location: Russia

Post by artie » Wed Jan 24, 2007 1:26 am

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 :(
per aspera ad astra

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Jan 24, 2007 7:10 am

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

Post by temper_3243 » Thu Mar 22, 2007 1:34 pm

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

Post by helloneo » Thu Mar 22, 2007 4:30 pm

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..

Post Reply

Return to “Volume 111 (11100-11199)”