2 player team knowing maximum moves

Question

Given a list of N players who are to play a 2 player game. Each of them are either well versed in making a particular move or they are not. Find out the maximum number of moves a 2-player team can know.

And also find out how many teams can know that maximum number of moves?

Example Let we have 4 players and 5 moves with ith player is versed in jth move if a[i][j] is 1 otherwise it is 0.

Here maximum number of moves a 2-player team can know is 5 and their are two teams that can know that maximum number of moves.

Explanation : (1, 3) and (3, 4) know all the 5 moves. So the maximal moves a 2-player team knows is 5, and only 2 teams can acheive this.

My approach : For each pair of players i check if any of the players is versed in ith move or not and for each player maintain the maximum pairs he can make with other players with his local maximum move combination.

vector<int> pairmemo;
for(int i=0;i<n;i++){
    int mymax=INT_MIN;
    int countpairs=0;
    for(int j=i+1;j<n;j++){
        int count=0;
            for(int k=0;k<m;k++){
                if(arr[i][k]==1 || arr[j][k]==1)
                {
                    count++;
                }
        }
        if(mymax<count){
            mymax=count;
            countpairs=0;
        }
        if(mymax==count){
            countpairs++;
        }

    }
    pairmemo.push_back(countpairs);
    maxmemo.push_back(mymax);
}

Overall maximum of all N players is answer and count is corresponding sum of the pairs being calculated.

for(int i=0;i<n;i++){
    if(maxi<maxmemo[i])
        maxi=maxmemo[i];
}

int countmaxi=0;

for(int i=0;i<n;i++){
    if(maxmemo[i]==maxi){
        countmaxi+=pairmemo[i];
    }
}

cout<<maxi<<"\n";
cout<<countmaxi<<"\n";

Time complexity : O((N^2)*M)

Code : How can i improve it?

Constraints : N<= 3000 and M<=1000

@πάνταῥεῖ Means ? I want to have better algorithm?Do you want me to write my code here? — user3786422, Jun 30 '14 at 19:32
@πάνταῥεῖ For N=3000 and M=1000 it takes far more than 2 seconds — user3786422, Jun 30 '14 at 19:33
_'Means ? I '_ Get a decent unit testing framework, write test cases for the various input combinations, and measure how the timing behavior actually is. — πάντα ῥεῖ, Jun 30 '14 at 19:34
@πάνταῥεῖ Hey i had done that also.Thats why posted here that it is taking quite long time then required for required constraints — user3786422, Jun 30 '14 at 19:37
I see a lot of text but if I read through the lines, the situation is as follows: given `N` bitstrings `S_i` of length `M` and define the size of a bitstring as the number of `1`s. Find indices `0 <= p < q < N` such that `S_p | S_q` has maximum size. Is that what you're saying? — Vincent van der Weele, Jun 30 '14 at 19:38
@user3786422 If you ask for code improvements, then you should show some code yes. — πάντα ῥεῖ, Jun 30 '14 at 19:39
I actually think this is a very interesting problem. In order to do better than the trivial brute force (`O(M*N^2)`) you need to identify some recurring sub-problem. So far I don't see any. I think you've just been a bit unlucky phrasing the problem which let to down votes, but I still hope someone comes by with a solution... — Vincent van der Weele, Jun 30 '14 at 19:53
Question is, do you need to improve the algorithm (complexity wise), or just run it fast? Given N<=3000 and M<=1000, that's only around 10^10 worst case, so if you can get your steps down to the 1-cycle range, it will only take a few seconds. You can easily do 64 bit operations in parallel in a 64-bit register, leading to less than 1 cycle each... — Chris Dodd, Jun 30 '14 at 21:16

score 0 · Accepted Answer · edited May 23 '17 at 11:49

0

If you represent each set of moves by a very large integer, the problem boils down to finding pair of players (I, J) which have maximum number of bits set in MovesI OR MovesJ.

So, you can use bit-packing and compress all the information on moves in Long integer array. It would take 16 unsigned long integers to store according to the constraints. So, for each pair of players you OR the corresponding arrays and count number of ones. This would take O(N^2 * 16) which would run pretty fast given the constraints.

Example: Lets say given matrix is

11010
00011

and you used 4-bit integer for packing it. It would look like:

1101-0000
0001-1000

that is,

13,0
1,8

After OR the moves array for 2 player team becomes 13,8, now count the bits which are one. You have to optimize the counting of bits also, for that read the accepted answer here, otherwise the factor M would appear in complexity. Just maintain one count variable and one maxNumberOfBitsSet variable as you process the pairs.

edited May 23 '17 at 11:49

Community

1
1

answered Jun 30 '14 at 20:09

Priyank Bhatnagar

794
6
10

Please provide some pseudocode or testcase explanation to understand as am not getting what you wanna say – user3786422 Jun 30 '14 at 20:14
Added example to explain. I am really surprised at the down vote. So much for trying to help. Thanks! – Priyank Bhatnagar Jun 30 '14 at 20:20
This sort of technique just improves the constant term, not the asymptotic complexity. Given such tiny requirements for N and M, it may well be fast enough. – Chris Dodd Jun 30 '14 at 21:12
@PriyankBhatnagar What after packing 32 bit integers.Am not getting last step.What you wanna say – user3786422 Jul 01 '14 at 03:12
@user3786422, Please read the answer again. I updated it to finding count of 2-player teams which know maximum movies. – Priyank Bhatnagar Jul 01 '14 at 09:45
@ChrisDodd, Yes, it is just constant optimization. And in this case it should lower the running time by a factor of `64`. – Priyank Bhatnagar Jul 01 '14 at 09:46

score 0 · Answer 2 · answered Jun 30 '14 at 21:21

0

What Ill do is: 1. Do logical OR between all the possible pairs - O(N^2) and store it's SUM in a 2D array with the symmetric diagonal ignored. (thats we save half of the calc - see example) 2. find the max value in the 2D Array (can be done while doing task 1) -> O(1) 3. count how many cells in the 2D array equals to the maximum value in task 2 O(N^2)

sum: 2*O(N^2)+ O(1) => O(N^2)

Example (using the data in the question (with letters indexes):

 A[10101] B[11100] C[11010] D[00101]

Task 1:

[A|B] = 11101 = SUM(4)
[A|C] = 11111 = SUM(5)
[A|D] = 10101 = SUM(3)
[B|C] = 11110 = SUM(4)
[B|D] = 11101 = SUM(4)
[C|D] = 11111 = SUM(5)

Task 2 (Done while is done 1):

Max = 5

Task 3:

Count = 2

By the way, O(N^2) is the minimum possible since you HAVE to check all the possible pairs.

answered Jun 30 '14 at 21:21

yossico

3,421
5
41
76

Since there are M moves, each OR operation is O(M), so you still have O(M*N^2). Expressing it this way does make it easier to vectorize, which will help raw speed. – Chris Dodd Jun 30 '14 at 21:23
Opps, forgot the M thing, I've just count it as a binary number and count the counting part as O(1) – yossico Jun 30 '14 at 21:26
@yossico your solution is still O(M*N^2). – user3786422 Jul 01 '14 at 03:11

Kenny Ostrom · Answer 3 · 2014-06-30T22:29:39.613

Since you have to find all solutions, unless you find a way to find a count without actually finding the solutions themselves, you have to actually look at or eliminate all possible solutions. So the worst case will always be O(N^2*M), which I'll call O(n^3) as long as N and M are both big and similar size.

However, you can hope for much better performance on the average case by pruning. Don't check every case. Find ways to eliminate combinations without checking them.

I would sum and store the total number of moves known to each player, and sort the array rows by that value. That should provide an easy check for exiting the loop early. Sorting at O(n log n) should be basically free in an O(n^3) algorithm.

Use Priyank's basic idea, except with bitsets, since you obviously can't use a fixed integer type with 3000 bits.

You may benefit from making a second array of bitsets for the columns, and use that as a mask for pruning players.

I DONT want to find all solutions but only count of the solutions. — user3786422, Jul 01 '14 at 03:07
Like I said, it may be possible to count the solutions without finding them, but I don't know how. I do know how to improve your algorithm, though, which was the question. Set up data structures that will help you eliminate large chunks of the work. I left out minor details (especially on the column mask) because it looks like homework. — Kenny Ostrom, Jul 01 '14 at 17:08

2 player team knowing maximum moves

3 Answers3