Ad It Ya

Shortest Circuit Evaluation
Short circuit evaluation of Boolean expressions denotes the semantic in which the second argument of some Boolean operator is not evaluated if the value of the first argument is enough to have the result. This technique is used in many programming languages to optimize the evaluation of Boolean expressions. Specifically for "A and B", if A is false we know that the whole expression is false and we don't need to evaluate B. For "A or B", if A is true we know the result to be true. Now having that those Boolean operations are commutative we may actually evaluate B first and not evaluate A in case B gives us the result. Moving the idea further if we have "A1 or A2 or...or An" we can evaluate the variables in any order and as soon as we have one of them as true we know that the whole expression is true. We can do similarly for and operation. Now let's consider some complex Boolean expression. We will fix the order in which we will evaluate the variables of the expression. Then we evaluate those variables in that order and we won't evaluate the variables that give us no new information about the value of the whole expression in the process. For example, assume we have "A and B or C" and we fix the order of evaluation B, A, C. First we evaluate B, if it's false we don't have to evaluate A and only evaluate C. However if B is true we will need to evaluate A. If A is true we know the expression is true and won't evaluate C, otherwise we evaluate C to have the value of the expression. Now your task is having some complex Boolean expression containing and, or, not operations and for each variable having the probability that this variable is true, you need to find the order of evaluation for which the expected number of evaluations in the process described above will be minimal.
Input
The first line of input file contains number t - the amount of test cases. Then t test cases follow. The first line of each test case will contain the Boolean expression. The expression will be valid and will consist of and, or, not operations, brackets and variable names. All the variable names in one expression will be distinct. Then for each variable present in the expression there will be a line in the input in the format s p, where s - the name of the variable and p - is the probability that the variable will be true. The names of the variables will consist of small Latin letters only.
Constraints
1 <= t <= 50 0<p<1 The length of the expression won't exceed 30000 characters. There will be no more than 1000 variable in the expression. The length of the variable names won't exceed 5 characters. Also the expression will be in the form of either conjunctive or disjunctive normal form.
Output
For each test case output the expected number of evaluations for the optimal order of evaluation of variables for short circuit evaluation process described above. Output the answer with 6 digits after the dot.
Example
Input: 3 (a and b) or c a 0.3 b 0.4 c 0.5 (a or b) and (not d or c) a 0.5 b 0.3 c 0.8 d 0.25 ab or bc or cd ab 0.3 bc 0.1 cd 0.2 Output: 1.650000 2.280000 2.260000
Explanation
In the first test case the best order is c, a, b
Rotation Puzzle
Given a MxN rectangular grid in which each cell contains a unique number from 1 to MxN. In each step, the player can pick any 2x2 subgrid and perform a rotation (whether clockwise or counterclockwise). The task is to transform from the initial grid to the final configuration, using as few steps as possible. The final configuration is the configuration 1 2 ... n n+1 n+2 ... 2n ... ... ... ... (m-1)n+1 (m-1)n+2 ... mn You may have guessed why this game is addictive: it requires a tremendous visualization skill!
Input
The first line contains a number T (about 5000), which is the number of test cases. Each test case has the following form. The first line contains two numbers M and N (2 <= M, N <= 34). The next M lines contains the description of the grid. Each test case's input is separated by a blank line. It is guaranteed that each input data has a solution.
Output
For each test case, output the result in the following format. The first line contains a number K, the number of steps you need to solve the puzzle. K must not exceed 10000. Each line of the next K lines contain three numbers c, i, j (c=0 or c=1, 1<=I < M, 1 <= J < N). (i,j) is the top-left coordinate of the 2x2 square that is need to be rotated. c=1 if the rotation if clockwise and c=0 if the rotation is counter-clockwise. Prints a blank link after each test case's output.
Scoring
Given m and n, we pick a random positive integer K* and starting from the final configuration, we perform a random operation K* times to generate the test case. For each test case, your score is K*/K+1.
Example
Input: 2 2 3 1 5 2 4 6 3 2 3 5 6 2 1 4 3 Output: 1 0 1 2 2 1 1 1 0 1 2
Graph Challenge
Statement
You are given a modified graph with N vertices and M edges. Each vertex is a rectangle [ dimension of each vertex may be different ] . Your task is to place these vertices in 2-d space such that :

No two vertices overlap [ remember, they are rectangles ] All rectangles have their sides parallel to the axis. Rectangles cannot be rotated.
For every edge in the graph, add the manhattan distance between the centres of the vertex for each edge as the cost of a solution ( C ). Now, there might be multiple ways to achieve this. So, you have to strive to keep C as low as possible.
Input
First line contains t ( 100 ) equal to the number of test cases. For each test case, the first line contains 2 space separated integers ( N and M respectively ). Then M lines follow, each line containing 2 integers x and y ( 0 x,y < N , x y ) denoting an edge between vertex x and y. Then follow N lines, where line number i contains 2 integers a and b denoting the dimension of the ith vertex [ Here, a denotes the length parallel to x-axis and b denotes the length parallel to y-axis ] ( Note : If the same pair x,y appears multiple times, it denotes multiple edges and hence, each pair contributes to the cost ). NOTE : Please note that all solutions will be tested on another set of test data after the contest which will follow the same pattern for test case generation ( as mentioned in 'Test Case Generation' section ). The final score for a solution will be the score of solution on latter test data.
Output
For each test case, print N lines , each containing 2 floating point numbers X and Y, denoting the co-ordinates of the centre of vertex i. Note : -109 X,Y 109 . Solutions not following the mentioned constraints will be adjudged as wrong answer. Please note that the answers may not be optimal
Scoring
The Score for a solution = (C+1). Your total score is the sum of your score for all the test cases. You have to keep the score as low as possible.
Constraints
2 N 50 1 M 200 [ The edges are randomly generated ] 1 a,b 100000 There can be multiple edges between a pair of vertices. Additionally for 50% of the cases 2 N 20. Also, for about 50% of cases, all vertices are squares [ a = b ] of same size.
Test Case Generation

There are about 100 cases in total. For first 50 cases, the number of vertex ( n ) is chosen as a random number in the interval [3,20]. The number of edges (m) is chosen as a random number in the range [2, n*(n-1)/2]. Then all edges are chosen as random pair of integers. All vertex are given the same dimension with the probability 0.5 else they are given a random dimension in [1,100000] * [1,100000]. For other 50 cases, n is chosen as a random integer in the interval [3,50]. m is chosen randomly from [2, min( n*(n-1)/2, 200) ]. Rest of the procedure remains the same.
Sample Input
1 2 0 2 2
1 1 2 2
Sample Output
2 2 10 3

Ad It Ya

Uploaded by

Copyright:

Available Formats

Ad It Ya

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ad It Ya

Uploaded by

Copyright:

Available Formats

Shortest Circuit Evaluation

Test Case Generation

You might also like