# Problem A – Loopy Tippy (Programming)

## Problem Description

**Background **As you may have learned in class, there is no known algorithm that is able to solve NP-complete problems in polynomial time (yet). However, these problems still happen a lot in real life^{[1]}. One method of solving these problems is to encode them into SAT, i.e., boolean satisfiability problems, and apply existing solvers^{[2]}. There are several benefits to this approach, such as being able to take advantage of existing, highly optimized solvers, and having more flexibility than domain-specific solvers.

### Story

I have coined a truly remarkable story about WillyPillow and Chino which this margin is too small to contain.

### Problem Formulation

You are given a Slitherlink^{[3]} puzzle and *Cryptominisat5*, a CNF-SAT solver (for which the details are given below). Please solve the puzzle by translating it to CNF-SAT and applying the solver.

In essence, the rules of the puzzle are as follows: you are given a rectangular grid, with each square possibly containing a number. The objective is to color a subset of the edges so that the following conditions are satisfied:

- If a square contains a number, the number of colored edges around it needs to be equal to the given number.
- The set of colored edges forms exactly one simple loop.

You can try the puzzle out here^{[4]} or (a harder version) here^{[5]}.

### Input Format

The first line contains two integers *r *and *c*, denoting the numbers of rows and columns of the board, respectively. *r *lines follow, where each line contains *c *characters representing the board. A character, “.”, corresponds to a square without a number. Note that the given puzzle is guaranteed to have a unique solution.

In addition, since it may be hard to predict the needed time for solving your SAT encoding, it is guaranteed that the puzzles in the subtasks 1 through 5 are sampled from this archive^{[6]}. However, due to a large number of the released test cases, **the upload quota is limited to 5 times a day **to ease the burden on the judge server.

**EDIT: **It is guaranteed that there is at least one non-zero number on the board.

**Subtask 1, 6 (10% each)**

- (
*r,c*) = (3*,*3)

**Subtask 2, 7 (10% each)**

- (
*r,c*) = (7*,*7)

**Output Format**

**Subtask 3, 8 (10% each)**

- (
*r,c*) = (10*,*10)

**Subtask 4, 9 (10% each)**

- (
*r,c*) = (15*,*15)

**Subtask 5, 10 (10% each)**

- (
*r,c*) = (20*,*20)

### Bonus (0%)

*r,c*≤ 128

Please print a binary string with (2*rc *+ *r *+ *c*) characters, denoting the answer to the puzzle. The following order shows an example of *r *= 1*,c *= 5. The *i*-th character in your output indicates whether the edge at location *i *is filled. Specifically, a character “1” denotes that the edge is filled and 0

otherwise.

**Sample Input **The human-readable solution to this board is

as follows:

7 7

…..3.

22.3..2

32….2 +-+-+-+-+-+ +-+ .3..2.3 |. . . . .|3|.|

3…..2 +-+-+-+-+ +-

.3132.2 2 2 . 3|. . 2|

3…..3 +-+-+-+-+ +-+-

|3 2 . . .|. 2

**Sample Output **+-+-+ +-+ +-+-

. 3|.|.|2 . 3|

1111101100001111111010000010 ^{+-+-+ + +-+ +-+}

0111110111000010011010110011 ^{|3 . .|. .|.|2}

1001110010110010110110100000 ^{+-+-+ +-+ + + +}

1011101101001100101011110011 ^{. 3|1 3|2|.|2}

+-+-+ +-+ + +-

(Line breaks added only for clarity; please out- |3 . .|. .|. 3| put the string in one single line.) +-+-+-+ + +-+-+ **Environment**

*Cryptominisat5*^{[7]} is installed on the judge server. Instructions about how to use it can be found on its website. It is recommended that you install the library locally for testing.

On the CSIE workstations, the library (and the cryptominisat5 binary) should be already installed. **Note that you need to compile your program with the flag **-lcryptominisat5**.**

On systems with the proper dependencies (most notably, make and cmake) installed, you can build *Cryptominisat5 *and compile your program with it by following this screencast^{[8]}.

However, if you have difficulty installing the library, we also provide the following alternative:

Please paste the provided header^{[9]} at the beginning of your source file. The following functions are then provided:

- void sat::Init(int n): Initialize the solver with n
- void sat::AddClause(std::vector
*<*int*>*v): Add a CNF clause that consists of the variables in v. Note that negative numbers denote the negation of a variable (e.g., {1, -2} ⇐⇒ (*x*_{1 }∨ ¬*x*_{2})), and thus the variable numbering has to start from 1. - bool sat::Solve(): Solve the given clauses. Returns true if a solution is found and false otherwise.
- int sat::GetResult(int id): Get the result of the variable id after calling Solve(). Returns 1 if the variable is true, −1 if it is false, and 0 if it is indeterminate.

If the macro DIMACS is *not *defined, the library merely redirects your calls to *Cryptominisat*. However, if it is defined, then Solve() writes your clauses to out.dimacs in DIMACS format^{[10]} and terminates the program. You can then feed the file to other solvers with standalone binaries, such as *Cryptominisat5*^{[11]}, *Microsat*^{[12]}, *Minisat*^{[13]}, *Glucose*^{[14]}, *Lingeling*^{[15]}, or even browser-based solvers like *Minisat.js*^{[16]}.^{[17]}

## Hints

- Tseytin transformation
^{18} - Truth table ⇐⇒ CNF
- Incremental SAT
^{[18]} - Flood fill
- https://codingnest.com/modern-sat-solvers-fast-neat-underused-part-1-of-n/
- It is possible to solve this
*without*using the solver, but I doubt that it is easier 🙂

# Problem B – Reachability Coefficient (Programming)

## Problem Description

For two sets *X *and *Y *, we define:

You are given a directed acyclic graph *G*, and for each vertex *v*, let *S*(*v*) be the set of vertices that are reachable from *v *(vertex *u *is reachable from vertex *v *if there exists a simple path from *v *to *u*). *Q *queries in the form of *u _{i},v_{i }*are specified, where

*u*and

_{i }*v*are vertices in

_{i }*G*. You need to answer

*f*(

*S*(

*u*)

_{i}*,S*(

*v*)), for all given queries.

_{i}You are not asked to find the **exact **ratio. Instead, your answer is considered correct if the **absolute error **does not exceed 0*.*1.

## Input

The first line of the input contains three integers *N,M,Q*, representing the number of vertices, the number of edges, and the number of queries, respectively. *M *lines follow, the *i*-th of which contains two integers *u _{i},v_{i}*, representing a directed edge from the vertex

*u*to the vertex

_{i }*v*.

_{i}*Q*lines follow, the

*i*-th of which contains two integers

*u*, representing a query on the vertex

_{i},v_{i}*u*and the vertex

_{i }*v*.

_{i}- 1 ≤
*N*≤ 2 × 10^{5} - 0 ≤
*M*≤ 3 × 10^{5} - 1 ≤
*Q*≤ 2 × 10^{5}

## Output

Print the answer to each query. Your answer can be considered correct if the *absolute error of it to the actual answer does not exceed *0*.*1.

### Test Group 0 (20 %)

- 1 ≤
*N,Q*≤ 1000 - 0 ≤
*M*≤ 5000

**Test Group 1 (80 %)**

- No other constraints

## Sample Input 1

6 7 5

1 2

- 3
- 3
- 4
- 5

3 5

5 6

- 3
- 4

1 6

5 5

2 5

## Sample Output 1

0.666666666667

0.600000000000

0.166666666667

1.000000000000

0.400000000000

## Hints

- Read the problem statement carefully.
- Read the output section carefully.

# Problem C – Yet Another Permutation Problem (Programming) (15 points)

## Problem Description

Let *S _{N }*be the set of all permutations of length

*N*. Let

*M*be the set of all 0-1 matrices of size

_{N }*N*×

*N*. We define

*f *: *S _{N }*×

*M*→

_{N }*M*

_{N}with *f*(*p,A*)* _{i,j }*=

*A*

_{p}

_{i}*,p*. That is, the function

_{j}*f*interchanges the rows (as well as the columns) of matrix

*A*according to the permutation

*p*.

Let *g*(*A*) be the maximum size of the submatrix *B *of *A *∈ *M _{N }*containing only 1’s such that the diagonal of

*B*lies on the diagonal of

*A*. Formally speaking,

*g*(

*A*) is the maximum

*r*(0 ≤

*r*≤

*N*) such that there exists 1 ≤

*i*≤

*N*−

*r*+ 1 with the following property:

*A _{xy }*= 1

*,*for all

*i*≤

*x,y*≤

*i*+

*r*− 1

Given a *N *×*N *0-1 matrix *A*, please find a permutation *p *∈ *S _{N }*such that

*g*(

*f*(

*p,A*)) is maximized.

## Input

The first line of the input contains an integer *N*, indicating the size of the matrix *A*. *N *lines follow, the *i*-th of which contains a string of length *N*, denoting the *i*-th row of the matrix *A*.

- 1 ≤
*N*≤ 120 *A*∈ {0_{ij }*,*1}

Test Group 0 (10 %)• 1 ≤ N ≤ 8Test Group 1 (10 %)• 1 ≤ N ≤ 20 |
Test Group 2 (50 %)• 1 ≤ N ≤ 80Test Group 3 (30 %)• No other constraints. |

**Output**

Print the optimal permutation *p*. If there are more than one solutions, any of which will be accepted.

## Sample Input 1

3

101

000

101

**Sample Output 1**

1 3 2

# Problem D – Hex (Programming)

## Problem Description

In this problem, you need to play the game, hex, with the computer. Please read Wikipedia for the rules^{[19]}. In this problem, the **pie rule **(or **swap rule**) is not used.

To try the game online, you can use this site^{21}. (Make sure to uncheck **swap rule **first.)

a 11×11 Hex Board that blue wins

To solve this problem, you need to write a program to play with ours. Your program will be accepted if you win *Y *rounds out of a total of *X *rounds. You are always the first player.

In your program, you only need to implement two functions:

- void init(int n): Start a new game with a nxn board
- std::pair<int, int> decide(std::pair<int, int> p): Decide your move. p is the last move by the opponent. If it is the first move, p would be {-1, -1}. The function should return the position you plan to put you color.

The position on the board is represented by a pair(std::pair<int, int> p), where p.first is the index (starting from 0) of the row and p.second is the index (starting from 0) of the column.

## Example Files

You can download a random sample solution and hex.h at: https://cool.ntu.edu.tw/courses/ 368/files/folder/Homework/Homework4%20Hex

The hex.h file would connect to our server, which is the same AI as the judge. So please send your solution to the judge only if the program already runs correctly at local. **You have a very limited quota per day!**

To compile sample files on Windows, you need to add -lws2_32 in the compiler options.

the index of grids on a board

## Input Limits

- 1 ≤
*X*≤ 20 - 1 ≤
*Y*≤*X* - 3 ≤ n ≤ 11
- 0 ≤ first, q.second
*<*n

### Test Group 0 (0 %)

### Test Group 1 (20 %)

### Test Group 2 (20 %)

### Test Group 3 (30 %)

### Test Group 4 (15 %)

### Test Group 5 (15 %)

# Problem E – Magic Wands Linking (Hand-Written) (25 points)

Have you seen *Harry Potter*? It is a fantasy story about wizards and magic. Every wizard has a magic wand, and there is a **fitness **value (which is always non-negative) between every pair of wands.

In the fantasy world, there are many phenomenal professors who teach at Hogwarts. Recently, one of the professors invented a new technology called **Magic Wands Linking**, which can greatly enhance the power of wizards. By linking two wands through the technology, both owners can increase their power by the fitness value between the two wands. For example, if a wand *w*_{1 }is linked to another wand *w*_{2}, and the fitness between *w*_{1 }and *w*_{2 }is 10, then both the power of *w*_{1 }and *w*_{2 }is enhanced by 10; the power of the Wizarding World is enhanced by 20 in total. Note that two wands can be linked even if their fitness is 0, but such a linking has no effect on their power. Also, a wand can be linked to more than one wand, and the power enhanced can be accumulated.

However, the technology is not yet mature. The links between the wands should follow the rules below:

**RULE1**There are three attributes of magic wands,**none**,**light**, and**dark**. Initially, all wands are unlinked and have the attribute**none**. If a wand*w*_{1 }is linked to another wand*w*_{2}, then the two wands must be assigned two opposite attributes,**light**and**dark**. (A wand can only be assigned an attribute once.)**RULE2**To maintain the balance of the Wizarding World, the number of light wands and the number of dark wands should be the same.

Given *N *magic wands ({*w*_{1}*,w*_{2}*,…,w _{N}*}) and

*M*fitness values, can you help the wizards to find the maximum power they can enhance in total? For all of the following questions, you can assume that

*N*

**is even,**

**, and the fitness values are always non-negative**.

- (4pts) Please solve two problems below.
- (2pts) Assume that:

N = 4 ({*w*_{1}*,w*_{2}*,w*_{3}*,w*_{4}}),

M = 6 ({(*w*_{1}*,w*_{2}*,*5)*,*(*w*_{1}*,w*_{3}*,*1)*,*(*w*_{1}*,w*_{4}*,*8)*,*(*w*_{2}*,w*_{3}*,*1)*,*(*w*_{2}*,w*_{4}*,*7)*,*(*w*_{3}*,w*_{4}*,*4)}).

(*w*_{1}*,w*_{2}*,*5) means that the fitness between *w*_{1 }and *w*_{2 }is 5.

Under RULE1 and RULE2, what is the maximum power they can enhance in total?

Please provide the linking method as well.

- (2pts) Following the question (1-1), now assume that we can temporarily
**ignore RULE2**. That is,*N*is still an even number, but the numbers of light wands and dark wands can be different. What is the maximum power they can enhance in total? Please provide the linking method as well.

- (9pts) Please solve two problems below.
- (4pts)
**Maximum Cut Problem**:

- (4pts)

For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the Maximum Cut Problem. Assuming that Maximum Cut Problem is NP-hard, prove the following problem is NPhard:

**Ignore RULE2**, given *N *magic wands and *M *fitness values, find a linking method to enhance the maximum power in total.

- (5pts)
**Ignore RULE2**, given*N*magic wands and*M*fitness values, now consider an approximation algorithm below:

Define *M _{i }*= {

*fitness of*(

*w*) |

_{k},w_{i}*k < i*},

*W*

_{1 }and

*W*

_{2 }as two sets of wands. Initially, set

*W*

_{1 }= {

*w*

_{1}}

*,W*

_{2 }=

*φ*. Then for each

*i*from 2 to

*N*, add

*w*to either

_{i }*W*

_{1 }or

*W*

_{2}, and link

*w*to all wands in the other set, such that the power enhanced in

_{i }*M*is maximized.

_{i }Prove that the above algorithm is a 2-approximation.

- (5pts) Now,
**under both RULE1 and RULE2**above, assuming that Maximum Cut Problem and the question (2-1) are NP-hard, prove that the following problem is NP-hard:

Given *N *magic wands and *M *fitness values, find a linking method to enhance the maximum power in total.

- (4pts) The professor who invented Magic Wands Linking realizes that the total power enhanced by linking wands can not be too large, or the Wizarding World will crash due to the power storm! Thus, now he wants to know the minimum power that can be enhanced in total when every wand has at least one linking, and all light wands are linked to all dark wands, so that he can evaluate the feasibility of Magic Wands Linking. However, the problem is harder than he thought.

Formally speaking, assuming that Maximum Cut Problem, the question (2-1), and the question (3) are NP-hard, please help him prove that the problem below is NP-hard:

Under both RULE1 and RULE2 above, given *N *magic wands and *M *fitness values, find a linking method such that **for each wand ***w***, there exists at least one link to ***w***, and all light wands are linked to all dark wands**, but the total enhanced power is minimized.

- (3pts) One week after all magic wands are linked, the Dementors attack Hogwarts suddenly!

In order to send wizards to the battlefield, they use two teleportation spells. However, teleportation takes time, so it is better to distribute the wizards evenly to the two spells.

Thus, the problem is:

Assuming that there are *N *wizards, given *N *non-negative integers (*t*_{1}*,t*_{2}*,…,t _{N}*) indicating the time each wizard takes to teleport, please determine whether there is a subset whose sum equals

*N *to ^{P }*t _{i}/*2.

*i*=1

Please reduce the **Subset Sum Problem**^{[20]} to the problem above in polynomial time.

# Problem F – Band Dream (Hand-Written)

Kasumi is the leader of the band Poppin’ Party. Because it is the fifth year since Poppin’ Party was created, she wants to create a new song containing continuous melodies of the songs that Poppin’ Party has released before.

For example, if there are two melodies **Do, Re, Mi **and **Mi, Re, Do**. Then **Do, Re, Mi, Re, Do **contains two sub-melodies above but **Do, Re, Do, Mi, Re, Do **does not contain the sub-melody **Do, Re, Mi**.

Because she does not know how to minimize the length of the new song, she wants us to find a song that is *short enough *in polynomial time.

(1) To solve this problem, we introduce another problem called **Set Cover Problem **and one of its approximate algorithms.

Given a universe of *n *elements *X *and a collection of *m *subsets *F *= {*S*_{1}*,S*_{2}*,…,S _{m}*}, where

*S*⊂

_{i }*X*for each

*S*∈

_{i }*F*. Each

*S*has a

_{i }**positive**cost, denoted as cost(

*i*). The goal is to find a sub-collection

*C*⊂

*F*of the minimum total cost that covers

*X*, assuming one exists.

**Algorithm 1: **GreedySetCover(X, F)

*C*←− ∅- Order
*X*as {*x*_{1}*,x*_{2}*,…,x*} by the order in which they were covered by the algorithm. If there is more than one element covered in the same iteration, order them arbitrarily. Please show that for each_{n}*k*∈ {1*,*2*,…,n*}*,*price(*x*)_{k}^{≤ }_{n}^{OPT}_{−k+1}, where OPT is the cost of the optimal cover. (4 points) - Please show that the above algorithm is in polynomial time, and it will obtain a (ln n +
*O*(1))-approximate solution. You can use the result of (1-1) even if you are not able to prove it. (3 points)

- Order
- The problem that Kasumi wants to solve can be modelled as below: Given a finite set of alphabet Σ, and a set of
*n*strings*M*= {*M*_{1}*,M*_{2}*,…,M*}, where each_{n}*M*∈ Σ_{i }^{∗}. WLOG, assume there is no*M*is sub-string of_{i }*M*, for_{j}*i*6=*j*. Find the shortest string*C*that contains all sub-strings*M*∈_{i }*M*. To make things easier, if a string*s*is a prefix of the string*y*, and a string*t*is a suffix of the string*y*, and**len**(*s*) +**len**(*t*)*>***len**(*y*), we can call*y*a possible**merge**of*s*and*t*. For example, “abbbc” and “abbbbc” are possible**merge**s of “abbb” and “bbc”, while “abbbbbc”, “abbbbbbc” are all not possible**merge**- Please show that we can reduce Kasumi’s problem to Set Cover Problem mentioned at the problem (1) in polynomial time, by picking
**all strings**and**all possible merges of each pair of strings**in*M*as the collection*F*of subsets. You can consider that the length of each string is not more than a constant*l*. Notice that some**merge**s may contain more than two sub-strings, and this reduction is actually a 2-approximate reduction. (6 points) - Please show that the solution in (2-1) will obtain a (2 ln n +
*O*(1))-approximate solution.

- Please show that we can reduce Kasumi’s problem to Set Cover Problem mentioned at the problem (1) in polynomial time, by picking

You can use the result of (1-2) even if you are not able to prove it. (7 points)

[1] E.g., *lock-chart solving *and *dependency management*.

[2] Usually based on conflict-driven clause learning (https://en.wikipedia.org/wiki/Conflict-driven clause learning), a fascinating algorithm worth reading about.

[3] https://en.wikipedia.org/wiki/Slitherlink

[4] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/loopy.html

[5] https://kwontomloop.com/

[6] https://www.csie.ntu.edu.tw/~b07902134/ada-19hw4p1-public.zip

[7] https://www.msoos.org/cryptominisat5/

[8] https://asciinema.org/a/oRbZ9UjnWL36RfEZocJYmCyVZ

[9] https://gist.github.com/WillyPillow/a5b4f12faefd66c7ce42690668c002b5

[10] https://en.wikipedia.org/wiki/Boolean satisfiability problem#SAT problem format

[11] Binaries for Windows and Linux can be found at https://github.com/msoos/cryptominisat/releases.

[12] https://github.com/marijnheule/microsat

[13] http://minisat.se/

[14] https://www.labri.fr/perso/lsimon/glucose/

[15] http://fmv.jku.at/lingeling/

[16] http://jgalenson.github.io/research.js/demos/minisat.html

[17] Other solvers can be found at https://en.wikipedia.org/wiki/Boolean satisfiability problem#External links. 18

https://en.wikipedia.org/wiki/Tseytin transformation

[18] https://baldur.iti.kit.edu/sat-competition-2016/index.php?cat=incremental

[19] https://en.wikipedia.org/wiki/Hex (board game)#Game play ^{21}http://www.lutanho.net/play/hex.html

[20] Given *n *non-negative integers (*a*_{1}*,a*_{2}*,…a _{n}*) and a positive integer

*W*, the Subset Sum Problem seeks whether there is a subset whose sum equals to

*W*. The Subset Sum Problem is known to be NP-hard.

## Reviews

There are no reviews yet.