text:
# Intuition behind equation of line in Vector form

I'm new to Vector and 3D Geometry and today I was taught the equation of a line passing through two points $$A(\vec{a})$$ and $$B(\vec{b})$$ as $$\vec{r}=\vec{a} + λ(\vec{b}-\vec{a})$$

It is difficult for me to imagine how this works. Why do we have a $$λ$$ here? What I can think of is that $$\vec{r}=\vec{a} + λ(\vec{b}-\vec{a}$$) means that if we draw a line passing through $$A$$ and $$B$$ and we plug in different values of $$λ$$, we will get the position vector of different points that lie on that line. Am i right in thinking so? So this is a bit different from the stuff we use in $$2D$$ geometry or other forms like expressing the line in terms of $$x,y,z$$?

• Yes you are right in your thinking. $\lambda=0$ corresponds to $A(\vec{a})$ and if you move parallel to a vector $\vec{b}$ you will get the line $\vec{r}=\vec{a}+\lambda \vec{b}$ Oct 20 at 15:29
• That equation isn't quite right. Oct 20 at 15:30
• @PM2Ring oops, my bad, I did correct it now.
– Vega
Oct 20 at 16:21
• That's much better. :) Oct 20 at 16:22
• FWIW, another useful way to write this is $$\vec{r}=(1-\lambda)\vec{a} + \lambda\vec{b}$$ Oct 20 at 16:35

Here is a visual explanation, for vectors in $$\mathbb{R}^2$$. The vectors $$\vec{a}$$ and $$\vec{b}$$ fix two points in space. Consider the difference $$\vec{b}-\vec{a}$$ shown by the red arrows. Then, we move a certain number of lengths of $$\vec{b}-\vec{a}$$ (given in the picture by $$\lambda=5$$) along the direction of $$\vec{b}-\vec{a}$$. The resulting vector $$\vec{a}+\lambda(\vec{b}-\vec{a})=\vec{a}+5(\vec{b}-\vec{a})$$ has its tip on a line that clearly goes through the tips of $$\vec{a}$$ and $$\vec{b}$$ and is parallel to $$(\vec{b}-\vec{a})$$.

In general, $$\lambda$$ can be anything, so there can be any number of $$\vec{b}-\vec{a}$$'s, including fractional amounts, added to $$\vec{a}$$. This traces out the entire line.

• +1, Awesome visual representation. So you basically have $\vec{a}$ and then $\vec{b}-\vec{a}$ is a vector parallel to the line joining $A$ and $B$ and this multiplied by $λ$ gives different vectors along the line which when added with $\vec{a}$ by triangular law of addition gives the position vector of different points on the line. Did I get it correct?
– Vega
Oct 20 at 16:26
• @Vega I updated me answer to correspond to your updated post. Oct 20 at 16:31
• And yes the original (typo) basically corresponds to the equation of a line passing through A and parallel to a vector $\vec{b}$
– Vega
Oct 20 at 16:37
• You got it correct. Oct 20 at 16:38

Remember, Euclidean vectors are not points; $$\begin{pmatrix} 1 \cr 1 \cr 1\end{pmatrix}$$ is neither the point $$(1,1,1)$$ nor affixed between the origin and $$(1,1,1);$$ rather it is "portable" and represents a particular translation in space.

The parametric equation$$\vec{r}=\vec{a} + λ\vec{u}$$ of a line is actually very intuitive: it is saying that to land on any point $$(x,y,z)$$ on the line, start at the origin and move directly to point $$A$$ (after all, $$\vec{a}$$ is just $$A$$'s position vector), then move along $$\vec{u}$$ by a $$some$$ (negative/zero/positive) multiple of its length.

Then, the position vector $$\vec{r}=\begin{pmatrix} x \cr y \cr z\end{pmatrix}$$ of that point is given by the vector sum of these two movements/translations.

There is one parameter҂, $$\lambda,$$ because a line has one degree of freedom҂: the real-valued multiple that I mentioned above is the value of $$\lambda$$ that lands us on that particular point (and which gives its particular position vector $$\vec{r}$$). As $$\lambda$$ varies over $$\mathbb R,$$ every single point on that line will have been covered.

҂ Lines (including curved lines) in $$3$$-D space are nonetheless $$1$$-dimensional objects in the sense that when constrained to the line, a single number (parameter) is sufficient to fully specify the position of each point. This is why their parametric equations (whether in $$2$$-D space or $$3$$-D space) contain only a single parameter. Planes, on the other hand, have two parameters in their parametric equation $$\vec{r}=\vec{a} + λ\vec{u}+\gamma\vec{v}$$.
• @RyanG Yeah, either way, in both questions, the concept was the same, which I understood
– Vega
Oct 20 at 17:18

Rather than looking at a line lets examine a line segment beginning at the point represented by a position vector $$p$$ and in the direction of some other vector $$x$$ that tells us the orientation and length of the segment. Geometrically this means we simple add $$p + x$$ to find where the line segment ends, but what if I want to label every position on the line segment? Well, looking at the half way point along the segment we see that it's at position $$p + \frac{1}{2}x$$ and a quarter is $$p + \frac{1}{4}x$$. Examining other points on the segment we see that as long as we pick some scalar multiple of $$x$$ between zero and one it represents a point on the segment. This gives us the geometric intuition as to why we can now parameterize the line segment as $$p + \lambda x$$ for some real number $$0 \leq \lambda \leq 1$$. Now that we have the segment parameterized all we have to do to get the entire line is let $$\lambda$$ take on any real value. Note that the dimension of the space was irrelevant here as everything was happening in the plane containing $$p$$ and $$x$$ so the two dimensional case is sufficient for geometric purposes.


text:
## Seminars and Colloquia by Series

Thursday, February 19, 2009 - 11:00 , Location: Skiles 269 , Amigo Garcia , Miguel Hernández University, Spain , Organizer: Guillermo Goldsztein
Molecular topology is an application of graph theory to fields like chemistry, biology and pharmacology, in which the molecular structure matters. Its scope is the topological characterization of molecules by means of numerical invariants, called topological indices, which are the main ingredient of the molecular topological models. These models have been instrumental in the discovery of new applications of naturally occurring molecules, as well as in the design of synthetic molecules with specific chemical, biological or pharmacological properties. The talk will focus on pharmacological applications.
Thursday, February 5, 2009 - 11:00 , Location: Skiles 269 , Alexander Shnirelman , Department of Mathematics, Concordia University , Organizer: Guillermo Goldsztein
Consider the 2-d ideal incompressible fluid moving inside a bounded domain (say 2-d torus). It is described by 2-d Euler equations which have unique global solution; thus, we have a dynamical system in the space of sufficiently regular incompressible vector fields. The global properties of this system are poorly studied, and, as much as we know, paradoxical. It turns out that there exists a global attractor (in the energy norm), i.e. a set in the phase space attracting all trajectories (in spite the fact that the system is conservative). This apparent contradiction leads to some deep questions of non-equilibrium statistical mechanics.
Thursday, January 22, 2009 - 11:00 , Location: Skiles 269 , Alexander Its , Indiana University-Purdue University Indianapolis , Organizer: Guillermo Goldsztein
In this talk we will review some of the global asymptotic results obtained during the last two decades in the theory of the classical Painleve equations with the help of the Isomonodromy - Riemann-Hilbert method. The results include the explicit derivation of the asymptotic connection formulae, the explicit description of linear and nonlinear Stokes phenomenon and the explicit evaluation of the distribution of poles. We will also discuss some of the most recent results emerging due to the appearance of Painleve equations in random matrix theory. The Riemann-Hilbert method will be outlined as well.
Thursday, January 15, 2009 - 11:00 , Location: Skiles 269 , Igor Pritzker , Oklahoma State University , Organizer: Guillermo Goldsztein
Issai Schur (1918) considered a class of polynomials with integer coefficients and simple zeros in the closed unit disk. He studied the limit behavior of the arithmetic means s_n for zeros of such polynomials as the degree n tends to infinity. Under the assumption that the leading coefficients are bounded, Schur proved that \limsup_{n\to\infty} |s_n| \le 1-\sqrt{e}/2. We show that \lim_{n\to\infty} s_n = 0 as a consequence of the asymptotic equidistribution of zeros near the unit circle. Furthermore, we estimate the rate of convergence of s_n to 0. These results follow from our generalization of the Erdos-Turan theorem on discrepancy in angular equidistribution of zeros. We give a range of applications to polynomials with integer coefficients. In particular, we show that integer polynomials have some unexpected restrictions of growth on the unit disk. Schur also studied problems on means of algebraic numbers on the real line. When all conjugate algebraic numbers are positive, the problem of finding \liminf_{n\to\infty} s_n was developed further by Siegel and many others. We provide a solution of this problem for algebraic numbers equidistributed in subsets of the real line.
Thursday, November 6, 2008 - 11:00 , Location: Skiles 269 , Chongchun Zeng , School of Mathematics, Georgia Tech , Organizer: Guillermo Goldsztein
In this talk, we discuss 1.) the nonlinear instability and unstable manifolds of steady solutions of the Euler equation with fixed domains and 2.) the evolution of free (inviscid) fluid surfaces, which may involve vorticity, gravity, surface tension, or magnetic fields. These problems can be formulated in a Lagrangian formulation on infinite dimensional manifolds of volume preserving diffeomorphisms with an invariant Lie group action. In this setting, the physical pressure turns out to come from the combination of the gravity, surface tension, and the Lagrangian multiplier. The vorticity is naturally related to an invariant group action. In the absence of surface tension, the well-known Rayleigh-Taylor and Kelvin-Helmholtz instabilities appear naturally related to the signs of the curvatures of those infinite dimensional manifolds. Based on these considerations, we obtain 1.) the existence of unstable manifolds and L^2 nonlinear instability in the cases of the fixed domains and 2.) in the free boundary cases, the local well-posedness with surface tension in a rather uniform energy method. In particular, for the cases without surface tension which do not involve hydrodynamical instabilities, we obtain the local existence of solutions by taking the vanishing surface tension limit.
Thursday, October 16, 2008 - 11:00 , Location: Skiles 269 , Mohammad Ghomi , School of Mathematics, Georgia Tech , Organizer: Guillermo Goldsztein
We prove that a smooth compact submanifold of codimension $2$ immersed in $R^n$, $n>2$, bounds at most finitely many topologically distinct compact nonnegatively curved hypersurfaces. This settles a question of Guan and Spruck related to a problem of Yau. Analogous results for complete fillings of arbitrary Riemannian submanifolds are obtained as well. On the other hand, we show that these finiteness theorems may not hold if the codimension is too high, or the prescribed boundary is not sufficiently regular. Our proofs employ, among other methods, a relative version of Nash's isometric embedding theorem, and the theory of Alexandrov spaces with curvature bounded below, including the compactness and stability theorems of Gromov and Perelman. These results consist of joint works with Stephanie Alexander and Jeremy Wong, and Robert Greene.
Thursday, October 2, 2008 - 11:00 , Location: Skiles 269 , John Etnyre , School of Mathematics, Georgia Tech , Organizer: Guillermo Goldsztein
Describe the trajectories of particles floating in a liquid. This is a surprisingly difficult problem and attempts to understand it have involved many diverse techniques. In the 60's Arold, Marsden, Ebin and others began to introduce topological techniques into the study of fluid flows. In this talk we will discuss some of these ideas and see how they naturally lead to the introduction of contact geometry into the study of fluid flows. We then consider some of the results one can obtain from this contact geometry perspective. For example we will show that for a sufficiently smooth steady ideal fluid flowing in the three sphere there is always some particle whose trajectory is a closed loop that bounds an embedded disk, and that (generically) certain steady Euler flows are (linearly) unstable.
Thursday, October 2, 2008 - 11:00 , Location: Skiles 269 , John Etnyre , School of Mathematics, Georgia Tech , Organizer: Guillermo Goldsztein
Describe the trajectories of particles floating in a liquid. This is a surprisingly difficult problem and attempts to understand it have involved many diverse techniques. In the 60's Arold, Marsden, Ebin and others began to introduce topological techniques into the study of fluid flows. In this talk we will discuss some of these ideas and see how they naturally lead to the introduction of contact geometry into the study of fluid flows. We then consider some of the results one can obtain from this contact geometry perspective. For example we will show that for a sufficiently smooth steady ideal fluid flowing in the three sphere there is always some particle whose trajectory is a closed loop that bounds an embedded disk, and that (generically) certain steady Euler flows are (linearly) unstable.
Thursday, September 18, 2008 - 11:00 , Location: Skiles 269 , Leonid Bunimovich , School of Mathematics, Georgia Tech , Organizer: Guillermo Goldsztein
It has been found about ten years ago that most of the real networks are not random ones in the Erdos-Renyi sense but have different topology (structure of the graph of interactions between the elements of a network). This finding generated a steady flux of papers analyzing structural aspects of networks.  However, real networks are rather dynamical ones where the elements (cells, genes, agents, etc) are interacting dynamical systems. Recently a general approach to the studies of dynamical networks with arbitrary topology was developed. This approach is based on a symbolic dynamics and is in a sense similar to the one introduced by Sinai and the speaker for Lattice Dynamical Systems, where the graph of interactions is a lattice. The new approach allows to analyse a combined effect of all three features which characterize a dynamical network (topology, dynamics of elements of the network and interactions between these elements) on its evolution. The networks are of the most general type, e.g. the local systems and interactions need not to be homogeneous, nor restrictions are imposed on a structure of the graph of interactions. Sufficient conditions on stability of dynamical networks are obtained. It is demonstrated that some subnetworks can evolve regularly while the others evolve chaotically. This approach is a very natural one and thus gives a hope that in many other problems (some will be discussed) on dynamical networks a progress could be expected.

format: plain


text:
### chokudai's blog

By chokudai, history, 3 months ago, ,

We will hold AtCoder Beginner Contest 133.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +36

 » 3 months ago, # |   +6 Thanks for organizing!I hope this will be my last (rated) ABC. :)
•  » » 3 months ago, # ^ |   +7 Good luck ! I hope that you continue to participate in future too and more importantly provide English Tutorial for the contest :D. It helps others a lot !
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +8 Thanks, your comment meant a lot to me. And I'll try my best to have an English editorial for this contest out today.Edit: check out Geothermal's write-up here: https://codeforces.com/blog/entry/68231.
•  » » » » 3 months ago, # ^ |   +11 I have to say that i really enjoy your editorial and i am thankful for that.
•  » » 3 months ago, # ^ |   +3 Did ur dreams come true?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 We'll see, haha, there are still a couple AGCs before the next ABC. Thanks for asking!
 » 3 months ago, # |   +11 How to solve F?
•  » » 3 months ago, # ^ |   +5 I solved it using Persistent Segment Tree.
•  » » » 3 months ago, # ^ |   0 Can you explain your solution more detailed, please?
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +3 You can have a look at https://atcoder.jp/contests/abc133/submissions/6297869 The basic idea is to keep track of sum of all edges having a particular colour and no of edges of that particular colour from root to all the vertices.
•  » » 3 months ago, # ^ |   +3 We essentially use LCA with square-root decomposition. A more detailed description of my solution is at https://codeforces.com/blog/entry/68231.
•  » » » 3 months ago, # ^ |   +5 I did F using LCA with Euler Tour+Segment Tree.Time Complexity — $O(n*log^2(n))$My Submission
•  » » » » 3 months ago, # ^ |   0 Can you explain your solution more detailed, please?
•  » » 3 months ago, # ^ |   +8 I solve by sqrt-decomposition of path (something like LCA).
•  » » 3 months ago, # ^ | ← Rev. 2 →   +10 We can also solve it using BIT maintaining the Eulerian order of the tree.Let $dis(u,v)$ be the sum of $d$ from $u$ to $v$ on the original tree. We have $Q(x,y,u,v) = dis(u,v) + \sum_{e \in path(u,v),color(e) = x} cst(e) + \sum_{e \in path(u,v),color(e) = x} 1$Thus, we can solve queries with the same $x$ together. Use two BITs to maintain $\sum_{e} cst(e)$ and $\sum_e 1$. Modify it before and clear it after printing answers to them.It works in $nlogn$ time.Actually, my solution is the fastest so far:D
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +8 My idea was exactly same. I did it in Online mode.My in contest submission is slowest so far. :D
•  » » 3 months ago, # ^ |   0 I think it can be solved in $O(n\ log(n))$.like this My Submission
•  » » » 3 months ago, # ^ |   0 My solution works in logn time
•  » » 3 months ago, # ^ |   +8 I had an online solution with LCA, Eulerian tour and prefix sums. The idea seems to be similar to those of 11235813213455.Let's write down an Eulerian tour over edges (counting them with "+" when going down and with "-" when going up). We store prefix sums for all the edges ("large" array), and for edges of each specific color ("small" arrays). When answering the query, we split the path into two parts and consider only paths from LCA to each vertex. To find an answer, we need total path length and the contribution of the specific color. But it's just a sum on a segment (on "large" array or on one of the "small" arrays). Also, to find the bounds of the segment on a "small array", we can store which edges appear in this array and then perform a binary search.The code is here.This solution is $O(N\log N)$. It's neither the slowest, nor the fastest :)
 » 3 months ago, # |   0 How to solve E?I solved F with sqrt-decomposition but didn't find any ideas in E
•  » » 3 months ago, # ^ |   +19
•  » » 3 months ago, # ^ | ← Rev. 5 →   +8 For E you could use multiplication principle. Start with the root. We have k choices here. Now the first child will have k — 1 choices, second will have k — 2 and so on. But while calling dfs for children keep track of how many siblings of the node you traversed. Because for node x all its siblings wont have an effect on children of x. Just work it out you will get it. One more thing for depths greater than 3 the dependency on the node higher than current nodes by 2 will not be there.
•  » » 3 months ago, # ^ |   +1 Root the tree arbitarily. If you are at the root. You can assign the color for the root in K ways and its children in (K-1)P(degree[root]) ways. For the other vertices you can assign the colors for its children in (K-2)P(degree[vertex]-1) ways.
 » 3 months ago, # |   +1 How to solve Problem D??
•  » » 3 months ago, # ^ | ← Rev. 2 →   +14 It was a system of linear equation. We had equations in the format. x1+x2=a1 x2 +x3=a2 . . . xn + x1=an But if you add and subtract first n-1 terms alternately. You will always get x1-xn = alternate sum of n-1 terms. Using this and last equation we can get x1 and now x2 and x3 and so on till xn can be ascertained
•  » » 3 months ago, # ^ |   +6 Let's denote the water in dams from 1 to $n$ as $x_1,x_2...x_n$ and the water on each mountain as $y_1,y_2...y_n$.Then the equations read as $x_1=(y_1+y_2)/2$, $x_2=(y_2+y_3)/2$, . . . $x_n=(y_n+y_1)/2$ Now see that $x_1-x_2+x_3-x_4+...x_n=y_1$ From $y_1$ we can successively find $y_2,y_3$ so on by substituting in the original equations.
 » 3 months ago, # | ← Rev. 2 →   +9 Two things. Since in the last few ABCs some people have volunteered for editorials it would be nice if you can add the link of such editorials in the announcement. Was E a case of coincidence?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 E was a problem from codejam semifinals(2008) but with slight reduction in constraints http://www.manchik.co.uk/problem/32010/2
 » 3 months ago, # |   0 I got C wrong, Test case 16, stride_zero_01. I dont get it. Can somebody tell me what is wrong? Thanksresult
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 2 2020 Your answer is 2, but the correct answer should be 0.I guess that you can't just swap l and r after l %= 2019 and r %= 2019.
•  » » 3 months ago, # ^ |   +2 Swapping l and r if l > r is incorrect. 6 2024 is a countercase: your solution prints 30; the correct answer is 0.Adding 2019 to r in this case should fix the error.
•  » » 3 months ago, # ^ |   +2 Modulos is circular. After taking modulo of l and r with 2019, if r > l then also answer can be zero. For ex. lets take l = 2 and r = 29 and taking mod with 5 , then after taking modulo with 5 , r = 4 and l = 2 , but here answer will be 0 as r became 4 after 3 or 4 round of modulo circle.
•  » » 3 months ago, # ^ |   +2 Your code gives 2 as output for l=1 and r=2023, ans should be 0(i=1,j=2019) The problem is SpoilerYou should check whether floor(l/2019) and floor(r/2019) are same or not. If they aren't, answer is 0 because a number between l and r is divisible by 2019.
•  » » » 3 months ago, # ^ |   0 This testdata is better than others, my submission code can accept 2 2020, 6 2024. But cannot accept this data.MY CODE ON ATCODER
•  » » » » 3 months ago, # ^ |   0 This is because my code turned into 1 and 4, and this causes error to my code
•  » » 3 months ago, # ^ |   0 It is enough to have all 2019 modulos of 2019 number. After it you can calculate minimum product of all modulos. In loop from l to r you calculate current module, when you size of modulos reaches 2019 you break from loop. Then you can calculate minimum product.
•  » » 3 months ago, # ^ |   0 I have a simple solution. If the distance between l and r is greater than 2019 then it will certainly contain a factor of 2019 and hence the answer will be zero. Otherwise we can calculate by brute force.
 » 3 months ago, # |   0 How to solve Problem F??
•  » » 3 months ago, # ^ |   0 No body can reply this?
•  » » » 3 months ago, # ^ |   0 Actually, you can find the solution of this problem by click the url below solution
•  » » » » 3 months ago, # ^ |   0 Thx
 » 3 months ago, # |   0 Can some explain F in simple words i know about sqrt decomposition but was unable to come up with the solution
 » 3 months ago, # |   0 Can anyone explain the logic behind E.
•  » » 3 months ago, # ^ | ← Rev. 5 →   +5 I will try to phase it so that everyone can understand. We will use multiplication principle of counting. Step number one consider any node(preferably 1) as root. We can color it in k ways. Now if I consider its children they cannot be colored in the same color as its parent(as a matter of fact no child can be colored with the same color as its parent). Now for any node, if it has sibling(same parent), it will have a distance of 2 from its sibling. So if a parent can be colored in $m$ ways, its first child can be colored in at least $m - 1$ ways(I will come to why more), second child at least $(m - 2)$, third $(m - 3)$ ways and so on. If you consider a set of nodes with same parent, the nodes among themselves cannot be colored with same color because they have a distance of 2 within them but their children, will have distance 3 from the other sibling hence, will be independent. To understand, this point consider following connections:1 21 32 4Here 2 and 3 children of 1 cannot have same color but 3 can have same color as 4 which is 2's child. So how to consider this in multiplication principle? Simple when you call dfs on unvisited children keep track of how many new nodes you found, if you found $c$ new nodes, then if you call the dfs on the $(c + 1)^{th}$ new node, you send that information onto it as a function parameter in a variable $siblingExplored$, so that when you call the child of the node it can get the correct multiplication factor. Let's run our example on an example. n = 5, k = 4 edges: 1 21 33 44 51 can be colored in 4 ways.2 can be colored in remaining 3 ways.3 can be colored in 2 ways(different from 1 and 2)now when we explored 3 we said can be colored in 2 ways, that doesn't mean 4 will be colored in only 1 way, but since we explored 1 child node of parent node 1, we went onto 3, we noted that 2 affects one but we sent that information(of having explored 1 sibling before) onto 3, so the multiplication factor of 4 remained 2 because 2 no longer affects it. And for nodes with height greater than 2 we will not reduce the multiplication factor by 1. Why because even though the number of possible colors are decreasing by 1 but at the same time, the dependecy on parent 3 levels up is also vanishing. codevll g[MAX]; bool vis[MAX]; ll ans = 1; void dfs(ll cur, ll k, ll d, ll ck, ll nbv) { vis[cur] = true; if(d > 2) k++; // cout << cur << ' ' << k << endl; ans = (ans * k) % mod; if(k) { bool p = true; ll nv = 0; for(auto x : g[cur]) { if(!vis[x]) { dfs(x, k - 1 + nbv, d + 1, ck, nv); nv++; k--; } } } } Parameter ck is useless ignore it
 » 3 months ago, # |   0 Hi! Can someone please share their approach and solution to problems C and D — I got stuck at a step in both of them. Also would be great if editorials can be provided for all problems, would help in upsolving. Thanks!
•  » » 3 months ago, # ^ |   0 Here is one written by Geothermal : https://codeforces.com/blog/entry/68231
 » 3 months ago, # |   0 can anyone solve problem B without brute force or use any nice property. Thanks...
 » 3 months ago, # |   +1 Official editorials are available here
 » 7 weeks ago, # |   0 Problem F: I used lca to range min query (using sparse table) inorder to find the distance between any two vertices in O(1). I ran DFS from any arbitrary source node, and storing the number of colors I can use for every node (color[i] = total_unassigned_color + number_of_vertices_that_have_been_visited and whose distance is > 2)I am getting TLE for most of the cases, i understand the the reason. But I'm also getting Wrong answer for two test cases and Run Time Error for two test cases. Can any one explain me what is going on?here is Link of my submissionhttps://atcoder.jp/contests/abc133/submissions/7205633


text:
# RFC: A design for concurrent orders in a TBS.

This topic is 3936 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hey folks, just sharing some design and offering opportunity for questions, comments, suggestions, criticisms... Backround The game (codename and hereafter MOE) is a turn based strategy game akin to Master of Magic, Civilization, Imperialism and their kin. MOE has no set towns. Units exist in tiles, and can work in projects which are not necessarily tied to a town or factory. They may also move, fight, die, and what normal things you might expect. Units have Action Points (AP). AP is gained each turn, and the amount is variable based on the health of the unit, its food intake, its race, and perhaps other factors. Making an action (such as working on a project, moving along the map, or slaying enemies) takes AP. AP may drop below 0, but may not rise above a max AP which is variable amongst units. No orders may be given by units with AP <= 0. Units are the only game objects which can do commands. Problem The problem comes with the multiplayer requirements of the design. Turn based strategy games are a bit slow. Really slow when you have to wait for every other guy to issue their orders before you can actually play. It would be better if players could issue their orders concurrently, and they then all would be resolved at end of turn. The problem is how to do that. Solution Enqueue-ing commands is fairly straight forward. Player issues command, command goes in player's queue. Player hits ready/end-turn, player's queue goes to server. Taking the various players' queues and deciding what order to process the commands is a little less straightforward. Here is the design that I'm aiming for: Once all players are ready, and their queues of commands are received, turn processing begins. - Take all units and save their AP at the beginning of the turn into the command structure. - Run through the command queues, pulling the first order for every unit. - Take those commands and calculate a double: ( (2 * current AP - AP cost of command) / 2) / AP at beginning of turn - Place those commands into a Sorted container, descending on the float. - Process all commands where the double equals the double of the first command in the container. - For each unit's command processed, pull the next command for that unit from the queues, inserting it as needed into the sorted container. - Repeat until queues and container are empty. What this should do is normalize the commands to be a percentage of the turn time. An example:
Unit 1, some guard. AP 8 max AP 10       Unit 3, evil zombie, AP 3 max AP 3
Commands:

Move into tile (0,0) [cost:2]            Move into tile (0,0) [cost:2]
Fortify [cost:2]

So, processing, the first guard command is (8 + 8-2)/2/8 or 7/8. The first zombie command is (3 + 3-2)/2/3 or 2/3. 7/8 > 2/3 so the guard goes first and moves into the tile. Process guard command #2: (6 + 6-2)/2/8 [remember, 2 ap spent moving already] or 5/8. 2/3 > 5/8 so the zombie goes next and moves into the tile, causing combat before the guard is fortified. And that's the idea. The guard can do more, and if both start at the same time the more 'rested' unit should gain the initiative. But the zombie shouldn't have to wait until the guard makes moves until he's only got 3 AP left until starting his only action.

##### Share on other sites
Why not take a phased aproach where all actions take place at the same time during those phases?

Players issue all their orders and then each order takes place during a different phase.

You could decide phases one of two ways.

Each command has a set phase it occurs at, such attack phase, move phase, build phase. So build bridge always occurs during the building phase. Charge zombie always occurs during the attack phase. If units can only take one actions per phase then players have to plan their choice more carefully as they can only do one of each type of action a turn regardless of AP. But it aso provides a more consistant gameplay.

The other option is to give units order queue and have all orders at that point in the queue take place at the same time. So the first orders for all units occurs and is resolved, before moving on 2nd, 3rd, and so on. This method favors units with more AP and add more uncertinty into the game.

##### Share on other sites
Quote:
 Original post by TechnoGothWhy not take a phased aproach where all actions take place at the same time during those phases?

Because that does still has problems with multiple commands which are mutually exclusive. Two players say... trying to mine from the same ore spot. Ore can only be mined once per turn. Who gets it? Actions cannot take place at the same time. You can fake it, but the computer (or tabletop gamers) will still resolve one after the other.

Quote:
 Players issue all their orders and then each order takes place during a different phase.You could decide phases one of two ways.Each command has a set phase it occurs at, such attack phase, move phase, build phase. So build bridge always occurs during the building phase. Charge zombie always occurs during the attack phase. If units can only take one actions per phase then players have to plan their choice more carefully as they can only do one of each type of action a turn regardless of AP. But it aso provides a more consistant gameplay.

I would like not to make such action constraints. As it stands on paper, projects to work on are not so clear cut as to if they're building, research, spellcasting, exploration... I also think that might remove strategic options. (should I spend all my points working on this building, or should I scout around?)

I'm also curious what your thinking is behind the consistent gameplay comment. I don't quite see that, but then again I've a poor perspective; hence the post [grin]

Quote:
 The other option is to give units order queue and have all orders at that point in the queue take place at the same time. So the first orders for all units occurs and is resolved, before moving on 2nd, 3rd, and so on. This method favors units with more AP and add more uncertinty into the game.

Sounds similar, though it gives less favor to units with high AP whilst simplifying things.

Thanks!

##### Share on other sites
It's been so long I forgot how to quote, forgive me.

"Who gets it? Actions cannot take place at the same time."
This one is troubling. Here's why, it's a game logic/rule question rather than a programming one. You simply must come up with a rule for dealing with that scenario.

I'm using phases. The key to phases is that only actions which may conflict go into the same phase.

Consistency is achieved because you always know what actions can happen now and in the next phase because the phases always follow the same order. It simplifies planning.

Another option is to give commands different times for completion and allow units to spend AP to complete tasks more quickly.

If you really want to make sure every zombie gets a chance, combine TechnoGoth's idea and your idea, resolve all the 1st orders, then sort and resolve the 2nd and 3rd's 4th's etc. based on your system(7/8 > 2/3).


text:
# PPM Pure Metals

### Arsenic

Arsenic High purity Arsenic is needed to produce III/V-semiconductors like GaAs, which is used to make high frequency integrated circuits (power amplifiers in cell phones, [...]

### Germanium

Germanium Germanium is transparent for infrared radiation that is that has a wavelength of between 2 and 12 micrometers. It is therefore ideal to produce IR-optical devices [...]

### Antimony

Antimony High purity Antimony is used to produce III/V-semiconductors like Indium Antimonide (InSb) used for Hall sensors and infrared detectors and as a dopant for [...]


text:
# Swimming Relay – 2.0.0 – Update

• Added ROSTER tab, where you can store selected relay from the RELAY tab (by long click on relay in RELAY tab). Swimmers from selected relay will not be used for next calculation in the same discipline.
• Added SUMMARY tab, where you can find overview of all relays and swimmers selected to the ROSTER. Total entry fee will be calculated here after filling entry fee data in Preferences.
• Added option of creating mixed relay 1+3 or 3+1 – M+F (in Preferences).


text:
Analyticity of log f(z)

In a solution to a problem, I read that, if $f(z)$ is entire, $f(z)\neq0$ and the domain of definition of $f(z)$ is simply connected, then it is possible to choose a branch of log $f(z)$ that is analytic in the entire plane.

I was a bit surprised by this. My understanding is that, given at point $z_0\neq0$, you can always choose a branch so that log $z$ is analytic at that point. But once you have chosen a branch, that branch will not be analytic in the branch cut. To me this implies, that you can never choose $one$ branch of the logarithm, such that log $f(z)$ is analytic in the whole plane.

Grateful if you can sort this out for me. Where do I go wrong? Am I misinterpreting what is said in the solution?

• If $f$ is entire then its domain is $\mathbb{C},$ which is simply connected - no need to state that assumption. – zhw. May 20 '15 at 19:25
• What was the original problem and its source? – whacka May 20 '15 at 19:43

If $f$ is holomorphic on a simply connected domain $U$ and $0\not\in f(U)$ then there exists another function $g$ also holomorphic on $U$ such that $f(z)=\exp g(z)$. In fact, observe that
$$f(z)=e^{g(z)}\implies f'(z)=g'(z)e^{g(z)}=g'(z)f(z)\implies g'(z)=\frac{f'(z)}{f(z)}$$
which inspires $g(z):=\displaystyle \int_w^z\frac{f'(\xi)}{f(\xi)}d\xi$ (this is well-defined since $U$ is simply connected).
It is not however true that $\log f(z)$ can be defined for a continuous single-valued branch of $\log$, for instance consider $f(z)=e^z$ and $U=\Bbb C$ - then $f(U)=\Bbb C\setminus\{0\}$ is not simply connected.
• Thanks for your answer, but I don't quite understand the difference. The first part of your answer states that it's possible to define a function $f(z)=e^{g(z)}$ such that $g(z)$ is analytic in the whole complex plane. Isn't that the same as saying that $g(z) =$ Log $f(z)$ is in fact entire? But then below you state that log $f(z)$ can't be defined for a single-valued branch for log... I'm confused. Please help me understand the difference here! – Jarvi79 May 21 '15 at 8:34
• @Jarvi79 Did you read my $f(z)=e^z$ example at the end? Clearly there is a holomorphic $g$ for which $f(z)=e^{g(z)}$ (it's just $g(z)=z$). However there is no branch of the $\log$ function for which $\log e^z$ is holomorphic, and in particular $\log e^z$ is not the same as $z$ (I never said anything about $g(z)$ being $\log f(z)$ by the way). Indeed, whatever branch you pick, the imaginary part of $\log e^z$ will jump discontinuously as $e^z$ crosses that branch, right? – whacka May 22 '15 at 2:13


text:
TROPICAL GEOGRAPHY ›› 2018, Vol. 38 ›› Issue (6): 791-798.

### Spatio-temporal Patterns and Driving Factors of Urban Population Density Change of Prefecture-level Cities in China during 2006-2016

DU Chunmeng, JIAO Limin, XU Gang

1. (a. School of Resource and Environment Sciences; b. Key Laboratory of Geographic Information System, Ministry of Education, Wuhan University, Wuhan 430079, China)
• Online:2018-11-30 Published:2018-11-30

Abstract: When the rate of land expansion was faster than that of population growth, the overall population density would decrease in urban built-up areas. Studying the law of urban population density change in built-up areas is of great significance for the decision-making of national land safety and urbanization health development. Based on the data of the urban resident population and built-up areas in 285 cities in China during 2006-2016, this paper analyzes the temporal trends and spatial distribution of urban population density in Chinese cities, and explains the drivers of urban population density changes. The results show that: 1) The average population density within the built-up area in China decreased from 10 845 person/km2 in 2006 to 8 279 person/km2 in 2016, with an average annual decreasing rate of 2.66%. 2) The urban population density decreased in more than 5/6 cities, while there was a significant difference of the changing rate of population density among cities. Cities with rapidly decreased, moderately decreased, slowly decreased, and increased population density accounted for 13.3%, 30.5%, 41.1% and 15.1%, respectively. 3) Cities, experiencing rapidly decreased population density were mainly distributed in Eastern China. Cities with moderately decreased and slowly decreased population density were mainly distributed in the Central China. Cities with fast inflow of population experienced an increase of urban population density, such as Beijing, Shanghai, and Shenzhen. We also found that urban population density increased in some small cities with slow development of economy. 4) Economic development level, city scale, location factor and urban development policy are the main driving factors of population density change.


text:
Article

# Statistical Determination of Bulk Flow Motions

(Impact Factor: 5.81). 01/2010; 1(01). DOI: 10.1088/1475-7516/2010/01/025
Source: arXiv

ABSTRACT

We present here a new parameterization for the bulk motions of galaxies and clusters (in the linear regime) that can be measured statistically from the shape and amplitude of the two-dimensional two-point correlation function. We further propose the one-dimensional velocity dispersion (v_p) of the bulk flow as a complementary measure of redshift-space distortions, which is model-independent and not dependent on the normalisation method. As a demonstration, we have applied our new methodology to the C4 cluster catalogue constructed from Data Release Three (DR3) of the Sloan Digital Sky Survey. We find v_p=270^{+433}km/s (also consistent with v_p=0) for this cluster sample (at z=0.1), which is in agreement with that predicted for a WMAP5-normalised LCDM model (i.e., v_p(LCDM=203km/s). This measurement does not lend support to recent claims of excessive bulk motions (\simeq1000 km/s) which appear in conflict with LCDM, although our large statistical error cannot rule them out. From the measured coherent evolution of v_p, we develop a technique to re-construct the perturbed potential, as well as estimating the unbiased matter density fluctuations and scale--independent bias. Comment: 8 pages, 5 figures

0 Followers
·
• Source
##### Article: Decomposition of Spectra from Redshift Distortion Maps
[Hide abstract]
ABSTRACT: We develop an optimized technique to extract density--density and velocity--velocity spectra out of observed spectra in redshift space. The measured spectra of the distribution of halos from redshift distorted mock map are binned into 2--dimensional coordinates in Fourier space so as to be decomposed into both spectra using angular projection dependence. With the threshold limit introduced to minimize nonlinear suppression, the decomposed velocity--velocity spectra are reasonably well measured up to scale k=0.07 h/Mpc, and the measured variances using our method are consistent with errors predicted from a Fisher matrix analysis. The detectability is extendable to k\sim 0.1 h/Mpc with more conservative bounds at the cost of weakened constraint.
Monthly Notices of the Royal Astronomical Society 03/2010; 407(2). DOI:10.1111/j.1365-2966.2010.16955.x · 5.11 Impact Factor
• Source
##### Article: Enhanced Peculiar Velocities in Brane-Induced Gravity
[Hide abstract]
ABSTRACT: The mounting evidence for anomalously large peculiar velocities in our Universe presents a challenge for the LCDM paradigm. The recent estimates of the large scale bulk flow by Watkins et al. are inconsistent at the nearly 3 sigma level with LCDM predictions. Meanwhile, Lee and Komatsu have recently estimated that the occurrence of high-velocity merging systems such as the Bullet Cluster (1E0657-57) is unlikely at a 6.5-5.8 sigma level, with an estimated probability between 3.3x10^{-11} and 3.6x10^{-9} in LCDM cosmology. We show that these anomalies are alleviated in a broad class of infrared-modifed gravity theories, called brane-induced gravity, in which gravity becomes higher-dimensional at ultra large distances. These theories include additional scalar forces that enhance gravitational attraction and therefore speed up structure formation at late times and on sufficiently large scales. The peculiar velocities are enhanced by 24-34% compared to standard gravity, with the maximal enhancement nearly consistent at the 2 sigma level with bulk flow observations. The occurrence of the Bullet Cluster in these theories is 10^4 times more probable than in LCDM cosmology. Comment: 15 pages, 6 figures. v2: added references
Physical review D: Particles and fields 04/2010; 82(4). DOI:10.1103/PHYSREVD.82.044032 · 4.86 Impact Factor
• Source
##### Article: Measuring Coherent Motions in the Universe
[Hide abstract]
ABSTRACT: We present new measurements of the coherent motion of galaxies based on observations of the large-scale redshift-space distortions seen in the two-dimensional two-point correlation function of Luminous Red Galaxies in Data Release Seven of the Sloan Digital Sky Survey. We have developed a new methodology for estimating these coherent motions, which is less dependent on the details of galaxy bias and of the cosmological model to explain the late-time acceleration of the expansion of the Universe. We measure a one-dimensional velocity dispersion of galaxies on large-scales of \sigma_v=3.01^{+0.45}_{-0.46} Mpc/h and \sigma_v=3.69^{+0.47}_{-0.47} \mpcoh$at a mean redshift of z=0.25 and 0.38 respectively. These values are fully consistent with predictions for a WMAP7-normalised LCDM Universe and inconsistent at confidence of 3.8\sigma with a Dvali-Gabadadze-Porrati (DGP) model for the Universe. We can convert the units of these$\sigma_v$measurements to 270^{+40}_{-41} km/s and 320^{+41}_{-41} km/s respectively (assuming a$\Lambda\$CDM universe), which are lower that expected based on recent low redshift (z<0.2) measurements of the peculiar velocity field (or "bulk flows"). It is difficult to directly compare these measurements as they cover different redshift ranges and different areas of the sky. However, one possible cosmological explanation for this discrepancy is that our Galaxy is located in unusually over, or under, dense region of the Universe.
Journal of Cosmology and Astroparticle Physics 06/2010; 5(05). DOI:10.1088/1475-7516/2011/05/020 · 5.81 Impact Factor


text:
How to prevent uPVC expanding | Good to be Home

· It will actually sort itself out – as when the Sun sets, your windows and doors will retract, returning to normal. In extreme circumstances you can cool down your uPVC by patting it down with a cold, damp cloth or alternatively spraying the outside with water. This should help the uPVC shrink back to size and work freely once more.

Get Quote

How Does Your Penis Change as You Age?

The scarred portion can’t expand, causing a curved erection. The condition can often be corrected surgically or treated with medications . Testicles: The small organs inside your scrotum mostly ...

Get Quote

Yes, you can replace wood boards with composite, though there are a few factors to take into consideration. First, you will want to make sure your substructure is code-compliant and can hold the extra weight of a TimberTech composite board. Confirm that the thickness of the new TimberTech board is the same as the wooden board it replaces to ...

Get Quote

Thermal Properties of Plastic Materials

Thermal Properties of Plastic Materials Material Formula Coefficient of thermal expansion x10-6 K-1 Heat-deflection temperature - 0.45MPa C Heat-deflection temperature - 1.8MPa C Lower working temperature C Specific heat J K-1 kg-1 Thermal conductivity W m-1 K-1 Upper working temperature C Cellulose Acetate CA 80-180 52-105 48-86 -20 1200-1900 ...

Get Quote

does pvc expand in cold and hot conditions? = Answered ...

does pvc expand in cold and hot conditions. kay. January 2010. D.I.Y, Windows and Doors. yes it does.All building materials expand and contract, but not at the same rate. For example, upvc materials expand and contract at a different rate than wooden materials. Dazzer.

Get Quote

Will a hole cut into a metal disk expand or shrink when ...

In order to get the hole to shrink, you would need to use a material with a negative thermal expansion coefficient $\alpha < 0$, which means it gets smaller as the temperature gets higher. In that case the entire disc would shrink as it heats up. Wikipedia has an …

Get Quote

Manufactured Stone Siding Causing Big Problems For Homeowners

· Manufactured Stone Veneer will be stuck to the surface of the wall, hence the technical name of AMSV (Adhered Masonry Stone Veneer). You should be able to see the manufactured stone veneer pieces stop a few inches above the grade (soil or mulch). The reality though, is that it hardly ever does.

Get Quote

Dealing with Expansion and Shrinkage in Woodworking Projects

· Methods for Dealing With Expansion and Shrinkage . When building a carcass for a cabinet, each of the four sides of the box should have the grain-oriented in the same direction. As such, all four sides should grow relatively equally (mainly if all four come from the same piece of original stock).

Get Quote

Q & A: Marble thermal shock | Department of Physics ...

· Marbles expand when they get hot and shrink when they cool off. A marble cannot instantaneously change its temperature, however -- heat must flow into and out of the marble at a rate governed by the temperature differences and the thermal conductivity of the marble. A hot marble has expanded -- every bit of it expands by the same fraction.

Get Quote

The Effects of Temperature on PVC Pipe | Heritage Plastics ...

Table 1 can also be used to determine the effects of temperature changes on the length of PVC pipe and conduit. Pressure Capacity PVC pipe exhibits increasing pressure capacity with decreasing temperature, and decreasing pressure capacity with increasing temperature. The pressure ratings given for PVC pipe are for a 73°F operating temperature.

Get Quote

How to Shrink Rubber: 7 Steps (with Pictures)

· Place the rubber in boiling water if hot tap water fails to shrink the rubber. The high heat will force the rubber to shrink if you allow it to boil for 5 to 10 minutes. In some cases, boiling will return the rubber object to the desired size and shape just by removing any dirt and debris that has collected.

Get Quote

Temperature change and its effect on wood | Woodworking ...

· Also, cold furniture might get some temporary condensation, but that will go away and evaporate as soon as the wood warms and dries.) So, the bottom line is that temperature alone does …

Get Quote

Working with Trex & Composite Decking | HomeTips

· Extra spacing is also important between board ends and where boards meet a wall when decking runs perpendicular to the wall. Between end-to-end boards, allow a 3/16-inch space. Where board ends meet a wall, leave a healthy 1/2-inch gap to ensure the material can expand and contract without coming into contact with the wall.

Get Quote

PL Construction Adhesives. Our Pro Line of adhesives provides superior bonding for all of your building needs. Bonds that last as long as the material they are joining together. Read More.

Get Quote

How to Weatherize Windows with Plastic Film Insulation ...

· I used this plastic shrink with a hairdryer kit before. During the night the wind would blow in, the plastic would bow inward, and the popping off of the tape around the sides would keep me up. Theres just no tape strong enough that will keep the plastic anchored to the wall or trim.

Get Quote

A Complete Guide to Heat Shrink Tubing | RS Components ...

Heat shrink tubing is a versatile plastic layer which can be applied to cabling and components for several purposes by electricians, engineers and similar professionals, including: Electrical insulation - for example, to repair a damaged or exposed length of wire. Protection – …

Get Quote

Thermal Expansion and Contraction

Thermal expansion and contraction of concrete varies primarily with aggregate type (shale, limestone, siliceous gravel, granite), cementitious material content, water cement ratio, temperature range, concrete age, and ambient relative humidity. Of these …

Get Quote

Insulation Materials | Department of Energy

Insulation materials run the gamut from bulky fiber materials such as fiberglass, rock and slag wool, cellulose, and natural fibers to rigid foam boards to sleek foils. Bulky materials resist conductive and -- to a lesser degree -- convective heat flow in a building cavity. Rigid foam boards trap air or another gas to resist heat …

Get Quote

What You Need To Know About Trex vs Plastic Decking | Trex

Composite decking does not splinter or crack and does not become as slippery as solid plastic in winter months. Fading and Scratching Trex composite decking products are infused with stain-resistant, fade-resistant color throughout the entire board to minimize the look of any surface scratches, giving uniform color all the way through.

Get Quote

Does Concrete Expand?| Concrete Construction Magazine

· However, concrete does indeed expand when it gets hot or when the moisture content changes. That's why you need expansion joints in bridges, buildings, and other structures. In exterior concrete, joints widen during cold weather because of cooling contraction and get narrower during hot weather as the concrete expands.

Get Quote

Vinyl Plank Buckling

Sunlight & Heat. One of the major causes of buckling in vinyl plank flooring is expansion and contraction of the material. As the material becomes warmer, it can expand slightly, causing the floor to buckle. In the colder weather, the opposite is true and the floor can contract, leaving gaps between two of the tiles.

Get Quote

How much gap should I leave for expansion or contraction ...

For areas that are subject to significant temperature swings, we recommend installing your deck boards using surface fasteners. First, ensure that the deck boards are aligned properly. Then, install a fastener in the middle of each board length to prevent shifting during thermal expansion and contraction.

Get Quote

Thermal Expansion: Table of Coefficient of Thermal ...

I suspect that other materials such as siding expand and contract more than the frame - considerably more - which is why installation instructions call for appropriate gaps. On 2019-05-06 by Herman. If I had a traditional wood frame house, say 25' x 35' how many inches would it shrink and grow from …

Get Quote

Plastic Trim Performance Problems | Builder Magazine

· Plastic trim expands and contracts. You can’t prevent it, so you have to allow for it. ... Stone Trim/Lattice ... it will shrink when the weather gets cold, and expand …

Get Quote

Is it possible to shrink plastic, then bring it back to ...

At the molecular level the plastic is always in motion. This can be explained by what we in the industry refer to as the "expansion/contraction" variable. To make this as simple as possible lets use HDPE Sheet Goods as an example (imagine plastic boards 4' x 8'). This material can shrink/expand depending on the temperature the material is ...

Get Quote

Decking Boards: Everything You Need to Know | TimberTech

· Step 3: Learn the Types of Composite Decking & How to Choose. By this step, you know: Decking boards vary in cost, appearance, and durability – among other factors. TimberTech decking boards are just as attractive as wood – but far outperform traditional lumber. Decking boards from TimberTech are either capped polymer or capped composite.

Get Quote

15 Frequently Asked Questions About Contact Cement (Download .pdf version)1) What is a contact cement? Contact cement is an adhesive, which, when coated on two mating surfaces and allowed to dry, provides an instant permanent bond when brought into firm contact.

Get Quote

Plastic Lumber

Yes, plastic lumber does expand in heat and contract in cold temperatures, however, that expansion and shrinking are minimal, roughly a quarter of an inch every 8 feet in length in regions with seasons. This movement should be taken into account when planning a project, as would be done with any material that moves. The Importance Of ...

Get Quote

Expansion and Contraction : Why does heat and cold make ...

Expansion and Contraction : Why does heat and cold make things expand and contract ? Also why do some metals expand more than others? Asked by: Marcus Mckean Answer Recall that all materials are made up of atoms. At any temperature above absolute zero ( …

Get Quote

Shrink Film 101

Shrink bundling machines with a shrink tunnel can be expensive and cost thousands. Polyethylene shrink film also requires more prolonged heat exposure to shrink fully. Products sensitive to heat can melt or become damaged while the shrink film is obtaining a full shrink. Polyethylene shrink film has a low shrink rate of 15% or less.

Get Quote

Customer Reviews

• Alison Ruth

"I will buy it again, which is very in line with my requirements. I hope you can open a company in our local area, and I hope to be able to buy it at any time".


text:
# AIO2010 Solution

## Ninjas

You used to like ninjas. That was before the shadowy shiro-obi ninja clan moved in next door. They're mostly decent neighbours - they keep to themselves and never throw loud parties - but every few nights they sneak into your house and raid the kitchen. With no one else to turn to, you decide to take matters into your own hands and catch them in the act.

There are N ninjas trying to get inside, one at a time. You wait and watch carefully, grabbing the first one who comes past. However, in the time it takes you to securely tie up this first ninja, K other ninjas manage to sneak past you. Nevertheless, you persevere, grabbing the next ninja. Again, while you tie them up, K more ninjas sneak past. This continues until all of the ninjas have tried to get in.

In the above example, K=2. That is, for each ninja you tie up, the following two ninjas will sneak past. You catch the first ninja who comes past, and then ninjas #2 and #3 sneak past you. You catch ninja #4, and then ninjas #5 and #6 sneak past you. This repeats until all N ninjas have either been caught or have snuck past you.

Your task is to write a program that reads in the values of N and K, and calculates the number of ninjas who sneak past you.

## Choreography

You are the long-suffering director of finance for the Australasian Academy of Aesthetic Arts, Astounding Acts of Acrobatics and Algebra. Week in, week out, the Academy organises increasingly elaborate and expensive arts events while you struggle to scrape together enough money to make ends meet.

The big thing this month is Machinations Infernal, a modern dance routine involving D dancers and H hula hoops. Each dancer is assigned a unique number between 1 and D, and starts off holding some number of hula hoops (possibly none). The dance routine is performed as a sequence of T throws where each throw is of the form "dancer i throws a hula hoop to dancer j" (where i and j represent different dancers). Each throw is performed in the order specified, one after another. No hoops may be thrown unless it is part of the routine.

For a dancer to throw a hula hoop, they clearly must hold at least one hoop at that instant. You have been tasked with determining how many hula hoops are needed at the start of the dance such that every dancer has one to throw when required by the routine. As everyone knows, hula hoops are very expensive, so you must determine the minimum number of hula hoops required for the dance routine.

For example, consider the following dance routine consisting of five dancers and eight throws.

 1 → 3 2 → 3 2 → 1 5 → 2 3 → 5 1 → 4 3 → 4 4 → 5

One way to begin the routine is to give one hoop to dancer 1, two hoops to dancer 2, and one hoop to dancer 5. Dancers 3 and 4 begin with no hoops. The following table shows how many hoops each dancer has after each step of the dance.

 Dancer 1 2 3 4 5 Initial set-up 1 2 0 0 1 1 → 3 0 2 1 0 1 2 → 3 0 1 2 0 1 2 → 1 1 0 2 0 1 5 → 2 1 1 2 0 0 3 → 5 1 1 1 0 1 1 → 4 0 1 1 1 1 3 → 4 0 1 0 2 1 4 → 5 0 1 0 1 2

With these four hoops, every dancer always has a hoop to throw when required and this in fact uses the fewest number of hoops possible.

## Oil Spill

The enormous family-friendly multinational corporation PB (Pollution Busters) has been hitting headlines this year due to the 2010 Golf of Tigerius oil spill. After an oil rig explosion in April, the company has been in serious hot water.

Due to petroleum toxicity and oxygen depletion, the spill is an environmental catastrophe. It has damaged the local fishing industry, the tourism industry and the habitats of hundreds of wildlife species. PB however, is not particularly worried, as made clear in the CEO's statement that the oil spill is "relatively tiny" in comparison with the "very big ocean".

PB has refused to allow independent scientists to perform accurate measurements on the oil spill rate. The media has been prevented from viewing affected areas or flying over the spill, and threatened with arrest when attempting to investigate.

The international environmentalist organisation Green Peas has employed you to write a program to help them calculate the severity of the environmental impact.

Green Peas has given you a grid of R rows and C columns, representing the environment surrounding the oil rig. The spill originated at the rig, which will be marked on your map with a \$'. Land squares will be marked with a #' and sea squares will be marked with a .'. Each day after the initial explosion, every sea square adjacent (north, east, south or west) to either the oil rig or a previously oil-covered sea square becomes covered by oil. Land squares are never covered by oil.

Your program must simulate the spread of the oil spill for K days, then output a map of the surrounding environment with oil-covered sea squares represented by *'.

## Heatwave

Summer is fast approaching. There are people who love the sun, thrive in the warmth and enjoy lazing by the water. Then there are people who are irritated by the flies, the sand and of course the hot days. Different countries and cities tend to have different definitions of what is considered a "hot" day. For example, in Australia a hot day might be considered anything from 36 degrees up. However, in Iceland a day of 20 degrees or more is highly unusual and could send the locals into heat stress.

A "heatwave" is defined to be a series of one or more consecutive hot days. In hope of finding a nice warm city to retire, you wish to determine for a given city how many days the longest heatwave lasted. Your sources have obtained all the historical temperature data for the cities you are interested in, together with the lowest temperature that constitutes a heatwave for the city.

Your task is to write a program that can determine the longest observed heatwave.

For example, consider the following historical data for Perth. People in Perth call a day hot when the temperature hits 38 degrees or more. The hot days are underlined below:

31   39   42   33   30   33   40   38   39   41   37   34   27

Here, the longest heatwave lasted four days (the consecutive days where the temperature hit 40, 38, 39 and 41).

## Snap Dragons

Have you ever heard of Melodramia, little one? It is a faraway kingdom: a land of daring knights and reclusive wizards, of terrifying gryphons and majestic phoenixes, of ice queens and talking lions. It is a place where every day is a fantastic adventure.

Once upon a time in Melodramia, there lived two dragons named Rose and Scarlet. They were the best of friends, never stealing each other's gold or kidnapped princes, and whenever they had an argument they always settled it with a game of Dragon Snap. Dragon Snap was a game they had invented, and it worked like this:

• Rose would take R blank cards and write a secret number on each one. These numbers were in no particular order, and sometimes she would write the same number more than once.
• Scarlet would take S blank cards and do the same.
• At the same time, both dragons flipped over one of their cards at random. If these had the same number written on them, the cards were aSnap pair, and whichever dragon shouted "Snap!" first was the winner. Otherwise, they flipped the cards back over and tried again.

After many years of playing, the dragons noticed that having more possible Snap pairs would often lead to a faster game. For example, if Rose chose 6,4,2,4 as her cards and Scarlet chose 9,5,2 as her cards, then only 1 out of the 12 possible pairs would be a Snap pair (Rose's 2 paired with Scarlet's 2), and the game could go many rounds without finishing.

On the other hand, if Rose chose 8,9,9,9,9 as her cards and Scarlet chose 9,9,8,9,9,9 as her cards, then 21 out of the 30 possible pairs would be Snap pairs (1 pair of 8s and 20 pairs of 9s), and the game would end very quickly.

Curious, Rose and Scarlet called upon a powerful magician (i.e. you) to write a program that would read in the list of cards they had each chosen and calculate how many Snap pairs could be made.

## Hippopotamus Island

Somewhere in the middle of the Great Inspecific Ocean, there is a little-known island called Hippopotamus Island. This peculiar island is in the shape of a square with a side length of L kilometres. There are houses at one kilometre intervals all the way around the island, with the first house on the north-west corner, giving 4L houses on the island in total. Each house may contain some number of people (islanders) or it may be unoccupied. The centre of the island is inhabited by hippopotami who are easily frightened, and so the islanders only ever walk around the coast.

You wish to construct a desalination plant on the island to produce and sell fresh water. You will demolish one of the houses on the island and build the plant in its place. Your plan is to become the sole supplier of fresh water on the island so that every islander will need to travel to you in order to buy their water.

Your calculations say that for each kilometre that an islander must walk, they will buy one litre of water. For example, an islander who must walk four kilometres to get to the desalination plant will buy four litres of water. Note that the islanders can walk around the island either clockwise or counter-clockwise but they will always choose the shorter route to get to their water. If the desalination plant is built on a house containing islanders, you compensate their loss by offering them water for free.

Thinking deviously, you realise that you can sell more water by forcing islanders to walk further. The amount of water you sell is determined by the sum of the distances that each islander must walk to get to your plant.

Consider the above island of side length 3. There are 12 houses on the island, numbered in clockwise order starting from 1 in the north-west corner. Houses 2, 4, 11 and 12 contain 3, 1, 1 and 2 islanders, respectively. If for example, you were to place the desalination plant where house 4 is, you would sell nothing to the one islander you displaced, 3 x 2 = 6 litres to the islanders living in house 2, 2 x 4 = 8 litres to the islanders in house 12, and 1 x 5 = 5 litres to the islanders living in house 11, giving a total of 19 litres of water sold.

Alternately, if the plant was placed on house 8, you would sell 3  x  6 = 18 litres from house 2, 1  x  4 = 4 from house 4, 1  x  3 = 3 from house 11, and 2  x  4 = 8 from house 11, giving a total of 33 litres. This is the maximum amount of water that you can sell.

Your task is, given the size of the island and the locations of the islanders, write a program to determine the maximum amount of water you can sell by strategically locating your desalination plant on the island.


text: let's say this past year I started a restaurant and I now want to think about what type of a profit I've been making at that restaurant we really think about it in two different ways really think about it in terms of an accounting profit which is really the type of profit that most of us associate with a business or a firm and we also think about it in terms of economic profit which we'll we'll see is a little bit different and instead of telling us whether a business is producing income it tells us whether it makes sense to even run the business in the way that we are actually running it so first let's focus on the traditional way of calculating profit so let's say my firm my restaurant my firm is a restaurant in year one it brings in in revenue in revenue it brings in $500,000 so revenue literally is the amount of money the customers pay me to eat at the restaurant they're paying for their dinners this is literally though the food the money that's coming in the door sometimes people call the top line because literally the top line of our income statement I just wrote it is the top line now have to think about our expenses expenses expenses now when you're starting it when you're running a restaurant one of the obvious expenses is going to be the cost of food so food we're going to say cost us$100,000 $100,000 and you have the cost of labor I have the wait staff and have the chefs in the busboy and all those people in this past year I spent$100,000 then I have and I would assume that I don't own the building that I rent the building so building rent so I'm assuming this is on the building as a that was $200,000 and then finally I really disrupted everything I also rented the equipment all of the stowe's the fridges and all of that stuff so I'm none of this stuff that I own so the equipment rent equipment rent I spent another$50,000 so how much profit do I have your those are all my expenses I didn't borrow any money as I didn't have any interest expense or anything like that how much profit do I have before paying tax or sent you my pre-tax profit those terms because you're you're the amount you pay in taxes usually derived from your pre-tax profit and that depends on where where this business is what country what state what type of business it is and the easy way to calculate pre-tax profit pre-tax profit and this is pre-tax in with again terms of accounting profit right over years we take how much money comes to the door and then we have to subtract out all of the all of them payment we essentially have to make two other people and what we have left is our pre-tax profit and so 500,000 minuses see mine is 450 gives us a pre-tax profit in that same bright yellow of $50,000 and I'm assuming that I'm the only owner of this business and so I can essentially take it all out for myself and I may be helping my own personal rent or whatever else or I could take some of this or all of this and reinvested back into business maybe I start buying my equipment to expand in some way who knows what I might do that money and this is just traditional accounting profit this is how profit is cocky at all this is a super simple example the future I'd like to do more nuanced examples in the accounting world but this you'd offered to assist accounting profit accounting profit when people in the in the real in the in the everyday world about profit this isn't really what they're talking about now one economist talk about product they're talking about something slightly different than the best way to realize that is to just calculate economic profit for this exact same business or this firm as an economist would call it really is a general idea for an organization that is trying to maximize profit so once again it's year was actually just copy and paste it so it's year one that's our revenue so I'm gonna copy and I'm going to paste it this right over here so so far so good looks pretty similar but now we're going to think about things in a slightly different way economist you cost in terms of opportunity costs and it will see some of the opportunity cost you can measure in terms of dollars but some are less explicit so i'm gona right here so we can get in the economist frame of mind opportunity opportunity costs and within opportunity cost there what they're going to be explicitly opportunity costs and implicit opportunity cost so first let's do the explicit explicit opportunity cost well actually all of these are explicit opportunity cost let me just copy and paste that so I will copy copy and paste so all of these are explicitly opportunity costs and the reason why they are explicitly as I'm actually making up and paying money for all of these things even though equipment and the and the rented apartment I don't own it I'm actually paying and paying whoever does on a time these are these are direct outlays out of the business I'm explicitly making these payments and the reason why we can't think of them as opportunity cost even though they're given in dollar terms is that if I'm spending$100,000 on food that's $100,000 that I couldn't spend on something else from 700,000 labor that's$100,000 that I couldn't spend on something else I'm just measuring the opportunity cost in terms of dollars but dollars that I could have spent on other things but so far it looks pretty much identical I'm just doing it with a slightly different lens would you like what what's the big deal here we're going to see a little bit of divergence we're starting but the implicit costs that really weren't taken into account you the implicit opportunity costs especially implicit implicit costs so fine running this business and let's say that in order to to run it I actually had to focus on it full time I couldn't have I couldn't have actually quit my job than this there is an implicit cost of an important opportunity cost of the job that I gave up for my wages foregone you write this down wages wages for gone and let's say and this will depend on who were talking about let's say I was a doctor and I was making a nice steady risk-free $150,000 a year so I was giving up one hundred and fifty thousand dollars a year now we've got it we've listed all the experts and the implicit opportunity cost now we're ready to calculate our economic profit draw a line over here so our economic economic profit is going to be our revenue they were taking in minus all of these expenses that gives us two positive$50,000 but now have to sub subtract the wages far for gone so then I get to negative $100,000 now this is interesting that with this is kind of a big discrepancy here one in an accounting terms I'm profitable and economic terms I'm not profitable and the important thing to realize is economic profit with its negative isn't saying or you could say that this write-up hundred-thousand economic loss on economic profit of negative hundred-thousand this is it saying that the business of the firm isn't spinning out money what it is saying is it probably doesn't make sense to run this business or at least run this business in this way if this was new to this 10 that means he's probably making money but you kind of neutral whether you whether it makes sense to run it this way or not if it's positive that means it definitely does make sense to to run the firm in this way that it is definitely doing better than all of the all of the alternatives so this right over here saying look you're making$50,000 a year that's the $50,000 that you have to spend if you're the owner reinvest in the firm this is saying essentially look you could have been making more money than$150,000 is that making fifty thousand doing this you could have been making $100,000 more doing something else so you are essentially giving up your giving up$100,000 to do this restaurant so if you're a rational decision maker and you really are about maximizing your profit this actually might not make so much sense for you


text:
Ring of Sets is Commutative Ring

Theorem

A ring of sets $\left({\mathcal R, *, \cap}\right)$ is a commutative ring whose zero is $\varnothing$.

Proof

By definition, the operations $\cap$ and $*$ are closed in $\mathcal R$.

Hence we can apply the following results:

• The identity of $\left({\mathcal R, *}\right)$ is $\varnothing$, and this, by definition, is the zero.

So $\left({\mathcal R, *, \cap}\right)$ is a commutative ring whose zero is $\varnothing$.

$\blacksquare$


text:
# Left Align \text{} in \aligned{} environment latex

I have generated the following code:

\begin{aligned} c(s) &= [x_c(s),y_c(s)]^T \in \mathbb{R}^2, & \text{Centerline}, \\ i(s) &= [x_{in},y_{in}]^T \in \mathbb{R}^2, & \text{Inner Border}, \\ o(s) &= [x_{out},y_{out}]^T \in \mathbb{R}^2, & \text{Outer Border}, \\ \Delta(s) &= o(s)-i(s) \in \mathbb{R}^2, & \text{Lateral Deviation}, \\ t(s) &= i(s) + \alpha(s)\Delta(s), \quad \alpha \in [0,1] & \text{Trajectory}. \end{aligned} \label{FrameworkTrajectory}

which leads to: The problem is that I want to also align the words in all the \text{}'s based on their first letter (left alignment) instead of right, but I fail miserably when trying to do so.

All help is greatly appreciated!

• as always on this site you are more likely to get any help if you provide a full minimal example that others can copy and test as is. That said use &&\text instead. Apr 23 '21 at 10:56
• Explanation: when you have several alignments the number of & per line is 2n-1 where n is the number of alignments, so it is n alignment &'s and n-1 & to separate the alignments. Apr 23 '21 at 10:57
• Thank you very much daleif! Apr 23 '21 at 11:57

## 1 Answer

Just double the ampersand before \text. The environment align & Co. always alternate right-aligned/left-aligned columns, so after two & like in your code you are in a right-aligned column; you need a further & to go into the left-aligned one.

\documentclass{article}

\usepackage{amsmath,amssymb}

\begin{document}

\begin{aligned} c(s) &= [x_c(s),y_c(s)]^T \in \mathbb{R}^2, &&\text{Centerline}, \\ i(s) &= [x_{\mathrm{in}},y_{\mathrm{in}}]^T \in \mathbb{R}^2, &&\text{Inner Border}, \\ o(s) &= [x_{\mathrm{out}},y_{\mathrm{out}}]^T \in \mathbb{R}^2, &&\text{Outer Border}, \\ \Delta(s) &= o(s)-i(s) \in \mathbb{R}^2, &&\text{Lateral Deviation}, \\ t(s) &= i(s) + \alpha(s)\Delta(s), \quad \alpha \in [0,1] \quad &&\text{Trajectory}. \end{aligned} \label{FrameworkTrajectory}

\end{document}

I've taken the liberty of making a small modification: ‘in’ and ‘out’ are not symbols but (abbreviations of) real words so they are customarily written with an upright font in sub/superscripts.

• Thank you very much campa! Apr 23 '21 at 11:58
• @IHBPP, if answer solve your problem, you can consider to accept it (by clicking on the check mark at the top left side of the answer). Apr 23 '21 at 12:07
• @Zarko, I will! Thanks for the reminder :). Apr 24 '21 at 14:19


text:
# Chapter 2: Case study

## Version 4: Reuse data in registers

In V2 we achieved a factor-3.3 speedup in comparison with V1 by exploiting instruction-level parallelism, and in V3 we achieved a factor-6.3 speedup in comparison with V1 by exploiting vector instructions. However, if we try to combine both of the techniques, we will not see much improvement in the performance.

The bottleneck will be in the memory system. CPU is much faster in doing arithmetic operations than in getting data from the main memory to the CPU. As a simple example, consider an application that tries to do just lots of single-precision floating-point additions. If all operands are readily available in the CPU registers, each CPU core is able to do 2 vector additions per clock cycle, and each vector contains 8 elements; overall, the entire 4-core CPU could do 64 floating-point additions per clock cycle.

But what would happen if we tried to get all operands from the main memory, without any data reuse in CPU registers or caches? Each floating-point addition needs two operands, a total of 8 bytes. The maximum main memory bandwidth of the CPU that we use is 34.1 GB/s, or approximately 10 bytes per clock cycle. This is enough input data for only 1.25 floating-point additions per clock cycle.

Hence there is a factor-50 difference between how fast we can get operands from the main memory, and how fast the CPU could “consume” operands if they were in the CPU registers. For a maximum performance, we can only afford to fetch 2% of the operands from the main memory; everything else has to come from the cache memory or CPU registers!

Caches are not fast enough to keep the processor busy, either — not even the L1 cache, which is the fastest and smallest cache closest to the processor. Under ideal conditions, each CPU core could read two vectors from the L1 cache per clock cycle, and hence enough operands for, e.g., 1 vector addition per clock cycle per core. However, if all data came from the registers, we could do 2 vector additions per clock cycle per core.

To achieve a good performance, it is necessary to design programs so that we reuse data that we have fetched from the main memory to CPU registers as much as possible.

### Opportunities for data reuse

So far all of our implementations have been based on the same basic idea: We calculate each element of the result $r_{ij}$ separately. For example, to find the value of $r_{00}$, we scan row $0$ and column $0$ of the input matrix and calculate the minimum of all pairwise sums $d_{0k} + d_{k0}$. While we do this calculation, there is zero short-term data reuse. Elements $d_{0k}$ and $d_{k0}$ are used only once, and they take part in only one addition. We go through all the trouble of getting $d_{0k}$ and $d_{k0}$ to the CPU, and then immediately throw them away.

However, we could do much better if we reorganize the way we do calculations. We could calculate e.g. $r_{00}$, $r_{01}$, $r_{10}$, and $r_{11}$ in one go. All data that we need to calculate these results is contained in rows $0$ and $1$ and columns $0$ and $1$. We could proceed as follows:

• Read $d_{0k}$, $d_{1k}$, $d_{k0}$, and $d_{k1}$.
• Calculate $d_{0k} + d_{k0}$, $d_{0k} + d_{k1}$, $d_{1k} + d_{k0}$, and $d_{1k} + d_{k1}$.
• Update $r_{00}$, $r_{01}$, $r_{10}$, and $r_{11}$.

Let us now compare this with the naive solution:

• Original: we read 1 row and 1 column to calculate 1 result.
• Improved: we read 2 rows and 2 columns to calculate 4 results.

There is more data reuse by a factor of 2. Each element that we read takes part in 2 additions. The overall number of memory accesses is halved.

This approach gives also another benefit: we have got now independent operations that can be executed in parallel. For example, we can update $r_{00}$, $r_{01}$, $r_{10}$, and $r_{11}$ simultaneously in parallel.

There is also no need to stop here; we can push this idea further. Instead of calculating a 2 × 2 block of the output matrix by scanning 2 rows and 2 columns, we could calculate a 3 × 3 block of the output matrix by scanning 3 rows and 3 columns. We get now more data reuse by a factor of 3, and even more independent operations that give plenty of opportunities for instruction-level parallelism.

Let us implement this idea next.

### Implementation

We still use vector operations to do the calculations, exactly the same way as we did in version 3. Each row or column is packed in 8-element vectors, and there is some padding in the last vector if n is not a multiple of 8.

However, the new ingredient is that the innermost loop will not calculate just 1 result, but it will calculate a 3 × 3 block of the result array. We use 9 local variables (array vv) to hold the intermediate results. We use 3 + 3 local variables (x0, x1, x2, y0, y1, and y2) to keep the values that we have read from the memory, and then we will calculate all 3 × 3 pairwise products, reusing data as much as possible.

Again, this is straightforward if n happens to be a multiple of 3. To make our life easy, we will again add some padding. Now e.g. vd is an array whose width is a multiple of 8 (so each row consists of complete 8-element vectors), and its height is a multiple of 3 (so that we can easily process 3 consecutive rows at a time).

void step(float* r, const float* d_, int n) {
// elements per vector
constexpr int nb = 8;
// vectors per input row
int na = (n + nb - 1) / nb;

// block size
constexpr int nd = 3;
// how many blocks of rows
int nc = (n + nd - 1) / nd;
// number of rows after padding
int ncd = nc * nd;

// input data, padded, converted to vectors
float8_t* vd = float8_alloc(ncd*na);
// input data, transposed, padded, converted to vectors
float8_t* vt = float8_alloc(ncd*na);

#pragma omp parallel for
for (int j = 0; j < n; ++j) {
for (int ka = 0; ka < na; ++ka) {
for (int kb = 0; kb < nb; ++kb) {
int i = ka * nb + kb;
vd[na*j + ka][kb] = i < n ? d_[n*j + i] : infty;
vt[na*j + ka][kb] = i < n ? d_[n*i + j] : infty;
}
}
}
for (int j = n; j < ncd; ++j) {
for (int ka = 0; ka < na; ++ka) {
for (int kb = 0; kb < nb; ++kb) {
vd[na*j + ka][kb] = infty;
vt[na*j + ka][kb] = infty;
}
}
}

#pragma omp parallel for
for (int ic = 0; ic < nc; ++ic) {
for (int jc = 0; jc < nc; ++jc) {
float8_t vv[nd][nd];
for (int id = 0; id < nd; ++id) {
for (int jd = 0; jd < nd; ++jd) {
vv[id][jd] = f8infty;
}
}
for (int ka = 0; ka < na; ++ka) {
float8_t y0 = vt[na*(jc * nd + 0) + ka];
float8_t y1 = vt[na*(jc * nd + 1) + ka];
float8_t y2 = vt[na*(jc * nd + 2) + ka];
float8_t x0 = vd[na*(ic * nd + 0) + ka];
float8_t x1 = vd[na*(ic * nd + 1) + ka];
float8_t x2 = vd[na*(ic * nd + 2) + ka];
vv[0][0] = min8(vv[0][0], x0 + y0);
vv[0][1] = min8(vv[0][1], x0 + y1);
vv[0][2] = min8(vv[0][2], x0 + y2);
vv[1][0] = min8(vv[1][0], x1 + y0);
vv[1][1] = min8(vv[1][1], x1 + y1);
vv[1][2] = min8(vv[1][2], x1 + y2);
vv[2][0] = min8(vv[2][0], x2 + y0);
vv[2][1] = min8(vv[2][1], x2 + y1);
vv[2][2] = min8(vv[2][2], x2 + y2);
}
for (int id = 0; id < nd; ++id) {
for (int jd = 0; jd < nd; ++jd) {
int i = ic * nd + id;
int j = jc * nd + jd;
if (i < n && j < n) {
r[n*i + j] = hmin8(vv[id][jd]);
}
}
}
}
}

std::free(vt);
std::free(vd);
}

### Results

The code is getting a bit complicated, but it is clearly worth the trouble:

The overall running is now only 1.1 seconds for the multi-threaded version. Recall that our starting point was 99 seconds. By putting together the ideas of multithreading, vector instructions, instruction-level parallelism, and data reuse, we were able to improve the running time by a factor of 91.

We are now using 56% of the theoretical maximum performance of the CPU; we do 35.8 useful arithmetic operations per clock cycle, and the best that we could do with this CPU is 64 additions and/or minimums per clock cycle. If we wanted to improve the running time by more than a factor of two, we would have to invent an entirely new kind of an algorithm that solves the problem with less than $n^3$ additions and $n^3$ minimums.

We are very happy now, but of course 56% is still somewhat far from 100%. Could we somehow do better?


text:
1. ## Calculating Ratios Problem

I was having difficulty with the following standardized test question:
If the ratio of boys to girls in a class is 5 to 3 which of the following could not be the no. of students in the class
Answers: a)32 b)36 c)40 d)48 e)56

The answer is 36 but i cant figure out how that is the answer ?

2. ## Re: Calculating Ratios Problem

Originally Posted by MikeNoob
I was having difficulty with the following standardized test question:

Answers: a)32 b)36 c)40 d)48 e)56

The answer is 36 but i cant figure out how that is the answer ?
the number of students in the class would have to be a multiple of 8 ... now, why?

3. ## Re: Calculating Ratios Problem

So Boys+girls = 8 . Exactly. Thanks.

4. ## Re: Calculating Ratios Problem

Originally Posted by MikeNoob
So Boys+girls = 8 . Exactly. Thanks.
boys+girls = 8x


text:
# What is Pearson's r association strength?

I am trying to grasp the concept of magnitude-of-effect estimations, as opposed to standard null hypothesis testing procedures.

According to a paper by (Snyder & Lawson, 1993) the magnitude-of-effect indices can be grouped into effect size (such as Cohen's d) and measures of association strength. I wish to calculate the Pearson r strength of association, which would be part of the second group in this classification.

Now my question is, is the correlation coefficient obtained by taking the square root of the correlation coefficient $r^2$ provided by standard least-squares linear regression software output (such that generated by a basic Excel linear regression) the same $r$ as the Pearson's $r$ associated with magnitude-of-effect calculations?

I am confused, because the standard output of a normal regression analysis delivers the Pearson product-moment correlation coefficient, if I am not mistaken. However, I wish to calculate the Pearson's $r$ strength of association, as described in the linked paper.

One line summary: Pearson correlation $r$ is a measure of strength of (linear) association and indeed numerically and necessarily equal to the square root of $r^2$ as reported with regressions for one response and one predictor variable.

$r^2$ as reported for a regression of one $y$ and one $x$ is indeed the square of the Pearson correlation coefficient $r$. That is the reason for the notation.

However, the usual name for $r^2$ is the coefficient of determination. $r^2$ is definitely not the correlation coefficient. But coefficient of determination is a wordy name, and it cannot be claimed to be transparent either. I couldn't give you a really convincing story on why we should be talking about "determination" in this context. The idea is presumably that some fraction of the variation, precisely $r^2$ of it, is "determined" by the relationship and the rest, the remaining fraction 1 $- r^2$, is not so determined. But to my taste that terminology gets us too close for comfort to arguments about determinism, cause and effect, and so forth, although some researchers in some moods are keen to discuss all that.

So statistical people usually get into the habit of talking about "r-square" or "r-squared" (in my book, either is fine). In reports, it is better to write $r^2$ unless tribal habits or instructions from elders indicate otherwise.

Let's visit an example. Here are regression and correlation results (which happen to be from Stata, but any good statistics program will do something similar) for gallons per 100 miles predicted from car weight in pounds:

. regress gp100m weight

Source |       SS       df       MS              Number of obs =      74
-------------+------------------------------           F(  1,    72) =  194.71
Model |  87.2964969     1  87.2964969           Prob > F      =  0.0000
Residual |  32.2797639    72  .448330054           R-squared     =  0.7300
Total |  119.576261    73  1.63803097           Root MSE      =  .66957

------------------------------------------------------------------------------
gp100m |      Coef.   Std. Err.      t    P>|t|     [95% Conf. Interval]
-------------+----------------------------------------------------------------
weight |    .001407   .0001008    13.95   0.000      .001206    .0016081
_cons |   .7707669   .3142571     2.45   0.017     .1443069    1.397227
------------------------------------------------------------------------------

. corr gp100m weight
(obs=74)

|   gp100m   weight
-------------+------------------
gp100m |   1.0000
weight |   0.8544   1.0000

. display sqrt(0.7300)
.85440037

So, $r^2$ is reported as 0.7300 which is the square of the correlation coefficient 0.8544, as an independent calculator-like display does show.

Side notes:

1. A little confusingly, $R^2$ is also common notation in reporting regression results, while $R$ is only rarely used for a correlation between two variables. In fact the Stata output I just showed did precisely this. The history and logic to this appear to be that regression can use several predictors or $x$ variables (historically called multiple regression) and in that more general context $r^2$ is less common notation than $R^2$. There are very small issues here; watching what your teacher uses and being consistent about using one symbol or the other is the best first advice.

2. Exceptionally if $r=0$ or $r=1$ then numerically the values of $r$ and $r^2$ will be identical, but the concepts remain distinct.

3. 4 decimal places for $r^2$ or $r$ as above is overkill practically, and rounding a bit is usually a good idea. The programmer's implication and inclination is to give more decimal places than you need and to let you choose what rounding you want: indeed, good programs let you specify explicitly how much rounding you want.

4. You may often see $r^2$ (or $R^2$) reported in percent terms: in this example, any of 85%, 85.4%, 85.44% could be a researcher's choices. The idea here behind using percent presentation is that $r^2$ is a fraction. However, the correlation $r$ itself is not to be thought of a fraction of anything, not least because it can be negative too.

5. $R$ as the positive square root of $R^2$ from (multiple) regression is also quite often seen and has a simple, concrete and useful interpretation as the correlation between observed response $y$ and predicted response $\hat y$.

6. Despite widespread use of these conventions in notation, other uses of $r$ and $R$ are certainly possible within statistical science, so watching out for exact definitions remains imperative.

• Many many thanks. One question on r versus R - I understand they are different things entirely? I have to dig up the article I was reading, but it mentioned that r, R, eta squared and so on were different measures. Anyway, that's a side story I guess, my question is perfectly answered, thanks! – AliceD Jun 17 '15 at 10:55
• Thanks for the positive comments. Please see edits, points 5 and 6. – Nick Cox Jun 17 '15 at 11:15
• What a nice, thorough, and clear answer. And while in principle one could have answered this question with maybe a couple sentences, this is a nice example of how one can take a relatively straightforward (and also nicely/clearly formulated) question and make something even more educational and instructive out it by adding context, an example, noting potential other sources of confusion, clarifying notation, and so on. This couldn't be upvoted often enough. – Wolfgang Jun 17 '15 at 11:50


text:
## The Annals of Statistics

### Universally optimal crossover designs under subject dropout

Wei Zheng

#### Abstract

Subject dropout is very common in practical applications of crossover designs. However, there is very limited design literature taking this into account. Optimality results have not yet been well established due to the complexity of the problem. This paper establishes feasible, as well as necessary and sufficient conditions for a crossover design to be universally optimal in approximate design theory in the presence of subject dropout. These conditions are essentially linear equations with respect to proportions of all possible treatment sequences being applied to subjects and hence they can be easily solved. A general algorithm is proposed to derive exact designs which are shown to be efficient and robust.

#### Article information

Source
Ann. Statist., Volume 41, Number 1 (2013), 63-90.

Dates
First available in Project Euclid: 5 March 2013

https://projecteuclid.org/euclid.aos/1362493040

Digital Object Identifier
doi:10.1214/12-AOS1074

Mathematical Reviews number (MathSciNet)
MR3059410

Zentralblatt MATH identifier
1347.62168

Subjects
Primary: 62K05: Optimal designs
Secondary: 62J05: Linear regression

#### Citation

Zheng, Wei. Universally optimal crossover designs under subject dropout. Ann. Statist. 41 (2013), no. 1, 63--90. doi:10.1214/12-AOS1074. https://projecteuclid.org/euclid.aos/1362493040

#### References

• Bose, M. and Bagchi, S. (2008). Optimal crossover designs under premature stopping. Util. Math. 75 273–285.
• Bose, M. and Dey, A. (2009). Optimal Crossover Designs. World Scientific, Hackensack, NJ.
• Chêng, C. S. and Wu, C.-F. (1980). Balanced repeated measurements designs. Ann. Statist. 8 1272–1283.
• Godolphin, J. D. (2004). Simple pilot procedures for the avoidance of disconnected experimental designs. J. Roy. Statist. Soc. Ser. C 53 133–147.
• Hedayat, A. and Afsarinejad, K. (1978). Repeated measurements designs. II. Ann. Statist. 6 619–628.
• Hedayat, A. S. and Yang, M. (2003). Universal optimality of balanced uniform crossover designs. Ann. Statist. 31 978–983.
• Hedayat, A. S. and Yang, M. (2004). Universal optimality for selected crossover designs. J. Amer. Statist. Assoc. 99 461–466.
• Hedayat, A. S. and Zheng, W. (2010). Optimal and efficient crossover designs for test-control study when subject effects are random. J. Amer. Statist. Assoc. 105 1581–1592.
• Huynh, H. and Feldt, L. S. (1970). Conditions under which mean square ratios in repeated measurements designs have exact $F$-distributions. J. Amer. Statist. Assoc. 65 1582–1589.
• Jones, B. and Kenward, M. G. (2003). Design and Analysis of Cross-Over Trials, 2nd ed. Chapman & Hall, London.
• Kiefer, J. (1975). Construction and optimality of generalized Youden designs. In A Survey of Statistical Design and Linear Models (Proc. Internat. Sympos., Colorado State Univ., Ft. Collins, Colo., 1973) (J. N. Srivastava, ed.) 333–353. North-Holland, Amsterdam.
• Kunert, J. (1984). Optimality of balanced uniform repeated measurements designs. Ann. Statist. 12 1006–1017.
• Kunert, J. and Martin, R. J. (2000). On the determination of optimal designs for an interference model. Ann. Statist. 28 1728–1742.
• Kunert, J. and Stufken, J. (2002). Optimal crossover designs in a model with self and mixed carryover effects. J. Amer. Statist. Assoc. 97 898–906.
• Kushner, H. B. (1997a). Optimality and efficiency of two-treatment repeated measurements designs. Biometrika 84 455–468.
• Kushner, H. B. (1997b). Optimal repeated measurements designs: The linear optimality equations. Ann. Statist. 25 2328–2344.
• Kushner, H. B. (1998). Optimal and efficient repeated-measurements designs for uncorrelated observations. J. Amer. Statist. Assoc. 93 1176–1187.
• Low, J. L., Lewis, S. M. and Prescott, P. (1999). Assessing robustness of crossover designs to subjects dropping out. Statist. Comput. 9 219–227.
• Majumdar, D., Dean, A. M. and Lewis, S. M. (2008). Uniformly balanced repeated measurements designs in the presence of subject dropout. Statist. Sinica 18 235–253.
• Matthews, J. N. S. (1988). Recent developments in crossover designs. Internat. Statist. Rev. 56 117–127.
• Pukelsheim, F. (1993). Optimal Design of Experiments. Wiley, New York.
• Ratkowsky, D. A., Evans, M. A. and Alldredge, J. R. (1992). Cross-Over Experiments: Design, Analysis, and Application. Dekker, New York.
• Senn, S. (2003). Cross-over Trials in Clinical Research, 2nd ed. Wiley, Chichester.
• Stufken, J. (1991). Some families of optimal and efficient repeated measurements designs. J. Statist. Plann. Inference 27 75–83.
• Stufken, J. (1996). Optimal crossover designs. In Design and Analysis of Experiments (S. Ghosh and C. R. Rao, eds.). Handbook of Statist. 13 63–90. North-Holland, Amsterdam.
• Yeh, C.-M. (1986). Conditions for universal optimality of block designs. Biometrika 73 701–706.
• Zhao, S. and Majumdar, D. (2012). On uniformly balanced crossover designs efficient under subject dropout. J. Stat. Theory Pract. 6 178–189.