Help in MTRICK

kuruma · February 3, 2014, 12:47am

Hello @all,

As some people said that brute-force was possible for this problem, I decided to try and solve it that way and wrote the following code:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iostream>
#include <map>
#include <functional>
#include <numeric>
using namespace std;
typedef unsigned long long int u64;

u64 multiplyModulo(u64 a, u64 b, u64 c)
{
    u64 result = 0ULL;
    a %= c;
    b %= c;
    while(b) {
        if(b & 0x1) {
            result += a;
            result %= c;
        }
        b >>= 1;
        a <<= 1;
        a %= c;
    }
    return result;
}

int main()
{
	ios_base::sync_with_stdio(false);
	int t;
	cin >> t;
	while(t--)
	{
		int N;
		cin >> N;
		vector<u64> v(N);
		for(int i = 0; i < N; i++)
		{
			cin >> v[i];
		}
		u64 A,B,C;
		cin >> A >> B >> C;
		string s;
		cin >> s;
		
		
		for(int i = 0; i < N; i++)
		{
			if(s.substr(i,1)=="R") //rev all elems... todo
			{
				reverse(v.begin(),v.end());
			}
			if(s.substr(i,1)=="A")
			{
				for(int j = i; j < N; j++)
				{
					v[j] += A;
					if(v[j] >= C)
						v[j] %= C;
				}
			}
			if(s.substr(i,1)=="M")
			{
				for(int j = i; j < N; j++)
				{
					v[j] = multiplyModulo(v[j],B,C);
				}
			}
			//for(int z = i; z < N; z++)
			//v[z] = v[z]%C;
		cout << v[i]<< " ";
		}
		cout << endl;
	}
	return 0;
}

Can anyone point me in the right track?

I didn’t really understood editorial’s concepts very well…

Best,

Bruno

hrculiz · February 3, 2014, 10:19am

I also solved this problem using brute force method, but getting TLE.
MY solution

vineetpaliwal · February 3, 2014, 3:20pm

The problem of TLE is because of slow I/O .

Use printf and scanf instead of cout and cin

kuruma · February 3, 2014, 4:18pm

Hello @vineetpaliwal,

I have changed my previous code to this:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iostream>
#include <map>
#include <functional>
#include <numeric>
using namespace std;
typedef unsigned long long int u64;

u64 multiplyModulo(u64 a, u64 b, u64 c)
{
    u64 result = 0ULL;
    a %= c;
    b %= c;
    while(b) {
        if(b & 0x1) {
            result += a;
            result %= c;
        }
        b >>= 1;
        a <<= 1;
        a %= c;
    }
    return result;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int N;
		scanf("%d",&N);
		vector<u64> v(N);
		for(int i = 0; i < N; i++)
		{
			scanf("%lld",&v[i]);
		}
		u64 A,B,C;
		scanf("%lld %lld %lld", &A,&B,&C);
		char* s;
		s=(char*) malloc(sizeof(char)*1024);
		scanf("%s",s);
		
		
		for(int i = 0; i < N; i++)
		{
			if(s[i]=='R') //rev all elems... todo
			{
				reverse(v.begin(),v.end());
			}
			if(s[i]=='A')
			{
				for(int j = i; j < N; j++)
				{
					v[j] += A;
					if(v[j] >= C)
						v[j] %= C;
				}
			}
			if(s[i]=='M')
			{
				for(int j = i; j < N; j++)
				{
					v[j] = multiplyModulo(v[j],B,C);
				}
			}
			//for(int z = i; z < N; z++)
			//v[z] = v[z]%C;
		printf("%lld ", v[i]);
		}
		printf("\n");
	}
	return 0;
}

However, I still get TLE…

This is just simple brute force method with the careful trick of the multiply function being used…

Any more tips on how to get AC?

Best,

Bruno

PS: I was using cin/cout with sync turned off because I was unsure on how to read strings with scanf(), but, I’ve now fixed that…

vineetpaliwal · February 3, 2014, 4:46pm

@kuruma : You need not process all the entries at each step .

a_0 , a_1 , a_2 , a_3 … is array .

Suppose string is AMAM …

then array would be

a_0 + A , a_1 + A , a_2 + A , a_3 + A after step 1

a_0 + A , ( a_1 + A ) * M , ( a_2 + A ) * M , ( a_3 + A ) * M after step 2

a_0 + A , ( a_1 + A) * M , ( a_2 + A ) * M + A , ( a_3 + A ) * M + A after step 3

a_0 + A , (a_1 + A) * M , (a_2 + A )* M + A , ( ( a_3 + A ) * M + A ) * M after step 4

If you look at fourth entry in array it is : a_3 * M * M + A * M * M + A * M .

If you pay attention you will find all further entries will also be of like : a_k * mult + add

where mult = M * M and add = AMM + A * M .

So you just maintain mult and add at every step .

You can process only one entry which you have to print at any time .

mult if updated only when a multiplication happens

add is updated both when addition and multiplication happens

initially add = 0 , mult = 1

This way you avoid O(N^2) complexity per test case

For reversing you may actually reverse the array as i did during the contest . Even though this brings O(N^2) complexity per test case , just exchanging values in placeholders is not costly since no modulo is involved

You can even maintain a begin and end and a direction to get rid of this also , but not needed to pass the test cases with given constraints .

Sorry , i just saw cout and cin and i immediately responded earlier without going through your code .

Hope this helps

Link my contest time solution :

http://www.codechef.com/viewsolution/3169070 .

This link solution does not have optimization for “reverse”

You can maintain a start , end and direction variable

Initially start = 0 , end = n - 1 and direction = true

When you read a character from string if direction = true , process array value at start and increment it and if direction = false , process array value at end and decrement it .

If the character read is ‘R’ then change direction i.e. direction = ! direction .

kuruma · February 4, 2014, 2:40am

Hello again @vineetpaliwal,

Sorry to bother you again, but, I’ve now re-written my code as follows:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iostream>
#include <map>
#include <functional>
#include <numeric>
using namespace std;
typedef unsigned long long int u64;

u64 multiplyModulo(u64 a, u64 b, u64 c)
{
    u64 result = 0ULL;
    a %= c;
    b %= c;
    while(b) {
        if(b & 0x1) {
            result += a;
            result %= c;
        }
        b >>= 1;
        a <<= 1;
        a %= c;
    }
    return result;
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int N;
		scanf("%d",&N);
		vector<u64> v(N);
		for(int i = 0; i < N; i++)
		{
			scanf("%llu",&v[i]);
		}
		u64 A,B,C;
		scanf("%llu %llu %llu", &A,&B,&C);
		char* s;
		s=(char*) malloc(sizeof(char)*1024);
		scanf("%s",s);
		u64 add = 0ULL;
		u64 mult = 1ULL;
		
		for(int i = 0; i < N; i++)
		{
			if(s[i]=='R')
			{
				reverse(v.begin(),v.end());
			}
			if(s[i]=='A')
			{
				add = (add + A)%C;
			}
			if(s[i]=='M')
			{
				mult = multiplyModulo(mult,B,C);
				add = multiplyModulo(add,B,C);
			}
			
		printf("%llu ", (multiplyModulo(v[i],mult,C)+add%C)%C);
		}
		printf("\n");
	}
	return 0;
}

And I still have WA veredict… I think I understood your explanation well and tried to be as faithful to it as I could…

Maybe any overflow issue?

Best,

Bruno

vineetpaliwal · February 4, 2014, 9:37am

@kuruma : I think the problem is in reverse(v.begin(),v.end()) . It should be reverse(i,v.end()) .

orchidmajumder · February 4, 2014, 10:22am

Hii @kuruma,
Instead of actually reversing the array,you can keep a boolean flag to indicate whether you should print the array from beginning or from end;when you encounter one reverse operation,you just toggle this bit value;Obviously it won’t save the WA verdict,but it can be used as a time factor improvement.

You can refer to my solution:
Link

kuruma · February 4, 2014, 4:25pm

Thanks, I finally got AC!! Thank you so, so much

vineetpaliwal · February 4, 2014, 11:19pm

@kuruma : Please accept one of the answers i gave if you think it solved your problem . Meanwhile thanks for upvoting .