text:
# Problem with rowcolor in tables

I have a problem with this table. I have other tables in my document, but rowcolor worked fine. Particularly, this code of my table has something wrong.
I want the header colored with gray.

\documentclass{article}

\usepackage{xcolor}
\usepackage{color, colortbl}
\definecolor{Gray}{gray}{0.9}
\usepackage{caption}
\usepackage{multirow,array}

\begin{document}
\begin{table}[H]
\caption{Title}
\centering
\begin{tabular}{|>{\raggedright\arraybackslash}m{50mm}|>{\raggedleft\arraybackslash}m{20mm}|>{\raggedleft\arraybackslash}m{20mm}|>{\raggedleft\arraybackslash}m{20mm}|}
\hline
\rowcolor{Gray} \multicolumn{1}{|c|}{\textbf{Text}} & \multicolumn{1}{>{\centering\arraybackslash}m{20mm}|}{\textbf{Text}} & \multicolumn{1}{>{\centering\arraybackslash}m{20mm}|}{\textbf{Text}} & \multicolumn{1}{>{\centering\arraybackslash}m{20mm}|}{\textbf{Text}}\\
\hline
\rowcolor{Gray} \textbf{Descripción} & \textbf{Nº} & \textbf{Sueldo mes} & \textbf{Total Año}\\\hline
\textbf{Text} & Text & & Text\\
\textbf{Text} & Text & & Text\\
\hline
\end{tabular}

\end{table}

\end{document}

-
@HarishKumar Thanks, but i defined the color in the preamble. I've just change the code. – Isai Jan 19 '13 at 1:42
Your code works for me. May be you need an update of your tex distro.? – Harish Kumar Jan 19 '13 at 1:44
@HarishKumar I have a question, if I define a new row without multicolumn, it works: \hline \hline \rowcolor{Gray} \textbf{Text} & \textbf{Text} & \textbf{Text} & \textbf{Text}\\\hline \hline May have something more in the code of the row where there are multicolumn commands? – Isai Jan 19 '13 at 2:00
It works as it is for me! More details may be needed here. – Harish Kumar Jan 19 '13 at 2:04
@HarishKumar I answered the question, with rowcolor in each cell. Thanks. – Isai Jan 19 '13 at 2:33

For people who has the same problem, this code works for me; I defined the \multicolumn{1}{|c|}{\rowcolor{Gray}\textbf{Text}} for each cell, instead of define de \rowcolor at the beginning of the row.

\documentclass{article}

\usepackage{color, colortbl}
\definecolor{Gray}{gray}{0.9}
\usepackage{caption}

\begin{document}
\begin{table}[H]
\caption{Title}
\centering
\begin{tabular}{|>{\raggedright\arraybackslash}m{50mm}|>{\raggedleft\arraybackslash}m{20mm}|>{\raggedleft\arraybackslash}m{20mm}|>{\raggedleft\arraybackslash}m{20mm}|}
\hline
\multicolumn{1}{|c|}{\rowcolor{Gray}\textbf{Text}} & \multicolumn{1}{>{\centering\arraybackslash}m{20mm}|}{\rowcolor{Gray}\textbf{Text}} & \multicolumn{1}{>{\centering\arraybackslash}m{20mm}|}{\rowcolor{Gray}\textbf{Text}} & \multicolumn{1}{>{\centering\arraybackslash}m{20mm}|}{\rowcolor{Gray}\textbf{Text}}\\
\hline
\textbf{Text} & Text & & Text\\
\textbf{Text} & Text & & Text\\
\hline
\end{tabular}

\end{table}

\end{document}

-
Of course you mean \cellcolor, because \rowcolor there will raise an error. But the table in your question compiles perfectly for me. – egreg Jan 19 '13 at 9:50
@egreg Maybe, the software I use miss some update, as HarishKumar said. I work in Texpad software. Anyway, cellcolor also works for me. – Isai Jan 20 '13 at 18:13


text:
Number theory

Problem for Secondary Group from Divisional Mathematical Olympiad will be solved here.
Forum rules
Please don't post problems (by starting a topic) in the "Secondary: Solved" forum. This forum is only for showcasing the problems for the convenience of the users. You can post the problems in the main Divisional Math Olympiad forum. Later we shall move that topic with proper formatting, and post in the resource section.
Drake
Posts: 1
Joined: Tue Dec 26, 2017 12:00 pm

Number theory

The energy of an ordered triple(a,b,c) formed by 3 positive integers a,b,c is said to be n and a<=b<=c and GCD(a,b,c)=1. There are some possible triples for which a^n+b^n+c^n is divisible by a+b+c for all n>0. Find the maximum possible value of a+b+c.

samiul_samin
Posts: 1007
Joined: Sat Dec 09, 2017 1:32 pm

Re: Number theory

I'll Latex it for you:
The energy of a ordered triple ($a,b,c$) formed by $3$ positive integers $a,b,c$ is said to be $n$ and $a\leq b\leq c$ & GCD($a,b,c$)$=1$.There are some possible triples for $a^n+b^n+c^n$ is divisible by $a+b+c$ for all $n>0$.Find the maximum possible value of $a+b+c$.

Note

NABILA
Posts: 28
Joined: Sat Dec 15, 2018 5:19 pm
Location: Munshigonj, Dhaka

Re: Number theory

samiul_samin wrote:
Sat Mar 03, 2018 9:53 pm
There are some possible triples for $a^n+b^n+c^n$ is divisible by $a+b+c$ for all $n>0$.
@Drake

format: plain


text:
# NAG Library Routine Document

## 1Purpose

g01gdf returns the probability associated with the lower tail of the noncentral $F$ or variance-ratio distribution.

## 2Specification

Fortran Interface
 Function g01gdf ( f, df1, df2, tol,
 Real (Kind=nag_wp) :: g01gdf Integer, Intent (In) :: maxit Integer, Intent (Inout) :: ifail Real (Kind=nag_wp), Intent (In) :: f, df1, df2, rlamda, tol
#include <nagmk26.h>
 double g01gdf_ (const double *f, const double *df1, const double *df2, const double *rlamda, const double *tol, const Integer *maxit, Integer *ifail)

## 3Description

The lower tail probability of the noncentral $F$-distribution with ${\nu }_{1}$ and ${\nu }_{2}$ degrees of freedom and noncentrality parameter $\lambda$, $P\left(F\le f:{\nu }_{1},{\nu }_{2}\text{;}\lambda \right)$, is defined by
 $PF≤f:ν1,ν2;λ=∫0xpF:ν1,ν2;λdF,$
where
 $PF : ν1,ν2;λ =∑j= 0∞e-λ/2 λ/2jj! ×ν1+ 2jν1+ 2j/2 ν2ν2/2 Bν1+ 2j/2,ν2/2$
 $×uν1+2j-2/2ν2+ν1+2ju -ν1+2j+ν2/2$
and $B\left(·,·\right)$ is the beta function.
The probability is computed by means of a transformation to a noncentral beta distribution:
 $PF≤f:ν1,ν2;λ=PβX≤x:a,b;λ,$
where $x=\frac{{\nu }_{1}f}{{\nu }_{1}f+{\nu }_{2}}$ and ${P}_{\beta }\left(X\le x:a,b\text{;}\lambda \right)$ is the lower tail probability integral of the noncentral beta distribution with parameters $a$, $b$, and $\lambda$.
If ${\nu }_{2}$ is very large, greater than ${10}^{6}$, then a ${\chi }^{2}$ approximation is used.

## 4References

Abramowitz M and Stegun I A (1972) Handbook of Mathematical Functions (3rd Edition) Dover Publications

## 5Arguments

1:     $\mathbf{f}$ – Real (Kind=nag_wp)Input
On entry: $f$, the deviate from the noncentral $F$-distribution.
Constraint: ${\mathbf{f}}>0.0$.
2:     $\mathbf{df1}$ – Real (Kind=nag_wp)Input
On entry: the degrees of freedom of the numerator variance, ${\nu }_{1}$.
Constraint: $0.0<{\mathbf{df1}}\le {10}^{6}$.
3:     $\mathbf{df2}$ – Real (Kind=nag_wp)Input
On entry: the degrees of freedom of the denominator variance, ${\nu }_{2}$.
Constraint: ${\mathbf{df2}}>0.0$.
4:     $\mathbf{rlamda}$ – Real (Kind=nag_wp)Input
On entry: $\lambda$, the noncentrality parameter.
Constraint: $0.0\le {\mathbf{rlamda}}\le -2.0\mathrm{log}\left(U\right)$ where $U$ is the safe range parameter as defined by x02amf.
5:     $\mathbf{tol}$ – Real (Kind=nag_wp)Input
On entry: the relative accuracy required by you in the results. If g01gdf is entered with tol greater than or equal to $1.0$ or less than  (see x02ajf), the value of  is used instead.
6:     $\mathbf{maxit}$ – IntegerInput
On entry: the maximum number of iterations to be used.
Suggested value: $500$. See g01gcf and g01gef for further details.
Constraint: ${\mathbf{maxit}}\ge 1$.
7:     $\mathbf{ifail}$ – IntegerInput/Output
On entry: ifail must be set to $0$, . If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value  is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, because for this routine the values of the output arguments may be useful even if ${\mathbf{ifail}}\ne {\mathbf{0}}$ on exit, the recommended value is $-1$. When the value  is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

## 6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Note: g01gdf may return useful information for one or more of the following detected errors or warnings.
Errors or warnings detected by the routine:
If on exit ${\mathbf{ifail}}={\mathbf{1}}$ or ${\mathbf{3}}$, then g01gdf returns $0.0$.
${\mathbf{ifail}}=1$
On entry, ${\mathbf{df1}}=〈\mathit{\text{value}}〉$.
Constraint: $0.0<{\mathbf{df1}}\le {10}^{6}$.
On entry, ${\mathbf{df1}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{df1}}>0.0$.
On entry, ${\mathbf{df2}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{df2}}>0.0$.
On entry, ${\mathbf{f}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{f}}>0.0$.
On entry, ${\mathbf{maxit}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{maxit}}\ge 1$.
On entry, ${\mathbf{rlamda}}=〈\mathit{\text{value}}〉$.
Constraint: $0.0\le {\mathbf{rlamda}}\le -2.0×\mathrm{log}\left(U\right)$, where $U$ is the safe range parameter as defined by x02amf.
${\mathbf{ifail}}=2$
The solution has failed to converge in $〈\mathit{\text{value}}〉$ iterations. Consider increasing maxit or tol.
${\mathbf{ifail}}=3$
The required probability cannot be computed accurately. This may happen if the result would be very close to zero or one. Alternatively the values of df1 and f may be too large. In the latter case you could try using a normal approximation, see Abramowitz and Stegun (1972).
${\mathbf{ifail}}=4$
The required accuracy was not achieved when calculating the initial value of the central $F$ or ${\chi }^{2}$ probability. You should try a larger value of tol. If the ${\chi }^{2}$ approximation is being used then g01gdf returns zero otherwise the value returned should be an approximation to the correct value.
${\mathbf{ifail}}=-99$
See Section 3.9 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 3.8 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

## 7Accuracy

The relative accuracy should be as specified by tol. For further details see g01gcf and g01gef.

## 8Parallelism and Performance

g01gdf is not threaded in any implementation.

When both ${\nu }_{1}$ and ${\nu }_{2}$ are large a Normal approximation may be used and when only ${\nu }_{1}$ is large a ${\chi }^{2}$ approximation may be used. In both cases $\lambda$ is required to be of the same order as ${\nu }_{1}$. See Abramowitz and Stegun (1972) for further details.

## 10Example

This example reads values from, and degrees of freedom for, $F$-distributions, computes the lower tail probabilities and prints all these values until the end of data is reached.

### 10.1Program Text

Program Text (g01gdfe.f90)

### 10.2Program Data

Program Data (g01gdfe.d)

### 10.3Program Results

Program Results (g01gdfe.r)


text:
# How to compute E[$g(X)$] in terms of $X$'s CCDF (complementary cumulative distribution function)?

If we know the PDF $$f$$ of a random variable $$X$$ then we can compute an expression like $$\mathrm E[g(X)]$$ as $$\mathrm E[g(X)] = \int_{\mathrm{Im}(X)} g(x) f(x) \mathrm dx \, .$$

Let $$F$$ be the CDF of a positive random variable $$X$$, then we call $$\bar{F}=1-F$$ the complementary CDF (CCDF) of $$X$$. It is a well-known result that $$\mathrm E[X] = \int_{\mathrm{Im}(X)} \bar{F}(x) \mathrm dx$$. Is there a handy formular that allows to apply that to terms like $$\mathrm E[g(X)]$$? Since we have $$\mathrm E[g(X)] = \int_{\mathrm{Im}(X)} g(x) \mathrm d F(x)$$, another way to phrase the question is whether there is a general way to relate the Lebesgue-Stieltjes integral with respect to the CDF of $$X$$ to an integral involving its CCDF?

These questions came up while I was trying to solve a problem and I could reduce it to asserting that for some positive constant $$r$$ we have \begin{align}r \int_0^\infty x \mathrm{e}^{rx}\bar{F}(x)\mathrm{d}x &= \frac{\mathrm{d}}{\mathrm{d}r} \mathrm{E}[\mathrm{e}^{rX}] - \int_0^\infty \mathrm{e}^{rx}\bar{F}(x)\mathrm{d}x \\ &= \int_0^\infty x \mathrm{e}^{rx} \mathrm{d}F(x) - \int_0^\infty \mathrm{e}^{rx}\bar{F}(x)\mathrm{d}x \, . \end{align}

And I don't see a way to relate the two sides of this equation. I hope that I didn't miss any piece of additional information which makes this true, not holding in general though.

• Do you know any properties of $g$ ? For instance if it is positive and increasing then the answer is straight forward. – P. Quinton Feb 7 at 13:14
• In my specific problem $g(x) = \mathrm{e}^{rx}$ or $g(x) = x \mathrm{e}^{rx}$ for $x \geq 0$ so yes, it is positive and increasing here. – Hölderlin Feb 7 at 13:30
• maybe this could help – Masacroso Feb 7 at 14:36
• It's exactly what I needed, thank you so much! – Hölderlin Feb 7 at 20:17


text:
# Maybe Euler's formula may be useful

1. Nov 25, 2004

### hedlund

Prove that if $$y = \sin^n{x}$$ then the only value for which $$y' = \sin{nx}$$ is for n=2. I'm think maybe Euler's formula may be useful ... $$\sin{x} = \frac{e^{ix}-e^{-ix}}{2i}$$ but I really got no good idea on how to solve it.

2. Nov 25, 2004

### Muzza

If y = sin^(n)(x), then y' = nsin(x)^(n - 1)cos(x). Suppose n is odd and that y' = sin(nx). Then sin(nx) = nsin(x)^(n - 1)cos(x) even for x = pi/2. The equation reduces into

sin(n * pi/2) = nsin(pi/2)^(n - 1)cos(pi/2)
<=>
sin(n * pi/2) = 0.

But n = 2k + 1 for some integer k, so sin(n * pi/2) = sin( (2k + 1)pi/2 ) = sin(kpi + pi/2) = cos(k * pi). But that is never equal to zero. Contradiction.

I don't know how to handle the case when n is even and > 2.


text:
• FEATURED

View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# DirectX 9.0a SDK

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

12 replies to this topic

### #1/ ProDevGURU   Members

Posted 05 December 2012 - 01:27 PM

### #2DgekGD  Members

Posted 05 December 2012 - 01:45 PM

You can download sdk from here . It includes everything you need for directx programming(9, 10, 11);

Edited by DgekGD, 05 December 2012 - 01:45 PM.

### #3/ ProDevGURU   Members

Posted 05 December 2012 - 02:25 PM

### #4Tispe  Members

Posted 06 December 2012 - 01:29 AM

The community is split between the older guys saying "why don't you just make an installer" and the newer folks saying "I want a single executable that works on all WinXP machines regardless". Personally I like the latter when doing mini-projects that I may want to distribute to a small volume of people. I would hardly install a simple modelviewer, I would sure want one that is a single exe, no installs required.

### #5/ ProDevGURU   Members

Posted 06 December 2012 - 02:47 AM

Excuse me but wtf? What is this doing with DirectX 9.0a?

### #6kubera  Members

Posted 06 December 2012 - 03:10 AM

Hi!

The old versions of DirectX has been removed from Mirosoft's servers.

I had the same problem. They would answer such question, but they rather do not publish them...
I aksed Chuck Waolburn, an expert at MS and he has suggested a newer version.
You would search the SDK through the Internet or ask someone only.

### #7Tispe  Members

Posted 06 December 2012 - 03:20 AM

Excuse me but wtf? What is this doing with DirectX 9.0a?

The only reason I can think of to use the 2003 SDK for is to build a release that works for all early WinXP releases. The only way to get a 2012 SDK to work on the early WinXP releases is to accompny your program with an installer packed with redistibutables.

Edited by Tispe, 06 December 2012 - 03:21 AM.

### #8kubera  Members

Posted 06 December 2012 - 03:29 AM

I am not sure, but WinXP SP2 is required from DIrectX June 2010 (because of Visual C++ 2010 runtime).
You would find something newer, that will be able to work on such platform.

### #9/ ProDevGURU   Members

Posted 06 December 2012 - 03:40 AM

No this is not my problem. I'm reverse engenering program which was compiled with this SDK so that's way I need it.

You would search the SDK through the Internet or ask someone only.

Hwo to ask ? Any ideas ?

### #10kubera  Members

Posted 06 December 2012 - 04:05 AM

I searched my bakcup CDs, I do not have it.

### #11/ ProDevGURU   Members

Posted 06 December 2012 - 04:18 AM

Why you think I have colleagues?

Anyway if somebody have this SDK I'll be glad if he/she upload it and send me the link.

### #12kubera  Members

Posted 06 December 2012 - 04:22 AM

It is rather a different version of DX, but I have a legacy DirectX9 without "a" suffix.
If you need it, please let me know.

### #13/ ProDevGURU   Members

Posted 06 December 2012 - 09:23 AM

Thank you but I already have it (from one chinese site) and actually there're some mistmatches with the SDK used and this one. I'll show what actually I need defined:

class SYS_DI_ADAPTER
{
public:
SYS_DI_ADAPTER(DIDEVICEINSTANCEA const &, SYS_DI *, SYS_ERROR &);

SYS_ERROR GetSettings(SYS_DI_DEVICE_SETTINGS &);
SYS_ERROR SetSettings(SYS_DI_DEVICE_SETTINGS &);
SYS_DI_ADAPTER_OBJECT * FindObject(unsigned long, unsigned long)const;

private:
SYS_ERROR RegOpenKeyA(bool,HKEY &);
SYS_ERROR SetSettings_Registry(SYS_DI_DEVICE_SETTINGS &);
SYS_ERROR GetSettings_Registry(SYS_DI_DEVICE_SETTINGS &);
SYS_ERROR GetSettings_Default(SYS_DI_DEVICE_SETTINGS &);
static int __stdcall DIEnumDeviceObjectsCallback(DIDEVICEOBJECTINSTANCEA const *,void *);
static int __stdcall DIEnumDeviceEffectsCallback(DIEFFECTINFOA const *, void *);

public:
DIDEVICEINSTANCEA m_0; //size 580
DIDEVCAPS m_588; //size 44
} ; //size of 636
class SYS_DI
{
public:
SYS_DI(SYS_COMMAND_LINE const &,HWND,SYS_ERROR &);
SYS_ERROR Create();
void CloseDevices();

SYS_ERROR Setup_Playback(char *);
SYS_ERROR Setup_Recording(char *);
SYS_ERROR CreateDI();
SYS_ERROR EnumDevices();
static int __stdcall DIEnumDevicesCallback(DIDEVICEINSTANCEA const *, void *);

SYS_COMMAND_LINE const & m_0; //size 4
HWND m_4; //size 4
BYTE m_8;
BYTE m_9;
HMODULE m_12; //size 4
HRESULT (*m_16)(
HINSTANCE hinst,
DWORD dwVersion,
REFIID riidltf,
LPVOID * ppvOut,
LPUNKNOWN punkOuter
); //size 4
LPDIRECTINPUT8A m_20; //size 4
unsigned char m_256;
unsigned char m_257;
HANDLE m_260; //size 4
HANDLE m_264; //size 4
} ;
{
SYS_ERROR result = SYS_ERROR_UNKNOWN;
__try {
LPDIRECTINPUTDEVICE8A v0 = 0;
if(a0->m_20->CreateDevice(m_4, &v0, 0)>=0)
{
DIDATAFORMAT tDat;
tDat./*m_24*/ = 24; //offset HERE!!!!!!!!!!!!!!!!
tDat.dwSize = sizeof(DIDATAFORMAT);
tDat.dwObjSize = sizeof(DIOBJECTDATAFORMAT);
tDat.dwFlags = 0;
tDat.dwDataSize = 0;
tDat.dwNumObjs = 0;
tDat.rgodf = NULL;
if(v0->SetDataFormat(&tDat)>=0)
{
if(v0->SetCooperativeLevel(a0->m_4, DISCL_EXCLUSIVE | DISCL_FOREGROUND)>=0)
{
memset(&m_588, 0, sizeof(DIDEVCAPS));
m_147 = sizeof(DIDEVCAPS);
if(v0->GetCapabilities(&m_588)>=0)
{
if(v0->EnumObjects(&DIEnumDeviceObjectsCallback, this, DIDFT_ALL)>=0)
{
sysDXListReverse(m_580);
if(v0->EnumEffects(&DIEnumDeviceEffectsCallback, this, DIDFT_ALL)>=0)
result = SYS_ERROR_NO;
}
}
}
}
}
RELEASE(&v0);
}
__except(1){}
return result;
}

So what is this the DIDATAFORMAT structure is with 24 bytes size but the program code is trying to access the element in it at 24 offset (this mean there need to be one extra member). Is this defined only in DirectX 9.0a but not in DirectX 9.0?

And the other strange thing is this http://www.gamedev.net/topic/634619-enum-d3dformat-problem/. Where is these format defined? Actually there isn't such an enumeration member in DirectX 9.0. The program ReadMe file says that it was used DirectX 9.0a. So that's way I think this is my problem.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


text:
## Friday, May 21, 2010

### Cleaner CDK Code #6: set the CDKException's cause Exception

For about two weeks now, I am working on fixing a bug in the nonotify module: they classes were still sending around change events. I decided to finally do it the proper way: sending around change events is extra functionality, so the data module should extend the nonotify module and not the other way around, as in CDK 1.2 and CDK 1.3 up to now. There was a dirty hack in place, introducing a boolean indicating it should send events or not, but that turned out to be insufficient.

Anyway, while working on a major refactoring like this one, you run into many, many small code issues. Clearly. the one I mostly run into is that a lot of code is not written against the interfaces yet. However, I just ran into another bit of code that can be improved.

Set the cause Exception when throwing a CDKException
This is the particular bit of code I ran into:
try {
molecule = (IMolecule) container.clone();
} catch (CloneNotSupportedException e) {
throw new CDKException(
"Error occured during clone " + e
)
}

However, there are two small improvements that can be applied to this code. The first is that the the error message passed to the CDKException constructor can reuse the message of the cause Exception. The second improvement is that we can actually pass the cause exception is cause to the CDKException. Therefore, the CDKException can be constructed as (also fixing the typo :):
new CDKException(
"Error occurred during clone " + e.getMessage(),
e
);

Oh, and, of course, CDK code should use variables of at least three characters. Now, the original CDKException construction was on one line, in total having four points of improvement :)


text:
# On Coalitional Manipulation for Multiwinner Elections: Shortlisting

Shortlisting of candidates--selecting a group of "best" candidates--is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the perhaps most basic voting rule in this scenario, l-Bloc (every voter approves l candidates). In particular, we investigate the influence of several tie-breaking mechanisms (e.g., pessimistic versus optimistic) and group evaluation functions (e.g., egalitarian versus utilitarian). Among other things, conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. Altogether, we provide a fairly comprehensive picture of the computational complexity landscape so far in the literature of this neglected scenario.

## Authors

• 21 publications
• 8 publications
• 57 publications
• ### Eliminating the Weakest Link: Making Manipulation Intractable?

Successive elimination of candidates is often a route to making manipula...
04/17/2012 ∙ by Jessica Davies, et al. ∙ 0

• ### The Computational Impact of Partial Votes on Strategic Voting

In many real world elections, agents are not required to rank all candid...
05/28/2014 ∙ by Nina Narodytska, et al. ∙ 0

• ### Protecting Elections by Recounting Ballots

Complexity of voting manipulation is a prominent topic in computational ...
06/17/2019 ∙ by Edith Elkind, et al. ∙ 0

• ### A Unifying Framework for Manipulation Problems

Manipulation models for electoral systems are a core research theme in s...
01/29/2018 ∙ by Dušan Knop, et al. ∙ 0

• ### Designing Stable Elections: A Survey

We survey the design of elections that are resilient to attempted interf...
06/09/2020 ∙ by Steven Heilman, et al. ∙ 0

• ### Persuading Voters: It's Easy to Whisper, It's Hard to Speak Loud

We focus on the following natural question: is it possible to influence ...
08/28/2019 ∙ by Matteo Castiglioni, et al. ∙ 0

• ### Natural Strategic Abilities in Voting Protocols

Security properties are often focused on the technological side of the s...
07/24/2020 ∙ by Wojciech Jamroga, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

A university wants to select the two favorite compositions in classical style to be played during the next graduation ceremony. The students were asked to submit their favorite compositions. Then a jury consisting of seven members (three juniors and four seniors) from the university staff selects from the six most frequently submitted compositions as follows: Each jury member approves two compositions and the two winners are those obtaining most of the approvals. The six options provided by the students are “Beethoven: Piano Concerto No. 5 ()”, “Beethoven: Symphony No. 6 ()”, “Mozart: Clarinet Concerto ()”, “Mozart: Requiem K626 ()”, “Uematsu: Final Fantasy ()”, and “Badelt: Pirates of the Caribbean ()”. The three junior jury members are excited about recent audio-visual presentation arts (both interactive and passive) and approve and . Two of the senior jury members are Mozart enthusiasts, and the other two senior jury members are Beethoven enthusiasts. Hence, when voting truthfully, two of them would approve the two Mozart compositions and the other two would approve the two Beethoven compositions. The winners of the selection process would be and , both receiving three approvals whereas every other composition receives only two approvals.

The senior jury members meet every Friday evening and discuss important academic issues including the graduation ceremony music selection processes, why movie background noise recently counts as classical music, and the influence of video games on the ability of making important decisions. During such a meeting they agreed that a graduation ceremony should always be accompanied by a composition of a first-class composer and by another composition of a second-class composer (two compositions of a first-class composer may overstrain students and junior researchers). Thus, finally all four senior jury members approve and making these two compositions playing during the graduation ceremony.

Already this little example above (which will be the base of our running example throughout the paper) illustrates important aspects of strategic voting in multiwinner elections. In case of coalitional manipulation for single-winner elections (where a coalition of voters casts untruthful votes in order to influence the outcome of an election; a topic which has been intensively studied in the literature (Rothe, 2015; Brandt et al., 2016)) one can always assume that a coalition of manipulators agrees on trying to make a distinguished alternative win the election. In case of multiwinner elections, however, already determining concrete possible goals of a coalition seems to be a non-trivial task: There may be exponentially many different outcomes which can be reached through strategic votes of the coalition members and each member could have its individual evaluation of these outcomes.

Multiwinner voting rules come up very naturally whenever one has to select from a large set of candidates a smaller set of “the best” candidates. Surprisingly, although at least as practically relevant as single-winner voting rules, the multiwinner literature is much less developed than the single-winner literature. In recent years (see a survey of Faliszewski et al. (2017a)), however, research into multiwinner voting rules, their properties, and algorithmic complexity grew significantly (Aziz et al., 2017a; Betzler et al., 2013; Aziz et al., 2017b, 2015; Barrot et al., 2013; Barberà and Coelho, 2008, 2010; Elkind et al., 2017; Faliszewski et al., 2016, 2017b; Meir et al., 2008; Obraztsova et al., 2013; Skowron, 2015; Skowron et al., 2015). When selecting a group of winning candidates, various goals can be interesting; namely, proportional representation, diversity, or a short list (see Elkind et al. (2017)). We focus on the last scenario. Here the goal is to select the best (say highest-scoring) group of candidates.

Shortlisting comes very naturally in the context of selection committees; for instance, for human resources departments that need to select, for a fixed number of positions, the best qualified applicants. A standard way of candidate selection in the context of shortlisting is to use scoring-based voting rules. We focus on the two most natural ones: SNTV (single non-transferable vote—each voter gives one point to one candidate) and -Bloc (each voter gives one point to each of different candidates, so SNTV is the same as -Bloc). Obviously, for such voting rules it is trivial to determine the score of each individual candidate. The main goal of our work is to model and understand coalitional manipulation in a computational sense—that is, to introduce a formal description of how a group of manipulators can influence the election outcome by casting strategic votes and whether it is possible to find an effective strategy for the manipulators to change the outcome in some desired way. In this fashion, we complement well-known work: manipulation for single-winner rules initiated by Bartholdi III et al. (1989), coalitional manipulation for single-winner rules initiated by Conitzer et al. (2007), and (non-coalitional) manipulation for multiwinner rules initiated by Meir et al. (2008). In coalitional manipulation scenarios, given full knowledge about other voters’ preferences, one has a set of manipulative voters who want to influence the election outcome in a favorable way by casting their votes strategically.

To come up with a useful framework for coalitional manipulation for multiwinner elections, we first have to identify the exact mathematical model and questions to be asked. The straightforward extensions of coalitional manipulation for single-winner elections or (non-coalitional) manipulation for multiwinner elections do not fit. Extending the single-winner variant directly, one would probably assume that the coalition agrees on making a distinguished candidate part of the winners or that the coalition agrees on making a distinguished candidate group part of the winners. The former is unrealistic because in multiwinner settings one typically cares about more than just one candidate—especially in shortlisting it is natural that one wants rather some group of “similarly good” candidates to become part of winners instead of only one representative of such a group. Agreeing on a distinguished candidate group to be part of the winners is also problematic since there may be exponentially many “equally good” candidate groups for the coalition. Notably, this was not a problem in the single-winner case; there, one can test for a successful manipulation towards each possible candidate avoiding an exponential increase of the running time (compared to the running time of such a test for a single candidate). The single-manipulator model for multiwinner rules of

Meir et al. (2008) is a helpful first step: the manipulator specifies the utility of each candidate; the utility for a candidate group is obtained by adding up the utilities of each group member. Aggregating utilities, however, becomes non-trivial for a coalition of manipulators which may have totally different utilities for single candidates but still have strong incentives to work together (e.g., as we have seen in our introductory example). Besides formalizing this either in a utilitarian or egalitarian way, our modeling also aims to distinguish between optimistic and pessimistic manipulators. In case of a tie, optimistic manipulators assume that the tie is broken in favor of them while pessimistic ones assume the opposite scenario. It turns out that this difference in manipulators’ behavior leads to significant differences in terms of computational complexity. Technically, analyzing the issues discussed above requires to study tie-breaking mechanisms and (winning) group evaluation functions.

Related Work. To the best of our knowledge, there is no previous work on coalitional manipulation in the context of multiwinner elections. We refer to recent textbooks for an overview of the huge literature on single-winner (coalitional) manipulation (Rothe, 2015; Brandt et al., 2016). Most relevant to this paper, Lin (2011) showed that coalitional manipulation in single-winner elections under -Approval is solvable in linear time by a greedy algorithm. Meir et al. (2008) introduced (non-coalitional) manipulation for multiwinner elections. While identifying manipulation for several voting rules as NP-hard problems, they showed that manipulation remains polynomial-time solvable for Bloc (which can be interpreted as a multiwinner equivalent of -Approval). Obraztsova et al. (2013) extended the latter result for different tie-breaking strategies and identified further tractable special cases of multiwinner scoring rules but conjectured manipulation to be hard in general for (other) scoring rules. Summarizing, Bloc is simple but comparably well-studied and was, hence, selected as a showcase for our study of the presumably computationally harder coalitional manipulation.

Organization. Section 2 introduces basic notations and formal concepts. In Section 3, we develop our model for coalitional manipulation in multiwinner elections. Its variants respect different ways of evaluating candidate groups (utilitarian vs. egalitarian) and two kinds of manipulators behavior (optimistic vs. pessimistic). In Section 4, we present algorithms and complexity results for computing the output of several tie-breaking rules that allow to model optimistic and pessimistic manipulators. In Section 5, we formally define the coalitional manipulation problem and explore its computational complexity using -Bloc as a showcase. We refer to our conclusion and Table 1 (Section 6) for a detailed overview of our findings.

## 2 Preliminaries

For a positive integer , let . We use the toolbox of parameterized complexity (Cygan et al., 2015; Downey and Fellows, 2013; Flum and Grohe, 2006; Niedermeier, 2006) to analyze the computational complexity of our problems in a fine-grained way. To this end, we always identify a parameter  that is typically a positive integer. We call a problem parameterized by  fixed-parameter tractable (in ) if it is solvable in time, where is the size of a given instance encoding, is the value of the parameter, and is an arbitrary computable (typically super-polynomial) function. To preclude fixed-parameter tractability, we use an established complexity hierarchy of classes of parameterized problems, . It is widely believed that all inclusions are proper. The notions of hardness for parameterized classes are defined through parameterized reductions similar to classical polynomial-time many-one reductions—in this work, it suffices to ensure that the value of the parameter in the problem we reduce to depends only on the value of the parameter of the problem we reduce from. Occasionally, we use a combined parameter which is a more explicit way of expressing a parameter .

An election  consists of a set  of  candidates and a multiset  of  votes. Votes are linear orders over —for example, for we write to express that candidate  is the most preferred and candidate  is the least preferred according to vote . We write  if the corresponding vote is clear from the context.

A multiwinner voting rule222Some literature use the name multiwinner voting correspondence for what we called multiwinner voting rule. In that case, a multiwinner voting rule is required to return exactly one set of the desired size. This is usually achieved by combining a multiwinner voting correspondence with a tie-breaking rule. is a function that, given an election  and an integer , outputs a family of co-winning size- subsets of representing the co-winning -excellence-groups. We use -egroup as an abbreviation for -excellence-group. The reason we do not use the established term “committee” is that in shortlisting applications “committee” traditionally rather refers to voters and not to candidates.

We consider scoring rules which assign points to candidates based on their positions in the votes. By , we denote the total number of points that candidate  obtains, and we use  when restricting the election to a subset  of voters. A (multiwinner) scoring rule selects a family  of co-winning -egroups with the maximum total sum of scores. It holds that if and only if . We focus on the family of -Bloc multiwinner voting rules which assign, for each vote, one point to each of the top  candidates.333The case where  coincides with the size  of the egroup is typically referred to as Bloc; -Bloc corresponds to SNTV (Meir et al., 2008). The case where  is also referred to as Limited Vote (or Limited Voting).

###### Example 1.

Referring back to our introductory example, we have a set of candidates and a set of voters . The voters , , and represent the three junior jury members, whereas , and , represent, respectively, the Beethoven and Mozart enthusiasts among the senior jury members. In the example, we described a way of manipulating the election by the senior jury members which leads to selecting two music pieces. There are several ways to illustrate this manipulation using our model. Below we present one of the possible sets of casted votes that represents the manipulated election:

 vy1,vy2,vy3:o1≻o2≻b1≻b2≻m1≻m2, vb1,vb2,vm1,vm2:b1≻m1≻b2≻m2≻o1≻o2.

Following the introductory example, we are choosing an egroup of size . Using the Bloc multiwinner voting rules (which coincides with our introductory example), the winning -egroup consist of candidates and . However, under the SNTV voting rule the situation would change, and the winners would be and . SNTV and Bloc alike output a single winning egroup in this example, and thus tie-breaking is negligible.

To select a single -egroup from the set of co-winning -egroups one has to consider tie-breaking rules. A multiwinner tie-breaking rule is a mapping that, given an election and a family of co-winning -egroups, outputs a single -egroup. Among them, there is a set of natural rules that is of particular interest in order to model the behavior of manipulative voters. Indeed, in case of a single manipulator both pessimistic tie-breaking as well as optimistic tie-breaking have been considered in addition to lexicographic and randomized tie-breaking (Meir et al., 2008; Obraztsova et al., 2013). To model optimistic and pessimistic tie-breaking in a meaningful manner444We cannot simply use ordinal preferences: Obraztsova et al. (2013) observed that already in case of a single manipulator one cannot simply set the fixed lexicographic order of the manipulators’ preferences (resp. the reverse of it) over candidates to model optimistic (resp. pessimistic) tie-breaking. For example, it is a strong restriction to assume that a manipulator would always prefer its first choice together with its fourth choice towards its second choice together with its third choice. It might be that only its first choice is really acceptable (in which case the assumption is reasonable) or that the first three choices are comparably good but the fourth choice is absolutely unacceptable (in which case the assumption is wrong)., we use the model introduced by Obraztsova et al. (2013) in which a manipulative voter  is described not only by the preference order  of the candidates but also by a utility function . To cover this in the tie-breaking process, coalition-specific tie-breaking rules get—in addition to the original election, the manipulators’ votes, and the co-winning excellence-groups—the manipulators’ utility functions in the input. The formal implementations of these rules and their properties are discussed in Subsection 3.2.

## 3 Model for Coalitional Manipulation

In this section, we formally define and explain our model and the respective variants. To this end, we discuss how we evaluate a -egroup in terms of utility for a coalition of manipulators and introduce tie-breaking rules that model optimistic or pessimistic viewpoints of the manipulators.

### 3.1 Evaluating k-egroups

As already discussed in the introduction, one should not extend the model of coalitional manipulation for single-winner elections to multiwinner elections in the simplest way (e.g., by assuming that the manipulators agree on some distinguished candidate or on some distinguished egroup). Instead, we follow Meir et al. (2008) and assume that we are given a utility function over the candidates for each manipulator and a utility level which, if achieved, indicates a successful manipulation. Meir et al. (2008) compute the utility of an egroup by summing up the utility values the manipulator assigns to each member of the egroup.

At first glance, summing up the utility values assigned by each manipulator to each member of an egroup seems to be the most natural extension for a coalition of manipulators. However, this utilitarian variant does not guarantee single manipulators to gain non-zero utility. In extreme cases it could even happen that some manipulator is worse off compared to voting sincerely, as demonstrated in Example 2.

###### Example 2.

Consider the election where is a set of candidates and is the following multiset of three votes:

 v1,v2:o1≻o2≻m1≻m2≻b1≻b2, v3:m2≻m1≻b2≻b1≻o1≻o2.

Additionally, consider two manipulators, and , that report utilities to the candidates as depicted in the table below.

Let us analyze the winning -egroup under the SNTV voting rule. Observe that if the manipulators vote sincerely, then together they give one point to and one to (one point from each manipulator). Combining the manipulators’ votes with the non-manipulative ones, the winning -egroup consists of candidates and that both have score two; no other candidate has greater or equal score, so tie-breaking is unnecessary. The value of such a group is equal to seven according to the utilitarian evaluation variant. Manipulator ’s utility is seven. However, both manipulators can do better by giving their points to candidate . Then, the winners are candidates and , giving the total utility of (according to the utilitarian variant). Observe that in spite of growth of the total utility, the utility value gained by , which is one, is lower than in the case of sincere voting.

In Example 2 manipulator  devotes its satisfaction to the utilitarian satisfaction of the group of the manipulators; that is, is worse off voting strategically compared to voting sincerely. Despite this issue, however, the utilitarian viewpoint can be justified if the manipulators are able to compensate such losses of utility of some manipulators, for example, by paying money to each other. For cases where manipulators cannot do that, we introduce two egalitarian evaluation variants. The (egroup-wise) egalitarian variant aims at maximizing the minimum satisfaction of the manipulators with the whole -egroup. The candidate-wise egalitarian variant aims at maximizing the manipulators’ satisfaction resulting from the summation of the minimum satisfactions every single candidate contributes. We do not distinguish “candidate-wise utilitarian” variant since this variant would be equivalent to the (regular) utilitarian variant.

We formalize the described variants of -egroup evaluation (for  manipulators) with Definition 1.

###### Definition 1.

Given a set of candidates , a -egroup , , and a family of manipulators’ utility functions where , we consider the following functions:

• ,

• ,

• .

Intuitively, these functions determine the utility of a -egroup according to, respectively, the utilitarian and the egalitarian variants of evaluating  by a group of  manipulators (identifying manipulators with their utility functions). We omit subscript  when is clear from the context. To illustrate Definition 1 we apply it in Example 3.

###### Example 3.

Consider our example set of candidates and two manipulators , whose utility functions over the candidates are depicted in the table below.

Then, evaluating the utility of -egroup applying the three different evaluation variants gives:

• ,

• ,

• .

Analyzing Example 3, we observe that we can compute the utilitarian value of an egroup by summing up the overall utilities each candidate contributes to all manipulators. Analogously, we can deal with the candidate-wise egalitarian variant by taking the minimum utility associated to each candidate as the overall utility of this candidate. In both variants we obtain a single utility function.

###### Observation 1.

Without loss of generality, one can assume that there is a single non-zero valued utility function over the candidates under the utilitarian or candidate-wise egalitarian evaluation.

### 3.2 Breaking Ties

Before formally defining our tie-breaking rules, we briefly discuss some necessary notation and central concepts. Consider an election , a size  for the egroup to be chosen, and a scoring-based multiwinner voting rule . We can partition the set of candidates  into three sets , , and as follows: The set  contains the confirmed candidates, that is, candidates that are in all co-winning -egroups. The set  contains the pending candidates, that is, candidates that are only in some co-winning -egroups. The set  contains the rejected candidates, that is, candidates that are in no co-winning -egroup. Observe that , , and that every candidate from  receives fewer points than every candidate from . Additionally, all candidates in receive the same number of points.

We define the following families of tie-breaking rules which are considered in this work. In order to define optimistic and pessimistic rules, we assume that in addition to , , and , we are given a family of utility functions which are used to evaluate the -egroups as discussed in Subsection 3.1.

Lexicographic . A tie-breaking  belongs to if and only if ties are broken lexicographically with respect to some predefined order  of the candidates from . That is,  selects all candidates from  and the top candidates from  with respect to .

Optimistic , . A tie-breaking belongs to if and only if it always selects some -egroup  such that and there is no other -egroup  with and .

Pessimistic , . A tie-breaking belongs to if and only if it always selects some -egroup  such that and there is no other -egroup  with and .

### 3.3 Limits of Lexicographic Tie-Breaking

From the above discussion, we can conclude that lexicographic tie-breaking is straightforward in the case of scoring-based multiwinner voting rules. Basically any subset of the desired cardinality from the set of pending candidates can be chosen. In particular, the best pending candidates with respect to the given order can be chosen. We remark that applying lexicographic tie-breaking may be more complicated for general multiwinner voting rules.

It remains to be clarified whether one can find a reasonable order of the pending candidates in order to model optimistic or pessimistic tie-breaking rules in a simple way. We show that this is possible for every , , , using the fact that in these cases we can safely assume that there is only one non-zero valued utility function (see Observation 1). On the contrary, there is a counterexample for and . On the way to prove these claims we need to formally define what it means that one family of tie-breaking rules can be used to simulate another family of tie-breaking rules.

###### Definition 2.

Let  be a fixed set of candidates. Let  be a set of confirmed and be a set of pending candidates. Let  be a family of utility functions and be a size of an egroup. Consider some subset of the set . For two families  and  of tie-breaking rules we say that can -simulate if there are some rules  and such that and have the same output for all possible elections assuming all elements from together with set are fixed. We call rule  a -simulator.

At first glance Definition 2 might seem overcomplicated. However, it is tailored to grasp different degrees of simulation possibilities. On the one hand, one can always find a lexicographic order and use it for breaking ties if all: confirmed candidates, pending candidates, utility functions, and the size of an egroup are known. Thus, one needs some flexibility in the definition of simulation for it to be non-trivial. On the other hand, it is somewhat obvious that without fixing the utility functions, one cannot simulate optimistic or pessimistic tie-breaking rules. In other words, we have:

###### Observation 2.

Let and . The family of lexicographic tie-breaking rules does not -simulate .

Next, we show that for some cases it is sufficient to fix just the utility functions in order to simulate optimistic or pessimistic tie-breaking rules (see Proposition 1). For other cases, however, one has to fix all: confirmed candidates, pending candidates, utility functions, and the size of an egroup (see Proposition 2).

###### Proposition 1.

Let  be a set of candidates,  be a family of utility functions, , and . Let  and . Then the family of lexicographic tie-breaking rules  can -simulate , and a -simulator can be found in  time.

###### Proof.

Recall from Observation 1 that if , then there is always a set of utility functions with just one non-zero valued utility function  that is equivalent to . Hence, we compute such a function  in time as follows: In the utilitarian case, function assigns every candidate the sum of utilities the manipulators give to the candidate. Considering the candidate-wise egalitarian evaluation, function assigns every candidate the minimum utility value among utilities given to the candidate over all manipulators. We say an order  of the candidates is consistent with some utility function  if implies for optimistic tie-breaking and implies for pessimistic tie-breaking. Any lexicographic tie-breaking rule defined by an order  that is consistent with the utility function  simulates . We compute a consistent order by sorting the candidates according to  in time. ∎

Proposition 1 describes a strong feature of optimistic utilitarian and candidate-wise egalitarian tie-breaking and their pessimistic variants. Intuitively, the proposition says that for these tie-breaking mechanisms one can compute a respective linear order of candidates. Then one can forget all the details of the initial tie-breaking mechanism and use the order to determine winners. The order can be computed even without knowing the details of an election. Unfortunately, the simulation of pessimistic and optimistic egalitarian tie-breaking turns out to be more complicated.

###### Proposition 2.

Let  be a set of candidates,  be a family of utility functions, be a set of confirmed candidates, be a set of pending candidates, and be a size of an egroup. For each , , the lexicographic tie-breaking family of rules does not -simulate  assuming .

###### Proof.

From Observation 2 we already know that the family of lexicographic tie-breaking rules cannot -simulate the family of egalitarian pessimistic tie-breaking rules or the family of egalitarian optimistic tie-breaking rules.

Next, we build one counterexample for each of the remaining size-three subsets of  to show our theorem. To this end, let us fix a set of candidates (compatible with our running example) and a family of utility functions as depicted in the table below.

First, we prove that the family cannot -simulate  (i.e.,  is unfixed) for . Let us fix , . We consider the optimistic variant of egalitarian tie-breaking, so we are searching for the best possible -egroup. Looking at the values of , we see that candidate gives the best possible egalitarian evaluation value which is four. This means that a -simulator  has to use an order where precedes both and . However, it turns out that if we set , then the best -egroup consists exactly of candidates and . This leads to a contradiction because now candidates and should precede in ’s lexicographic order. Consequently, family  does not -simulate . Using the same values of utility functions and the same sequence of the values of we get a proof for the pessimistic variant of egalitarian evaluation.

Second, we prove that the family cannot -simulate  (i.e., set is unfixed) for . This time, we fix , . We construct the first case by setting . Using the fact that in both functions candidate has utility zero, we choose exactly the same candidate as in the proof of -simulation for the case ; that is, for the optimistic variant, the winning -egroup is and . Consequently, this leads to the fact that precedes and in the potential -simulator’s lexicographic order. Towards a contradiction, we set . The situation is exactly the same as in the proof of the -simulation case. Now, the winning -egroup consists of and which ends the proof for the optimistic case. By almost the same argument, the result holds for the pessimistic variant.

Finally, we prove that the family cannot -simulate  (i.e., set is unfixed) for . We fix , . For the first case we pick . The best egalitarian evaluation happens for the -egroup consisting of and . This imposes that, in the potential -simulator’s order, and  precede the remaining candidates (in particular, precedes ). However, for the best -egroup changes to that consisting of and which gives a contradiction ( precedes ). As in the previous cases, the same argument provides a proof for the pessimistic variant. ∎

Proposition 2 implies that pessimistic and optimistic egalitarian tie-breaking cannot be simulated without having full knowledge about an election. In terms of computational complexity, however, pessimistic egalitarian tie-breaking remains tractable whereas optimistic egalitarian tie-breaking is intractable. In the next section, among other things, we show that the egalitarian optimistic tie-breaking significantly differs from the egalitarian pessimistic tie-breaking with respect of hardness of computing winners.

## 4 Complexity of Tie-Breaking

It is natural to ask whether the tie-breaking rules proposed in Subsection 3.2 are practical in terms of their computational complexity. If not, then there is little hope for coalitional manipulation because tie-breaking is a subtask to be solved by the manipulators.

Clearly, we can apply every lexicographic tie-breaking rule that is defined through some predefined order of the candidates in linear time. Hence, we focus on the rules that model optimistic or pessimistic manipulators. To this end, we analyze the following computational problem.

-Tie-Breaking (-TB), ,
Input: A set of candidates  partitioned into a set  of pending candidates and a set  of confirmed candidates, the size  of the excellence-group such that , a family of manipulators’ utility functions where , and a non-negative, integral evaluation threshold .
Question: Is there a size- set such that  is selected according to , , and ?

Naturally, we may assume that the number of candidates and the number of utility functions are polynomially bounded in the size of the input. However, both the evaluation threshold and the utility function values are encoded in binary.

Note that an analogous problem has not been considered for single-winner elections since, for single-winner elections, optimistic and pessimistic tie-breaking rules can be easily simulated by straightforward lexicographic tie-breaking rules.

### 4.1 Utilitarian and Candidate-Wise Egalitarian: Tie-Breaking Is Easy

As a warm-up, we observe that tie-breaking can be applied and evaluated efficiently if the -egroups are evaluated according to the utilitarian or candidate-wise egalitarian variant. The corresponding result follows almost directly from Proposition 1.

###### Corollary 1.

Let denote the number of candidates and denote the number of manipulators. Then one can solve -Tie-Breaking in time for , .

###### Proof.

The algorithm works in two steps. First, compute a lexicographic tie-breaking rule  that simulates in time as described in Proposition 1. Second, apply tie-breaking rule , and evaluate the resulting -egroup in time. The running time of applying a lexicographic tie-breaking rule is linear with respect to the input length (see Subsection 3.3). ∎

### 4.2 Egalitarian: Being Optimistic Is Hard

In this subsection, we consider the optimistic and pessimistic tie-breaking rules when applied for searching a -egroup evaluated according to the egalitarian variant. First, we show that applying and evaluating egalitarian tie-breaking is computationally easy for pessimistic manipulators but computationally intractable for optimistic manipulators even if the size of the egroup is small. Being pessimistic, the main idea is to “guess” the manipulator that is least satisfied and select the candidates appropriately. We show the computational hardness of the optimistic case via a reduction from the -complete Set Cover problem parameterized by solution size (Downey and Fellows, 2013).

###### Theorem 1.

Let denote the number of candidates, denote the number of manipulators, denote the evaluation threshold, and denote the size of an egroup. Then one can solve -Tie-Breaking in time, but -Tie-Breaking is -hard and -hard when parameterized by  even if and every manipulator only gives either utility one or zero to each candidate.

###### Proof.

For the pessimistic case, it is sufficient to “guess” the least satisfied manipulator  by iterating through possibilities. Then, select the pending candidates with the smallest total utility for this manipulator in time. Finally, comparing the -egroup with the worst minimum satisfaction over all manipulators with the lower bound on satisfaction level given in the input solves the problem.

We prove the hardness for the optimistic case reducing from the -hard Set Cover problem which, given a collection of subsets of universe and an integer , asks whether there exists a family of size at most  such that . Let us fix an instance of Set Cover. To construct an -Tie-Breaking instance, we introduce pending candidates representing subsets in and manipulators representing elements of the universe. Note that there are no confirmed and rejected candidates. Each manipulator gives utility one to candidate  if set  contains element  and zero otherwise. We set the excellence-group size and the threshold  to be .

We observe that if there is a size- subset such that , then there exists a family —consisting of the sets represented by candidates in —such that each element of the universe belongs to the set . On the contrary, if we cannot pick a group of candidates of size for which every manipulator’s utility is at least one, then instance is a ‘no’ instance. This follows from the fact that for each size- subset there exists at least one manipulator for whom . This translates to the claim that there exists no size- subset such that all elements in  belong to the union of the sets in .

Since Set Cover is -hard and -hard with respect to parameter , we obtain that our problem is also -hard and -hard when parameterized by the size  of an excellence-group. ∎

Inspecting the -hardness proof of Theorem 1, we learn that a small egroup size (alone) does not make -Tie-Breaking computationally tractable even for very simple utility functions. Next, using a parameterized reduction from the -complete Multicolored Clique problem (Fellows et al., 2009), we show that there is still no hope for fixed-parameter tractability (under standard assumptions) even for the combined parameter “number of manipulators and egroup size”; intuitively, this parameter covers situations where few manipulators are going to influence an election for a small egroup.

###### Theorem 2.

Let denote the size of an egroup and denote the number of manipulators. Then, parameterized by , -Tie-Breaking is -hard.

###### Proof.

We describe a parameterized reduction from the -hard Multicolored Clique problem (Fellows et al., 2009). In this problem, given an undirected graph , a non-negative integer , and a vertex coloring , we ask whether graph  admits a colorful -clique, that is, a size- vertex subset  such that the vertices in are pairwise adjacent and have pairwise distinct colors. Without loss of generality, we assume that the number of vertices of each color is the same; to be referred as  in the following. Let , , be a Multicolored Clique instance. Let denote the set of vertices of color , and let , defined for , , denote the set of edges that connect a vertex of color  to a vertex of color .

Candidates. We create one confirmed candidate  and  pending candidates. More precisely: for each , we create one vertex candidate  for each vertex , and for each such that we create one edge candidate  for each edge  , . We set the size  of the egroup to and set the evaluation threshold . Next, we describe the manipulators and explain the high-level idea of the construction.

Manipulators and main idea. Our construction will ensure that there is a -egroup  with and if and only if  contains  vertex candidates and  edge candidates that encode a colorful -clique. To this end, we introduce the following manipulators.

1. For each color , there is a color manipulator  ensuring that the -egroup contains a vertex candidate  corresponding to a vertex of color . Herein, variable  denotes the id of the vertex candidate (resp. vertex) that is selected for color .

2. For each such that , there is one color pair manipulator  ensuring that the -egroup contains an edge candidate  corresponding to an edge connecting vertices of colors and . Herein, variable  denotes the id of the edge candidate (resp. edge) that is selected for color pair , .

3. For each such that , there are two verification manipulators , ensuring that vertex  is incident to edge  if or incident to edge  otherwise.

If there exists a -egroup in agreement with the description in the previous three points, then this -egroup must encode a colorful -clique.

Utility functions. Let us now describe how we can guarantee correct roles of the manipulators introduced in points 1 to 3 above using utility functions.

1. Color manipulator , , has utility  for the confirmed candidate , utility one for each candidate corresponding to a vertex of color , and utility zero for the remaining candidates.

2. Color pair manipulator , , , has utility  for the confirmed candidate , utility one for each candidate corresponding to an edge connecting a vertices of colors and , and utility zero for the remaining candidates.

3. Verification manipulator , , , has utility  for candidate , , utility  for each candidate corresponding to an edge that connects vertex to a vertex of color , and utility zero for the remaining candidates.

4. Verification manipulator , , , has utility  for candidate , , utility  for each candidate corresponding to an edge that connects vertex , to a vertex of color , and utility zero for the remaining candidates.

Correctness. We argue that the graph admits a colorful clique of size if and only if there is a -egroup  with and .

Suppose that there exists a colorful clique  of size . Create the -egroup  as follows. Start with  and add every vertex candidate that corresponds to some vertex of  and every edge candidate that corresponds to some edge of . Each color manipulator and color pair manipulator receives total utility , because  contains, by definition, one vertex of each color and one edge connecting two vertices for each color pair. It is easy to verify that the verification manipulator  must receive utility  from a vertex candidate and utility  from an edge candidate and that the verification manipulator  must receive utility  from a vertex candidate and utility  from an edge candidate. Thus, .

Suppose that there exists a -egroup  such that . Since each color manipulator cannot achieve utility unless belongs to the winning -egroup, it follows that . Because each color manipulator  receives total utility at least , must contain some vertex candidate  corresponding to a vertex of color  for some . We say that  selects vertex . Since each color pair manipulator  receives total utility at least , must contain some edge candidate  corresponding to an edge connecting a vertex of color  and a vertex of color  for some . We say that  selects edge . We implicitly assumed that each color manipulator and color pair manipulator contributes exactly one selected candidate to . This assumption is true because there are exactly such manipulators and each needs to select at least one candidate; hence,  is exactly of the desired size. In order to show that the corresponding vertices and edges encode a colorful -clique, it remains to show that no selected edge is incident to a vertex that is not selected. Assume towards a contradiction that  selects an edge and some vertex . However, either verification manipulator  or verification manipulator  receives the total utility at most ; a contradiction. ∎

Finally, devising an ILP formulation, we show that -Tie-Breaking becomes fixed-parameter tractable when parameterized by the combined parameter “number of manipulators and number of different utility values”. This parameter covers situations with few manipulators that have simple utility functions; in particular, when few voters have utility functions. Together with Theorem 1 and Theorem 2, following Theorem 3 shows that neither few manipulators nor few utility functions make -TB fixed-parameter tractable, but only combining these two parameters allows us to deal with the problem in time.

###### Theorem 3.

Let denote the number of different utility values and  denote the number of manipulators. Then, parameterized by , -Tie-Breaking is fixed-parameter tractable.

###### Proof.

We define the type of any candidate to be the size-vector . Let be the set of all possible types. Naturally, the size of is upper-bounded by . We denote the set of candidates of type  by . Now, the ILP formulation of the problem using exactly variables reads as follows. For each type , we introduce variable indicating the number of candidates of type in an optimal -egroup. We use variable to represent the minimal value of the total utility achieved by manipulators. We define the following ILP with the goal to maximize (indicating the utility gained by the least satisfied manipulator) subject to:

 ∀ti∈T: xi≤|Ti|, (1) ∑ti∈Txi=k, (2) ∀ℓ∈[r]: ∑ti∈Txi⋅ti[ℓ]≥s. (3)

Constraint set (1) ensures that the solution is achievable with given candidates. Constraint (2) guarantees a choice of an egroup of size . The last set of constraints imposes that holds at most the minimal value of the total utility gained by manipulators. By a famous result of Lenstra (1983), this ILP formulation with the number of variables bounded by yields that -Tie-Breaking is fixed-parameter tractable when parameterized by the combined parameter . ∎

## 5 Complexity of Coalitional Manipulation

In the previous section, we have seen that breaking ties optimistically or pessimistically—an essential subtask to be solved by the manipulators—can be computationally challenging; in most cases, however, this problem turned out to be computationally easy. In this section, we move on to our full framework and analyze the computational difficulty of voting strategically for a coalition of manipulators. To this end, we formalize our central computational problem. Let  be a multiwinner voting rule and let  be a multiwinner tie-breaking rule.

---Coalitional Manipulation (---CM),
Input: An election , a searched egroup size , manipulators represented by their utility functions such that , and a non-negative, integral evaluation threshold .
Question: Is there a size- multiset  of manipulative votes over  such that -egroup wins the election under and , and ?

The ---CM problem is defined very generally; namely, one can consider any multiwinner voting rule (in particular, any single-winner voting rule is a multiwinner voting rule with ). In our paper, however, we focus on -Bloc; hence, from now on, we narrow down our analysis of ---CM to the ---CM problem.

As a step on the way to show our results we also use a restricted version of ---Coalitional Manipulation that we call ---Coalitional Manipulation with consistent manipulators. In this variant, the input stays the same, but all manipulators cast exactly the same vote to achieve the objective.

To increase readability, we decided to represent manipulators by their utility functions. As a consequence, we frequently use, for example, referring to the manipulator itself, even if we do not care about the values of utility function

at the moment of usage. In the paper, we also stick to the term “voters” meaning the set

of voters of an input election. We never call manipulators “voters”; however, we speak about the manipulative votes they cast.

As for the encoding of the input of ---CM, we use a standard assumption; namely, that the number of candidates, the number of voters, and the number manipulators are polynomially upper-bounded in the size of the input. Analogously to -Tie-Breaking, both the evaluation threshold and the utility function values are encoded in binary.

### 5.1 Utilitarian and Candidate-Wise Egalitarian: Manipulation Is Tractable

We show that ---Coalitional Manipulation can be solved in polynomial time for any constant , any , and any .

For Bloc (i.e., ), we give a quadratic-time algorithm with respect to the size of the input. We start with an algorithm for ---CM with consistent manipulators and show that this algorithm solves also Bloc---CM. The algorithm “guesses” the minimum score among all members of the winning egroup and then carefully (with respect to the tie-breaking method) selects the best candidates that can reach this score.

In several proofs in Subsection 5.1 we use the value of a candidate for manipulators (coalition) and say that a candidate is more valuable or less valuable than another candidate. Although we cannot directly measure the value of a candidate for the whole manipulators’ coalition in general, thanks to Observation 1, we can assume a single non-zero utility function when discussing the utilitarian and candidate-wise egalitarian variants. Thus, assigning a single value to each candidate is justified.

###### Proposition 3.

Let denote the number of candidates, denote the number of voters, and denote the number of manipulators. Then one can solve ---Coalitional Manipulation with consistent manipulators in time for any and .

###### Proof.

Consider an instance of ---CM with consistent manipulators with an election where is a candidate set and is a multiset of non-manipulative votes,  manipulators, an egroup size , and a lexicographic order used by to break ties. In essence, we introduce a constrained solution form called a canonical solution and argue that it is sufficient to analyze only this type of solutions. Then we provide an algorithm that efficiently seeks for an optimal canonical solution.

At the beginning, we observe that when manipulators vote consistently, then we can arrange the top candidates of a manipulative vote in any order. Hence, the solution to our problem is a size- subset (instead of an order) of candidates which we call a set of supported candidates; we call each member of this set a supported candidate.

Strength order of the candidates. Additionally, we introduce a new order of the candidates. It sorts them descendingly with respect to the score they receive from voters and, as a second criterion, according to the position in . Intuitively, the easier it is for some candidate to be a part of a winning -egroup, the higher is the candidate’s position in . As a consequence, we state Claim 1.

###### Claim 1.

Let us fix an instance of ---CM with consistent manipulators and a solution which leads to a winning -egroup . For every supported (resp. unsupported) candidate , the following holds:

• If is part of the winning -egroup, then every supported (resp. unsupported) predecessor of , according to , belongs to .

• If is not part of the winning -egroup, then every supported (resp. unsupported) successor of , according to , does not belong to .

Claim 1 justifies thinking about as a “strength order”; hence, in the proof we use the terms stronger and weaker candidate. Using Claim 1, we can fix some candidate as the weakest in the winning -egroup and then infer candidates that have to be and that cannot be part of this -egroup. To formalize this idea, we introduce the concept of a canonical solution.

Canonical solutions. Assuming the case where , we call a solution leading to a winning -egroup  canonical if all candidates of the winning egroup are supported; that is, . In the opposite case, , solution is canonical if and is a set of the weakest candidates in . For the latter case, the formulation describes the solution which favors supporting weaker candidates first and ensures that no approval is given to a candidate outside the winning -egroup.

Canonical solutions are achievable from every solution without changing the outcome. Observe that one cannot prevent a candidate from winning by supporting the candidate more because this only increases the candidate’s score. Consequently, we can always transfer approvals to all candidates from the winning -egroup. For the case of , we then have to rearrange the approvals in such a way that only the weakest members of the -egroup are supported. However, such a rearrangement cannot change the outcome because, according to Claim 1, we can transfer an approval from some stronger candidate to weaker keeping both of them in the winning -egroup.

Dropped and kept candidates. Observe that for every solution (including canonical solutions), we can always find the strongest candidate who is not part of the winning egroup. We call this candidate the dropped candidate. Note that we use the strength order in the definition of the dropped candidate; this order does not take manipulative votes into account. Moreover, without loss of generality, we can assume that the dropped candidate is not a supported candidate. This is because if the dropped candidate is not in the winning -egroup even if supported, then we can support any other candidate outside of the winning -egroup without changing the winning -egroup (see Claim 1). There always exists some candidate to whom we can transfer our support because . Naturally, by definition of the dropped candidate, all candidates stronger than the dropped candidate are members of the winning -egroup. We call these candidates kept candidates.

High-level description of the algorithm. The algorithm solving ---CM with consistent manipulators iteratively looks for an optimal canonical solution for every possible (non-negative) number of kept candidates (alternatively the algorithm checks all feasible possibilities of choosing the dropped candidate). Observe that . The upper bound  is the consequence of the fact that each kept candidate is (by definition) in the winning -egroup. Since all candidates except for kept candidates have to be supported to be part of the winning egroup, we need at least kept candidates, in order to be able to complete the -egroup.

Running time. To analyze the running time of the algorithm described in the previous paragraph, several steps need to be considered. At the beginning we have to compute values of candidates and then sort the candidates with respect to their value. This step runs in time. Similarly, computing  takes time. Having both orders, Procedure 1 (described in detail later in this proof) needs to find an optimal canonical solution for some fixed number of kept candidates. Finally, we have at most possible values of . Summing the times up, together with the fact that , we obtain a running time .

What remains to be done. Procedure 1 describes how to look for an optimal canonical solution for a fixed number of kept candidates. First, partition the candidate set in the following way. By we denote the kept candidates (which are the top candidates according to ). Consequently, the -st strongest candidate is the dropped candidate; say . For every value of , the corresponding dropped candidate, by definition, is not allowed to be part of the winning egroup. Let

 D={C*∪{c∗}∌c∣(scoreV(c)+r>scoreV(c∗))∨(scoreV(c)+r=scoreV(c∗)∧c>Fc∗)}

be the set of distinguished candidates. Each distinguished candidate, if supported, is preferred over to be selected into the winning -egroup. Consequently, the distinguished candidates are all candidates who can potentially be part of the winning -egroup. We remark that to fulfil our assumption that the dropped candidate is not part of a winning egroup, it is obligatory to support at least distinguished candidates. Note that is not necessarily equal to . The remaining candidates cannot be a part of the winning -egroup under any circumstances assuming kept candidates. Making use of the described division into , , and , Procedure 1 incrementally builds set  of supported candidates associated with an optimal solution until all possible approvals are used.

Detailed description of the algorithm. Before studying Procedure 1 in detail, consider Figure 1 illustrating the procedure on example data. In line 1, the procedure builds set  of supported candidates using the best valued distinguished candidates. Since only the distinguished candidates might be a part of the winning -egroup besides the kept candidates, there is no better outcome achievable. Then, in line 1, the remaining approvals, if they exist, are used to support secured candidates. This operation does not change the resulting -egroup. Then Procedure 1 checks whether all approvals were used; that is, whether . If not, then there are exactly remaining approvals to use. Note that at this stage set contains supported candidates who correspond to the best possible -egroup, however, without spending all approvals. Let us call this -egroup . It is possible that there is no way to spend the remaining approvals without changing the winning -egroup . Then substitutions of candidates occur. The new candidates in the -egroup can be only those that are distinguished and so far unsupported whereas the exchanged ones can be only so far supported distinguished candidates. This means that each substitution lowers the overall value of the winning -egroup. So, the best what can be achieved is to find the minimal number of substitutions and then pick the most valuable remaining candidates from to be substituted. The minimal number of substitutions can be found by analyzing how many candidates would be exchanged in the winning -egroup if the weakest previously unsupported candidates were supported. The procedure makes such a simulation and computes the number  of necessary substitutions, in lines 1-1. Supporting the weakest unsupported candidates and then the most valuable so far unsupported distinguished candidates gives the optimal -egroup for  kept candidates (when all approvals are spent). Note that the number of approvals is strictly lower than the number of candidates, so one always avoids supporting .


text:
# Ten \$10s make \$100

Alignments to Content Standards: 2.NBT.A.1

1. How many ten-dollar bills equal a hundred-dollar bill?
2. Jem had 20 ten-dollar bills. How many hundred-dollar bills can she trade them for?
3. Dan had 6 hundred-dollar bills. How many ten-dollar bills can he trade them for?

## IM Commentary

People often use pennies, dimes, and dollars as a context for thinking about bundling by ten. However, using one, ten, and one-hundred dollar bills is easier for students to understand initially because the names of the bundles match the names of the numbers. While dimes are bundles of ten pennies and dollars are bundles of ten dimes, the translation between base-ten numbers and pennies, dimes, and dollars is more complex because of the name differences. Furthermore, there is the potential for confusion since a penny can be thought of as both 1/100 of a dollar and as 1 cent. As a result students may require more support from the teacher to understand contexts involving e.g. dimes and dollars than they would for this task context.

## Solution

1. 10 ten-dollar bills equal 1 hundred-dollar bill.
2. Jem can trade 20 ten-dollar bills for 2 hundred-dollar bills.
3. Dan can trade 6 hundred-dollar bills for 60 ten-dollar bills.


text:
# Define functions

I want to know how to define functions. I dont mean a function in the sense f[x_]:=x^2 for example, but I mean a function which takes parameters and returns something. Like in C++, you can define such a function as

int function(int parameter){
//do something
return something;
}

and then in the main function we can call this function. How can we do something like this in Mathematica? If I look for function on google, all I get is the function in the sense f[x_]:=x^2.

Edit:

I want to do the following for example. I want the input and output to be polynomials in some variables, and the function is a differential operator. For example, $p(x_1,...,x_n)=x_1^2+...+x_n^2$ and the differential operator is for example $\sum_{i=1}^nx_{n+1-i}\partial x_i$ where $\partial x_i$ takes the derivative of the polynomial with respect to $x_i$.

• f[x_] := x^2 takes one parameter and returns one result. In this respect it behaves just like the C function you showed. I don't understand your question. Perhaps read through this: reference.wolfram.com/language/tutorial/… – Szabolcs Oct 28 '16 at 13:34

Working out the example from the edit:

expr = x1^2 + x2^2 + x3^2 + x4^2 + x5^2;

Extract the variables:

var = Variables @ expr

{x1, x2, x3, x4, x5}

Then compute the sum:

Sum[var[[Length @ var + 1 - i]] D[expr, var[[i]]], {i, 1, Length @ var}]

2 x3^2 + 4 x2 x4 + 4 x1 x5

Those intermediate steps can be gathered into a single function:

operator[input_] := Block[{var},
var = Variables @ input;
Sum[var[[Length @ var + 1 - i]] D[input, var[[i]]], {i, 1, Length @ var}]
]

operator[expr]

2 x3^2 + 4 x2 x4 + 4 x1 x5

In case of expressions like

a x1^2 + x2^2 + b x3^2 + 2 x4^2 + c x5^2

also a, b, c will be treated as variables by Variables. If some symbols are to be treated as parameters, it's probably simplest and safest to manually set which symbols are variables and which are not, like in Sumit's answer below. Also, Variables works well on polynomials, but fails e.g. with this:

Variables @ Sin[x]

{Sin[x]}

• In the function operator[input_] in the second line you write var = Variables @ expr; Dont you have to replace expr with input? Because I want also to input other polynomials – Badshah Oct 28 '16 at 13:39
• Yup, good call. Edited. – corey979 Oct 28 '16 at 13:41
• I have one more question: I made a table of all the variables I am working with, it is a little different than in the example above. I have variables $p_{i,j}$ where $i$ and $j$ run through some index. I used vars = Table[Subscript[p, i, j], {i, 1, 7}, {j, 1, 3}] to define these variables in a table. How can I use these variables in the Block? I couldnt adjust your code to work with variables in a table. In this case I would have differential operator which is written as a double sum over $i$ and $j$. – Badshah Oct 28 '16 at 16:15

Something like this

func[poly_, var__] := Module[{n}, n = Length[var];
Sum[var[[n + 1 - i]] D[poly, var[[i]]], {i, 1, n}]]

func[a x1^2 + b x2^3, {x1, x2}]

2 a x1 x2 + 3 b x1 x2^2


text:
Forward covariate search

forwardSearch(covInfo, fit, pVal = 0.05, outputDir, restart = FALSE)

## Arguments

covInfo a list containing information about each variable-covariate pair an nlmixr 'fit' object p-value that should be used for selecting covariates in the forward search the name of the output directory that stores the covariate search result a boolean that controls if the search should be restarted; default is FALSE

## Value

returns the updated 'fit' object at the end of the forward search and a table of information for all the covaraites tested

## Author

Vipul Mann, Matthew Fidler


text:
What is the time complexity of this algorithm?

In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed:

She represented the cost of the algorithm by the following sum:

$\sum\limits_{i=1}^n \sum\limits_{j=1}^i\sum\limits_{k=1}^j 3 = \frac{n^3}{2} + \frac{3n^2}{2} + n$

The step by step used to solve the sum bellow:

n = 10
count=0
for i in range (0, n):
for j in range (0, i):
for k in range (0, j):
count+=3

print count

Then, I wrote a algorithm in python to verify the solution, but it not produce the expected output, for example, for n = 10 we expected 660 operations, but it print 360.

Change the index to start with 1 like in the bellow didn't worked either, in fact it got more distance from the expected (252).

n = 10
count=0
for i in range (1, n):
for j in range (1, i):
for k in range (1, j):
count+=3

print count

• You cannot expect 860 operations, as 860 is not divisible by 3. Running loops as intended gives $count = 858$. – Evil Apr 24 '16 at 0:49
• @EvilJS Sorry, the 860 is a typo it should be 660. Where did you find the 858 ? – Guilherme Torres Castro Apr 24 '16 at 1:05
• Very easy, I just executed your triple loop and got result - it was before the edit. From 0 to n inclusively. And without the last element it was 360. Now when you changed the code, if you do $count += 3$ it is not the same as sum of $i, j, k$ indices on every iteration. Please look at D.W. answer and comment, if you got result somehow, but describe it differently in pseudocode, differently in python and MathJax it is the most probable place of error. – Evil Apr 24 '16 at 1:59
• @EvilJS My mistake, the only operation we should count is the sum in the most deep loop. Even so you are able produce 858 as output, or did you count the for operations ? Perdon my ignorance, but can you elabore a little more how you got the 858 ? – Guilherme Torres Castro Apr 24 '16 at 2:17
• I'm going to repeat my comment. How exactly did you get 360? You said you wrote an algorithm in Python, but you don't show us the Python; one possible error is that you wrote the Python wrong. How have you ruled that out? Note that your pseudocode at the top of the question does not match the Python at the bottom. – D.W. Apr 24 '16 at 2:24

Now, you need to make index reach n, rather than go just up to it,
so instead of range(1,n), it should be range(1,m) for some m such that  n < m .
To avoid n+1, one also needs  m ≤ n+1 .    Combining those gives  n < m ≤ n+1 .
The simplest such m is obviously  m = n+1 ,  so your initial range should be range(1,n+1).

In Python, range(0,n) iterates through the values 0, 1, 2, .., n-1 (but not n). Therefore, your summation should have been

$$\sum_{i=0}^{n-1} \cdots$$

rather than

$$\sum_{i=1}^{n} \cdots$$

and similarly for the other sums as well.

• 0 to n-1 and 1 to n are not equivalent? Anyway change the ranges to 1 to n-1 did not work either. – Guilherme Torres Castro Apr 24 '16 at 0:59
• Just to clarify the original program is not written is python is a PseudoCode with i <- 1 to n do. What's bother me is even if a change the program range (1 to n) it will no produce the expected output. – Guilherme Torres Castro Apr 24 '16 at 1:01
• @GuilhermeTorresCastro, rather than posting comments, I suspect you need to edit your question. I can only go by what's in the question; I can't read your mind. Your question says "Looking at this algorithm write in python".... If you say it's in Python, we'll take you at your word. If it's not written in Python, you need to edit the post to define your notation (e.g., what you mean by range), and tell us exactly how you measured how many operations were performed (not the calculations; but how did you run the algorithm and get 360?). – D.W. Apr 24 '16 at 1:40
• Ok, thanks for you suggestion I update the question with the real problem. – Guilherme Torres Castro Apr 24 '16 at 1:56

Your teacher was incorrect in thinking that a triple summation of i + j + k (in Python, temp += i + j + k) equals a triple of summation of 1 + 1 + 1 (in Python, temp += 1 + 1 + 1 or temp += 3). See my step-by-step work attached at bottom.

The triple summation of 1 + 1 + 1, i.e. incrementing by 3, over k from 1 to j, j from 1 to i, and i from 1 to n, equals (n3 + 3*n2 + 2*n) / 2. For n = 10, for instance, 1320/2 = 660. Simple Python 3 code confirms this math.

In Python 3, n = 10 count=0 for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+=3 print(count) 660

The more intricate summation of (i + j + k) over k from 1 to j, j from 1 to i, and i from 1 to n, equals (n4 + 4*n3 + 5*n**2 + 2*n) / 4, which is exactly (n+1)/2 times the previous sum. Can you deduce why? Because, on average, the quantities i, j, and k will be halfway between 1 and n. For n = 10, for instance, 14520/4 = 3630. Again, Python 3 code that increments count += i + j + k confirms this result at n = 10.

n = 10 count=0 for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+= i + j + k print(count) 3630

• Please refrain from posting mathematical formulae as images (and especially in wrong orientation). This site provides full LaTeX support. – dkaeae Jan 3 at 15:57

Your implementation does not match the algorithm written in the pseudo-code. In the pseudo-code:  for i ← 1 to n do  means i could take n values from 1 to n. for simple, let's consider the last iteration, namely i=n. Then consider the second loop:  for j ← 1 to j do  could be reduced to:  for j ← 1 to n do  That's to say, j could also take n values from 1 to n. But for your implementation in python,  for i in range (0, n)  i could take n values from 0 to n-1. Let's also consider the last iteration, namely i=n-1. Unfortunately, for the second loop:  for j in range (0, n-1)  here j can only take n-1 values from 0 to n-2. Obviously mismatched to the original algorithm. Two ways to solve your problem:

Index start from 1 and use LCRC rule:
 for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+=3  or start from index 0, but use LCRC rule for all inner loops:
 for i in range (0, n): for j in range (0, i+1): for k in range (0, j+1): count+=3  The first one is preferred as it exactly match the algorithm. But the second one could let you clearly understand the difference between the outer loop and inner loops.


text:
# “When to take medicine” CodeChef Challenge MEDIC

I just submitted this code to solve the "When to take medicine" challenge on CodeChef:

#include <iostream>
#include <string>
#include <sstream>

int countDays(int dd, int subtract)
{
return ((subtract - dd) / 2) + 1;
}

int main()
{
int t {0};
std::cin >> t;
std::cin.ignore();
while (t--)
{
std::string date {};
std::getline(std::cin, date);
std::stringstream ss {date};
int yy {0}, mm {0}, dd {0};
std::string temp {};
std::getline(ss, temp, ':');
yy = std::stoi(temp);
std::getline(ss, temp, ':');
mm = std::stoi(temp);
std::getline(ss, temp, ':');
dd = std::stoi(temp);
int subtract {0};
bool leap {false};
if (yy % 4 == 0 && (!(yy % 100 == 0) || yy % 400 == 0))
leap = true;
switch (mm)
{
case 2:
if (leap)
subtract = 29;
else
subtract = 59;
break;
case 4: case 6: case 9: case 11:
subtract = 61;
break;
default:
subtract = 31;
}
std::cout << countDays(dd, subtract) <<'\n';
}
}

In short, it is a program to tell how many days a guy has took his pill correctly, considering that he has to take a pill every 2 days and only takes it in odd or even days, depending on the day he started to take the pill. We provide a number of test cases in the first line and then we provide a date in a single line in the format yyyy:mm:dd. Check the link above if you're interested in reading the whole problem.

The thing is that I am not really satisfied with the way I am parsing the string separated by the char :

I also want to mention that I want to stay away from any C code like the scanf() function. It would make things a lot easier, but I don't want to use C in C++.

So, how could I redesign my string parse code to make it look nicer? I am just a newbie with C++ so all feedback / criticism is greatly appreciated.

1. You don't check whether the input is invalid.

2. Try to extract useful well-named functions, like int days(int month, int year) and bool is_leap_year(int year).

3. You can extract the numbers directly from std::cin, the colon will be left behind.
And the colon can thereafter be extracted like any other single character.

4. As an aside, using scanf() would probably be easier than juggling streams.

5. break should be indented like any other Statement. It does not deserve more indentation (first occurrence), nor less (second occurrence).

• 1, 2, 3 - all good tips! – msmilkshake Jul 11 at 7:25
• 4 - I just wanted to avoid using C code. – msmilkshake Jul 11 at 7:25
• 5 - I think that indentation was a copy / paste mistake. Overall, thanks for your review! – msmilkshake Jul 11 at 7:26
• Re 4: There are projects doing their best to mate the usability of format-string driven printf/scanf with the safety, flexibility and potential performance of templates. It's just that this code shows <iostream> at its most cumbersome. – Deduplicator Jul 11 at 15:06

It might be overkill for just the task at hand, but I've found it useful to write an overload of operator>> to read and match a string literal:

std::istream &operator>>(std::istream &is, char const *s) {
while (*s && *s == is.peek()) {
++s;
is.ignore(1);
}
if (*s != '\0')
is.setstate(std::ios_base::failbit);
return is;
}

With this, reading in your data becomes much simpler, and (at least IMO) the intent becomes much more apparent:

int yy;
int mm;
int dd;

std::cin >> yy >> ":" >> mm >> ":" >> dd;

Depending on what you want/need, you can make this a bit more elaborate. For one example, it can be useful to have the literals act a little like scanf format strings, so any white space in the string matches an arbitrary amount of white space in the stream. You might also want to turn that behavior on/off, depending on whether the stream's skipws flag is set.

• What does the *s && *s mean? Not null? – msmilkshake Jul 11 at 7:29
• @msmilkshake: You have to look at the whole thing: *s && *s == is.peek(). The first *s is equivalent to *s != 0, so with a C-style string, it means "we haven't reached the end of the string yet". the second part is *s == is.peek(), which means the character in the string passed matches with the next character to be read from the stream. – Jerry Coffin Jul 11 at 7:46
• oh yea, operator precedence. i was not considdering it lol. – msmilkshake Jul 11 at 9:51