[ GYM Tutorial ] 2016 ACM Amman Collegiate Programming Contest

Revision en1, by Hasan0540, 2017-01-02 16:57:24

Hello Everyone,

This tutorial should have been published 3 months ago, but I only got some free time to write it today, sorry for that.

A. Coins

Instead of having one DP table that combines all states for both Hasan and Bahosain, and having too many parameters (and therefore, huge complexity), we can build two tables, one for each person.

Let A[0][i] be the number of ways in which Hasan can pay i dollars using all coins from index 0 to the end, and B[0][i] similar but for Bahosain, then we can compute the final answer by using these two tables as follows:

for (int hasan = 0; hasan <= W; ++hasan) { int bahosain = W — hasan; if (abs(hasan — bahosain) <= K) res += A[0][hasan] * B[0][bahosain]; }

Building each table is a simple DP problem.

The Little Match Girl

Instead of trying to move some sticks as the problem suggests, let's count the total number of matchsticks we have and build the maximum possible number of N digits using all these sticks.

We can fill the N digits starting from the left using a simple greedy algorithm. We try to put 9 in the current digit if it is possible to to fill the remaining digits with the remaining sticks, if that's not possible, we try 8, then 7 and so on...

How do we check if it's possible to fill X digits using Y sticks? The digit 1 requires two sticks, so Y should be at least 2X to be able to fill all the digits with at least two sticks. Also, since we can't fill a digit with more than 7 sticks (the digit 8), Y should not exceed 7X, otherwise we will have some unused sticks at the end.

Digit 3 requires one more stick than 1, digit 4 requires two more, digit 5 requires 3 more, and digit 6 requires 4 more. So the conditions Y >  = 2X and Y <  = 7X are sufficient as we can use any remaining number of sticks to fill one digit that is not 8.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English Hasan0540 2020-07-21 13:39:02 0 (published)
en12 English Hasan0540 2020-07-21 13:37:58 440
en11 English Hasan0540 2017-01-02 18:55:26 3 Tiny change: '$\n\n### [The Little' -> '$\n\n### [B. The Little'
en10 English Hasan0540 2017-01-02 18:52:23 1
en9 English Hasan0540 2017-01-02 18:50:37 772
en8 English Hasan0540 2017-01-02 18:36:18 497
en7 English Hasan0540 2017-01-02 18:28:46 2238
en6 English Hasan0540 2017-01-02 17:27:10 246
en5 English Hasan0540 2017-01-02 17:23:25 226
en4 English Hasan0540 2017-01-02 17:18:47 1056
en3 English Hasan0540 2017-01-02 17:03:32 28
en2 English Hasan0540 2017-01-02 17:02:37 14
en1 English Hasan0540 2017-01-02 16:57:24 2107 Initial revision (saved to drafts)