text:
# Building unusual IComparer<T> from expressions

I've needed a couple of very special comparers recenty and didn't want to implement each one of them every time so I created a builder and a couple of supporting classes that do that for me.

### Example

I'll start with an example. Given a collection of Products:

var products = new[]
{
new Product {Name = "Car", Price = 7 },
new Product {Name = "Table", Price = 3 },
new Product {Name = "Orange", Price = 1 },
};

private class Product
{
public int Id { get; set; }

public string Name { get; set; }

public int Price { get; set; }
}

I'd like to sort them either by the length of their name or price. Instead of implementig this type of unusual sorting with a new comparer I can use my new builder that allows me to create a comparer for that on the fly:

var comparer = ComparerFactory<Product>.Create(
x => new { x.Name.Length, x.Price },
(builder, x, y) =>
{
builder
.LessThen(() => x.Length < y.Length || x.Price < y.Price)
.Equal(() => x.Length == y.Length || x.Price == y.Price)
.GreaterThan(() => x.Length > y.Length || x.Price > y.Price);
});

var sorted = products.OrderByDescending(p => p, comparer).ToList();

### Implementation

On top of everything else I use the ComparerFactory<T> that implements the tedious null checks and comparisons. No magic here.

internal static class ComparerFactory<T>
{
private class Comparer : IComparer<T>
{
private readonly IDictionary<CompareOperator, Func<T, T, bool>> _comparers;

internal Comparer([NotNull] IDictionary<CompareOperator, Func<T, T, bool>> comparers)
{
_comparers = comparers;
}

public int Compare(T x, T y)
{
if (ReferenceEquals(x, y)) return 0;
if (ReferenceEquals(x, null)) return -1;
if (ReferenceEquals(y, null)) return 1;

if (_comparers[CompareOperator.LessThan](x, y)) return -1;
if (_comparers[CompareOperator.Equal](x, y)) return 0;
if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

// Makes the compiler very happy.
return 0;
}
}

public static IComparer<T> Create<TComparable>(Expression<Func<T, TComparable>> selectComparable, Action<ComparerBuilder<T, TComparable>, TComparable, TComparable> create)
{
var builder = new ComparerBuilder<T, TComparable>(selectComparable);
create(builder, default, default);
var funcs = builder.Build();
return new Comparer(funcs);
}
}

The interesing part begins with the ComparerBuilder<T, TComparable>. An instance of this class passed to the Create call just after the expression that selects the relevant value or properties as an anonymous object:

var comparer = ComparerFactory<Product>.Create(
x => new { x.Name.Length, x.Price },
(builder, x, y) => { ... });

The user also receives the two arguments that should be compared x and y. I'm doing this to not have to repeat myself when defining each comparison like I did before.

This was the first version but I didn't like it. Too much redundancy so I moved the two repeating variables to the top.

(
isLessThan: (x, y) => x.Ordinal < y.Ordinal,
areEqual: (x, y) => x.Ordinal == y.Ordinal,
isGreaterThan: (x, y) => x.Ordinal > y.Ordinal
);

The builder collects a couple of expressions. One for selecting the value or the properties that should be compared and one expression for each operation.

Finally the Build method turns each three operation expressions into three Func<T, T, bool>:

internal class ComparerBuilder<T, TComparable>
{
private readonly IDictionary<CompareOperator, Expression<Func<bool>>> _expressions = new Dictionary<CompareOperator, Expression<Func<bool>>>();

public ComparerBuilder(Expression<Func<T, TComparable>> getComparable)
{
_getComparable = getComparable;
}

public ComparerBuilder<T, TComparable> LessThen(Expression<Func<bool>> expression)
{
_expressions[CompareOperator.LessThan] = expression;
return this;
}

public ComparerBuilder<T, TComparable> Equal(Expression<Func<bool>> expression)
{
_expressions[CompareOperator.Equal] = expression;
return this;
}

public ComparerBuilder<T, TComparable> GreaterThan(Expression<Func<bool>> expression)
{
_expressions[CompareOperator.GreaterThan] = expression;
return this;
}

internal IDictionary<CompareOperator, Func<T, T, bool>> Build()
{
var left = Expression.Parameter(typeof(T), "left");
var right = Expression.Parameter(typeof(T), "right");

return _expressions.ToDictionary(x => x.Key, x => CompileComparer(x.Value, new[] { left, right }));
}

private Func<T, T, bool> CompileComparer(Expression compare, ParameterExpression[] parameters)
{
var rewritten = CompareRewriter.Rewrite(_getComparable, parameters, compare);
var lambda = Expression.Lambda<Func<T, T, bool>>(Expression.Invoke(rewritten), parameters);
return lambda.Compile();
}
}

But since the original operation expressions are incompatible with the Func<T, T, bool> signature:

() => x < y

I cannot call them from the comparer yet. I need something else that wold accept parameters:

(x, y) => x < y

In order to achieve this I created the CompareRewriter that is a ExpressionVisitor and replaces closures with calls to the selector for the comparable type or value. In case it's an anonymous type an additional conversion is necessary. Here a property access needs to be done to get the result of the type selector and not the closure which is useless later.

This means that on the left and right side of each <, > and == operator I inject the selector specified as the first argument:

x => new { x.Name.Length, x.Price }

Rewriting the expressions was the trickiest part but I managed to create the correct expressions and it behaves just as I expect it to.

internal class CompareRewriter : ExpressionVisitor
{
private int _param;

public CompareRewriter(Expression getComparable, ParameterExpression[] parameters)
{
_getComparable = getComparable;
_parameters = parameters;
}

public static Expression Rewrite(Expression getComparable, ParameterExpression[] parameters, Expression compare)
{
var visitor = new CompareRewriter(getComparable, parameters);
return visitor.Visit(compare);
}

protected override Expression VisitLambda<T>(Expression<T> node)
{
var binary = Visit((BinaryExpression)node.Body);
return Expression.Lambda<Func<bool>>(binary);
}

protected override Expression VisitBinary(BinaryExpression node)
{
if (node.NodeType == ExpressionType.Equal) return base.VisitBinary(node);

// Rewrite
// () => ClosureT1.x < ClosureT2.y
// to
// () => getComparable(T2).x < getComparable(T2).y

var getLeft = Expression.Invoke(_getComparable, _parameters[0]);
var getRight = Expression.Invoke(_getComparable, _parameters[1]);

_param = 0;
var left = Visit(node.Left);
_param++;
var right = Visit(node.Right);

// Determine whether a member-access is necessary or are we using pure values?
left = left == node.Left ? getLeft : left;
right = right == node.Right ? getRight : right;

switch (node.NodeType)
{
case ExpressionType.LessThan: return Expression.LessThan(left, right);
case ExpressionType.Equal: return Expression.Equal(left, right);
case ExpressionType.GreaterThan: return Expression.GreaterThan(left, right);
}
return base.VisitBinary(node);
}

protected override Expression VisitMember(MemberExpression node)
{
return
node.Member.MemberType == MemberTypes.Property
? Expression.MakeMemberAccess(Expression.Invoke(_getComparable, _parameters[_param]), node.Member)
: base.VisitMember(node);
}
}

internal enum CompareOperator
{
LessThan,
Equal,
GreaterThan
}

What do you think of this kind of a builder where you need to rewrite the expressions afterwards? What do you say about the expression-visitor?

The same code but as a single file can be found here and my two tests here.

• What will the array look like after it's sorted? – tinstaafl Nov 6 '18 at 1:42
• @tinstaafl it'll be [Orange, Car, Table] because Orange is the longest word, Car has then the highest price and Table is inbetween. – t3chb0t Nov 6 '18 at 6:57
• I know there aren't too many uses for such crazy comparers but I'm always keen to create something with expressions and it's been a lot of fun to debug them too ;-) – t3chb0t Nov 6 '18 at 7:08

        builder
.LessThen(() => x.Length < y.Length || x.Price < y.Price)
.Equal(() => x.Length == y.Length || x.Price == y.Price)
.GreaterThan(() => x.Length > y.Length || x.Price > y.Price);

gives me a very bad feeling, which turned out to be justified when I saw

        public int Compare(T x, T y)
{
...

if (_comparers[CompareOperator.LessThan](x, y)) return -1;
if (_comparers[CompareOperator.Equal](x, y)) return 0;
if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

// Makes the compiler very happy.
return 0;
}

Fundamentally, what you have here may implement the IComparer<T> interface but it is not a comparer, as shown by the following test:

    [TestMethod]
public void ComparerIsComparer()
{
var comparer = ComparerFactory<Product>.Create(
x => new { x.Name.Length, x.Price },
(builder, x, y) =>
{
builder
.LessThen(() => x.Length < y.Length || x.Price < y.Price)
.Equal(() => x.Length == y.Length || x.Price == y.Price)
.GreaterThan(() => x.Length > y.Length || x.Price > y.Price);
});

var products = new[]
{
new Product {Name = "Car", Price = 7 },
new Product {Name = "Table", Price = 3 },
new Product {Name = "Orange", Price = 1 },
};

foreach (var a in products)
{
foreach (var b in products)
{
var cmp1 = comparer.Compare(a, b);
var cmp2 = comparer.Compare(b, a);
Assert.IsTrue((cmp1 < 0 && cmp2 > 0) || (cmp1 == 0 && cmp2 == 0) || (cmp1 > 0 && cmp2 < 0));
}
}
}

From the mention of "special comparers" in the question and "crazy comparers" in a comment on the question I assume that this is the intended behaviour, but it's still a violation of the principle of least surprise and should be very clearly commented in the code.

Note that a further consequence is that the test CanCreateCanonicalComparer is unreliable. Microsoft could (they probably won't, but they could) change the implementation of OrderByDescending in such a way that it still respects its documented behaviour and continues working for code which uses reasonable comparers, but breaks your test. Perhaps more likely, a third party implementation of .Net might write OrderByDescending differently to Microsoft.

            // Makes the compiler very happy.
return 0;

The compiler would be equally happy if you threw an exception, and in my opinion that would be a more honest fix. If execution reaches this line, there's a programming error either in this code or in the code which uses it.

        internal Comparer([NotNull] IDictionary<CompareOperator, Func<T, T, bool>> comparers)
{
_comparers = comparers;
}

public int Compare(T x, T y)
{
...

if (_comparers[CompareOperator.LessThan](x, y)) return -1;
if (_comparers[CompareOperator.Equal](x, y)) return 0;
if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

...
}

I'm not entirely convinced that a dictionary is appropriate but, given the decision to use it, in my opinion the constructor should check that it contains all of the necessary keys.

Postscript: my suggestion for a ComparerBuilder API would be the following:

public class ComparerBuilder<T>
{
private ComparerBuilder() { }

public static ComparerBuilder<T> CompareBy<TProjection>(Func<T, TProjection> projection) =>
new ComparerBuilder<T>().ThenBy(projection);

public static ComparerBuilder<T> CompareByDesc<TProjection>(Func<T, TProjection> projection) =>
new ComparerBuilder<T>().ThenByDesc(projection);

public ComparerBuilder<T> ThenBy<TProjection>(Func<T, TProjection> projection);

public ComparerBuilder<T> ThenByDesc<TProjection>(Func<T, TProjection> projection);

public Comparer<T> Build();
}

with a test to show usage:

    [TestMethod]
public void TestComparerChain()
{
var data = new ValueTuple<string, int>[]
{
("A", 10),
("B", 5),
("C", 2),
("C", 10),
("B", 5),
("A", 2),
};
var cmp = ComparerBuilder<ValueTuple<string, int>>.
CompareByDesc(tuple => tuple.Item2).
ThenBy(tuple => tuple.Item1).
Build();

data = data.OrderBy(x => x, cmp).ToArray();
Assert.IsTrue(data.SequenceEqual(new ValueTuple<string, int>[]
{
("A", 2),
("C", 2),
("B", 5),
("B", 5),
("A", 10),
("C", 10),
}));
}

This gives plenty of scope to use expression parsing and code generation...

• About I'm not entirely convinced that a dictionary is appropriate - in fact, I started by having three Func<T, T, bool> fields but after adding the autogeneration of them I found it was too much work to pass them around and replaced it with a dictionary. You're right, I definitely need validation but didn't want to implement it yes as there might be other changes necessary that could break it. – t3chb0t Nov 6 '18 at 9:11
• I'm not sure which principle you mean that I break here. I find your comparer test very interesing and will have to add to my comparer-test extensions. Have I broke something that I'm not aware of? – t3chb0t Nov 6 '18 at 9:12
• A comparer should be (or perhaps induce) a total order. The most robust way of doing that is to define only one comparison (e.g. <); then a < b && b < a is an error and !(a < b) && !(b < a) means equality. – Peter Taylor Nov 6 '18 at 9:36
• You win, back to the drawing board ;-] btw, I like the new API you've suggested in the last edit. – t3chb0t Nov 8 '18 at 17:38

I really admire your efforts and I read the question as more about Expressions than comparison.

Anyway: as for the comparison, you should be aware that the result is different if the initial order of the Products is changed:

this:

  var products = new[]
{
new Product {Name = "Car", Price = 7 },
new Product {Name = "Table", Price = 3 },
new Product {Name = "Orange", Price = 1 },
};
var sorted = products.OrderByDescending(p => p, comparer).ToList();

gives:

Orange, Car, Table

where

  var products = new[]
{
new Product {Name = "Orange", Price = 1 },
new Product {Name = "Car", Price = 7 },
new Product {Name = "Table", Price = 3 },
};
var sorted = products.OrderByDescending(p => p, comparer).ToList();

gives

Table, Orange, Car

I would call that an undesired side effect

In the same way you'll get different results if you change the order of the operators:

if (_comparers[CompareOperator.LessThan](x, y)) return -1;
if (_comparers[CompareOperator.Equal](x, y)) return 0;
if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

will potentially give another result than:

    if (_comparers[CompareOperator.Equal](x, y)) return 0;
if (_comparers[CompareOperator.LessThan](x, y)) return -1;
if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

but which one is right?

If you extent the Product class to:

  public class Product
{
public int Id { get; set; }
public string Name { get; set; }
public int Price { get; set; }
public string Category { get; set; }

public override string ToString()
{
return $"{Name} -> {Id} -> {Price} -> {Category}"; } } var products = new[] { new Product {Name = "Car", Price = 7, Category = "Vehicle" }, new Product {Name = "Table", Price = 3, Category = "Furniture" }, new Product {Name = "Orange", Price = 1, Category = "Fruit" }, };  and define the comparer as:  var comparer = ComparerFactory<Product>.Create( x => new { x.Name.Length, x.Price, CategoryLitra = x.Category[0] }, (builder, x, y) => { builder .LessThen(() => x.Length < y.Length) .Equal(() => x.CategoryLitra == y.CategoryLitra) .GreaterThan(() => x.Price > y.Price); });  then the comparer should fall through to  ... // Makes the compiler very happy. return 0; }  for "Table" (x) and "Car" (y) because none of the operators return true - but it doesn't. It evaluates them as Equal The problems relates to this: protected override Expression VisitBinary(BinaryExpression node) { if (node.NodeType == ExpressionType.Equal) return base.VisitBinary(node); ...  But I'm not the one to explain why (or why you make this exception), but if you remove that if-statement it works. I can only agree with Peter Taylor in his comment and strongly recommend only to compare in one "dimension" - otherwise I only see trouble as shown above. If you insist on this design a more straight forward and naive solution could be:  public class StrangeComparer<T> : IComparer<T> { Func<T, T, bool> m_lessThan; Func<T, T, bool> m_equals; Func<T, T, bool> m_greaterThan; public StrangeComparer(Func<T, T, bool> lessThan, Func<T, T, bool> equals, Func<T, T, bool> greaterThan) { m_lessThan = lessThan; m_equals = equals; m_greaterThan = greaterThan; } public int Compare(T x, T y) { if (ReferenceEquals(x, y)) return 0; if (x == null) return -1; if (y == null) return 1; if (m_lessThan(x, y)) return -1; if (m_equals(x, y)) return 0; if (m_greaterThan(x, y)) return 1; throw new InvalidOperationException($"Compare of {x} and {y}");
}
}

but IMO you're better off with something like:

  public class StrangeComparer<T> : IComparer<T>
{
Func<T, T, int> m_comparer;

public StrangeComparer(Func<T, T, int> comparer)
{
m_comparer = comparer;
}

public int Compare(T x, T y)
{
if (ReferenceEquals(x, y)) return 0;
if (x == null) return -1;
if (y == null) return 1;

return m_comparer(x, y);
}
}

• Crappy-crap, I hadn't thought about the order of operations... I need to make this builder simpler and prevent the user from specifying operators or properties - I see there is too much that can go wrong. – t3chb0t Nov 6 '18 at 13:06
• You're also correct about the expressions... I wanted very much to build something usign them ;-P – t3chb0t Nov 6 '18 at 13:06

I'd say this is far too complicated. It took me some time to figure out what those expressions are getting rewritten to, and the results do not look very efficient:

(x => new { x.Name.Length, x.Price }).Invoke(left).Length < (x => new { x.Name.Length, x.Price }).Invoke(right).Length || ...

What are the benefits here compared to a simple Comparer<T> class that wraps a Func<T, T, int>? Not only would that require less boilerplate code, it also simplifies the calling code and should be several times faster:

var comparer = new Comparer<Product>((x, y) =>
{
if (x.Name.Length < y.Name.Length || x.Price < y.Price) return -1;
if (x.Name.Length == y.Name.Length || x.Price == y.Price) return 0;
return 1;
});
products.OrderByDescending(p => p, comparer).ToList();

Automatically taking care of the standard reference checks in the Comparer class is a good idea - I'd definitely keep that. However, what if Name is null? With the above approach, you can use Elvis operators, but they're apparently not (yet?) supported in expression trees.

• I actually started with a super simple version like this one here (ComparerFactory) but then I thought... come on, this can be made much cooler ;-) so I started experimenting and wanted to build something with expressions - three hours later I ended up with this ;-] – t3chb0t Nov 6 '18 at 13:00
• Expressions are fun, yes. ;) – Pieter Witvoet Nov 6 '18 at 13:05
• @t3chb0t, I think the link in your last comment is wrong. – Peter Taylor Nov 7 '18 at 11:09
• You're right! Sorry, this one is correct. – t3chb0t Nov 7 '18 at 11:12


text:
• # question_answer The mean of a set of 30 observations is 75. If each other observation is multiplied by a non-zero number $\lambda$ and then each of them is decreased by 25, their mean remains the same. The $\lambda$ is equal to                                            [JEE Online 15-04-2018] A) $\frac{10}{3}$                                  B) $\frac{4}{3}$C) $\frac{1}{2}$                        D) $\frac{2}{3}$

Since mean is a linear operation, after taking product with the same number and subtracting the same number, the mean becomes$75\lambda -25$. We thus have by the condition given in the problem$75\lambda -25=75\Rightarrow \lambda =\frac{4}{3}$.

format: plain


text:
3 Tutor System
Starting just at 265/hour

# A capsule of medicine is in the shape of a sphere of diameter 3.5 mm. How much medicine (in $${mm}^3$$) is needed to fill this capsule?

Given :
Radius (r) of capsule = $$\frac{3.5}{2} mm = 1.75 mm$$

We know that,

Volume of spherical capsule
= $$\frac{4}{3}{\pi}{r}^3$$
= $$\frac{4}{3} × \frac{22}{7} × {1.75}^3$$ $${mm}^3$$
= $$22.458$$ $${mm}^3$$
= $$22.46$$ $${mm}^3$$(appro×.)

Therefore ,the volume of the spherical capsule is $$22.46$$ $${mm}^3$$.


text:
# Python PuLP - Unable to Model Non-Square Matrix

I am having issues with setting up constraints using both input arrays from excel and variable arrays within PuLP.

It appears the model only works with square matrices and my final code has a matrix that is 365x24. The code below has a matrix of 5x6 and throws an error when running saying index out of range.

I have provided the code that I am working with so far.

Sheet11 Matrix

91  37  36  38  33  16
1   36  59  29  23  4
25  74  72  39  69  1
22  68  48  70  12  41
98  86  75  16  99  12

Sheet12 Matrix

59  63  66  57  4   15
26  33  75  71  21  2
37  88  89  1   90  3
91  48  27  24  23  14
68  13  61  37  77  20

from pulp import *
from pandas import *
import pandas as pd
import numpy as np
import xlrd

model = pulp.LpProblem("Basic Model", pulp.LpMinimize)

YPER = 5
HE = 6

yearlyhours = []
yearlyhours = [(i,j) for i in range(YPER) for j in range(HE)]

book = xlrd.open_workbook('Stack.xlsx')
sheet11 = book.sheet_by_name('Sheet11')
sheet12 = book.sheet_by_name('Sheet12')
sheet13 = book.sheet_by_name('Sheet13')

TEST = [[sheet11.cell_value(i,j) for i in range(YPER)] for j in range(HE)]
YAPR = [[sheet12.cell_value(i,j) for i in range(YPER)] for j in range(HE)]
MAPR = [[sheet13.cell_value(i,j) for i in range(YPER)] for j in range(HE)]

YAHL = pulp.LpVariable.dicts("YAHL", (range(YPER), range(HE)), lowBound=0, cat='Continuous')
MAHL = pulp.LpVariable.dicts("MAHL", (range(YPER), range(HE)), lowBound=0, cat='Continuous')

##OBJECTIVE##
model += pulp.lpSum([YAPR[i][j] * YAHL[i][j] + MAPR[i][j] * MAHL[i][j] for i in range(YPER) for j in range(HE)]), 'Sum_of_Value'

for i,j in yearlyhours:
model += pulp.lpSum([YAHL[i][j] + MAHL[i][j]]) == ([TEST[i][j]])

LpSolverDefault.msg = 1
model.writeLP('Opt.lp')
model.solve()
pulp.LpStatus[model.status]
print("Status:", LpStatus[model.status])
obj = value(model.objective)
print("Total Cost: \${}".format(obj,2))
print('\n')

When changing to a non-square matrix the following error message is given:

IndexError: list index out of range

Any help appreciated as I am still learning.

I think that the issue is the following:

YAPR = [[sheet12.cell_value(i,j) for i in range(YPER)] for j in range(HE)]

Here you create a list of list (YAPR) to represent your matrix. The outer list has a length of HE and the inner lists have a length of YPER.

model += pulp.lpSum([YAPR[i][j] * YAHL[i][j] + MAPR[i][j] * MAHL[i][j] for i in range(YPER) for j in range(HE)]), 'Sum_of_Value'

Here you address the list of list YAPR as if the outer list had a size of YPER and the inner list a size of HE. This is causing your out of bounds exception. You do not have the issue with square matrix because then YPER=HE which means that swapping the dimensions does not cause to go out of bounds.

You probably want to review your complete model because I saw those indices inversion on multiple lines.

• This makes complete sense...not sure how I didn't see that problem. The real difficulty lies in the fact that I am unsure how to properly set up the indices such that this issue does not arise. Would you or anyone else be able to give me one example of the correct way to re-write the Sum_of_Value line so that I can see the right way of doing it? Thanks! Jun 23 '19 at 3:12
• Well the easiest is probably to change your definition of YAPR into: YAPR = [[sheet12.cell_value(i,j) for j in range (HE)] for i in range(YPER)] Jun 23 '19 at 18:08
• Dude...Renaud...you are amazing. Was just able to implement this across my full model (not just the sample above) and it finally works the way I wanted it to. Appreciate the help! Jun 24 '19 at 14:29
• Happy to help :-) Jun 24 '19 at 14:29


text:
## § What is a syzygy? (WIP)

#### § The ring of invariants

Rotations of $\R^3$ We have a group $SO(3)$ which is acting on a vector space $\mathbb R^3$. This preserves the length, so it preserves the polynomial $x^2 + y^2 + z^2$. This polynomial $x^2 + y^2 + z^2$ is said to be the invariant polynomial of the group $SO(3)$ acting on the vector space $\mathbb R^3$. But how do we attach meaning to the symbols $x, y, z$? Well, we can formulate them as linear operators on the vector space : $x, y, z : \mathbb R^3 \rightarrow \mathbb R$ $x(a, b, c) \equiv a$, $y(a, b, c) \equiv b$, and $z(a, b, c) \equiv c$. Then the expression $x^2 + y^2 + z^2$ is a polynomial of linear operators of $V$. So the objects that are involved in the story are:
• The vector space $V$ of dimension $n$ over the field $k$
• The group $G$ that acts on the vector space $V$
• The space of linear operators $V^*$
• The ring of linear operators $R$.
We can write any polynomial of the linear operators as polynomials of the 'elementary' projection operators $p_1, \dots, p_n$ [where $n$ is the dimension of $V$]. So we have that $R \simeq k[p_1, \dots, p_n]$. Now this ring $R$ is said to be the ring of invariants of the action of the group $G$ onto the vector space $V$. We haven't seen what a syzygy is yet; We'll come to that.


text:
# How a Mexican state ended up with more drug war homicides than total homicides

December 5, 2012
By

(This article was first published on Diego Valle's Blog, and kindly contributed to R-bloggers)

During 2007 and 2008 the Mexican state of Sinaloa had more drug war-related homicides than total homicides. This should in theory be impossible since drug war homicides are a subset of total homicides. How did this happen?

Here is a chart from my old post highlighting the monthly difference between the vital statistics data and drug war-related homicides (Dec 2006- Dec 2009):
Just two weeks ago 8 bodies were found in Sinaloa, I can only image how difficult it must be to determine the exact dates the homicides occurred in some cases. So it's not a big deal if a month ends up having 5 or so extra drug war homicides than total homicides. But when drug homicides exceed total homicides for a year and a half as it did in Sinaloa, you know something is wrong.

Most homicides in Sinaloa are caused by firearms, and given the other errors in the mortality database it seems one should look if the discrepancy in the numbers lie in an excess of firearm deaths.

Here's a table of the yearly vital statistics data on homicides, firearm accidents and drug war-related homicides:

 Year All Homicides Drug-Related  Homicides Accidental  Firearm Deaths 2004 387 NA 61 2005 450 NA 47 2006 451 NA 26 2007 387 426 204 2008 869 1,084 198 2009 1,422 1,059 36 2010 2,277 1,815 67†
† Preliminary estimates undercounted by about 6%

I highlighted the years where drug homicides exceeded all homicides. As you can see the anomalous years also had an extremely high number of firearm accidents (I used the External Cause of Injury Mortality Matrix for ICD-10 to code accidents by firearm)
In fact, there's a very high correlation when looking at the unexplained drug homicides (the drug homicides left over when we substract the drug war-related homicides from the total homicides) and firearm accidents, but only during the anomalous years:
I don't think there can be any doubt that at least some of deaths by firearm accident correspond to those in the drug-war related homicide database during 2007 and 2008. Now the question is whether they are really homicides or accidents.

It seems natural that firearm accidents would rise along with homicides as the drug war ratcheted up, since an escalation of violence would involve hiring newer, less experienced gunmen. As you'd expect the newer gunmen were not the brightest bulbs in the box. But even for dumb cartel gunmen I'm surprised by the sudden increase in accidents and the sudden drop after 2008.

There's also the fact that the police and government authorities are under much more pressure to bring down the number of homicides than the number of accidents. For all these reasons I think it is much more likely that at least some homicides were misclassified as accidents, and that this explains part of the discrepancy during 2007 and 2008.

As funny as I find this, it probably didn't happen in Sinaloa in 2007 and 2008

What I'll do to find out whether the deaths were accidents or homicides is to first ignore the classification specified in the mortality database for all firearm accidents from January 2007 to December 2008. Then use machine learning to see if the characteristics of the original firearm accidents (sex, age, place of occurrence, etc) are sufficient to separate them into homicides and accidents.

Homicides in Sinaloa tend to occur on public streets:
However, accidentals deaths tend to occur all over the place except for 2007 and 2008 when there were a lot accidents on public streets (surprise, surprise):

Once we ignore the firearm accidents that occurred in 2007 and 2008 there are very few accidentals deaths by firearm in Sinaloa, and since the more data the better, I used all 1,834 firearms accidents in the rest of Mexico (excluding Chiapas because its vital statistics are a mess) together with all homicides and accidents by firearm in Sinaloa (excluding 2007 and 2008 obviously) to train a classifier.

There are still some unresolved problems with this approach since the state of Baja California went from having 6 deaths by firearm in 2006, to 100 in 2007, to 6 again in 2008, in comparison homicides went from 303 in 2006 down to 243 in 2007. This could imply that Sinaloa is not the only state with mortality misclassifications and underlines just how difficult it is to get training data (I ignored any possible errors in the rest of the country for classifying the data)

I ended up using the age, sex, place of occurrence of the injury, year of death, marital status and whether an autopsy was perfomed as the variables (including their interactions) in a penalized logistic regression to separate homicides from accidents. To avoid overfitting I separeted 30% of the data into a test dataset.

These are the results of crossvalidating on the test database:
           Reference
Prediction Accident Homicide
Accident      193       82
Homicide      166      933

Accuracy : 0.8195
95% CI : (0.7981, 0.8395)
No Information Rate : 0.7387
P-Value [Acc > NIR] : 8.951e-13

Kappa : 0.4942
Mcnemar's Test P-Value : 1.360e-07

Sensitivity : 0.5376
Specificity : 0.9192
Pos Pred Value : 0.7018
Neg Pred Value : 0.8490
Prevalence : 0.2613
Detection Rate : 0.1405
Detection Prevalence : 0.2001

'Positive' Class : Accident

Specificity measures the proportion of homicides which were correctly identified, which in this case is more important than misclassified accidents (sensitivity), since I'm trying to prove that the accidents are really homicides. With a specificity of 92% we can be pretty certain that a homicide classified as such is actually a homicide, but with a sensitivity of only 54% we might as well flip a coin when determining how certain we are that an accident is actually an accident. With such a low sensitivity we can consider the number of homicides in the table below as a sort of lower limit.

 Year Imputed Intent Number of Deaths 2007 Accident 61 2007 Homicide 143 2008 Accident 20 2008 Homicide 178

The result of classifying the 204 and 198 firearm accidents in 2007 and 2008.

As you can see the data looks much more reasonable now, though in 2008 there were still more drug homicides than total homicides, which may have been because some homicides were registered as accidents by a cause other than firearm (in around 23% of accidents the cause is left unspecified). When it comes to violence in Mexico it seems we watch shadows projected on a cave's wall.

Given that the sudden increase in homicides coincided with the end and start of a new year there may have been some sort of law or some legal means that made it ok to classify a homicide as an accident but that is just a matter of calling a tail a leg. But at this point I'm just speculating as to possible motives for recording a homicide as an accident, so I'll stop.
I can't confitm anything. There's something to what you ask, but I can't confirm anything. We have to perfom tests, you'll have the data later. What we know is that it was an accident, but a very strange one because the body was dumped at the public hospital where he died.
No te puedo confirmar nada. Algo hay de lo que preguntas, pero no te puedo confirmar nada. Faltan pruebas periciales por realizar, después tendrás los datos. Lo que sabemos es que es un accidente, pero muy raro porque el cuerpo fue arrojado en el Seguro Social y ahí murió
P.S. The data and code are available from my GitHub


text:
# Tag Info

## New answers tagged nodes-near-coords

1

Here I present an alternative, if you don't want to enlarge the ymax. For details, please have a look at the comments in the code. % used PGFPlots v1.17 \documentclass[border=5pt]{standalone} % we need PGFPlotsTable ... \usepackage{pgfplotstable} % ... to store the data in an inline table % (alternatively one could store it in a file) \...

2

\documentclass{article} \usepackage{pgfplots} \begin{document} \begin{tikzpicture} \begin{axis}[ title=sample count per class, xbar, xmin=0,xmax=3000000, width=8cm, height=6cm, enlarge y limits=0.15, symbolic y coords={{,},{.},{-},{:}, {?}}, ytick=data, nodes near coords, nodes near coords align={horizontal}, point meta=rawx, ...

4

A reasonable choice for 3D graphics would be Asymptote: // file diag.asy // // run // asy diag.asy // to get a standalone image diag.pdf // settings.tex="pdflatex"; import graph3; size(200,0); currentprojection=orthographic(camera=(67,9,14)); import fontsize; defaultpen(fontsize(7pt)); texpreamble("\usepackage{lmodern}\usepackage{...

6

I don't know exactly what kind of changes you will need, but perhaps this could be a starting point. My approach is basically to use calc library to compute the coordinates of the dots. \documentclass[border=2mm]{standalone} \usepackage {amsmath} % for pmatrix \usepackage {tikz} \usetikzlibrary{calc} % for coordinates \begin{document} \begin{...

Top 50 recent answers are included


text:
# Why would a suit of armour need power to provide protection to its wearer? [closed]

Why would electricity be needed to provide protection to the user of a suit of power armour? I'm not referring to the movement or any other systems in the armour. I mean, if the user gets shot, stabbed or otherwise physically attacked power is used & needed by the armour to protect from this attack. Why would this be the case? There is near future technology. It can't just be energy shields.

• VTC:Needs-Details. We need to convert this from an off-topic infinite list of things to an on-topic finite list of things. As written, there's no way to judge wither "because you need headlights" is better or worse than "you need electromagnetic shielding!" Please remember that fishing-for-ideas questions don't work well here. If you think about it, this is also a classic off-topic high concept question. Oct 13 at 16:37
• Specifically, I would appreciate some details about what kind of soldiers would be using the armour and under what circumstances. Oct 13 at 18:20

Your armour functions like ERA In Space

ERA usually stands for explosive reactive armour, a subtype of reactive armour. Currently seen on tanks, ERA comprises of explosive blocks that detonates outwards to counteract the impact of a weapon. In the case of ERA, the energy is already pre-stored in the explosives. However, your power armour could function as electric reactive armour instead, as described in the Wikipedia article linked. The external layers of your armour would be constantly electrically charged, and require a power supply as a result. Your suit of armour could also use a directed energy solution like lasers or a cutting torch directed outwards as a form of active protection system to intercept incoming attacks. Naturally, those would also require power to function.

Just as importantly, behind the aforementioned defensive systems, there are computers running software that govern their function and are necessary for their operation. Unsurprisingly those also require power.

• But of course. So lame to wait in space like a lame duck for the incoming to hit you and only then engage in a momentum transfer transaction. Why, now you can be reactive like a rocket! Oct 13 at 12:45
• So something like this: en.wikipedia.org/wiki/Trophy_(countermeasure) Oct 13 at 22:03

Electroshapable material

Electroshapable material is material that can be shaped when an electric current is flowing through, while rigit otherwise. The inverse of this also possible, but I can't find the correct word for it. It is experimental and not for use in body armour, but with near future technology it might be possible.

The idea is simple. You want your soldiers to have as little obstruction in manipulation. Soldiers need to manipulate the environment, like moving from one wall to another, aiming or pulling the trigger, to be effective soldiers. Enter the inverse electroshapable material. It's flexible when there's no current through it, giving maximum mobility to your soldiers. But on impact this can change. The impact of a bullet will start pushing the material. If the pressure is high enough a circuit will be completed, making the material rigit. All further energy of the bullet bill is canceled by the electricity.

Power armour might be more like bulky big suits of metal. Yet here it can still apply. It might look big and intimidating, but good inverse electroshapable material can seriously reduce weight and increase flexibility. Your armour is essentially electricity, though some wear and tear of the material is certainly to be expected.

• The word is piezoelectricity. It works both ways: bending the material produces electricity, while adding electricity makes the stuff rigid. Your answer is the same as mine :) Oct 13 at 12:09
• I just can't wait to try my GAU-8 pellet gun on them, I'll even load it with 30mm depleted uranium pellets. I'm sure the instant rigidity of the armor will play as nice as those trust inspiring rigid chassis of the cars before they invented the lame crumple zones. ;) Oct 13 at 12:38
• @AdrianColomitchi what's your point? Incredibly big weapons against people in power armour is effective? All armour can fail. In addition, the electricity can be ramped up with pressure, meaning you have a scale of rigidity as well as less or no effect if too little pressure is applied. Otherwise the armour would lock up with every movement. Oct 13 at 13:25
• @Trioxidane my point is that rigidity is a suboptimal choice, gradual deceleration is better. AK47 - muzzle velocity 700m/s, 7.62x51 - mass of 25.4g. Deceleration over 20mm by bullet deformation (rigid armor)=>311150N. Deceleration over 50mm=>124460N (say, hardening "ballistic gel" 50mm thick). In both cases, the body receiving it ain't going to stay put, it will be throw back by a "punch" of 6kJ. And AK47 is not what one would call a "big weapon". Oct 13 at 14:55
• @Nosajimiki because the question asks for electricity and in this future fantasy it works much better than non-Newtonian fluids. Thinner, lighter, stronger, easier to work into a suit of armour. Oct 14 at 2:38

The suit is made of hard stuff over softer padding, all mundane materials that do not need electricity because the same design has been in use since Ancient Greece. But it covers the body entirely, without any gaps or weak points. That means that it quickly gets hot inside. A vein system of coolant runs through the lower layer, just like modern space suits, but that system of course needs power to function.

You could wear it with an empty battery and be protected, but unless you are in Siberia, you would quickly suffer a heat stroke while doing so.

The armour is made of a revolutionary but not unthinkable substance that's soft like jelly for most of the time. It is barely a centimetre thick and fits over the wearer like a second skin, allowing for the same flexibility and range of movement as if the wearer had been in their birthday suit. It is covered in sensors that transmit sensations of touch, hot and cold to the skin underneath.

However, when an impact is registred by those sensors, an electric pulse is sent out and the jelly temporarily solidifies in a large region around the point of contact. This distributes the force over a large portion of the body, in a nigh-flawless manner. Once the impact has impacted, it liquifies again and regular movement can continue.

When the battery is empty, there's no current to harden the suit. Climate control would also fail without electricity. So without a full battery, the suit is generally useless.

• May I like the militarized version of P-5000 better, please? I mean, if I am to carry a battery, then let it be a BFB and power a lot more useful tools. Oct 13 at 12:15
• Why use piezoelectricity when you can get the same effect passively out of non-Newtonian fluids? Oct 13 at 21:57
• @Nosajimiki for reference youtube.com/watch?v=L5Ts9lYZIDk Oct 13 at 23:11

Air bags.

A problem with armoring a body against an impact is that the kinetic energy of the impactor is still transferred to the target. Frangible armor plates can absorb the impact but are then destroyed. Reactive armor meets the impactor with an outward explosion and is also then destroyed.

Car air bags deal with kinetic energy in a way similar to reactive armor - an explosion inflates a bag of gas which is compressed, absorbing the kinetic energy. Auto air bags are also one use defenses and must be replaced after use.

Your armor contains electric air bags. On impact by a hard surface (bullet, club) or shock wave (explosion), powered sensors deploy small air bags between the hard armor and the body beneath. These bags are inflated pneumatically and receive the energy of impact as compression, then deflate again. The compressed air charge held ready for inflation is renewed by electrical power but more importantly the detectors are electrical and without them the bags will not deploy.

The armor will still work as a barrier when unpowered. Without power, the person wearing the armor will still not get cut by an edge or penetrated by a bullet. But that person will get bruised, and will have little protection against shock waves.

• Better than what I've seen so far. But "air bag inflation" needs to be really explosive to deploy in the available time. That's gonna break some ribs anyway. Oct 13 at 15:01

The armor protects the wearer from damages by astonishingly quickly repairing the damages it has taken, so that, by all means, acts like a brand new armor at any moment. This thanks to the patented NoMoDa$$^{TM}$$ (No More Damage)

Of course, in order for this to happen, energy has to be supplied to the armor. Without energy it will quickly break and fail to fulfill its scope.

• I'd so much better like an armor that stops the bullet first than one that quickly repairs the hole left after the bullet passed through it. ;) Oct 13 at 12:08
• @AdrianColomitchi its fine. The armor has a hard time differentiating from itself and its wearer! it'll patch you up in no time flat (as long as its powered). Just don't think about the Ship of Theseus too hard. also, try not to scream as it will give away your position! Oct 13 at 12:20

## Polarized Armor Plating

In the near future, escalation in material science either made ballistic armor so good that militaries have to switch to energy weapons or energy weapons got so good that they rendered kinetic weapons obsolete.

To protect you from this new trend in high energy weapons, you need to magnetize your armor which would create a form fitting magnetic field around the user that will trap and redirect electrons, ions, and/or plasma around the user instead of hitting him.

Covering a solider in always-on magnets would pose all sorts of complications; so, instead the armor uses electromagnets to only polarize itself as needed.

While this may sound like just a variation of "energy shields" it is an actual technology that more or less exists today, we just don't have many practical applications for it since it is useless against kinetic weapons which is 99% of what we now face on the battlefield.

I don't know what exactly you consider 'near future technology,' but an armour could have its plates made out of a relatively flexible, ferrous material held in shape by electromagnets. Any dents or impacts are immediately counteracted by the magnetic force actively straightening the armour plate back out, requiring varying amounts of power. Alternatively, there's also an option of a material that gets deformed normally, but is able to form itself back into a predetermined shape and 'heal' when electric current is applied.


text:
# SEDMAX - Editorial

Author: Bhavyesh Desai
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

Easy-Medium

# PREREQUISITES:

Observation, Stack

# PROBLEM:

You are given an array A of length N. Your task is to find out the number of different possible costs that can be obtained across all possible choices for the subarray.

The cost is calculated as follows:

• A subarray B of size at least 2 will be chosen.
• The cost will be calculated as the difference between the maximum and the second maximum element in the subarray B.

# QUICK EXPLANATION:

• An element A_i can act as a second maximum element for at most two elements of an array, say A_L and A_R.

• A_L is the first greater (or equal) element on the left side of A_i, whereas A_R is the first greater (or equal) element on the right side of A_i in the array.

• Find A_L and A_R for every element of an array, which can be done in a single traversal of an array using a stack.

• Find out the difference for every pair of the maximum and second maximum elements.

• Finally, output the number of unique differences possible.

# EXPLANATION:

Here, \sum{N} overall cases is less than or equal to 5 \cdot 10^3

What really matters in the subarray is the maximum and the second maximum element. Suppose we have a subarray [A_L, A_{L+1},......, A_R] and the maximum element be max and the second maximum element is smax.

What happens when a new element A_{R+1} is added to this subarray?

Case 1: A_{R+1} is greater than than the maximum element max.

• Since A_{R+1} is the maximum element in the new subarray hence max becomes equal to A_{R+1}. And the previous max will become smax as now the previous max will be the second maximum element of the new subarray.

Case 2: A_{R+1} is smaller than the maximum element max but greater than the second maximum element smax.

• Now max is still the maximum element in the new subarray hence max will remain as it is. But smax will no longer remain the second maximum element as A_{R+1} > smax, hence smax becomes equal to A_{R+1}.

Case 2: A_{R+1} is smaller than both maximum element max and second maximum element smax.

• In this case, the max and smax will remain as it is as they are still the maximum and the second maximum element of the new subarray respectively.

As every element of an array can be the starting point of the subarray except the last element of the subarray since the minimum length needs to be 2.

Hence taking every element as the starting point of the subarray and keep on adding the elements on this subarray till we reach the rightmost element of the array. Every time we add the element to the subarray, find the maximum and the second maximum element for this new subarray as explained in the cases above. Every time we calculate the difference between the maximum and the second maximum element. Finally, we output the number of unique differences possible.

Time Complexity

O(N^2) per test case

Solution
// Subtask 1

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mxN=1e5+5;
int a[mxN];
int n;

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
{
cin>>n;

for(int i=1;i<=n;i++)
{
cin>>a[i];
}

set <int> ans;

for(int i=1;i<n;i++)
{
int ma1=max(a[i],a[i+1]);
int ma2=min(a[i],a[i+1]);

ans.insert(ma1-ma2);

for(int j=i+2;j<=n;j++)
{
if(a[j]>ma1)
{
ma2=ma1;
ma1=a[j];
}
else if(a[j]>ma2)
{
ma2=a[j];
}

ans.insert(ma1-ma2);
}
}

cout<<ans.size()<<"\n";
}

return 0;
}

Since the value of N is large enough, we need to optimize our solution. As the only thing that matters in the problem is to find the pairs (x,y) such that x is the maximum element of the subarray and y is the second maximum element of the subarray. If we can find all the possible pairs then we can easily find the number of unique differences possible.

Claim: There can exist at most 2 pairs where an element A_i acts as a second maximum element. Those possible pairs are (A_L, A_i) and (A_R, A_i) where A_L is the first greater (or equal) element on the left side of A_i, whereas A_R is the first greater (or equal) element on the right side of A_i in the array.

Proof

Consider an array A of N numbers such that:

A_1,....A_L,A_{L+1},....,A_i,...,A_{R-1},A_R,....A_N

Now, Suppose for A_i, the next greater (or equal) element on the left side is A_L, and the next greater (or equal) element on the right side is A_R.

Initially, we have a subarray [A_i, A_{i+1}.., A_R] such that the maximum element is A_R and the second maximum element is A_i since max(A_i, A_{i+1}.., A_R)=A_R and max(A_i, A_{i+1}.., A_{R-1})=A_i.

Now let us try adding elements on this subarray as we were doing in subtask 1.

Case 1: When A_{R+1}>A_R

• In this case, A_i will no longer remain the second maximum element as the A_{R+1} will be the maximum element of the new subarray and A_R will be the second maximum element.

Case 1: When A_{R+1}<A_R and A_{R+1}>A_i

• In this case, A_i will no longer remain the second maximum element as the A_{R+1} will be the second maximum element of this new subarray since A_{R+1}>A_i.

Case 3: When A_{R+1}<A_R and A_{R+1}<A_i

• In this case, there will be no changes i.e A_i will be the second maximum element and A_R will be the maximum element.

We can clearly see for all the cases when A_i is the second maximum element then only and only A_R is the maximum element and that happens in Case 3. For other cases, A_i no longer remains the second maximum element.

• Similarly, we can prove for the left side i.e when we have a subarray [A_L, A_{L+1}.., A_i] such that the maximum element is A_L and the second maximum element is A_i. Now when we keep adding elements on the left side of this subarray similar cases appear.

• For all the subarray that has staring index greater than L and ending index less than R, and containing A_i as the element of the subarray. In those cases, A_i will be the maximum element as max(A_{L+1},..., A_i.., A_{R-1})=A_i

• For such subarray that contains both A_L and A_R, then as A_i is smaller than both A_L and A_R. Hence A_i won’t be acting as the second maximum element.

Hence there can exist at most 2 pairs where an element A_i acts as a second maximum element. Those possible pairs are (A_L, A_i) and (A_R, A_i) where A_L is the first greater (or equal) element on the left side of A_i, whereas A_R is the first greater (or equal) element on the right side of A_i in the array.

So, We are left with finding A_L and A_R for every element of an array, which can be done in a single traversal of an array using a stack as explained here

Finally, find out the difference for every pair of the maximum and second maximum elements and output the number of unique differences possible.

Time Complexity

O(N) per test case

# TIME COMPLEXITY:

O(N) per test case.

# SOLUTIONS:

Setter
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(x) ((int)x.size())
#define endl "\n"
#define inf (1LL<<62)
#define ninf (-inf)

template<typename Tleaf>
void print(Tleaf &&leaf, int n)
{
for(int i = 1; i <= n; i++)
cout << leaf[i] << " \n"[i==n];
}

template<typename Tleaf>
void print(Tleaf &&leaf, int n, int m)
{
for(int i = 1; i <= n; i++)
print(leaf[i], m);
}

const int nax = 100005;
int a[nax];

int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
set<int> s;
stack<int> p;
for(int i = 1; i <= n; i++)
{
while(sz(p) && p.top() <= a[i])
{
s.insert(a[i]-p.top());
p.pop();
}
p.push(a[i]);
}
while(!p.empty())
p.pop();
reverse(a+1, a+n+1);
for(int i = 1; i <= n; i++)
{
while(sz(p) && p.top() <= a[i])
{
s.insert(a[i]-p.top());
p.pop();
}
p.push(a[i]);
}
cout << sz(s) << "\n";
}
}

Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}

long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int sum_n=0;
pii a[100005];
int le[100005],ri[100005];
int leg[100005],rig[100005];
void solve() {
sum_n+=n;
assert(sum_n<=1000'000);
fr(i,1,n) {
if(i!=n)
else
a[i].se=i;
}
set<pii> qu,qu1;
fr(i,1,n) {
while(qu1.size()&&(*qu1.begin())<a[i]) {
rig[(*qu1.begin()).se]=i;
qu1.erase(qu1.begin());
}
while(qu.size()&&(*qu.begin())<a[i]) {
ri[(*qu.begin()).se]=i;
qu1.insert(*qu.begin());
qu.erase(qu.begin());
}
qu.insert(a[i]);
}
while(qu.size()) {
ri[(*qu.begin()).se]=n+1;
qu1.insert(*qu.begin());
qu.erase(qu.begin());
}
while(qu1.size()) {
rig[(*qu1.begin()).se]=n+1;
qu1.erase(qu1.begin());
}
for(int i=n; i>0; i--) {
while(qu1.size()&&(*qu1.begin())<a[i]) {
leg[(*qu1.begin()).se]=i;
qu1.erase(qu1.begin());
}
while(qu.size()&&(*qu.begin())<a[i]) {
le[(*qu.begin()).se]=i;
qu1.insert(*qu.begin());
qu.erase(qu.begin());
}
qu.insert(a[i]);
}
while(qu.size()) {
le[(*qu.begin()).se]=0;
qu1.insert(*qu.begin());
qu.erase(qu.begin());
}
while(qu1.size()) {
leg[(*qu1.begin()).se]=0;
qu1.erase(qu1.begin());
}
int ans=0;
set<int> anser;
fr(i,1,n) {
if(le[i]!=0)
anser.insert(a[le[i]].fi-a[i].fi);
if(ri[i]!=n+1)
anser.insert(a[ri[i]].fi-a[i].fi);
//		trace(le[i],leg[i],ri[i],rig[i]);
//		ans+=(ri[i]-le[i]-1)*a[i].fi;
//		trace(ans);
//		ans-=((rig[i]-ri[i])*(i-le[i])*a[i].fi);
//		ans-=((le[i]-leg[i])*(ri[i]-i)*a[i].fi);
//		ans-=a[i].fi;
//		trace(ans);
}
cout<<sz(anser)<<endl;
//	cout<<ans<<endl;
}

signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
//	int t;
//	cin>>t;
fr(i,1,t)
solve();
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int mxN=1e5+5;
int a[mxN];
int n;
int lft[mxN];
int rght[mxN];

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
{
cin>>n;

for(int i=1;i<=n;i++)
{
cin>>a[i];
}

set <int> ans;

stack <int> s;

for(int i=1;i<=n;i++)
{
while(s.size()>0 && s.top()<a[i])
s.pop();

if(s.size()>0)
lft[i]=s.top();
else
lft[i]=-1;

s.push(a[i]);
}

while(s.size()>0)
s.pop();

for(int i=n;i>=1;i--)
{
while(s.size()>0 && s.top()<a[i])
s.pop();

if(s.size()>0)
rght[i]=s.top();
else
rght[i]=-1;

s.push(a[i]);
}

for(int i=1;i<=n;i++)
{
if(lft[i]!=-1)
ans.insert(lft[i]-a[i]);
if(rght[i]!=-1)
ans.insert(rght[i]-a[i]);
}

cout<<ans.size()<<"\n";
}

return 0;
}

# VIDEO EDITORIAL:

8 Likes

Great solution by setter in O(N), an O(N log N) solution to the (almost) exact problem is unfortunately also available on GFG https://www.geeksforgeeks.org/find-all-unique-pairs-of-maximum-and-second-maximum-elements-over-all-sub-arrays-in-onlogn/

8 Likes

Now I understand how these many AC solutions for the problem in Div2.

11 Likes

ohhh this was the solution , i was thinking it seems a little bit standard

lol

2 Likes

Well if you look closely both the solution are almost same , the authors one and the GFG one , there also the Complexity is O(NlogN) only because of using set , using unordered set can get it down to O(N)

1 Like

I solved it using a constructive algo in O(NLOGN). Sort in descending the values along with their indexes and iterate this array to find the left and right greater elements incrementally. Here is my solution - Solution: 43170109 | CodeChef
I was astonished to see everyone using stack all other solutions!

6 Likes
#include <iostream>
#include <vector>
#include<stack>
#include<set>
#include<cmath>
using namespace std;
int main()
{int t;
cin>>t;
while(t--){
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{cin>>a[i];}
stack<int>s;set<int>u;
for(int i=0;i<n;i++){
if(s.size()==0){
s.push(a[i]);
}
else if(s.size()==1){
u.insert(abs(s.top()-a[i]));
s.push(a[i]);
}
else if(s.top()>=a[i])
{
u.insert(abs(s.top()-a[i]));
s.push(a[i]);
}
else{
while( s.size()>0 && s.top()<a[i]){
u.insert(abs(s.top()-a[i]));
s.pop();
}
if(s.size()>0)
u.insert(abs(s.top()-a[i]));
s.push(a[i]);
}}
cout<<(int)u.size()<<endl;}}

Can someone please help me figure out the flaw in this implementation? If possible, please provide a test case that would fail on this.

Will you please explain how you reached upto this conclusion …

1 Like

next level

I did exactly same.

@aniket_0206 The concept is basically the same (fixing the second max). You can sort descending order the values and iteratively fix the second max element. Meanwhile, you have an indices array of elements greater than the current element (because you are iterating descending thats possible, initially that array is empty). You can do a binary search and find the indices greater and smaller than the element in iteration and that would produce new diffs needed. Update the current element’s index in the indices array (in sorted order) and proceed for the next iteration.

explain with eg?

Tester is writing the shittiest code possible.

3 Likes

This is not a easy-medium level problem. It is at least medium level problem as we first have to observe that every element can be second maximum at most 2 times and then know the trick to find the two maximum elements of each element in O(N) time.

1 Like
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;

using namespace std;

const ll N = 1e9+7;

ll nextgreater[100000+5];
ll previousgreater[100000+5];

void solve()
{
memset(nextgreater,-1,sizeof(nextgreater));
memset(previousgreater,-1,sizeof(previousgreater));
ll n;
cin>>n;

vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}

stack<ll> selement;
stack<ll> sindex;
for(int i=0;i<n;i++){
if(selement.empty()){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] > selement.top()){
while(!selement.empty() && v[i] >= selement.top()){
ll index = sindex.top();
nextgreater[index] = v[i];
selement.pop();
sindex.pop();
}
selement.push(v[i]);
sindex.push(i);
}
else{
selement.push(v[i]);
sindex.push(i);
}

}
}
while(!selement.empty()){
selement.pop();
}
while(!sindex.empty()){
sindex.pop();
}

for(int i=n-1;i>=0;i--){
if(selement.empty()){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] > selement.top()){
while(!selement.empty() && v[i] >= selement.top()){
ll index = sindex.top();
previousgreater[index] = v[i];
selement.pop();
sindex.pop();
}
selement.push(v[i]);
sindex.push(i);
}
else{
selement.push(v[i]);
sindex.push(i);
}

}
}

set<ll> ansset;
for(int i=0;i<n;i++){
if(nextgreater[i] != -1){
ansset.insert(nextgreater[i] - v[i]);
}
if(previousgreater[i] != -1){
ansset.insert(previousgreater[i] - v[i]);
}
}

cout<<ansset.size();
}

int main()
{
fast;
ll t;
// t = 1;
cin>>t;

while(t--)
{
solve();
cout<<endl;
}

}

Can someone tell what is wrong in my solution plz

Consider

tc

2
1 1

1 Like
#include<bits/stdc++.h>
#define line cout<<endl;
#define space cout<<" ";
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define PI 3.141592653589793238
typedef long long int ll;

using namespace std;

const ll N = 1e9+7;

ll nextgreater[100000+5];
ll previousgreater[100000+5];

void solve()
{
memset(nextgreater,-1,sizeof(nextgreater));
memset(previousgreater,-1,sizeof(previousgreater));
ll n;
cin>>n;

vector<ll> v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}

// cout<<"hello world"; line;

stack<ll> selement;
stack<ll> sindex;

for(int i=0;i<n;i++){
if((int)selement.size() == 0){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] >= selement.top()){
while((int)selement.size() > 0 && v[i] >= selement.top()){
nextgreater[sindex.top()] = v[i];
selement.pop();
sindex.pop();
}
}

selement.push(v[i]);
sindex.push(i);
}
}

// cout<<"next greater is done: "; line;

while((int)selement.size() > 0){
selement.pop();
}
while((int)selement.size() > 0){
sindex.pop();
}

for(int i=n-1;i>=0;i--){
if((int)selement.size() == 0){
selement.push(v[i]);
sindex.push(i);
}
else{
if(v[i] >= selement.top()){
while((int)selement.size() > 0 && v[i] >= selement.top()){
previousgreater[sindex.top()] = v[i];
selement.pop();
sindex.pop();
}
}

selement.push(v[i]);
sindex.push(i);

}
}
// cout<<"previous greater id one: ";line;

unordered_set<ll> ansset;
for(int i=0;i<n;i++){
if(nextgreater[i] != -1){
ansset.insert(nextgreater[i] - v[i]);
}
if(previousgreater[i] != -1){
ansset.insert(previousgreater[i] - v[i]);
}
}

cout<<ansset.size();
}

int main()
{
fast;
ll t;
// t = 1;
cin>>t;

while(t--)
{
solve();
cout<<endl;
}

}

I have modified the soluntion just a bit
2
1 1
this test I’m getting ans 1

this is also getting TLE on some case in subtask 2, but the solution is almost identical to author’s solution

That’s what the correct solution supposed to get.

1 Like

Yes for the test case you suggested I’m getting correct ans for above solution , but after submitting it m getting TLE on 1 testcase of subtask 2


text:
# example of a non differentiable manifold

Take the manifold: The graph of $|x|$ on $(-1,1)$, with the induced topology from $\mathbb{R}^2$. This is a topological manifold, which is homeomorphic to $(-1,1)$ by projection. Is it a differentiable manifold? I believe it is, because we can take an atlas with only the projection, and then we will have only one transition map which is the identity, and therefore differentiable. But I'm not sure I get the definition of a differentiable manifold right...

Thanks!

-
The graph is not a submanifold of $\mathbb R^2$ but can be endowed with the structure of a differentiable manifold whose underlying topology is that induced by $\mathbb R^2$. See the link here for a proof that it is not a submanifold. –  Georges Elencwajg Aug 18 '13 at 11:58
I'm not sure if submanifold are my interest at the moment. Still my question is: Is it a differentiable manifold? –  cruvadom Aug 18 '13 at 13:25

You're correct that you can define a smooth structure via the projection map - this should come as no surprise, since the homeomorphic space $(-1,1)$ is obviously a smooth manifold. The reason you're feeling uneasy is that the topological embedding into $\mathbb{R}^2$ is not smooth - there is a corner at the origin.

-
So is the graph of $|x|$ on $(-1,1)$ with the induced topology a differentiable manifold according to definitions? –  cruvadom Aug 18 '13 at 13:27
@cruvadom: when equipped with the correct atlas, yes. The smooth structure is not compatible with that of the ambient space $\mathbb{R^2}$ in the way that the topological structure is, however. –  Anthony Carapetis Aug 18 '13 at 14:07


text:
+0

# Inequalities Again

0
47
4
+179

Let x, y and z be positive real numbers such that x + y + z = 1.

Find the minimum value of $$\frac{x + y}{xyz}$$.

After submitting my first answer, I found that the minimum value does not occur when x=y=z=1/3, meaning that the answer must be less than 18 (because 18 is achievable).

Thanks for any help, especially if you could briefly describe the proof you used.

Have a great day!

Jun 30, 2021

### 3+0 Answers

#1
+2104
+3

Your questions are always so hard but I'll try my best.

Since x and y seem to be used the same in the equation.

I'm going to assume that x = y. *This could be totally incorect.

(2x)/(x^2z) is our new equation.

z = 1 - 2x

Let a be (x+y)/(xyz).

(2x)/(x^2(1-2x)) = a

2x = a(x^2 - 2x^3)

Just quickly graphing this out in desmos by setting a = y (not the y in the original equation, but for coordinate purposes), it seems like the sum can be any value other than from the range (0, 16].

Not sure what went wrong, but I hope this helped a bit.

Good luck.

=^._.^=

Jun 30, 2021
#2
+179
+4

Ay!  Turns out, the answer was 16, occurring when x=y=1/4 and z=1/2.

We use a combination of the AM-HM and the AM-GM in that order.

Starting, we have by the AM-HM $$\frac{x + y}{2} \ge \frac{2}{\frac{1}{x} + \frac{1}{y}} = \frac{2xy}{x + y}$$

So we have $$\frac{x + y}{xy} \ge \frac{4}{x + y}$$.

Multiplying by 1/z, we get $$\frac{x + y}{xyz} \ge \frac{4}{(x + y)z}$$.

By the AM-GM inequality,

$$\sqrt{(x + y)z} \le \frac{x + y + z}{2} = \frac{1}{2}$$

meaning $$(x + y)z \le \frac{1}{4}$$.

Hence,

$$\frac{4}{(x + y)z} \ge 16$$.

Using what we had before, we can write

$$\frac{x + y}{xy} \ge \frac{4}{x + y} \ge 16$$.

Equality occurs when x=y, and the minimum value is 16.

If you ask me, this solution was quite interesting.  I thought of using the QM-AM-GM-HM relationship, as well as the Cauchy-Schwarz Inequality, but not in this way.  Thanks for your help!

EnchantedLava68  Jun 30, 2021
#3
+2104
+2

YAYYY. :DDDD

That is such an intresting solution.

I have not yet learned about AM-GM/AM-HM, but I'm planning to do so soon through alcumus.

I think the mistake I made was forgetting that x, y, and z were all positive, meaning that (x+y)/(xyz) was also positive.

=^._.^=

catmg  Jul 1, 2021


text:
# zbMATH — the first resource for mathematics

On periodic $$\beta$$-expansions of Pisot numbers and Rauzy fractals. (English) Zbl 0991.11040
Let $$\beta$$ be a real number greater than 1 and $$T_{\beta}x=\beta x - [\beta x],$$ where $$[\dots ]$$ stands for the integer part. Then each $$x \in [0,1)$$ has a $$\beta$$-greedy expansion by the series $$\sum _{k=1} ^{\infty} [\beta T_{\beta}^{k-1}x] \beta^{-k}.$$ Let $$\beta$$ be a Pisot number, namely, all its conjugates over $$\mathbb Q$$ except for $$\beta$$ itself are strictly inside the unit circle. It is known [see, e.g., K. Schmidt, Bull. Lond. Math. Soc. 12, 269-278 (1980; Zbl 0494.10040)] that $$x \in {\mathbb Q}(\beta) \cap [0,1)$$ iff the $$\beta$$-greedy expansion of $$x$$ is periodic. Let $$x \in {\mathbb Q}(\beta) \cap [0,1),$$ where $$\beta$$ is a cubic Pisot number. The authors find the respective ‘if and only if’ condition on $$x$$ for its $$\beta$$-greedy expansion to be purely periodic. It depends on the other two conjugates of $$x$$ and on the minimal polynomial of $$\beta$$ over $${\mathbb Q}.$$

##### MSC:
 11J71 Distribution modulo one 11R06 PV-numbers and generalizations; other special algebraic numbers; Mahler measure
##### Keywords:
Pisot numbers; Rauzy fractals; greedy expansion
Zbl 0494.10040


text:
# Seven Times a Number Minus the Number Is -48. Find the Number.

## Question: Seven times a number minus the number is -48. Find the number.

The given question is based on linear equations in one variable.

## Answer: The required number is -8, which satisfies the condition: seven times a number minus the number is -48.

Let's interpret the given information mathematically and solve the equation.

## Explanation:

Let the required number be "a".

Given that, seven times a number minus the number is -48

7 × a - a = -48

7a - a = -48

6a = -48

a = (- 48) / 6

a = -8


text:
# How to know the name of the an active preset dropdown?

Hello i created a custom operator preset system.

i'd like to know how to have acces to the name of an active preset. i think an example from any preset in blender could help me in my research.

Here is my set up

This is the code i was able to collect so far

#this is the correct code mut within blender ! no with my addon
bpy.data.window_managers["WinMan"].preset_name = "New Preset"
bpy.ops.wm.call_panel(name="CYCLES_PT_sampling_presets")

#execute a preset from my addon

i need to find the bpy.data.window_managers["WinMan"].preset_name = "New Preset" for my addon menu. i don't know how this is possible ?

• You mean this bpy.context.workspace.name and [ws.name for ws in bpy.data.workspaces]? – lemon Sep 7 '19 at 6:27
• @lemon sorry for being unclear. i was referencing drop down presets. – DB3D Sep 7 '19 at 11:09
• @lemon i updated the question/descritption – DB3D Sep 7 '19 at 12:05
• I'm not skilled at that. But why don't you store the preset identification/name/whatever as an operator property? (not sure there is some Blender mechanism that does it automatically, except maybe by preset path). – lemon Sep 7 '19 at 12:53
• It’s the bl_label of the preset menu. – AFWS Oct 11 '19 at 21:11

Thanks to @AFWS

print(bpy.types.CYCLES_PT_integrator_presets.bl_label)

active preset is in fact the name of the bl_label

Assuming that panel for the preset uses preset_operator = "script.execute_preset" the selected preset is indeed stored in bl_label. This can be seen in class ExecutePreset(Operator) in the presets.py where the label is changed to the most recent selection when the operator is executed.
    # change the menu title to the most recently chosen option


text:
Smooth data over age fitting linear models, preserving the open age group if necessary. This is a wrapper to stats::lm() but using standard demographic arguments.

poly_smth1(Value, Age, degree = 2, trans, pow = 2, OAG = TRUE, ...)

## Arguments

Value numeric vector of counts in single, abridged, or 5-year age groups. integer vector of ages corresponding to the lower integer bound of the counts. integer degree of polynomial. Default 2. if a transformation is desired, either specify "log" or "power", otherwise leave missing. if "power" specified for trans then the power transformation to apply. logical. Whether or not the top age group is open. Default TRUE. optional arguments passed to stats::lm()

## Details

The total sum of Value is preserved in the output. One can control smoothness by adjusting the degree of the polynomial (higher degree more wiggly). See lm for more details. One may wish to log transform the data before fitting the polynomial, in which case trans should be specified as "log". "power" is also an option in which case the data is transformed by Value^(1/pow) before fitting, and then the prediction is back-transformed (negative values not allowed)-- This is friendlier in the case of 0s. For the log transformation, 0s have no weight.

lm

## Examples

if (FALSE) {
Age <- 0:99
cols <- RColorBrewer::brewer.pal(7,"Reds")[3:7]
plot(Age,pop1m_pasex)
lines(Age, poly_smth1(pop1m_pasex, Age, OAG = FALSE),col=cols[1])
lines(Age, poly_smth1(pop1m_pasex, Age, degree = 3, OAG = FALSE), col = cols[2])
lines(Age, poly_smth1(pop1m_pasex, Age, degree = 3, trans = "log", OAG = FALSE), col = cols[3])
lines(Age, poly_smth1(pop1m_pasex, Age, degree = 3,
trans = "power", pow = 2, OAG = FALSE), col = cols[4])
lines(Age, poly_smth1(pop1m_pasex, Age, degree = 4,
trans = "power", pow = 3, OAG = FALSE), col = cols[5])
}