text:
# Practical Scalability for Stackelberg Security Games

Stackelberg Security Games (SSGs) have been adopted widely for modeling adversarial interactions. With increasing size of the applications of SSGs, scalability of equilibrium computation is an important research problem. While prior research has made progress with regards to scalability, many real world problems cannot be solved satisfactorily yet as per current requirements; these include the deployed federal air marshals (FAMS) application and the threat screening (TSG) problem at airports. Further, these problem domains are inherently limited by NP hardness shown in prior literature. We initiate a principled study of approximations in zero-sum SSGs. Our contribution includes the following: (1) a unified model of SSGs called adversarial randomized allocation (ARA) games that allows studying most SSGs in one model, (2) hardness of approximation results for zero-sum ARA, as well as for the sub-problem of allocating federal air marshal (FAMS) and threat screening problem (TSG) at airports, (3) an approximation framework for zero-sum ARA with provable approximation guarantees and (4) experiments demonstrating the significant scalability of up to 1000x improvement in runtime with an acceptable 5

• 17 publications
• 3 publications
• 2 publications
• 50 publications
07/16/2022

### A Survey of Decision Making in Adversarial Games

Game theory has by now found numerous applications in various fields, in...
04/29/2021

### Computing Possible and Necessary Equilibrium Actions (and Bipartisan Set Winners)

In many multiagent environments, a designer has some, but limited contro...
10/05/2021

### Robustness and sample complexity of model-based MARL for general-sum Markov games

Multi-agent reinfocement learning (MARL) is often modeled using the fram...
06/17/2021

### Multi-Agent Training beyond Zero-Sum with Correlated Equilibrium Meta-Solvers

Two-player, constant-sum games are well studied in the literature, but t...
11/20/2019

### Solving Online Threat Screening Games using Constrained Action Space Reinforcement Learning

Large-scale screening for potential threats with limited resources and c...
02/17/2021

### Provably Efficient Policy Gradient Methods for Two-Player Zero-Sum Markov Games

Policy gradient methods are widely used in solving two-player zero-sum g...
03/14/2022

### Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limits

An ideal strategy in zero-sum games should not only grant the player an ...

## 1 Introduction

The Stackelberg Security Game (SSG) model (and variants) has been widely adopted in literature and in practice to model the defender-adversary interaction in various domains [Tambe2011, Jiang et al.2013, Blum, Haghtalab, and Procaccia2014, Guo et al.2016, Blocki et al.2013, Basilico, Gatti, and Amigoni2009, Munoz de Cote et al.2013]. Over time SSGs have been used to model increasingly large and complex real world problems, hence an important research direction in SSGs is the study of scalable Strong Stackelberg Equilibrium (SSE) computation algorithms, both theoretically and empirically. The scalability challenge has led to the development of a number of novel algorithmic techniques that compute the SSE of SSGs (see related work).

However, scalability continues to remain a pertinent challenge across many SSG applications. There are real world problems that even the best known approaches fail to scale up to, such as threat screening games (TSGs) and the Federal Air Marshals (FAMS) domain. The TSG model is used to allocate screening resources to screenees at airports and solves the problem for every hour (24 times a day). Yet, recent state-of-the-art approach for airport threat screening [Brown et al.2016] (TSG) scales only up to 110 flights per hour whereas 220 flights can depart per hour from the Atlanta Airport [FAA2014]. The FAMS problem is to allocate federal air marshals to US based flights in order to protect against hijacking attacks. Again, the best optimal solver for FAMS in literature [Jain et al.2010] solves problems up to 200 flights (FAMS is an already deployed application), whereas on average 3500 international flights depart from USA daily [USDOT2016]. Further, these problems are fundamentally limited by the hardness of computing the exact solution.

To overcome the computational hardness, and also provide practical scalability we investigate approximation techniques for zero-sum SSGs. Towards that end, our first contribution in this paper is a unified model of SSGs that we name adversarial randomized allocation (ARA) games. ARA captures a large class of SSGs which we call linearizable SSGs (defined later) and it includes TSGs and FAMS. Further, the ARA model provides a unified characterization of implementability of marginal strategies that has been studied in separate papers in literature.

Our second contribution is a set of hardness of approximation results for the class of zero-sum ARA problems, and also for sub-classes such as TSGs. For ARA, we show that the ARA equilibrium computation problem and the defender best response problem in the given ARA game have the same hardness of approximation property and in the worst case ARA is not approximable. Further, we show that even the restricted set of ARA problems given by FAMS and TSGs are both hard to approximate to any logarithmic factor.

Our third contribution is a general approximation framework for finding the SSE for zero-sum ARAs. As an application, we demonstrate the use of this framework for FAMS and TSGs. The approximation approach combines techniques from dependent sampling [Tsai et al.2010]

with domain specific heuristics to yield simple to implement approximation algorithms. We provide theoretical approximation bounds for both FAMS and TSGs.

Finally, as our fourth contribution, we demonstrate via experiments that we can solve FAMS problem up to 3500 flights and TSG problems up to 280 flights with runtime improvements up to 1000x. Moreover, the loss for FAMS problems is less than 5% with increasing flights and for TSGs is less than 1.5% across all cases. Hence, our results provide a practical and simple framework for approximating zero-sum SSGs (more generally ARAs) with provable approximation guarantees. Moreover, our approach enables solving the real world FAMS and airport screening problem satisfactorily for a US wide deployment. All full proofs are in the Appendix.

## 2 Related Work

Two major approaches to scale up in SSGs include incremental strategy generation (ISG) and use of marginals. ISG uses a master slave decomposition, with the slave providing a defender or attacker best response [Jain et al.2010]. All these approaches are fundamentally limited by the computational complexity of finding an exact solution [Korzhyk, Conitzer, and Parr2010, Xu2016] and thus in some cases ISG has included approximation of defender/attacker best responses [Guo et al.2016, Gan, An, and Vorobeychik2015]. Use of marginals and directly sampling from marginals while faster suffers from the issue of non-implementable (invalid) marginal solutions [Kiekintveld et al.2009, Tsai et al.2010]. Fixing the non-implementability again runs into complexity barriers [Brown et al.2016]. Combinations of marginals and ISG approaches [Bošanský et al.2015] and gradient descent based approach [Amin, Singh, and Wellman2016] have also been used. Our study stands in contrast to these approaches as we aim to approximate the SSE and not compute it exactly, providing a viable alternative to ISG and bypassing the non-implementability of marginals approach. Another line of work uses regret minimization and endgame solving techniques [Moravčík et al.2017, Brown and Sandholm2017] for approximately solving large scale sequential zero sum games. Our game does not have a sequential structure and the large action space ( for TSG and for FAMS; see appendix for the calculation) precludes using a standard no-regret learning approach.

Our approximation approach is inspired by randomized rounding (RR) [Raghavan and Thompson1987]. However, distinct from standard RR, our problem has equality constraints. Previous work on RR with equality constraints address only equality constraints [Gandhi et al.2006] or works on obtaining an integral solution given an approximate fractional solution within a polyhedron with integral vertices [Ageev and Sviridenko2004, Chekuri, Vondrák, and Zenklusen2009]. However, our initial fractional solution may not lie in an integral polyhedron, and we have both equality and inequality constraints. Thus, we provide an approach that exploits the disjoint structure of equality constraints in TSGs in order to use previous work on comb sampling [Tsai et al.2010] and then alters the output [Bansal et al.2012] to handle both equality and inequality constraints.

While there exists other hardness of approximation results for other Stackelberg security game like models [Guo et al.2016] that rely on the graph characteristics of those domains, our hardness of approximation results are the first such results for the simple FAMS and the recent TSG security games problem.

## 3 Model and Notation

We present a general abstract model of adversarial randomized allocation (ARA). ARA captures all linearizable

SSGs, which is defined as those in which the probability

of defending a target is linear in the defender mixed strategy. The ARA game model is a Stackelberg game model in which the defender moves first by committing to a randomized allocation and the adversary best responds. We start by presenting the defender’s action space. There are defense assets that need to be allocated to objects to be defended. In this model, assets and objects are abstract entities and do not represent actual resources and targets in a security games. We will instantiate this abstract model with concrete examples of FAMS and TSG in the following sub-sections.

Defender’s randomized allocation of resources: The allocation can be represented as a matrix with the entry denoting the allocation of asset to object , and each . There is a set of assignment constraints on the entries of the matrix. Each assignment constraint is characterized by a set of indexes of the matrix and the constraint is given by , where are non-negative integers. We will refer to each assignment constraint as

. Also for sake of brevity, we denote the vector of all the entries in the matrix as

and as .

Pure strategies of the defender are integral allocations that respect the assignment constraints, i.e., integral ’s such that for all assignment constraints . See Figure 1 for an illustrative example of the assignment constraints and a valid pure strategy. Let the set of pure strategies be and we will refer to a single pure strategy as . On the other hand, the space of marginal strategies are those ’s that satisfy the assignment constraints for all ; note that marginal strategies need not be integral.

Mixed strategies are probability distributions over pure strategies, e.g., probabilities

() over pure strategies . An expected (marginal) representation of a mixed strategy is . Thus, the space of mixed strategies is exactly the convex hull of , denoted as . Typically, the space of marginal strategies is larger than , i.e., , hence all marginal strategies are not implementable as mixed strategies. The conditions under which all marginal strategies are implementable (or not) has an easy interpretation in our model (see the implementability results later in this section).

Adversary’s action: The presence of an adversary sets our model (and SSGs) apart from a randomized allocation problem [Budish et al.2013] and makes ARA a game problem. The attacker’s action is to choose a target to attack. In our abstract formulation a target is given by a set of indexes of the allocation matrix. In order to capture linearizable SSGs, the probability of successfully defending an attack on target is where ’s are given constants such that . The constraint on ensures that . We assume the total number of targets in polynomial in the size of the allocation matrix. Then, as is standard for SSGs, the defender utility for defender strategy and attacker strategy is given by the expected value

 Ud(x,t)=ctUts+(1−ct)Utu

where (resp. ) is the defender’s utility when target is successfully (resp. unsuccessfully) defended. As we restrict ourselves to zero-sum games, the attacker’s utility is negation of the above111We remark that modeling-wise the extension to general-sum case, non-linearity in probabilities or exponentially many targets is straightforward; here we restrict the model as it suffices for the domains we consider. See online appendix for the extension..

The problem of Strong Stackelberg equilibrium computation can be stated as: subject to and , where the last constraint represents . Note that the inputs to the SSE problem are the assignment constraints, and the number of pure strategies can be exponential in this input. Thus, even though the above optimization is a LP, its size can be exponential in the input to the SSE computation problem. However, using the marginal strategies instead of the mixed strategies results in a polynomial sized :

 maxx,z,ctzsubject toz≤U(x,t)∀tns≤x[S]≤NS∀S and xi,j≥0∀i,j

But, as stated earlier , and hence the solution to the optimization above may not be implementable as a valid mixed strategy. In our approximation approach we will solve the above as the first step obtaining marginal solution .

Bayesian Extension222Typically player types denotes different utilities but as Harsanyi harsanyi1967games originally formulated, types capture any incomplete information including, as for our case, the lack of information about the action space of adversary. The game is still zero-sum.: We also consider the following simple extension where we consider types of adversary and each adversary type attacks a set of targets such that for all . The adversary is of type with probability (). Then, the exact SSE optimization can be written as: subject to and . A corresponding can be defined in exactly the same way as for original ARA. Next, we show how the FAMS and TSG domain are instances of this abstract ARA model and Bayesian ARA respectively.

Implementability: Viewing the defender’s action space as a randomized allocation provides an easy way to characterize non-implementability of mixed strategies across a wide range of SSGs, in contrast to prior work that have identified non-implementability for specific cases [Korzhyk, Conitzer, and Parr2010, Letchford and Conitzer2013, Brown et al.2016] . The details of this interpretation can be found in the Appendix.

### 3.1 Fams

We model zero-sum FAMS in the ARA model. The FAMS problem is to allocate federal air marshal (FAMS) to flights to and from US in order to prevent hijacking attacks. The allocation is constrained by the number of FAMS available and the fact that each FAMS must be scheduled on round trips that take them back to their home airport. Thus, the main technical complication arises from the presence of schedules. A schedule is a subset of flights that has to be defended together, e.g., flight f1 and f2 should be defended together as they form a round trip for the air marshal. Air marshals are allocated to schedules, no flight can have more than one air marshal and some schedules cannot be defended by some air marshals. The adversary attacks a flight.

Then, we capture the FAMS domain in the above model by mapping schedules in FAMS to objects (on columns) and air marshal in FAMS to assets (on rows). See Figure 1 for an illustrative example. The assignment constraints include the constraint for each resource : , which states that every resource can be assigned at most once. If an air marshal cannot be assigned to schedule then add the constraint . A target in the abstract model maps to a flight in FAMS, and the set are all the indexes for all schedules that include this flight: flight f is in schedule . The constraint that a flight cannot have more than one air marshal is captured by adding the target allocation constraint . The probability of defending a target (flight) is , hence the weights ’s in ARA are all ones.

### 3.2 Tsg

We model TSGs using the Bayesian formulation of ARA. The TSG problem is how to allocate screening resources to screenees in order to screen optimally, which we elaborate in the context of airline passenger screening. In TSGs, different TSG resources such as X-Rays, Metal Detector act in teams to inspect an airline passenger. The possible teams are given. Passengers are further grouped into passenger categories with a given number of passengers in each category . The allocation is of resource teams to passenger categories. There are resource capacity constraints for each resource usage (not on teams but on each resource). Further, all passengers need to be screened. Each resource team has an effectiveness of catching the adversary. Observe that, unlike SSGs, the allocation in TSGs is not just binary but any positive integer within the constraints. The passenger category is a tuple of risk level and flight ; the adversary’s action is to choose the flight but he is probabilistically assigned his risk level.

Then, we capture the TSG domain in the above abstract model by mapping passenger categories in TSGs to objects (on columns) and resource teams in TSGs to assets (on rows). See Figure 1 for an illustrative example. The capacity constraint for each resource is captured by specifying the constraint which contains all indexes of teams that are formed using the given resource : team is formed using resource with equal to the resource capacity bound for resource . For every passenger category , the constraint enforces that all passengers are screened. A target in TSG is simply a passenger category , thus, the set is is given passenger category. The probability of detecting an adversary in category is given by , hence the weights are ; since it is easy to check that for any . The adversary type is the risk level , and each type of adversary can choose a flight , thus, choosing a target which is the passenger category . The probability of the adversary having a particular risk level is given.

## 4 Computation Complexity

In this section, we explore the hardness of approximation for ARAs, FAMS and TSGs. In prior work on computation complexity of SSGs, researchers [Xu2016] have focused on hardness of exact computation providing general results relating the hardness of defender best response (DBR) problem (defined below) to the hardness of exact SSE computation. In contrast, we relate the hardness of approximation of the DBR problem to hardness of approximation of ARAs. We also prove that special cases of ARA such as FAMS and TSGs are also hard to approximate.

First, we formally state the equilibrium computation problem in adversarial randomized allocation: given the assets, objects and assignment constraints of an adversarial randomized allocation problem as input, output the SSE utility and a set of pure strategies and probabilities that represents the SSE mixed strategy. We restrict to be polynomial in the input size. This is natural, since a polynomial time algorithm cannot produce an exponential size output. Also, as discussed in prior literature [Xu2016] the size of the support set of any mixed strategy is one more than the dimension of any pure strategy, which is the poly in our case.

Next, as has been defined in prior literature [Xu2016], we state the defender best response (DBR) problem which will help in understanding the results. The DBR problem can be interpreted as the defender’s best response to a given mixed strategy of the adversary. The DBR problem also shows up naturally as the slave problem in column generation based approaches to SSGs. While it is easy to show the hardness of approximation of given DBR problems, the question of how its relates to the hardness of approximation of SSE computation is open.

###### Definition 1.

The DBR problem is where is a vector of positive constants. DBR is a combinatorial problem that takes the assignment constraints as inputs, and not .

Next, we state the standard definition of approximation

###### Definition 2.

An algorithm for a maximization problem is -approximate if it provides a feasible solution with value at least , where is the exact maximum value.

Note that lower means better approximation. Depending on the best

possible, optimization problems are classified into various approximation complexity classes with increasing hardness of approximation in the following order PTAS, APX, log-APX, and poly-APX. We extensively use the well-known approximation preserving AP reduction between optimization problems for our results. We do not delve into the formal definition of complexity classes or AP reduction here due to lack of space and these concepts being standard

[Ausiello et al.1999]. Our first result shows that the ARA’s approximation complexity is same as that of the DBR problem and in the worst case cannot be approximated.

###### Theorem 1.

The following hardness of approximation results hold for ARA problems

• ARA problems cannot be approximated by any bounded factor in polynomial time, unless .

• If the DBR problem for given ARA problem lies in some given approximation class (PTAS, APX, log-APX, poly-APX), then so does the ARA problem.

###### Proof Sketch.

The first result works by constructing a ARA from a NP hard unweighted () DBR problem such that the feasibility of the constructed ARA solves the DBR problem, thereby ruling out any approximation. Such unweighted DBR problems exist (for example for FAMS). The second part of the proof works by constructing an ARA problem with one target and showing that the solution yields an approximate value for a relaxed DBR with . Moreover, this solution is an expectation over integral points (pure strategies), thus, at least one integral point in the support set output by ARA also provides an approximation for the corresponding combinatorial DBR. ∎

As the above complexity result is a worst case analysis, one may wonder whether the above result holds for sub-classes of ARA problems. We show that strong versions of inapproximatibility also holds for FAMS and TSGs.

###### Theorem 2.

TSGs cannot be approximated to any logarithmic factor in poly time, unless P=NP.

###### Theorem 3.

FAMS problems cannot be approximated to any logarithmic factor in poly time, unless P=NP.

Both the proofs above use AP reduction from max independent set. The proof for TSG follows from an observation that a special case of the TSG problem is the independent set problem itself, thus, any approximation for TSGs can provide an equivalent approximation for the max independent set problem. The proof for FAMS is much more involved. It involves constructing a poly number of FAMS instance (with varying number of resources) given any independent set problem. The FAMS instances are such that pure strategies corresponds to independent sets and the multiple instances are constructed such that the optimal exact solution for one of these instances provides a solution for the max independent set problem. Then, it is shown that any approximation for the FAMS problem yields at least one pure strategy (over all the FAMS instances) that corresponds to a better than approximation for the max independent set problem, thereby completing the AP reduction. See the supplementary material for details.

## 5 Approximation approach

Our approach to approximation first solves the , which is quite fast in practice (see experiments) and provides an upper bound to the true value of the game. Then, we sample from the marginal solution, but unlike previous work [Tsai et al.2010], we alter the sampled value to ensure that the final pure strategy output is valid. We describe an abstract sampling and alteration approach for ARA in this part, which we instantiate for FAMS and TSGs in the subsequent sub-sections. Recall that a constraint is given by an index set and the constraint is an equality if . For our abstract approach we restrict our attention to ARAs with partitioned equality assignment constraints, which means the index set for all equality constraints partitions the index set of the allocation matrix. Further, for inequality constraints we assume . Call these problems as PE0-ARA; this class still includes FAMS and TSGs. For FAMS, which does not have equality constraints, we use dummy schedules to get partitioned equalities ; denotes that resource is unallocated. Our abstract approximation approach for PE0-ARA is presented in Algorithm 1.

The Algorithm takes as input the marginal solution from and produces a pure strategy. The first for loop (line 1-2) performs comb sampling for each equality constraint to produce integral values for the variables involved in . Comb sampling was introduced in an earlier paper [Tsai et al.2010]; it provides the guarantee that is rounded up or down for all , the sample has expected value for all and equality S is still satisfied after the sampling. See Figure 2 for an example. Briefly, comb sampling works by creating buckets of length one each, where , where denotes fractional part. Each of the length fraction is packed into the bucket (in any order and some of the fraction may have to be split into two buckets), then a number between is sampled randomly, say , and for each bucket a mark is put at length . Finally, the whose fraction lies on the marker for each bucket is chosen to be rounded up, and all other are rounded down.

Observe that in expectation the output of comb sampling matches the marginal solution, thus, providing the same expected utility as the marginal solution. Recall that this expected utility is an upper bound on the optimal utility. However, the samples from comb sampling may not be valid pure strategies. Thus, in case the output of comb sampling is not already valid, the two abstract methods in line 3 and 4 modify the sample strategy by first decreasing the integral values to satisfy the violated inequalities and then increasing the integral values to satisfy the equalities. Such modification of the sampled strategy to obtain a valid strategy is guided by the principle that the change in defender utility between the sampled and the resultant valid strategy should be small, which ensures that change in expected utility from the marginal solution due to the modification is small. As the expected utility of the marginal solution is an upper bound on the optimal expected utility this marginal expected utility guided modification leads the output expected utility to be close to the optimal utility.

These two methods on line 3 and 4 are instantiated with domain specific heuristics that implement the principle of marginal expected utility guided modification. Below, we show the instantiation for the TSG and FAMS domains. A sample execution of the above approach for TSGs is shown in Figure 2.

### 5.1 Tsg

The heuristics for TSG are guided by three observations: (1) more effective resources are more constrained in their usage, (2) changing allocation for passenger categories with higher number of passengers changes the probability of detection of adversary by a smaller amount than changing allocation for category with fewer passengers and (3) higher risk passenger categories typically have lower number of passengers.

Recall that for TSGs the inequalities are resource capacity constraints. Thus, for fixing violated inequalities we need to decrease allocation which decreases utility; we wish to keep the utility decrease small as that ensures that the expected utility does not move much further away from the upper bound marginal expected utility. Our approach for such decrease in allocation has the following steps: (a) prioritize fixing inequality of most violated resources first and (b) for each such inequality we attempt to lower allocation for passenger category with higher number of passengers. In light of the observations for TSG above this approach aims to keep the change in expected utility small. Specifically, observation 1 makes it likely that constraints for more effective resources are fixed in step a above. Observation 3 suggests that the changes in step b happens for lower risk passengers. Thus, step a aims to keep the allocation of effective resources for high risk passengers unchanged. This keeps the utility change small as changing allocation for high risk passengers can change utility by a large amount. Next, by observation 2, step b aims to minimize the change in probability of detecting the adversary by a low amount so that expected utility change in small. For example in Figure 2, the inequality fix reduces the allocation for the third passenger category (column) which also has the highest number of passengers (15).

Next, the equalities in TSGs are the constraints for every passenger category. For fixing equalities we need to increase allocation which increases utility; we wish to keep this utility increase high as it brings the expected utility closer to the upper bound marginal expected utility. Here we aim to do so by (a) prioritizing increase of allocation for categories with fewer people and (b) increasing allocation of those resources that have least slack in their resource capacity constraint (low slack could mean higher effectiveness). By Observation 1 low slack means that resource could be more effective and by Observation 2 fewer people means higher risk passengers. This ensures that higher risk passengers are screened more using more effective resources thereby raising the utility maximally. For example in Figure 2, the equality for the third column is fixed by using the only available resource MD.

Recall that TSGs differs from FAMS in that the allocation for TSGs can be non-binary. This offers an advantage for TSGs with respect to approximation, as small fractional changes in allocation do not change the overall allocation by much (0.5 to 1 is a 50% change in FAMS, but 4.5 to 5 is less than 10% change for TSGs). Thus, we assume here that the changes due to Algorithm 1 do not reduce the probability of detecting an adversary in any passenger category (from the marginal solution) by more than factor, where is a constant. This restriction is realistic as it is very unlikely that any passenger category will have few passengers and we only aim to change the allocation for passenger categories with a higher number of passengers. Hence we prove the following

###### Theorem 4.

Assume that Algorithm 1 always successfully outputs a pure strategy and the change in allocation from the marginal strategy does not change the probability of detecting an adversary by more than factor. Then, the approximation approach above with the heuristic provides a -approximation for TSGs.

As a remark, the above result does not violate the inapproximatability of TSGs since the above result holds for a restricted set of TSG problems. Also, the approximation for TSGs may sometimes fail to yield a valid pure strategy as satisfying the equalities may become impossible after using certain sequences of decreasing allocation. In our experiments we observe that the failure of obtaining a pure strategy after Algorithm 1 is rare and also easily handled by repeating the approximation approach with a new sample (approximation runs in milli-secs).

### 5.2 Fams

Recall that for FAMS the inequalities are the target allocation constraints: and fixing violations for these involves decreasing allocation. Our heuristic is simple: the variables are set to zero (i.e., decreased) starting from those schedules that contain the most number of targets for which target allocation constraint is violated and do not contain any target for which the target allocation constraint is satisfied. We can guarantee to find a decrease in allocation that satisfies the constraint for without changing the allocation for targets that already satisfy constraints in the cases when the target with violated constraint (1) belongs to a schedule that exclusively contains that target ( can be decreased without affecting any other constraint) or (2) belongs to only one schedule (all other targets in this schedule will violate their constraints). This approach ensures that we only work to fix the violated constraints and cause a minimal change in utility by leaving the satisfied constraints undisturbed. However, if in fixing a violated target allocation constraint for it becomes necessary to reduce allocation for another already satisfied target constraint, then sample uniformly from the schedules that belongs to in order to choose the allocation to reduce. Do this till all inequality constraints are satisfied.

Then, we do nothing to fix equality constraints since we have only decreased and if any equality is not satisfied we can always set the dummy to be one. Also, observe that since we only always decrease allocations, we always find a pure strategy for any sample from Algorithm 1 (unlike TSGs). We prove the following:

###### Theorem 5.

Let be the number of targets that share a schedule with any target , and . The approximation approach above with the heuristic provides a -approximation for FAMS.

Next, we show experimental results that reveal the average case loss of our approximation approach (as opposed to the worst case approximation guarantees in this section).

## 6 Experimental Results

Our set of experiments provide a comprehensive analysis of our randomized approach, which we name RAND. We compare RAND to the best know solver for TSGs called MGA; MGA [Brown et al.2016] has been previously shown to outperform column generation based approaches by a large margin. For the FAMS problem the best known solver in literature for the general sum case is called the ASPEN [Jain et al.2010], which is a column generation based branch and price approach. Through private communication with the company (Avata Intelligence) managing the FAMS software, we know the FAMS problem is solved as a zero-sum problem for scalability and takes hours to complete. For our zero-sum case we implemented a plain column generation (CG) solver for FAMS, since branch and price is an overkill for the zero sum case. All results in this section are averaged over 30 randomly generated game instances. All game instances fix to and randomly select from integers between and

. The utility for RAND is computed by generating 1000 pure strategies and taking their average as an estimate of the defender mixed strategy. All experiments were run using a system with Xeon 2.6 GHz processor and 4GB RAM.

For FAMS, we vary the number of flights, keeping the number of resources fixed at 10 and number of schedules fixed at 1000 and 5 targets/schedule. The runtime in log scale is shown in Figure 3. CG hits the 60 min cut-off for 700 flights and the run time for RAND is much lower at only a few seconds. Next, we report the solution quality for RAND by comparing with the solution using CG. It can be seen that the solution gets better with increasing flights starting from 19% loss at 300 flights to 5% loss at 900 flights. Thus, the numbers show that we obtain large speed-ups up to factor of 1000x and are still able to extract 95% utility for higher number of flights when the CG approach starts taking huge amount of time.

For TSGs, we used six passenger risk levels, eight screening resource types and 20 screening team types. We vary the number of fights and we also randomly sample the team structure (how teams are formed from resources) for each of the 30 runs. The results in Figure 4 show runtime (in log scale) and defender utility values varying with number of flights (on x-axis). As can be seen, MGA only scales up to 110 flights before hitting the cut-off of 60 mins, while RAND takes only 10 sec for 110 flights. Also, the solution quality loss for RAND has a maximum averaged loss of 1.49%. Thus, we obtain at-least 360X speed-ups with very minor loss.

Finally, we test the scalability of RAND for FAMS and TSG, shown in Figure 5. As can be seen, the runtime for RAND is low even with the highest number of flights we tested: 280 for TSG and 3500 for FAMS. The maximum runtime for FAMS was under 5 seconds. With TSGs the maximum runtime was under 25 secs. Overall, these results demonstrate the scalability of our approach with minor solution quality loss on average. Importantly, the scalability results shows that RAND can solve the FAMS and TSG problem for sizes that are required for a US wide deployment, and the results also provide evidence that further scalability with increasing number of flights is also possible. This also provides evidence that approximations is a viable approach to solving zero-sum SSGs at a large scale.

## 7 Conclusion

We studied approximations in SSGs both theoretically and practically. In fact, while our paper title talks about half a loaf (optimal solution), we practically obtain up to 97% of the loaf (optimal solution). We obtain 1000x speedups with losses within 5%. Thus, approximations open the door to solving very large scale zero-sum SSGs and we believe that we have laid a fertile ground for future research in approximating large scale zero-sum security games. Our approach also provided an avenue to solve the real world FAMS and airport screening problem in order to increase the scope of applicability of these already deployed application (in case of FAMS) or applications under test (airport screening).

## References

• [Ageev and Sviridenko2004] Ageev, A. A., and Sviridenko, M. I. 2004. Pipage rounding: A new method of constructing algorithms with proven performance guarantee.

Journal of Combinatorial Optimization

8(3):307–328.
• [Amin, Singh, and Wellman2016] Amin, K.; Singh, S.; and Wellman, M. 2016. Gradient methods for stackelberg security games. In

Conference in Uncertainty in Artificial Intelligence

.
• [Ausiello et al.1999] Ausiello, G.; Protasi, M.; Marchetti-Spaccamela, A.; Gambosi, G.; Crescenzi, P.; and Kann, V. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties.
• [Bansal et al.2012] Bansal, N.; Korula, N.; Nagarajan, V.; and Srinivasan, A. 2012. Solving packing integer programs via randomized rounding with alterations. Theory of Computing 8(1):533–565.
• [Basilico, Gatti, and Amigoni2009] Basilico, N.; Gatti, N.; and Amigoni, F. 2009. Leader-follower strategies for robotic patrolling in environments with arbitrary topologies. In AAMAS, 57–64.
• [Blocki et al.2013] Blocki, J.; Christin, N.; Datta, A.; Procaccia, A.; and Sinha, A. 2013. Audit games. In IJCAI.
• [Blum, Haghtalab, and Procaccia2014] Blum, A.; Haghtalab, N.; and Procaccia, A. D. 2014. Learning optimal commitment to overcome insecurity. In NIPS, 1826–1834.
• [Bošanský et al.2015] Bošanský, B.; Jiang, A. X.; Tambe, M.; and Kiekintveld, C. 2015. Combining compact representation and incremental generation in large games with sequential strategies. In AAAI.
• [Brown and Sandholm2017] Brown, N., and Sandholm, T. 2017. Safe and nested subgame solving for imperfect-information games. arXiv preprint arXiv:1705.02955.
• [Brown et al.2016] Brown, M.; Sinha, A.; Schlenker, A.; and Tambe, M. 2016. One size does not fit all: A game-theoretic approach for dynamically and effectively screening for threats. In AAAI.
• [Budish et al.2013] Budish, E.; Che, Y.-K.; Kojima, F.; and Milgrom, P. 2013. Designing random allocation mechanisms: Theory and applications. The American Economic Review 103(2):585–623.
• [Chekuri, Vondrák, and Zenklusen2009] Chekuri, C.; Vondrák, J.; and Zenklusen, R. 2009. Dependent randomized rounding for matroid polytopes and applications. arXiv preprint arXiv:0909.4348.
• [FAA2014] FAA. 2014. Airport capacity profiles. Accessed: 2017-02-15.
• [Gan, An, and Vorobeychik2015] Gan, J.; An, B.; and Vorobeychik, Y. 2015. Security games with protection externalities. In AAAI.
• [Gandhi et al.2006] Gandhi, R.; Khuller, S.; Parthasarathy, S.; and Srinivasan, A. 2006. Dependent rounding and its applications to approximation algorithms. Journal of the ACM (JACM) 53(3):324–360.
• [Guo et al.2016] Guo, Q.; An, B.; Vorobeychik, Y.; Tran-Thanh, L.; Gan, J.; and Miao, C. 2016. Coalitional security games. In AAMAS.
• [Harsanyi1967] Harsanyi, J. 1967. Games with incomplete information played by” bayesian” players, i-iii part i. the basic model. Management Science 14(3):159–182.
• [Jain et al.2010] Jain, M.; Kardeş, E.; Kiekintveld, C.; Tambe, M.; and Ordóñez, F. 2010. Security games with arbitrary schedules: a branch and price approach. In AAAI, 792–797.
• [Jiang et al.2013] Jiang, A. X.; Procaccia, A. D.; Qian, Y.; Shah, N.; and Tambe, M. 2013. Defender (mis) coordination in security games. AAAI.
• [Kiekintveld et al.2009] Kiekintveld, C.; Jain, M.; Tsai, J.; Pita, J.; Ordóñez, F.; and Tambe, M. 2009. Computing optimal randomized resource allocations for massive security games. In AAMAS, 689–696.
• [Korzhyk, Conitzer, and Parr2010] Korzhyk, D.; Conitzer, V.; and Parr, R. 2010. Complexity of computing optimal Stackelberg strategies in security resource allocation games. In AAAI.
• [Letchford and Conitzer2013] Letchford, J., and Conitzer, V. 2013. Solving security games on graphs via marginal probabilities. In AAAI.
• [Moravčík et al.2017] Moravčík, M.; Schmid, M.; Burch, N.; Lisý, V.; Morrill, D.; Bard, N.; Davis, T.; Waugh, K.; Johanson, M.; and Bowling, M. 2017. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science.
• [Munoz de Cote et al.2013] Munoz de Cote, E.; Stranders, R.; Basilico, N.; Gatti, N.; and Jennings, N. 2013. Introducing alarms in adversarial patrolling games: Extended abstract. In AAMAS.
• [Raghavan and Thompson1987] Raghavan, P., and Thompson, C. D. 1987. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7(4):365–374.
• [Tambe2011] Tambe, M. 2011.

Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned

.
• [Tsai et al.2010] Tsai, J.; Yin, Z.; Kwak, J.-y.; Kempe, D.; Kiekintveld, C.; and Tambe, M. 2010. Urban security: Game-theoretic resource allocation in networked physical domains. In AAAI.
• [USDOT2016] USDOT. 2016. Bureau of transportation statistics. Accessed: 2017-02-15.
• [Xu2016] Xu, H. 2016. The mysteries of security games: Equilibrium computation becomes combinatorial algorithm design. In The 17 ACM Conference on Economics and Computation (ACM-EC).

## Appendix A Appendix

### a.1 ARA complex model

It is easy to change the probability to be so that the probability is non-linear (as given by f) in the entries. Also, clearly increasing number of targets to be large is allowed as targets can be any subset of the indexes. A general sum variant can also be stated by specifying the adversary utilities in terms of . Of course, as in SSGs, the general sum case cannot be written as a LP but can be written as multiple optimizations or a MILP.

### a.2 Implementability

Viewing SSGs as ARAs provides an easy way of determining implementability using results from randomized allocation [Budish et al.2013]. First, we define bi-hierarchical assignment constraints as those that can be partitioned into two sets such that two constraints in the same partition ( or ) it is the case that either or or . Then, we obtain the following sufficiency result

###### Proposition 1.

All marginal strategies are implementable, or more formally , if the assignment constraints are bi-hierarchical.

###### Proof.

The proof is just an application of Thm 1 in [Budish et al.2013]. ∎

In contrast to prior work that have identified cases of non-implementability [Korzhyk, Conitzer, and Parr2010, Letchford and Conitzer2013, Brown et al.2016] for specific cases, this provides an easy way to characterize non-implementability across a wide range of SSGs. As Figure 1 reveals, both FAMS and TSG have non-implementable marginals due to overlapping constraints. Next, as defined in [Budish et al.2013], canonical assignment constraints are those that impose constraints on all rows and columns of the matrix (with possibly additional constraints), using which we obtain the following necessity result

###### Proposition 2.

Given canonical assignment constraints, if all marginal strategies are implementable then the assignment constraints are bi-hierarchical.

###### Proof.

The proof is just an application of 2 in [Budish et al.2013]. ∎

### a.3 Proofs

Proof of Theorem 1:

###### Proof.

For the first part, given any ARA problem with a NP hard DBR-U instance (for the decision version of DBR-U), we construct another ARA instance such that the feasibility problem for that ARA instance solves the DBR-U decision problem. Thus, as the feasibility is NP Hard, there exists no approximation. First, since ARA problem is so general there exists DBR-U problems that are NP Hard. For example the DBR-U problem for FAMS has been shown to be NP Hard [Xu2016]. Given the hard DBR-U problem, form an ARA problem with by adding the constraint . Also, let there be only one target in the problem, so that the objective becomes insted of and all constraints in the optimization are just the marginal space constraints and . Now, the existence of any solution of the optimization gives a feasible point as , where the integral points is solution to the question of does there exist a solution of the DBR-U optimization problem with value . Next, a binary search on can answer the decision DBR-U problem of whether there exists a solution for decision DBR-U with value . Thus, existence of any solution for ARA is NP Hard, thus, no approximation is easy.

For the second part, we present a AP approximation preserving reduction (with problem mapping that doe not depend on approximation ratio); such a reduction preserves membership in PTAS, APX, log-APX, Poly-APX (see ). Given any DBR problem, we construct the ARA problem with one target such that . Choose the weights ’s such that and . Observe that is computable efficiently and , thus, the ARA is well-defined. Thus, due to just one target, the ARA optimization is same as . Suppose we can solve this problem with approximation with the solution mixed strategy being for some pure strategies . Now, since we also know that this solution also provides approximation for DBR-C. Let the optimal solution for DBR-C be ; note that is also the optimal solution for DBR. provides a solution value . Further, as the objective is linear in and , it must be the case that there exists a such that . Thus, since , provides approximation for DBR. Since, the number of the pure strategies in support of is polynomial, can be found in polynomial time by a linear search. ∎

Proof of Theorem 2:

###### Proof.

Given an independent set problem with vertices, we construct a TSG with team types, where each team type in corresponds to a vertex. The team is special in the sense that it does not correspond to any vertex and it is made up of just one resource with a very large resource capacity . Construct just one passenger category with passengers . Since, there is just one passenger category (and target) we will use as the matrix entries instead of . Choose and and efficiencies for all teams, except . Then, the objective of the integer LP is where is a vector with first components as 1 and last component as 0.

Next, have resources for every edge with resource capacity . This provides the inequality . Also, we have . Inspection of every passengers provides the constraints . Treating as a slack, we can see that the constraint and are redundant. For the left over constraints , we can easily check that any valid integral assignment (pure strategy) is an independent set. Moreover, the objective tries to maximize the independent set. The optimal value of this optimization over is an extreme point which is integral and equal to the maximum independent set OPT. Thus, suppose a solution to the SSE problem with value . Further, as the objective is linear in and , it must be the case that there exists a such that . Thus, since , provides approximation for maximum independent set. Since, the number of the pure strategies in support of is polynomial, can be found in polynomial time by a linear search.

Proof of Theorem 3:

###### Proof.

We provide an AP reduction from independent set. As max independent set is poly APX complete, this rules out any log factor approximation.

Given an independent set maximization problem with vertices and edges construct the following FAMS problems, one for each . Use resources. All resources can be assigned to any schedule. Construct schedules corresponding to the vertices . Construct target corresponding to every edge such that and . All ’s have the same value for being defended or undefended and that value is ; thus, these targets do not need to covered but impose the constraint that and cannot be simultaneously defended. Thus, it is clear that any allocation of resources to corresponds to an independent set. Next, consider additional targets and expand the schedules such that . Further, add more singleton schedules with . All additional targets provide value when defended and otherwise. Thus, the expected utility of defending an additional target given coverage is .

First, assume we have a poly time algorithm to approximately compute the SSE with approx factor (). We will run this poly time algorithm with resources to which is again a poly time overall, and also the overall output size is poly. For the given max independent set problem, let the solution be . Observe that for problems with resources where , all valuable (additional) targets can be covered by covering schedules with targets in and using the remaining resources to cover the remaining targets. This provides utility of for the SSE. In particular, the utility with resources is . Also note that for every problem, there is always a trivial allocation of resources to the singleton schedules such that coverage of each target is . (this is deducible as the allocation to singleton schedules is unconstrained and can be implemented in poly time by Birkhoff-von Neumann result as provided in [Korzhyk, Conitzer, and Parr2010]). This trivial allocation provides an utility 0.

Also the following result will be useful: given approximation factor for the case with resources then one of the pure strategy output for this case will have at least schedules among covered where . Before proving the above note that by definition and .

To prove the result in last paragraph consider the contra-positive: suppose all pure strategies output cover at most schedules among , then in each pure strategy at least targets are not covered (since 2 targets are covered for the schedules and rest of resources can cover only 1 target). Then the coverage of the least covered target in the mixed strategy formed using such pure strategies is . The utility for this least covered target is . The overall utility has to be lower than utility for any target, hence the utility is . The optimal utility is . Thus, by definition of approximation ratio we must have or re-arranging but by definition of we must have hence a contradiction.

The above result also shows that at least one pure strategy yields an independent set of size . As is the max size of independent sets we obtain and approximation ratio for the max independent set problem such that . Thus, we obtain a better approximation given approximation for the SSE. Thus, we have an AP reduction. ∎

Proof of Theorem 5:

###### Proof.

Consider the event of a target having an infeasible assignment after the comb sampling. Call this event . Let be the event that resource covers this target . Then, . From the guarantees of comb sampling we know that and . Also, by comb sampling if then for any . Next, we know that is the probability that the any of the other is assigned a one, which is the probability that all other are assigned 0. Thus,

 P(Et|Ct,i)=1−∏i′≠i(1−P(Ct,i))

Let . Considering the fact that , we get

 1−∏i′≠i(1−P(Ct,i))≤∑(i′,j):i′≠i∧(i′,j)∈Txmi′,j≤1−∑jxmi,j

where the last inequality is due to the fact that .

Thus, . Next, we know from standard sum of squares inequality that . Thus, we get The RHS is maximized when , thus, . Also, then

Now consider the coverage of target : . According to our algorithm the allocation for target continues to remain with probability if its allocation is already feasible after comb sampling (and we always obtain a pure strategy). This is because this target shares schedules with other targets and thus in the worst case may be reduced with probability for each of the targets. We do a worst case analysis and assume that no resource is allocated to a target when the sampled allocation is infeasible for that target. Thus, let

denote the random variable denoting that target

is covered. Thus, . Now, is same as and we assumed the worst case of . Thus, we have . As the utilities are linear in , we have the utility for as , where is the utility under the marginal . Thus, if is the choice of adversary under the marginal we know that is the lowest utility for the defender over all targets . Hence, we can conclude that the utility with the approximation is at least

Proof of Theorem 4:

###### Proof.

The main assumption in the proof is that the steps after after comb sampling changes the probability of detecting an adversary in passenger category by at most . Also, by assumption of the theorem since Algorithm 1 does not fail ever, the change in utility for any passenger category is at most a factor of . By similar reasoning as for FAMS, we conclude that this provides a -approximation. ∎


text:
NEW
New Website Launch
Experience the best way to solve previous year questions with mock tests (very detailed analysis), bookmark your favourite questions, practice etc...
1

### WB JEE 2008

Subjective

If 2a $$-$$ 5b $$-$$ 3c = 0, show that the straight line ax + by + c = 0 always passes through a fixed point. Find the equation of one straight line passing through this fixed point and parallel to the line 9x + 12y = 20.

.

## Explanation

We have, $$2a - 5b - 3c = 0$$.

or, $$c = {{2a - 5b} \over 3}$$ ..... (i)

Hence, equation of the straight line can be written as

$$ax + by + {{2a - 5b} \over 3} = 0$$

or, $$3ax + 3by + 2a - 5b = 0$$

or, $$a(3x + 2) + b(3y - 5) = 0$$.

This will be true for all values of a and b, only if (3x + 2) and (3y $$-$$ 5) are simultaneously zero which means, for x = $$-$$2/3 and y = 5/3, the equation is always satisfied for any values of a and b.

$$\therefore$$ The straight line passes through the point ($$-$$2/3, 5/3)

Now, slope of the given line 9x + 12y = 20 is $$-$$3/4

Any straight line parallel to this line will also have slope of $$-$$3/4

$$\therefore$$ Equation of the line parallel to 9x + 12y = 20 and passing through ($$-$$2/3, 5/3) is

$$y - {5 \over 3} = - {3 \over 4}\left( {x + {2 \over 3}} \right)$$

$$y - {5 \over 3} = - {3 \over 4}\left( {x + {2 \over 3}} \right)$$ or, $$- 4y + {{20} \over 3} = 3x + 2$$

or, $$3x + 4y - {{14} \over 3} = 0$$ or, $$9x + 12y - 14 = 0$$.

### Joint Entrance Examination

JEE Main JEE Advanced WB JEE

### Graduate Aptitude Test in Engineering

GATE CSE GATE ECE GATE EE GATE ME GATE CE GATE PI GATE IN

NEET

Class 12

format: plain


text:
## Introduction

Dental caries is the most common chronic disease amongst all oral conditions1. Caries experience is found in 21% of children between the ages of 6–11 years, and in 91% of adults older than 20 years of age in the United States2. While odds for untreated decay increases with decreasing income, dental caries prevalence in the primary dentition is 10.8% in the Philippines, 64.2% in India, and 30% in Spain, signifying the varying effects of geographic location and socioeconomic status on onset and spread of dental caries3,4,5,6.

Demineralized tooth structure and the formation of dental caries is associated with acid production by microbial metabolism of sugar7. Studies have shown that the initial colonizing microorganisms are mainly Streptococcus sanguinis, Streptococcus oralis and Streptococcus mitis8. Eventually, Streptococcus mutans proportionally increases when compared to other decay bacterial species, while surface enamel changes to a frosty white colour caused by the acid damage8. This domination of S. mutans will subsequently reduce at the advancing stages of dental caries due to the increasing numbers of other microorganisms, such as Lactobacilli, Prevotella, and Bifidobacterium9. Therefore, the detection of microorganisms and the number of microbial colonies formed inside carious lesions can be considered as definitive and sensitive indicators for carious lesion severity. Carious lesion severity could be essentially defined as the level of clinical treatment needs (e.g. intrusive or minimal) of a carious lesion based on the amount of microbial colonies isolated from the carious lesion as dentinal lesions that contain large amounts of isolated microbial colony forming units (CFUs) often require a more intrusive clinical treatment (e.g. caries debridement and restoration) if compared to those with less isolated CFUs which may either require less intrusive treatments such as chemotherapeutic treatments (e.g. topical fluoride treatment) or no treatment need at all10,11,12,13,14. Furthermore, by identifying the number and types of microbial species isolated from carious lesions, the stages of caries progression might be distinguished with great specificity, sensitivity, and reliability.

The most common methods used for dental caries detection in clinical practice are visual and tactile examinations15. Under normal daylight, the colour of a lesion is categorized by visual comparison with a standard guide of four shades (yellow, light brown, dark brown, and black) which is prepared from photographs of primary dentinal carious lesions. On the other hand, the texture or hardness of lesions are classified into three grades (hard, medium or leathery, soft) as described by Hellyer et al.16. Briefly, under standard dental lighting, hard lesions are as hard as the surrounding tooth tissue, leathery lesions are penetrated by a new Ash No. 6 probe under modest pressure but displayed resistance to its withdrawal, while soft lesions are easily penetrated by a new Ash No.6 probe under modest pressure and displayed no resistance to withdrawal of the probe10,17. However, visual and tactile examinations result in low reproducibility and low sensitivity due to their subjective nature, but produce highly specific outcomes18. Studies indicated that cariogenic microorganisms produce acids that destroy tooth structure, resulting in changes of colour, consistency, and moisture content of dental tissue. For instance, darker and softer carious lesions contained larger numbers of microorganisms10,14,19,20. Thus, to improve the sensitivity, specificity, and reliability of clinical dentine caries examination detection methods, it is suggested that visual and tactile criteria for caries detection should be assessed in relation to the carious microbial activity as this would provide an accurate consistent method to assess caries quantitatively and qualitatively.

Therefore, the aim of this study was to systematically review the literature into colour and hardness of dentine caries and their association with microbial activity, particularly the amount of microbial colony forming units (CFU) that are isolated clinically from biopsies of these lesions following colour and hardness clinical examinations. This potentially proves which of the categories of colour or hardness is more specific and reliable to reflect the severity of carious lesions.

## Methods

The Preferred Reporting Items for Systematic reviews and Meta-Analysis (PRISMA) guidelines were adopted for the current study21.

### Search strategy

Studies that assessed the association between colour and hardness with the quantification of CFUs from biopsies of these carious lesions as an indicator of dentinal carious lesion severity were accessed using a defined search strategy in the following electronic databases from 1950 to April 1st, 2018: PubMed, Medline via Ovid, and Web of Science. Handsearching was also performed by accessing the following journals: Community Dentistry and Oral Epidemiology, Caries Research, Journal of Dental Research, Journal of Pediatric Dentistry, Journal of Dentistry, Journal of Oral Health and Preventive Dentistry, and Journal of Dentistry for Children to April 1st, 2018. The following search terms were used: “color” or “colour” or “hardness” or “texture” or “consistency” and “dentin caries” or “dentine caries” and “microbiology” or “microflora” or “bacteria”.

### Eligibility criteria

Search strategy and literature search findings were reviewed by two authors (Hon and Mohamed) to determine whether the identified studies met the inclusion criteria. The inclusion criteria were as follows: (1) randomized controlled trial (RCT) or diagnostic tests studies; (2) colour and hardness scored clinically; (3) CFU reported; (4) dentine caries; (5) open primary dentine caries in deciduous or permanent teeth; (6) articles published in English; and (7) human studies in vivo. Animal studies, in vitro studies, reviews, comments, editorials, and non-English studies were excluded. Additionally, research that contained irreversible pulpitis, secondary caries, hidden caries or caries that could only be seen radiographically were excluded. Disagreements between the two authors were resolved by an independent reviewer (Lynch). For detailed information, please refer to Fig. 1.

### Data extraction and quality assessment

Two authors (Hon and Mohamed) extracted data using a pre-set data extraction sheet. The data extraction sheet included the following information: author, title, population, intervention, comparison, sample size, confidence level, results and outcomes. For the data extraction details, please refer to Table 1. The quality of evidence in the included studies was assessed by the Critical Appraisal Skills Programme (CASP) tools22,23. The included studies were randomized controlled trials and diagnostic tests studies. Thus, the respective CASP tools were used to assess each study type. Each article was independently assessed by two authors (Hon and Mohamed), while disagreements were resolved by an independent reviewer (Lynch). Inter-examiner variability among the 2 examiners was measured by calculating the percentage of agreement (%) among the 2 examiners in each CASP checklist criteria. This is due to the low number of included studies (diagnostic studies n = 2 and RCTs n = 5)24,25,26,27. For detailed information, please refer to Fig. 2.

### Statistical analysis

Clinical recordings using colour and hardness of carious dentine have been proposed as indicators of lesion severity. Microbiological biopsies of carious samples have been used to enumerate the numbers of microorganisms expressed as CFUs. The primary outcome measures analyzed were: total microbial load in CFU in each category of colour (yellow, light brown, dark brown, black) and hardness classification (soft, medium hard or leathery, hard). Differences (dcolour) in means of total microbial load between categories of the colour scale were assumed as a measure of “discriminant power” using this test. Three differences between adjacent categories were computed as: yellow vs. rest, yellow/light brown vs. dark brown/black, black vs. rest. Differences (dhardness) in means of total microbial load between categories of the hardness scale were also assumed as a measure of “discriminant power” using this test: hard vs. rest, soft vs. rest. If the difference obtained from the colour test is significantly higher than those from the hardness test, it means that the colour test is more discriminating than the hardness test. Inversely, if the difference obtained from the colour test is significantly lower than those from the hardness test, it means that the colour test is less discriminating than the hardness test. Therefore, mean differences between all colour and hardness category differences were computed and the weighted mean difference (WMD) was the global effect measure in a random-effects model.

In addition, the effect size of the differences between colour (or hardness) categories regarding mean CFU was also calculated. The effect size index for a conventional one-way ANOVA is…$$f=\sqrt{\frac{{{\beth }}^{2}}{1-{{\beth }}^{2}}}$$, whereby $${\beth }^{2}$$ is the ratio of the between-groups variance to the total variance. The larger the effect size “f ” is, the larger the difference between mean total microbial load of categories is, meaning there is a higher power to discriminate. As a general convention, small $$f=0.10$$, medium $$f=0.25$$, and large $$f=\mathrm{0.40.}\,$$An overall effect size was estimated weighting the individual numbers by the sample size of each study. The level of significance used in the analysis was 5% (α = 0.05). The software used to perform this meta-analysis was R 3.0.2 and its ‘metafor’ package. The software Gpower 3.1.3 was used to estimate effect sizes.

## Results

### Study characteristics and quality assessment

Fig. 1 shows the detailed steps used for the literature search. Of the 64 potentially relevant articles, 26 articles were eligible for full text screening. However, 19 articles were further excluded because they did not meet the inclusion criteria. Please refer to Table 2 for detailed information on the excluded papers and the rationale for their exclusion. Therefore, only seven articles10,14,19,28,29,30,31 were included for full text quantitative and qualitative assessment in this systematic review. These seven articles were published between 1950 and 2018. Among these articles five were randomized controlled trials19,28,29,30,31 and two were diagnostic test studies10,14.

### A-Randomized controlled trials

Five randomized controlled trial articles were included19,28,29,30,31. One article disclosed the gender of the participants: 51 females and 60 males28. Three articles detailed the age of participants age: 4–15 years old28, 12–23 years old29, and 5–8 years old31; therefore, the range of the age groups of the participants within the latter three studies was 4–23 years old. Three articles specified the type of teeth that received intervention and comparator treatments: 94 mandibular second primary molars and 60 mandibular first permanent molars28 and primary molars30,31. Only one article provided the number of subjects recruited28, whilst the other studies only reported the number of teeth investigated29,30,31. Sample size calculations were only carried out by Lula et al., who conducted sample size calculations based on a pilot study where 16 teeth obtained an 80% power at a 5% statistical significance. It was noticeable that the article by Bjorndal et al. did not give details as to the gender, age, or type of teeth used (incisor, canine, premolars, molars, primary dentition, and permanent dentition).

As we investigated the intervention and comparison groups, colour and hardness of lesions were related to the total CFU each contained. Two articles scored colour and hardness of lesions whilst evaluating different levels of carious dentine prior to final restoration in a stepwise approach19,28, which was using incomplete removal of dentine caries to try to prevent pulpal exposure. Three articles related total CFU in carious dentine with colour and hardness at different time points, at intervals of 6–7 months29, 4–6 months30, and 3–6 months31. Refer to Table 1 for further details on study characteristics. The CASP quality assessment for these included randomized controlled trials is presented in Fig. 2. According to the CASP analysis, the study of Lula et al. produced the highest quality of evidence and therefore its findings carried more weight. The inter-examiner variability for quality assessment was 72.7% for the five RCT’s, signifying high reproducibility between the two examiners.

### B-Diagnostic test studies

Two articles were diagnostic test studies10,14. Both articles examined the colour and hardness of carious lesions and compared these to their respective total CFU counts10,14. Both these articles reported the number of participants and gender: 45 females and 72 males14, 25 females and 34 males10. Therefore, the total number of participants in each gender was 70 females and 106 males. Both articles examined the same age range: 29–80 years old10,14. Both articles10,14 reported the number of teeth included in each study but neither article detailed the type of teeth that had been examined (incisor, canine, premolars, molars, primary dentition, permanent dentition). Neither article reported any sample size calculation10,14. For further details on study characteristics, please refer to Table 1. According to the CASP quality assessment, both articles produced equally high-quality evidence. For further detail CASP analysis of the aforementioned articles, please refer to Fig. 2. The inter-examiner variability for quality assessment was 83.3% for the diagnostic test studies, signifying high reproducibility between the two examiners.

## Comparison of CFU’s Between Colour and Hardness Examination Methods

### A-Randomized controlled trials

One article compared CFUs in one-visit indirect pulp treatment (IPT) with two-visit IPT and direct complete excavation (DCE)28. Four articles were paired study designs that compared samples from different time points19,29,30,31. These four articles measured the CFUs taken for colour or hardness categories. The total CFU counts were only measured and compared within the categories of caries colour or categories of caries hardness independently19,28,29,30. Only one article related both colour and hardness to total CFU. This study also compared the CFU counts within each caries colour category (i.e. yellow, light brown, dark brown) and within caries hardness categories (i.e. soft, medium hard, hard)31.

Findings of statistical significance are summarized in the study characteristic Table 1. Two articles28,31 found no statistical significance in total CFU, S. mutans or for Lactobacillus spp., recovered from different colour categories but harder lesions contained less total CFU than softer lesions28,31. One article did not carry out any statistical analysis between the microflora associations with colour and/or hardness categories because the study did not include sufficient number of samples30.

### B-Diagnostic test studies

Both articles assessed the relationships between total CFU with colour and hardness10,14. Total CFUs was highest in all soft colour categories compared to all colour categories of leathery lesions which in turn contained more total CFU than all hard colour categories10,14, and black soft lesions contained more lactobacilli than black leathery lesions10. For further details, please refer to Table 1.

### Statistical analysis for pooled CFU’s outcomes

Some of the included papers had to be excluded from the meta-analysis because they did not have a mean load for each category28, where microbial levels were only measured by turbidity methods28,30, or where data were only shown as percentages of specific species instead of the total CFU14.

The microbial load in each colour and hardness category (Black [B], Dark Brown [DB], Light Brown [LB], Yellow [Y], Soft [S], Medium [M], Hard [H]) was calculated by measuring the log10CFU in the studies by Bjorndal et al., Maltz et al., Lula et al., and Beighton et al. as shown in Table 3. When lesions were described as leathery these were classified as medium for this analysis.

When comparing B-DB/LB/Y vs. S-M/H, the only possible comparison was by using the study by Beighton et al. It was found that there were more CFU (2.32 units of log10 CFU in average) in black samples than any of the other colour groups. In addition, it was found that there were on average 3.72 units more of log10CFU in soft samples than in leathery samples and in turn these had significantly more CFU than in hard lesions. The differences in CFU between the hardness categories were considerably more than any differences between the CFU contained in the different colour categories. Therefore, the hardness test was more discriminant, but no meta-analysis was conducted because only 1 study was involved in this comparison as shown in Fig. 3.

When comparing B-DB/LB/Y vs. S/M – H, Beighton et al. and Bjorndal et al. provided data in relation to CFU differences between these categories, so a meta-analysis was performed, and a forest plot is shown in Fig. 3. The WMD value for the difference was −0.067. The effect size on the population was estimated to be between −1.88 and 1.74 with a confidence of 95%. It should be noted that the interval includes zero, so no significant difference was reached (p = 0.942). Therefore, none of these tests were more discriminant than the other.

Because of the large sample size of Beighton et al., (n = 301) in the comparisons between B/DB - LB/Y vs. S - M/H, its weight was very dominant compared to Lula et al. (n=16). The overall effect measure of the meta-analysis was similar to the Beighton et al. individual results. The WMD value for the difference was −3.67 (p < 0.001), indicating that the hardness test was more discriminant than colour. The analysis for this forest plot is shown in Fig. 4.

When comparing B/DB - LB/Y vs. S/M – H, the results are similar to the previous comparison. The WMD value for the difference was −3.37 (p < 0.001), suggesting that the hardness test was again more discriminant than colour and the forest plot of this analysis is presented in Fig. 4.

When comparing B/DB/LB - Y vs. S - M/H, the WMD value for the difference was −4.74 (p < 0.001), supporting that the hardness test was again more discriminate than colour. The analysis for this forest plot is shown in Fig. 5.

When comparing B/DB/LB - Y vs. S/M – H, the WMD value for the difference was −4.45 (p < 0.001), also indicating that the hardness test was more discriminant than colour. The forest plot of this analysis is shown in Fig. 5.

For Bjorndal et al., Lula et al. and Beighton et al. the effect size for the hardness category is larger than the colour categories; for Bönecker et al. the results again favored hardness over colour. Consequently, the weighted total effect size showed a large advantage for hardness as a discriminant rather than colour. However, this difference is caused, especially, by the huge dominance of the Beighton et al. data in the overall numbers. The effect size table is shown in Table 4.

## Discussion

Dental caries involve microorganisms excreting acid resulting in changes in dental tissue hardness and colour. However, the accuracy and reliability of dentine colour and hardness as indicators for carious lesion severity has never been assessed in a systematic review. Thus, the aim of this study was to systematically analyze published research investigating whether colour or hardness of dentine caries was a more accurate, reliable, and valid method in detecting carious lesion severity when related to the amount of detectable CFU in biopsies of these lesion categories.

Seven papers met the inclusion criteria for this systematic review from searching multiple electronic databases and hand searching multiple journals: five articles were RCTs and two were diagnostic test studies. The five included RCTs were not primarily conducted to investigate the relationship between colour and hardness with the numbers of microorganisms. They were rather trial studies to investigate certain clinical interventions (e.g. one-visit IPT, two-visit IPT, DCE, step-wise excavation, and atraumatic restorative treatment). For the purpose of this systematic review, only the RCT data related to the CFU counts obtained from carious biopsies following the colour and hardness measurements were reported.

The quality of each study was critically appraised using CASP tools. The RCT and diagnostic test studies have separate CASP tools to systematically examine and appraise the evidences of each article. Using CASP tools, it was noticeable that many articles lacked details of patient’s age, gender, type of teeth, socioeconomic status, ethnicity, diet, or sample size calculations19,30,31. This would question the quality of evidence in the included papers. In fact, the unreported randomization protocols10,14,19,29,30,31, sample size calculations10,14,19,28,29,30, and confidence limits10,14,19,28,29,30,31 are additional evidence of the low quality of evidence in most of the included studies. This study shows that only the studies by Lula et al., Lynch et al. and Beighton et al. reported acceptable levels of evidence.

From the meta-analysis, only 4 articles were considered for meta-analysis, as these provided CFU data for different categories of colour and hardness. Differences in log10CFU between categories of hardness were significantly greater than between categories of colour. However, CFU results were also not consistently reported. For instance, all 30 samples for Maltz et al. were categorized as ‘soft’, thus no comparison was possible. Also, Bjorndal et al. provided CFU for samples (n = 31) but they all were classified exclusively in only 2 colour categories (dark brown and black) and 2 hardness categories (medium hard and hard). Therefore, comparisons had to be focused to results from Lula et al. and Beighton et al. The difference between their sample sizes was extreme, so overall results from the meta-analysis inherited mostly properties and results from Beighton et al. As with weighted effect size calculations, results data also showed a large advantage for hardness examination compared to colour examination. However, unlike pooled meta-analysis calculations, the study by Bönecker et al. was added to the weighted total effect size calculations. This was possible because effect size can be calculated regardless of the differences in the reported units of CFUs as effect size calculations measure ratio of variability between groups to within-groups32. Nevertheless, the meta-analyses and effect size calculations data in this study indicate that the texture (or hardness) tactile clinical examination has more discriminatory power in comparison to the colour visual clinical examination. Therefore, hardness or texture categories are more reliable in reflecting the amount of isolated cariogenic microorganisms and thereby more reliable in detecting the severity of carious lesions. Thus, based on the findings of this study, the hardness tactile clinical examination is a more specific and sensitive clinical examination method as hardness categories would be more reliable indicators for treatment planning in which soft carious lesions would harbor more cariogenic microorganisms, if compared to hard carious lesions, and therefore may require a more intrusive dental clinical intervention. These findings are consistent with previously reported data in which hard carious lesions were found to harbour no cariogenic bacteria (e.g. neither streptococci nor lactobacilli) and therefore required no dental clinical interventions. On the other hand, a large proportion of soft carious lesions contained the latter species (63.6% and 48.4% respectively) and required both caries debridement and restoration10.

The findings of this systematic review can be viewed as additional evidence in support of the International and Caries Detection Assessment System (ICDAS), which is currently considered as the recommended dental caries examination scoring index in dental practice33. In this study, hardness clinical examination was found to be more specific and reliable than colour examination. Thus, changes in dental tissue hardness should warrant more scores in dental caries classification indices, which match the current setup of the ICDAS that emphasizes on the importance of hardness clinical examination by allocating more scores to changes in hardness33.

The findings of this systematic review must be interpreted with caution as there are a number of limitations. Firstly, it was not possible to group study data and findings in all of the included 7 studies due to the inconsistency and heterogeneous approaches in which the authors recorded teeth colour, hardness, and CFU. For instance, the articles reported various methodologies for detecting and analyzing microbial CFU. Also, the authors used dissimilar approaches to report CFU data, such as: some studies presented the results with “total CFU counts”19,28, while other studies used “turbidity tests”28,30. Other articles normalized the CFU data by using log10(CFU/mg)31 or log10(CFU + 1)10,14,29. Secondly, all data tables presented by the diagnostic test studies10,14 showed CFU percentages of different bacterial species instead of stating the exact numerical actual counts, which further made it difficult to group and compare data and findings across the studies and therefore made it difficult for conducting a meta-analysis of all included studies which also hampered our ability to have an overall systematic understanding of the data. Finally, most of the included studies were RCTs, a design that is more vulnerable to sampling bias without accurate sample size calculations. It was noticeable in this systematic review that sample size calculation was only reported in one study31.

In summary, this study presents systematically reviewed evidence in support of hardness clinical examination being a more reliable and specific dental caries detection method. Therefore, it is recommended to consider the use of tactile examination over visual inspection for caries detection during routine and treatment dental visits. However, due to the limitations in this study, further research is needed to consolidate the findings in this systematic review.

In conclusion, the microbial differences between hardness types showed a weighted total effect size with a large advantage for hardness compared to colour and colour alone also yielded inconsistent microbial results. Hardness is more reliable than colour to detect dentine caries severity.


text:
Challenges

+6
−0

# Description

From the Esolangs wiki,

In Fractran,

• a program consists of a finite list of positive, rational numbers.
• The input to a program is a positive integer n.
• The list is then searched in order, for a rational number $p/q$ such that $n×p/q$ is an integer.
• Then n is replaced by $n×p/q$ and the search is restarted from the beginning of the list.
• The program halts when no such number $p/q$ can be found, and the final n becomes the output from the program.
• Output the final value of $n$.

Your task is to implement an interpreter for this language.

# Input

You are to take two inputs:

• $n$, an integer
• $A$, an array of fractions, which may be taken as a list of pairs, or in the rational datatype of your language.

# Output

A single integer, the final value of $n$.

# Test Cases

Formatted as

program
input
output

78/55, 5/3, 1/5, 11/2, 5/7
1096135733
328842888196762472689573703

3/2
1296
6561

455/33, 11/13, 1/11, 3/7, 11/2, 1/3
72
15625
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

+6
−0

# APL (Dyalog Unicode), 33 bytes

{×x←⊃(2⌷⍵)(÷⍨(/⍨)0=|)⍺×1⌷⍵:x∇⍵⋄⍺}

Try it online!

The first case doesn't work because it gets really big, but the other two do. The input is taken on the left and the fractions are taken as a table on the right.

{×x←⊃(2⌷⍵)(÷⍨(/⍨)0=|)⍺×1⌷⍵:x∇⍵⋄⍺}
⍺×            ⍝ n multiplied by
1⌷⍵         ⍝ The first row of the right argument (every p)
(2⌷⍵)                        ⍝ Second row of right arg (all q's)
|              ⍝ All n×p modulo q
0=               ⍝ Check which ones are 0 (rational)
÷⍨                      ⍝ Make another vector of 'n×p÷q's
/⍨                  ⍝ And keep the ones that were rational
⊃                              ⍝ Pick the first (0 if empty)
x←                               ⍝ Assign to x
×                                 ⍝ Sign of x
⍺ ⍝ If sign is 0, return n
x∇⍵   ⍝ Otherwise, call again with x as new n

Why does this post require moderator attention?
You might want to add some details to your flag.

+4
−0

# Brachylog, 16 bytes

g₂;.z∋zbᵗ×ᵐ/ℤ↰|w

Try it online!

This is a function submission, which inputs n from the left and A from the right (as a list of two-element lists). Output is to standard output.

## Explanation

g₂;.z∋zbᵗ×ᵐ/ℤ↰|w
g₂                  place two list wrappers around the left input
;.                append the right input
z               cycling zip; because the left input is length 1,
this pairs it with each element of the right input
∋              find {the first} element for which no assertions fail
[at this point, the element looks like [[n], [num, denom]]
for some pair [num, denom] in A]
z             rearrange to [[n, num], [n, denom]]
bᵗ           remove first of last pair ([[n, num], [denom]])
×ᵐ         take product of each inner list ([n×num, denom])
/ℤ       divide; assert result (n×num÷denom) is an integer
↰      recurse (loop back to start of program)
|     if all else fails (i.e. ∋ found no elements)
w    output the current value to standard output

Why does this post require moderator attention?
You might want to add some details to your flag.

+3
−0

# Python 3, 76 71 bytes

Saved 5 bytes thanks to user

def f(p,n):l=[n*p//q for(p,q)in p if n%q<1];return f(p,l[0])if l else n

Try it online!

This code assumes that the fractions are given as completely cancelled pairs of integers.

Why does this post require moderator attention?
You might want to add some details to your flag.

#### 1 comment thread

General comments (1 comment)
+2
−0

# JavaScript, 44 bytes

a=>g=n=>a.every(([p,q])=>(x=n*p/q)%1)?n:g(x)

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

+2
−0

# Japt v2.0a0, 18 bytes

The r÷ can be removed if we can take an array of floats instead.

T=V£*Xr÷Ãæv1)?ßT:U

Try it

T=V£*Xr÷Ãæv1)?ßT:U     :Implicit input of integer U and 2D-array V
T=                     :Assign to variable T
V£                   :  Map each X in V
*                  :    Multiply U by
Xr÷               :    X reduced by division
Ã              :  End map
æ             :  Get the first element that
v1           :    Is divisible by 1
)          :End assignment
?         :If truthy (not undefined)
ßT       :Recursive call with arguments U=T and V unchanged
:U     :Else return U
Why does this post require moderator attention?
You might want to add some details to your flag.

+1
−0

# Ruby, 51 50 bytes

-1 from Razetime

->p,n{while i=p.find{(_1*n).to_f%1==0}
n*=i
end
n}

Try it online!

Why does this post require moderator attention?
You might want to add some details to your flag.

#### 1 comment thread

-1 changing to n*=i (1 comment)

This community is part of the Codidact network. We have other communities too — take a look!

You can also join us in chat!

Want to advertise this community? Use our templates!


text:
2019
Том 71
№ 6

# Automorphisms of a finitary factor power of an infinite symmetric group

Hudzenko S. V.

Abstract

We consider a semigroup $FP^{+}_{\text{fin}}(\mathfrak{S}_{\text{fin}}(\mathbb{N}))$ defined as a finitary factor power of a finitary symmetric group of countable order. It is proved that all automorphisms of $FP^{+}_{\text{fin}}(\mathfrak{S}_{\text{fin}}(\mathbb{N}))$ are induced by permutations from $\mathfrak{S}_{\text{fin}}(\mathbb{N})$.

English version (Springer): Ukrainian Mathematical Journal 62 (2010), no. 7, pp 1158-1162.

Citation Example: Hudzenko S. V. Automorphisms of a finitary factor power of an infinite symmetric group // Ukr. Mat. Zh. - 2010. - 62, № 7. - pp. 997–1001.

Full text


text:
# In (O'Brien et al. 2004), why is the target qubit not affected when the control is $\vert 0\rangle$?

I'm currently reading this paper https://arxiv.org/abs/quant-ph/0403062 but I fail to understand how the input of the control qubit affects the output of the target qubit. I do understand that when the logical value of the control qubit channel is $$\vert 0\rangle$$ the qubit in the channel of the target qubit is not affected. But I don't see how does the gate work when the control and target qubit have a logical value of $$\vert 1\rangle$$.

• quoting or including in the post the relevant parts of the paper would make the question easier to answer without people having to go read the paper itself
– glS
May 27 at 19:16
• Looks like they cited this paper regarding the CNOT they implement: arxiv.org/pdf/quant-ph/0112088.pdf May 28 at 9:57


text:
Formatted question description: https://leetcode.ca/all/2022.html

# 2022. Convert 1D Array Into 2D Array (Easy)

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with  m rows and n columns using all the elements from original.

The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.

Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation:
The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.

Example 2:

Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation:
The constructed 2D array should contain 1 row and 3 columns.
Put all three elements in original into the first row of the constructed 2D array.

Example 3:

Input: original = [1,2], m = 1, n = 1
Output: []
Explanation:
There are 2 elements in original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.

Example 4:

Input: original = [3], m = 1, n = 2
Output: []
Explanation:
There is 1 element in original.
It is impossible to make 1 element fill all the spots in a 1x2 2D array, so return an empty 2D array.

Constraints:

• 1 <= original.length <= 5 * 104
• 1 <= original[i] <= 105
• 1 <= m, n <= 4 * 104

Similar Questions:

## Solution 1. Brute Force

// OJ: https://leetcode.com/problems/convert-1d-array-into-2d-array/
// Time: O(K) where K is the length of the original array
// Space: O(1)
class Solution {
public:
vector<vector<int>> construct2DArray(vector<int>& A, int m, int n) {
if (A.size() != m * n) return {};
vector<vector<int>> ans(m, vector<int>(n));
int k = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans[i][j] = A[k++];
}
}
return ans;
}
};

## Discuss

https://leetcode.com/problems/convert-1d-array-into-2d-array/discuss/1499226/C%2B%2B-Brute-Force


text:
Spring scale

1. Jun 29, 2008

ace123

If you stand on a bathroom scale, spring inside compresses .6mm, and tells your weight is 710 N. Now if you jump on the scale from a height of 1m, what does the read at it's peak?

This is what I tried to do:

I used Hooke's law: F$$_{}s$$= k*x
and solved for the k which is spring constant.

Then I wasn't too sure of how to find the spring compression when he jumps from a height of 1m. I tried to use conservation of mechanical energy:

I did the potential energy of the the guy at 1m and set it equal to the kinetic energy when he hits the scale.

I then set up another conservation of mechanical energy for the scale. Which was Kinetic energy equal to the compression 1/2kx^2.

This is wrong however and I have no clue what else to try.

Thanks for the help

2. Jun 29, 2008

Hootenanny

Staff Emeritus
Your method seems correct to me, however there is no need for the intermediate step you can just jump straight to setting the gravitational potential energy equal to the potential energy stored in the spring.

Note however, that the question asks for the reading on the scale, not the compression of the spring.

3. Jun 29, 2008

ace123

I understand that so after I find the compression of the spring i should multiply it by the spring constant. Correct? I threw in the intermediate step because I wasn't sure if you could jump from the gravitational potential energy straight to the spring.

4. Jun 29, 2008

ace123

Prehaps I made a mathematical mistake. Let me check it again.

5. Jun 29, 2008

Hootenanny

Staff Emeritus
That is correct. In that case, it is most likely that you have made an arithmetic error; or if you are submitting your answer online your significant figures are out.

6. Jun 29, 2008

ace123

Well the answer in the book is 4.2*10^4. But I'm not getting that. Can you check my math when I post it? Thanks

7. Jun 29, 2008

Hootenanny

Staff Emeritus
No problem

8. Jun 29, 2008

ace123

Wow you will not believe what I did. I thought .6mm was .6*10^-5. Got it confused with micro. Sorry for bothering you.

9. Jun 29, 2008

Hootenanny

Staff Emeritus
It usually is the small mistakes that trip you up! Don't worry about it.


text:
## LaTeX forum ⇒ MiKTeX and proTeXt ⇒ pdfcrop: The Perl script could not be found.

Information and discussion about MikTeX distribution for Windows and the related proTeXt: Installing, updating, configuring
Ede_123
Posts: 5
Joined: Tue Jan 25, 2011 7:37 pm

### pdfcrop: The Perl script could not be found.

Hi,

I have a problem concerning pdfcrop.

When I call pdfcrop from commandline I get the following error:
`D:\>pdfcroppdfcrop: The Perl script could not be found.pdfcrop: Data: scripts/pdfcrop/perl/pdfcrop.pl`

I'm using Windows7 x64, Miktex 2.9 (x86) and I installed Active Perl (x86).
The following files are present in my miktex installation:
C:\Program Files (x86)\TeX\MiKTeX 2.9\miktex\bin\pdfcrop.exe
C:\Program Files (x86)\TeX\MiKTeX 2.9\scripts\pdfcrop\pdfcrop.pl

I also tried copying pdfcrop.pl to
C:\Program Files (x86)\TeX\MiKTeX 2.9\scripts\pdfcrop\perl\pdfcrop.pl
but it didn't change anything.

My PATH varialbe contains:
C:\Program Files (x86)\Perl\site\bin
C:\Program Files (x86)\Perl\bin
C:\Program Files (x86)\TeX\MiKTeX 2.9\miktex\bin

I allready tried calling the perl script directly. It works but produces another error (probably due to some path error)

Does anyone have an idea what's wrong with my setup of pdfcrop?
Last edited by Ede_123 on Fri Aug 19, 2011 9:01 pm, edited 1 time in total.

Ede_123
Posts: 5
Joined: Tue Jan 25, 2011 7:37 pm
Update:
Ok, I successfully broke pdfcrop on my laptop were it used to work before.
What I did was an update of MikTeX today. Yesterday everything worked ok...

Is there somebody who could assist me in locating the origin of the problem? Since I'm not too familiar with the internal structure of LaTeX it's quite complicated for me to track down what package update broke pdfcrop for me.

I assume first step would be to find what packages got updated and what version they were before. Is there a logfile somewehere, where the updates are written to?

Update 2:
Okay, I did it! pdfcrop is working again.

Problem seems, that pdfcrop.exe actually searches for pdfcrop.pl in
MiKTeX 2.9/scripts/pdfcrop/perl/
but after the pdfcrop update to v1.32 from 2011/08/10 ist is just written to
MiKTeX 2.9/scripts/pdfcrop

My approach to copy pdfcrop.pl into the subfolder /perl didn't work in the first place because I forgot to refresh file name database. (MiKTeX Options -> Refresh FNDB)

I'm going to refer this thread to Heiko Oberdiek, pdfcrops author. I assume he knows what to do, to resolve this problem in future versions.

Update 3:
Since it's probably an issue with MiKTeX and not with pdfcrop itself I created a bugreport here:
https://sourceforge.net/tracker/?func=d ... tid=110783

Stefan Kottwitz
Posts: 8072
Joined: Mon Mar 10, 2008 9:44 pm
Location: Hamburg, Germany
Contact:

Stefan

Ede_123
Posts: 5
Joined: Tue Jan 25, 2011 7:37 pm
The bug has been fixed. The fix will be made available with the
next update cycle. You can watch the MiKTeX project page
for further information on the next update.

(From http://sourceforge.net/tracker/?func=de ... tid=110783)