UVa 11088 - End up with More Teams

Problem Statement:
11088 - End up with More Teams


Solution:
This problem looks innocent enough, until it bit me with a few WA and TLE. The idea to solve this problem is by using a bitmask DP technique, which I will elaborate. This solution took \( O(kN2^N) \) time.

Firstly let B be the set for which \( i \in B\) if and only if i-th person is already chosen as a member of some team. Let a[i] be the "ability" value of i-th person, we know that a[i] \( \leq 30\). Lastly, let D[B][val] be the maximum number of groups that can be formed using people in B, and such that if the total number of people in B is not divisible by 3, val will be the total ability of the extra people in B not in any group yet. For every j not in B yet, we do:

UVa 10364 - Square

Problem Statement :

UVa 10364 - Square

Solution:

This is an innocent looking problem, but actually it is a variant of set partitioning, an NP complete problem. To solve the problem, I used a bitmasking technique coupled with a dynamic programming technique to come up with an \( O(N2^N) \) solution. While I like the problem itself, to pass the time limit on UVa, you may require some optimisations to the plain DP implementation, which makes the experience a little bit unappealing to me.

Codeforces Round #290 (Div. 1 B / Div. 2 D) - Fox and Jumping

Problem Statement:
512B - Fox and Jumping

Solution:
The idea to solve this problem is pretty simple (but the DP is not :P): Find the lowest cost combination of cards for which their greatest common divisor is 1. The official editorial has succinctly explained the DP approach in merely a few lines, check it out!

The proper DP approach is to do a bitmask on prime factors, which will give a running time of \(O(2^k N^2)\), where k is at most 9, since there can at most be 9 different prime factors in any integer less than \(10^9\). How does it work?

Codeforces 441E - Valera and Number

Problem Statement:
441E - Valera and Number

Solution:
Another tedious DP problem, but it has some interesting ideas. The official editorial to this problem is pretty easy to understand.

There are two types of operation we can have on a given bit string: left shift and increment by one. Notice that since there are at most 200 increment operations, we can show that it suffices to keep track of the last 8 bit of the bit string. This is because in each increment operation, we can have either:

Codeforces 442A - Borya and Hanabi

Problem Statement:
442A - Borya and Hanabi

Solution:
Not an easy problem for me.. The first and easiest thing to say is there are 10 type of hints and hence we can do a complete search on each \(2^{10}\) combination of them. Now the hardest part is that, given a combination of hints, check whether they will allow us to differentiate amongst all the cards. For me this is not an obvious task.. One observation is that if a type of cards occurs more than once, we can consider them as one. This is because given a hint (color or value) in which the type belongs to, we will open up all cards belonging to that type, which can be considered as one set. Each type of cards belong to only one set at most, and these sets are disjoint, hence the observation is valid. So it suffices to keep track on the type of cards present.

Codeforces Round 285 Div. 1 Problem D - Misha and XOR

Problem Statement:
504D - Misha and XOR

Solution:
Another tedious problem. The strategy is to apply the idea of linear independence. Let's say we already transformed every decimal strings into binaries, and place them in rows such that they form a matrix of 0s and 1s. We want to apply Gauss Elimination such that we achieve linear independence between the rows. Eg :

numbers     binaries
7           111
5           101

initial matrix:
111
101

linear independence between rows, after Gauss Elimination:
111
010

Codeforces 453B - Little Pony and Harmony Chest

Problem Statement:
453B - Little Pony and Harmony Chest

Solution:
Learnt new thing thanks to the official editorial :)

The low constraints for both n and \(a_i\) suggests that we can do a complete search, and in fact we can use a bitmasking technique to perform this search more efficiently. Firstly, to minimize \(|a_i-b_i|\), we would like to choose \(b_i\) that can do better than just simply assigning 1 to \(b_i\). This means that \(b_i\) should be between [1..\(2a_i-1\)], and thus 2*30-1 = 59 marks the upperbound for \(b_i\). Our strategy would be simply try each of these 59 numbers on each i, but simply trying all combinations would be too slow. So what we can do a dynamic programming approach: d[i][bm] be the minimum possible \(\sum_{k=1}^{i} |a_k-b_k|\), while bm indicates the bitmask, where if k-th bit is on, then we have assigned number k a \(b_i\). However, using such bitmask prove to be too big in space, since bm can go up to \(2^{59}\). We can do better, but just bitmasking the prime factors that have been used (i.e. if bit k is set, then some \(b_i\) is divisible by k-th prime)! There are only 17 primes in [1..59], so we reduced the bitmask states to \(2^{17}\) :D

Follow Up: Codeforces 275 Div. 2 Problem E / Div. 1 Problem C

Problem Statement:
482C - Game of String

Solution:
The most excruciating problem I've done so far in my life.. haha
Anyway, I was not able to come up with a purely \(O(L 2^L) \) solution, but there is such solutions, and I am still trying to understand the thought process. The one that I managed to get it accepted is actually \(O(NL 2^L)\) but the N term is very small thanks to __builtin_popcount() function.

a bit of dp and bit manipulation: SPOJ - ASSIGN

Problem Statement:
SPOJ - ASSIGN

Summary:
There are N students and N assignments, and an NxN matrix where cell[i,j] = 1 if student i likes assignment j, and 0 otherwise. Find the number of ways of assigning N assignments which satisfies all students' preference. (N <= 20)

Solution:
In recursive terms, this is mostly a straight forward DP problem with the following relationship:
S(k, bitmask) = the number of ways of assigning assignments to students k .. N, with bitmask representing the assignments that are already assigned to students 1 .. k-1. Then,
S(k, bitmask) = sum { S(k+1, bitmask with bit i switched ON if student k likes assignment i) }

However, the recursive DP does not cut for the time limit, while the bottom-up DP can. Starting from all bits turned ON in bitmask, we proceed down to 0 by decreasing bitmask with 1 each time. For each particular bitmask, we compute the number of bits turned ON, which tells us which student we are at.

/* Bottom-up implementation 

As we go decrement b, all values dp[NMAX-1] .. dp[b+1] are already computed

Hence they can be used to calculate dp[b].

*/

cin >> N;
for(int i=0;i<N;++i){
    for(int j=0;j<N;++j){
        cin >> like[i][j];
    }
}
int NMAX = (1<<N);
for(int i=0;i<NMAX;++i) {
    dp[i] = 0;
}
dp[NMAX-1] = 1;
for(int b=NMAX-1;b>=0; --b) {
    int n = b;
    int k = 0;
    while(n){
        k += (n&1);
        n /= 2;
    }
    for(int i=0;i<N;++i){
        if(like[k][i] && !(b & (1<<i))){
            dp[b] += dp[b | (1<<i)];

        }
    }
}
cout << dp[0] << endl;

a bit of bitmask : UVa 10718 - Bit Mask

So today I learn a new bitwise manipulation technique :D

Problem Statement:
UVa 10718 - Bit Mask

Summary
For \(N, M, U, L\) such that \(L \leq M \leq U\), find minimum \(M\) such that \(M\) OR \(N\) is maximum (where OR refers to bitwise OR operation).

This problem requires a strategy to switch on bits on M (starting from all 0 bit) such that we only switch on a bit on M when we absolutely need to, but we must also ensure that M can fall between L and U.

Strategy:
For i-th bit of N starting from the leftmost bit:
1. If the i-th bit of N is ON, the best case scenario is we do not need to turn on the i-th bit of M. That is, if by letting the i-th bit of M off, we can still have M in between L and U, we will do so. Otherwise, the i-th bit of M must be on.
2. Else, if the i-th bit of N is OFF, the best case to maximize M OR N is by switching the i-th bit of M to ON. However, if the resulting M is higher than U, we must switch the i-th bit of M to OFF instead.

As such, the resulting M will be in between L and U.

For example, when N = 101101, L = 011010, U = 011110

i = 5:
leftmost bit of N is ON, hence M should be off, and indeed the resulting M can still fall between L and U.
i = 4:
bit of N is OFF, hence we would like to turn it on. The resulting M = 01**** can still be less than U, i.e the lowest M = 010000 is indeed less than U, so we can do so.
i = 3:
bit of N is ON, hence we want that bit on M to be OFF. but M = 010*** will always be less than L, i.e the highest possible M = 010111 is not lower than L, hence we must have that bit to be switched ON, i.e M = 011***
i = 2:
bit of N is ON, and we want M to be OFF. M = 0110** can still be in between L and U, i.e. the highest possible M = 011011 is not lower than L.
i = 1:
bit of N is OFF. If we switch that bit of M on, M = 01101* can still be less than U.
i = 0:
the rightmost bit is ON, so we want that bit on M OFF, and we have our minimum M such that M OR N is maximum.

Here is the code:

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;

int main(){
 ll N,U,L,ans;
 while(scanf("%lld %lld %lld",&N,&L,&U)!=EOF){
  ans = 0;
  for(int i=0;i<=32;++i){
   ll state = (N & (1L<<(32-i)));
   //printf("%lld\n", state);
   //printf("%lld\n", ans);
   if(state){
    //if the bit is set
    //if not setting this bit can still fulfill the constraint
    ll temp = state -1;
    temp |= ans;
    if(temp < L){
     ans |= state;
    }
   } else {
    //if not set, should set if fulfill constraint
    ll temp = ans;
    temp |= (1L<<(32-i));
    if(temp <= U){
     ans = temp;
    }
   }
  }
  printf("%lld\n",ans);
 }
 return 0;
}