11868 - Game of Blocks

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

Moderator: Board moderators

Post Reply
Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

11868 - Game of Blocks

Post by Leonid » Sun Oct 31, 2010 10:10 pm

Hey guys, this thread is for someone who maybe has at least approached this problem.

It can be deduced to matrix exponentiation problem, which can be solved relatively efficiently in O(N^2.376*log(max(leni))) using Coppersmith-Winograd algorithm and fast exponentiation. But it seems that a more efficient algorithm is required, as Coppersmith-Winograd implies a large constant factor. Do you have any other ideas?

JPvdMerwe suggested approach to divide the range repeatedly by 2. But as discussed it seems to be a bit inefficient.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11868 - Game of Blocks

Post by Angeh » Fri Nov 05, 2010 3:27 pm

i implemented this approach, but i time out :((
could someone help us on this ?
thanks in advance
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11868 - Game of Blocks

Post by Leonid » Fri Nov 05, 2010 7:47 pm

Angeh, what optimizations have you tried?

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11868 - Game of Blocks

Post by Angeh » Fri Nov 05, 2010 7:55 pm

i didnt use many optimization ... only used Memorization (Using STL map )...
also Calculated the result for i:0...10^6 using incremental method ... it tool 4s To calculate FOR 10^6

but FOR this Test Case
2
750 749
999999999999999

it took minutes to complete ...
so i didnt try much other minor optimizations like reducing number of * or % ...

There should be other method to solve this Test Case ...
100
750 749 748 747 746 745 744 743 742 741 740 739 738 737 736 735 734 733 732 731
730 729 728 727 726 725 724 723 722 721 720 719 718 717 716 715 714 713 712 711
710 709 708 707 706 705 704 703 702 701 700 699 698 697 696 695 694 693 692 691
690 689 688 687 686 685 684 683 682 681 680 679 678 677 676 675 674 673 672 671
670 669 668 667 666 665 664 663 662 661 660 659 658 657 656 655 654 653 652 651
999999999999999

one other possible optimization could be to avoid computing for same block sizes and just calculate distinct sizes ...
but it would not work in worst Case ....

in Rank list There are ACs below 2s ... :( i wonder whats the Right approach !!

Code: Select all

#include<iostream>
#include<algorithm>
#include<map>
#include<ctime>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
map<long long ,long long> DP;
long long memorize[1000000];
const long long Mode= 100000007;
int in[128],n;
long long Find(long long range){
    //printf("%lld\n",range);
    if(DP.count(range) )return DP[range];
    long long res=0;
    FOR(i,n){
        if(in[i]>range)continue;
        else if(in[i]==range)res+=1;
        else {
            FOR( r,in[i] ){
                long long a= range/2-in[i]+r+1,
                    b= range-(range/2+r)-1;
                //printf("%lld %lld %lld\n",a,b,range );
                if(a<0 || b<0)continue;
                res= ( res+(Find(a)*Find(b)) )%Mode;
            }
        }
    }
    return ( DP[range]=res%Mode );
}
int main(){
    //FOR(i,100)printf("%d ",750-i );
    freopen("in.txt","r",stdin);
    int cas;
    scanf("%d",&cas);
    FOR(ca,cas){
        DP.clear();
        scanf("%d",&n);
        int mini=214778;
        FOR(i,n){
            scanf("%d",&in[i] );
            mini=min(mini,in[i] );
        }
        FOR(i,mini) DP[i]=memorize[i]=0;
        DP[0]=memorize[0]=1;

        long long range;
        scanf("%lld",&range);

        //long long start=clock();
        int Max=min<long long>(1000000,range+1 );
        
        for(int i=mini;i<Max;++i){
            memorize[i]=0;
            FOR(j,n)if(in[j]<=i)memorize[i]+=memorize[ i-in[j] ];
            memorize[i]%=Mode;
            DP[i]=memorize[i];
        }

        //printf("PreTime : %lld\n",clock()-start );
        //start=clock();
        long long res=Find(range);
        //long long end=clock();
        pr//intf("Time : %lld\n",end-start );
        printf("Case %d: %lld\n",ca+1,res);        
        //break;
    }
    return 0;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11868 - Game of Blocks

Post by Leonid » Fri Nov 05, 2010 11:04 pm

The solution can be improved by using hashes, by at least a factor of 10. And MOD operation can be done only in the outer loop, that could improve the solution by around a factor of 2. How many seconds does it currently take on the maximum possible test? How many states there are in the map in the worst possible case? Robert Gericz, who wrote the fastest solution under 1 second is expert in number theory and usually writes highly optimized solutions. However, for some reason he used C++ (wondering why?? ).

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

Re: 11868 - Game of Blocks

Post by tanaeem » Sun Nov 07, 2010 6:12 am

My solution is polynomial exponentiation instead of matrix exponentiation. Basic steps are
1. Find a polynomial P(x) of degree 750.
2. Find R(x)=(x^n) mod P(x)
3. Replace x^i by F_i in R(x). The answer is solution.
The polynomial P(x) is related to generating function and I am leaving the detail.
This method can be proved using Cayley–Hamilton theorem.
The problem is inspired by Project Euler problem 258.
http://projecteuler.net/index.php?secti ... ems&id=258

My solution takes more than 13s. I have no idea what Robert Gericz have done.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11868 - Game of Blocks

Post by Leonid » Mon Nov 08, 2010 1:21 am

What is the complexity of your solution? There exists a solution with complexity O( (L^2 + L*C) * log N ) which is described in this thread.

Post Reply

Return to “Volume 118 (11800-11899)”