Pages

Tuesday, June 1, 2010

SPOJ - Assignments (ASSIGN)

URL: http://www.spoj.pl/problems/ASSIGN/
Category: Dynamic Programming, Bit Manipulation

The problem is quite simple: to calculate the number of different assignments of n topics to n students provided that every student gets exactly 1 topic that he likes. Each student likes different topics which is given in the format of a matrix. The essence of the problem lies in optimisation, a brute force algorithm will clearly time out if that isn't already evident. As a note, the maximum number of assignments for a 20x20 (filled with 1's) matrix is a massive 2,432,902,008,176,640,000. Since we are enumerating we can easily eliminate greedy as a design approach. Naturally we turn to dynamic programming to somehow reduce the running time to an acceptable amount.

As with all dynamic programming problems, we first define the state. The most natural and obvious state is:

D(s,u) = amount of ways to assign up to student s with a bitmask of subjects u used.

The space complexity of this DP state is O(N * 2^N). However, a observation allows us to reduce the memory footprint by a factor of N, giving a complexity of O(2^N). How does this work? The unique property of the problem is that the number of students and subjects are the same, so we can deduce that when we are up to student V, there are also exactly V bits set in the bitmask. Hence, we can simply just use the bitmask to determine which student we are up to!

Now let's define the recurrence relation:

F(u) = sum of all i { F(u | (1 << i) } where student count_of_bits(u) likes subject i

The base case is,

F((1 << total_students)-1) = 1

Note we have done something implicit. That is, we do not define the base case for where we have "left over" subjects that weren't assign to a student - this is implicitly handled by our looping.

We then code a memoised solution using the recurrence above:

long long memo[1<<20];

int count_bits(int n) {
   int r = 0;
   while (n > 0) { r += (n&1); n >>= 1; }
   return r;
}

long long func(int topicMask) {
   int idx = count_bits(topicMask);
   if (idx >= size) {
      if (topicMask != (1 << size)-1) return 0;
      return 1;
   }
   if (memo[topicMask] != -1) return memo[topicMask];
   long long res = 0;
   for (int i = 0; i < size; i++) {
      if (adjmat[idx][i] == 0 || topicMask & (1 << i)) {
         continue;
      }
      res += func(topicMask | (1 << i));
   }
   return memo[topicMask] = res;
}

Unfortunately, this times out in SPOJ, i.e. it exceeds over 20 seconds for all test cases. This is where bottom-up dynamic programming shines, given that our algorithm is probably close to the time limit (you can check by running on your own machine and noting the speed - if it's quite fast but times out in SPOJ, you are within a constant time factor of passing). Now turning it into a bottom-up dynamic programming is a bit more tricky than usual. The problem lies with the order on which to evaluate.

If we set the same base case as before with,

F((1 << total_students)-1) = 1

We need to somehow traverse backwards whilst also ensuring that we have computed all DP states that are one bit away from the one we are calculating. Turns out due to binary number representation, traversing from (1 << total_students)-1 to 0 is sufficient. This is a rather easy proof and hence left to the exercise of the reader (just list them out for 4-bit numbers and you should see the connection).

The implementation is detailed below:

int adjmat[21][21];
int size;
long long memo[1<<20];

int count_bits(int n) {
   int r = 0;
   while (n > 0) { r += (n&1); n >>= 1; }
   return r;
}

int main() {
   memset(adjmat,0,sizeof(adjmat));
   ios_base::sync_with_stdio(false);
   int nT;
   cin >> nT;
   while (nT-- && cin >> size) {
      memset(adjmat,0,sizeof(adjmat));
      memset(memo,0,sizeof(memo));
      for (int i = 0; i < size; i++) {
         for (int j = 0; j < size; j++) {
            int val; cin >> val;
            adjmat[i][j] = val;
         }
      }
      memo[(1<<size)-1] = 1;
      for (int j = (1 << size)-1; j >= 0; j--) {
         int idx = count_bits(j);
         for (int k = 0; k < size; k++) {
            if (adjmat[idx][k] == 0 || (j & (1 << k))) continue;
            memo[j] += memo[j | (1 << k)];
         }
      }
      cout << memo[0] << "\n";
   }
   return 0;
}

We can shave off some extra time by using a constant time bit counting algorithm (you can google it):

#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int adjmat[21][21];
int size;
long long memo[1<<20];

unsigned numbits(unsigned i)
{
    const unsigned MASK1  = 0x55555555;
    const unsigned MASK2  = 0x33333333;
    const unsigned MASK4  = 0x0f0f0f0f;
    const unsigned MASK8  = 0x00ff00ff;
    const unsigned MASK16 = 0x0000ffff;

    i = (i&MASK1 ) + (i>>1 &MASK1 );
    i = (i&MASK2 ) + (i>>2 &MASK2 );
    i = (i&MASK4 ) + (i>>4 &MASK4 );
    i = (i&MASK8 ) + (i>>8 &MASK8 );
    i = (i&MASK16) + (i>>16&MASK16);

    return i;
}

int main() {
   memset(adjmat,0,sizeof(adjmat));
   ios_base::sync_with_stdio(false);
   int nT;
   cin >> nT;
   while (nT-- && cin >> size) {
      memset(adjmat,0,sizeof(adjmat));
      memset(memo,0,sizeof(memo));
      for (int i = 0; i < size; i++) {
         for (int j = 0; j < size; j++) {
            int val; cin >> val;
            adjmat[i][j] = val;
         }
      }
      memo[(1<<size)-1] = 1;
      for (int j = (1 << size)-1; j >= 0; j--) {
         int idx = numbits(j);
         for (int k = 0; k < size; k++) {
            if (adjmat[idx][k] == 0 || (j & (1 << k))) continue;
            memo[j] += memo[j | (1 << k)];
         }
      }
      cout << memo[0] << "\n";
   }
   return 0;
}

30 comments:

  1. U can also use __builtin_popcount() function

    ReplyDelete
  2. The bottom-up idea for the Bitmask is really beautiful. I never thought like that before. Thanks.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. that is very nice post and very informative and knowledgeable post. So thank you for sharing with us.
    we have some related posts.
    visit here:- coursework help

    ReplyDelete
  5. Thank you for some other informative blog. Where else could I get that type of information written in such an ideal means? I have a mission that I’m just now working on, and I have been at the look out for such information. completed coursework

    ReplyDelete
  6. Are you looking for assignment help australia company? Don't worry, Student Assignment Help is here only for you to solve your problems to regard assignment help. We have 7+ years experienced experts, who holds expertise in different subjects. Student Assignment Help has some of the finest writers, who has years of expertise in assignment writing services.

    ReplyDelete
  7. thanks.. for explanation of bottom up approach
    does anybody has any idea to further optimize top down approach, since it is much easier to understand

    ReplyDelete
  8. Get Your best mba assignment writers in australia
    now. MyAssignmentHelp is the top most online service provider in Australia. We have the best expert writers in the industry. Every single one of our tutors has either a master or Ph.D. in their subject area. The MBA assignment help has been designed by taking into account the perspective of the students and the learners so that their learning process can be supported and they will be able to grasp the knowledge that comes their way. Contact or visit our website for further information .

    ReplyDelete
  9. Thank you for sharing such an informative article. foot massage increases the circulation in your feet and helps your blood and lymph systems carry away toxins. The very process of a foot massage sends messages to the rest of your body to relax. Massaging the feet targets the rest of the body. Visit Best Foot Massager for Diabetics for more.

    ReplyDelete
  10. I appreciate the effort you make to give out article like this. The number of students seeking urgent assignment is on the rise globally due to students receiving the urgent assignment from their professors but many scholars lacking the time needed to complete the tasks on an urgent basis. Urgent assignment help, therefore, results in many students failing to secure the complete the tasks on an urgent basis which results in the students seeking assignment help for the tasks from our professional assignment writing services. Go ahead and reach out to us for Timed Assignment help

    ReplyDelete
  11. A group called Satta king is an established one which has experienced satta players and they prefer to offer guidance to other people creating formula numbers and deviating people for trusting them. Most of the time Black Satta King is not trustworthy as they create false attractions and prevent the players from actually winning the game. Many of them have created online sources promising the upcoming satta players to follow certain tricks. Rarely some of them are reliable and one should also take guidance from experienced trustworthy sources whom they know before taking decision for the game.

    ReplyDelete
  12. If we talk about the gameplay of the black satta king online game. Well, once a player has finished betting and placing money on their favorable winning satta number. Now, all they have to do is to simply wait for the winning satta number to be announced by an authentic and legitimate satta organizing authority. Like the Satta king Results website where all the satta king players would certainly get online to see an overview of the number, they have priorly selected.

    ReplyDelete
  13. standard process is to use Zoom or Microsoft Teams to capture a speaker live and process this video feed in OBS. virtual edge and vitual gifts

    ReplyDelete
  14. Best assignment expert one of the leading writing service providers is now providing Writing assignment online help to every student. Our PhD experts and professionals are present 24/7 round the clock to aid students with these assignments

    ReplyDelete
  15. Help With My Assignment

    Get the best Help with the Best Assignment from the professional writers Help With My Assignment for Best Assignment Experts. We are committed and provide all academic assignment writing help.

    ReplyDelete
  16. Bellsouth Email Login AT&T Inc. converged with BellSouth on December 29, 2006, and the AT&T name was safeguarded. In the event that you made a BellSouth email represent your business, you can in any case utilize it to send and get messages. You can sign in to your BellSouth account from any Web program in the event that you know the right ID and secret word mix. Besides, you can add the BellSouth email record to email customers like Microsoft Office Outlook.

    ReplyDelete
  17. Get Professional Case Study Assignment HelpToday from Assignment studio. Our qualified academic case studies writers’ team provides writing help with all kind of case study and research papers

    ReplyDelete
  18. Hey friend, it is very well written article, thank you for the valuable and useful information you provide in this post. Keep up the good work! FYI, please check these depression, stress and anxiety related articles:
    Essay On Places related to Freedom Struggle , A radical awakening book review

    ReplyDelete
  19. If you have any doubt on how to get services forassignment help in your academic writing paper, then reach out to us and get help from our assignment helper.

    ReplyDelete
  20. This blog has enlightened me on what I suppose to know about. As a matter of fact, it has shown me the necessary steps I should take. You can still click here to see noun cut off mark for jamb

    ReplyDelete
  21. This blog is really an great web i like it the most
    Daily Contributors

    ReplyDelete
  22. I have bookmarked your website because this site contains valuable information. I am really happy with the quality and presentation of the articles. Thanks a lot for keeping great stuff. I am very much thankful for this site. Want to troubleshoot your keyboard problem then try The Free Online Keyboard Key Tester tool which helps you find out the health of your Keyboard in a matter of seconds.

    ReplyDelete
  23. Academic-Answers.net is a professional academic writing service dedicated to assist our clients achieve scholarly excellence. Our agency has a reputation of a trustworthy and caring writing service not only among customers but also among academic writers. Get Academic-Answers

    ReplyDelete
  24. This is an interesting one and I should add it to my collection. You did a great job! This must be a popular blog. Thank you for sharing this informative article. The following articles discuss How to butterfly click and aim. See my latest post Butterfly clicking about this.

    ReplyDelete
  25. This absolutely amazing, you got true and fresh information posted here, really found it useful, thanks for posting and the effort! Please keep sharing more of such blogs. coeikwo cut off mark for educational foundation

    ReplyDelete
  26. The piece of educative info is really nice and captivating. Your outcome is clear and understandable. I'm appreciating your effort for sharing. Visit us: cibn past questions and answers pdf format

    ReplyDelete
  27. How To Find An Appropriate Answer To What Time Does Cash App Direct Deposit Hit?
    Are you one of those who started using the direct deposit feature on their Cash App accounts to deposit paychecks on their cash App accounts? To determine the best possible solutions and the appropriate answer to clarify What Time Does Cash App Direct Deposit Hit, you don’t need to wander here and there as you have landed on the right place where you will be able to get assisted by a team of professionals who will assist you.

    ReplyDelete
  28. This comment has been removed by the author.

    ReplyDelete