← 返回题目列表

Codeforces · 1089/H

H. 更难满足

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Harder Satisfiability - 原题 PDF 第 1 页
原题PDF第9页
可复制的 PDF 提取文本
ICPC 2018 2019, NEERC   Northern Eurasia Finals, Online Mirror
                         St. Petersburg   Barnaul   Tbilisi   Almaty, December 2, 2018
Problem H. Harder Satis ability

A fully quanti ed boolean 2-CNF formula is a formula in the following form: Q1x1 . . . Qnxn F(x1, . . . , xn).
Each Qi is one of two quanti ers: a universal quanti er ∀( for all ), or an existential quanti er ∃( exists );
and F is a conjunction (boolean AND) of m clauses s ∨t (boolean OR), where s and t are some variables
(not necessarily di erent) with or without negation. This formula has no free variables, so it evaluates to
either true or false. We can evaluate a given fully quanti ed formula with a simple recursive algorithm:

   1.  If there are no quanti ers, return the remaining expression's value of true or false.
   2. Otherwise, recursively evaluate formulas: Fz = Q2x2 . . . Qnxn F(z, x2, . . . , xn) for z = 0, 1.
   3.  If Q1 = ∃return F0 ∨F1; otherwise if Q1 = ∀return F0 ∧F1.

You are given some fully quanti ed boolean 2-CNF formulas. Find out if they are true or not.

Input

The  rst line of the input contains a single integer t (1 ≤t ≤105)   the number of test cases.
The  rst line of a test case contains two integers n and m (1 ≤n, m ≤105)   the number of variables and
the number of clauses in F. The next line contains a string s with n characters describing the quanti ers.
If si = `A' then Qi is a universal quanti er ∀, otherwise if si = `E' then si is an existential quanti er ∃.

Next m lines describe clauses in F. Each line contains two integers ui and vi (−n ≤ui, vi ≤n; ui, vi ̸= 0).
If ui ≥1 then the  rst variable in the i-th clause is xui. Otherwise, if ui ≤−1 then the  rst variable is
x−ui (negation of x−ui). The second variable in the i-th clause is similarly described by vi.
The sum of values of n for all test cases does not exceed 105; the sum of values of m does not exceed 105.

Output

For each test case output TRUE   if the given formula is true or FALSE  otherwise.

Example

             standard input                         standard output
 3                                       TRUE
 2 2                                     FALSE
 AE                                      FALSE
 1 -2
 -1 2
 2 2
 EA
 1 -2
 -1 2
 3 2
 AEA
 1 -2
 -1 -3

Note

The  rst sample corresponds to a formula ∀x1 ∃x2 (x1 ∨x2) ∧(x1 ∨x2) = ∀x1 ∃x2 x1 ⊕x2. For any x1 we
can choose x2 = x1 making it true, hence the formula is true.

The second sample changes the order of quanti ers. Now the answer is FALSE , because for any value of
x1 we can choose x2 = x1 and the formula becomes false.

The third formula is ∀x1 ∃x2 ∀x3 (x1 ∨x2) ∧(x1 ∨x3). If we substitute x1 = 1, x3 = 1 then no assignment
of x2 can make the second clause true, so the formula is false.



                                         Page 9 of 15