Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is Yet Another Dynamic Programming Problem. No heuristics needed.</p> <p>At each <code>i</code> from <code>0</code> to <code>n</code>, by how far along you are to satisfying all currently open conditions, you need to track the minimum and maximum number of liars. (An open condition is something of the form, "From here to <code>j</code> I need <code>k</code> more liars.")</p> <p>If you have the solution for <code>i</code>, moving to <code>i+1</code> goes as follows for each partial solution that you have:</p> <ol> <li>Drop all conditions that you've reached and satisfied.</li> <li>Add all new conditions for this number. If a new condition conflicts with your existing solution, throw this partial solution away. Here are the rules for conflict between a condition saying that by <code>j</code> you need <code>k</code> liars and by <code>j'</code> you need <code>k'</code> liars with <code>j &lt;= j'</code>: <ol> <li>If <code>k &lt; k'</code> there is a conflict. (You can't have more liars by <code>j</code> and then less again by <code>j'</code>.</li> <li>If <code>j' - j &lt; k' - k</code> there is a conflict. (You can't add <code>k' - k</code> liars in <code>j' - j</code> soldiers.)</li> <li>Otherwise there is no conflict.</li> </ol></li> <li>If no condition say that by soldier <code>j</code> you need to add <code>j-i</code> liars, you can add for the current step a partial solution with the current soldier not being a liar. (By "add" here I mean "make sure this state is tracked, and update max/min as needed if it was not tracked".)</li> <li>If no condition says <code>0</code> additional soldiers by a future point, you can add for the current step a partial solution with the current soldier being a liar. (In this solution first alter the state to say that every condition needs one fewer liars - because you added one, then proceed as before.)</li> </ol> <p>Your starting condition is that with <code>i = 0</code>, there is <code>1</code> solution with <code>0</code> liars and absolutely no conditions.</p> <p>From the solution for <code>0</code> start generating partial solutions for <code>1</code>, <code>2</code>, ... , <code>n</code>. And when you reach <code>n</code> you have your answer.</p> <p>(Note, with a modest modification you can figure out not only what the max and min are, but exactly how many solutions there are.)</p>
    singulars
    1. This table or related slice is empty.
    1. POThe puzzle of Liars
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USbtilly
    1. USbtilly
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHey! Thanks for your reply! I guess using DP is the correct way. I'm trying to implement it now.
      singulars
      1. PO
      1. USzcb
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload