text:
Inventory Allocation for Online Graphical Display Advertising
Abstract

We discuss a multi-objective/goal programming model for the allocation of inventory of graphical advertisements. The model considers two types of campaigns: guaranteed delivery (GD), which are sold months in advance, and non-guaranteed delivery (NGD), which are sold using real-time auctions. We investigate various advertiser and publisher objectives such as (a) revenue from the sale of impressions, clicks and conversions, (b) future revenue from the sale of NGD inventory, and (c) “fairness” of allocation. While the first two objectives are monetary, the third is not. This combination of demand types and objectives leads to potentially many variations of our model, which we delineate and evaluate. Our experimental results, which are based on optimization runs using real data sets, demonstrate the effectiveness and flexibility of the proposed model.

TECHNICAL REPORT

YL-2010-004

Inventory Allocation for Online Graphical Display Advertising

Jian Yang             Erik Vee       Sergei Vassilvitskii       John Tomlin

Jayavel Shanmugasundaram       Tasos Anastasakos

Yahoo! Labs

701 First Ave

Sunnyvale, CA 94089

{ jianyang, erikvee, sergei, tomlin, jaishan, tasos}@yahoo-inc.com

Oliver Kennedy

Computer Science Department

Cornell University

Ithaca, NY 14840

okennedy@cs.cornell.edu

Bangalore Barcelona Haifa Montreal New York Santiago Silicon Valley

Inventory Allocation for Online Graphical Display Advertising

Jian Yang             Erik Vee       Sergei Vassilvitskii       John Tomlin

Jayavel Shanmugasundaram       Tasos Anastasakos

Yahoo! Labs

701 First Ave

Sunnyvale, CA 94089

{ jianyang, erikvee, sergei, tomlin, jaishan, tasos}@yahoo-inc.com

Oliver Kennedy

Computer Science Department

Cornell University

Ithaca, NY 14840

okennedy@cs.cornell.edu

1 Introduction

As with most forms of online advertising [7], one of the central questions that arises in the context of online graphical display advertising is that of inventory allocation, i.e., determining how to allocate supply/inventory (user visits) to demand (advertiser campaigns) so as to optimize for various publisher and advertiser objectives. However, even formulating the inventory allocation problem for online graphical display advertising is quite challenging, for two reasons.

1.1 Contributions

Given the aforementioned unique requirements for online graphical display advertising, one of the main technical contributions of this paper is an inventory allocation optimization model that can capture these requirements. At a high-level, the proposed allocation model represents forecasts of future inventory (user visits) and guaranteed advertiser campaigns as nodes in a bipartite graph. Each edge of the bipartite graph connects a user visit to an eligible guaranteed advertiser campaign. In addition, each user visit is annotated with a forecast of the highest bid fetched on the non-guaranteed marketplace and a forecast of the expected pay-out. Similarly, each edge of the graph is annotated with a forecast of the click or conversion probability for the advertiser campaign and the specific user visit.

Given the previous model, the objectives for online graphical display advertising are captured as follows. There are two parts to the objective function: one that captures guaranteed campaigns, and the other that captures non-guaranteed campaigns. The objective for the latter is simply to maximize the revenue for the publisher, since advertisers only bid for what the user visit is worth to them. The objective for the guaranteed campaigns, on the other hand, is more complex because advertisers could be interested in brand awareness, or performance, or both. Furthermore, the publisher faces penalties for under-delivering – that is displaying an advertisement to fewer users than agreed on.

In our model, delivery guarantees are treated as feasibility constraints. (If the instance is infeasible, we trim the demand to find the feasible solution with the minimum under-delivery penalties.) The objective for guaranteed contracts has two parts. The brand awareness objective is captured in terms of “representativeness” (see [15]), which tries to maximize the reach of the guaranteed campaign by uniformly distributing the contracts among the user visits to the extent possible 111Reach can also be specified in terms of users as opposed to user visits (as above) by using user cookie information, but we do not elaborate on this extension here. The performance objectives for guaranteed campaigns are captured as the expected pay-out, i.e., the probability of clicks and conversions, times the value of each click and conversion.

Consequently, the final allocation objective has three parts: non-guaranteed revenue, guaranteed representativeness, and guaranteed clicks/conversions. While multi-objective programming has been a standard technique for some time, previous optimization models for online advertising (see e.g. [17, 18]) have used a single objective function. One of our major contributions is to use the multi-objective optimization framework [24] to model the sometimes conflicting objectives in a rigorous way.

While the multi-objective optimization model described above captures the various objectives, it also introduces a new set of challenges both in terms of operability and in terms of computational feasibility. Specifically, with regard to operability, the question that arises is: how do we trade-off between the various objectives (such as representativeness and non-guaranteed revenue), which do not even have the same units? With regard to computational feasibility, the question that arises is: how do we solve a multi-objective formulation efficiently over large volumes of data (tens of billions of user visits per day and hundreds of thousands of advertiser campaigns per year)? Another key technical contribution of this paper is a method that enables operators of the system to trade-off between multiple objectives based on the monetary unit of a single objective. For instance, an operator can trade-off representativeness in terms of the impact it has on non-guaranteed revenue, which is expressed in monetary units. A significant advantage of this method is that it also allows for an efficient solution, which can be solved on a small sample of the original bipartite graph, without significantly compromising accuracy.

We note that there are two other closely related topics that impact inventory allocation: pricing and ad serving. While the details of these methods are beyond the scope of this paper, the proposed allocation method works with quite general pricing and ad serving techniques. Specifically, in terms of pricing, we assume that guaranteed campaigns are priced using some external method (which may itself use forecasts of non-guaranteed bids to ensure appropriate prices), and the inventory allocation model can work with the booked prices without regards to how exactly the prices were computed. Similarly, we assume that we have some forecast of non-guaranteed bids, but do not make any assumptions on how the bids by themselves are generated by individual campaigns. In terms of ad serving, the allocation model produces both a primal and dual solution, the latter of which can be stored compactly and interpreted by the ad server to serve ads to user visits in an online, real-time manner (e.g., see  [10, 26]).

We have implemented the proposed inventory allocation model and the solution techniques, motivated by the context of an operational online graphical display advertising system. Our results using real user visits, guaranteed campaigns, non-guaranteed bids, and click/conversion data, indicate that the proposed approach is both versatile in capturing and trading off between various advertiser and publisher objectives, as well as efficient to solve with high accuracy.

In summary, the main contributions of this paper are:

• A formalization of the inventory allocation model and objectives for online graphical display advertising (Section 2).

• A multi-objective optimization formulation and various solution techniques for optimizing the multiple objectives (Section 3).

• An experimental evaluation of the proposed techniques using real data sets (Section 4).

2 Model and Objectives

We begin by first defining some notation, and then motivating and formalizing the various objectives in online graphical display advertising.

2.1 Supply and Demand Model

As mentioned earlier, the main goal of inventory allocation is to match supply (user visits) and demand (advertising campaigns). We thus begin by modeling user visits, advertising campaigns, and their interaction.

User visits can be represented as attributes-value pairs, where the attributes represent the properties of a user, the properties of the page they visit, as well as the time stamp of the visit. An example user visit could be represented as: Gender = Male, AgeGroup = 30-40, Interests = {Sports, Finance}, Location = California, …, PageCategory = {Sports}, …, Day = 15 Jan 2011, Time = 12:35pm GMT.

A display advertising campaign targets a subset of user visits by specifying a targeting predicate. For instance, an advertising campaign that targets Males in California visiting Sports pages in the month of Jan 2011 can be represented as: Gender {Male} Location {California} PageCategory {Sports} Duration [1 Jan 2011 - 31 Jan 2011]. A user visit is said to be eligible for an advertising campaign if the attribute-value pairs of the user visit satisfy the targeting predicate of the advertising campaign. In the rest of this paper, we will focus on just the eligibility relationship between user visits and advertising campaigns, and not on the specific attribute-value pairs or the targeting predicates.

Advertising campaigns can be of two types: guaranteed campaigns, whereby the publisher guarantees a fixed number of user visits to an advertiser in advance, and non-guaranteed campaigns, where advertisers bid in real-time for user visits. Both guaranteed and non-guaranteed campaigns can have one or more advertiser goals: to obtain user visits (this is the only goal that is guaranteed in a guaranteed campaign), to obtain clicks, and/or to obtain conversions. In non-guaranteed campaigns, however, these objectives are converted into a bid by a bidding agent and thus, for the purpose of modeling, they can be represented as a bid for each user visit. Guaranteed campaigns, on the other hand, need to be modeled in more detail. Specifically, a guaranteed campaign has a user visit goal (the guarantee), a penalty function that specifies the penalty to be paid by the publisher if the guarantee is not met, and a value for each click and/or conversion. A key aspect that enables yield optimization for clicks and/or conversions is the probability of a click and/or conversion given a user visit.

Finally, for reasons of scale, it is usually not practical to work with all future user visits for a duration of many months (many large publishers have billions of impressions per day). Consequently, the inventory allocation problem often has to be solved on a sample of user visits, and thus each sampled user visit is annotated with a sample weight.

The following notation summarizes the above discussion:

• : Set of user visits

• : Sample weight of user visit

• : The payout for user visit by non-guaranteed campaigns

• : Set of guaranteed campaigns

• : User visit goal for guaranteed campaign

• : Penalty function for guaranteed campaign , which maps under-delivery (how much a guarantee is missed) to a penalty.

• : The value of a click for a guaranteed campaign

• : The value of a conversion (action) for a guaranteed campaign

• : The probability that a user corresponding to user visit clicks on an ad corresponding to guaranteed campaign

• : The probability that a user corresponding to user visit converts on an ad corresponding to guaranteed campaign

• : Set of user visits that are eligible for guaranteed campaign .

It is often convenient to view the user visits and guaranteed campaigns in a bipartite graph, with user visits on one side, guaranteed campaigns, on the other, and an edge between a user visit and a guaranteed campaign if , that is if satisfies the targeting predicates of . An example of such graph is shown in Figure 1.

It should be noted that the construction of this graph, which may involve tens of thousands of nodes and millions of edges, is in itself a major computational task.

2.2 Objectives

In this section, we motivate and formalize the various objectives that are relevant to the inventory allocation problem. In the next section, we introduce a mathematical model to trade-off and optimize across these different objectives.

An overriding objective of publishers is to minimize the penalties incurred in case guarantees are not met. Minimizing penalties is important because the publisher not only incurs an immediate monetary loss, but also because the publisher could suffer longer-term losses due to advertiser attrition. Define as the weight of user that is allocated to guaranteed campaign . Then the amount of user visits delivered to a guaranteed campaign is , and the objective of minimizing penalties can be formalized as:

 min∑jPj(dj−∑iyij) (1)

However, in this paper we avoid this issue by ensuring feasibility of the constraints (see section 3.1).

At a high-level, there are two parts to the inventory allocation problem, corresponding to non-guaranteed and guaranteed campaigns. The objective for non-guaranteed campaigns is simple: to maximize the revenue for the publisher, since advertisers only bid what each user visit is worth to them. Modeling the objectives for guaranteed campaigns, on the other hand, is more complex because advertisers could be interested in brand awareness/reach or performance (clicks, conversions) or both. We thus have three objectives: non-guaranteed revenue, brand awareness/reach, and performance.

Before formalizing the above objectives, we introduce some notation:

• : The weight of user visit that is allocated to non-guaranteed campaigns

• : The total amount of user visits eligible for guaranteed campaign

• : The ideal fully representative target allocation fraction of user visit to guaranteed campaign (motivated further below)

2.2.1 Non-Guaranteed Revenue

The prices paid by non-guaranteed advertisers depend heavily on the particular user. Therefore, a natural goal of an allocation is to maximize the publisher’s revenue by allocating the highest valued user visits to the non-guaranteed contracts. Since the amount of revenue that a publisher obtains from a user visit is , this objective is written as:

 max∑irizi (2)

2.2.2 Brand Awareness/Reach

There are two primary reasons why it is important to have a brand awareness/reach objective. The first reason is that brand advertisers typically want to reach a large swath of their target audience. For instance, a brand advertiser who targets user visits from the US will likely be quite unhappy if all of their delivered user visits are from fourteen year old males in Wyoming, and none from the rest of the population (even though all the delivered user visits technically satisfy the targeting predicate of the advertiser). In other words, brand advertisers often want a representative subset of their target audience222Advertisers could potentially control their target allocation (other than uniformly at random) more closely if they desire, at the cost of targeting more defined, and therefore likely more expensive, inventory.

The second reason for having a brand awareness and reach objective is more subtle, and it relates to the interaction with non-guaranteed campaigns. Specifically, if the primary goal of the publisher was to maximize short-term revenue, then he could allocate all of the high-value impressions to the highest bidding non-guaranteed campaigns, and allocate only the remaining impressions to the guaranteed campaigns. However, this is clearly detrimental to the advertiser, and is also a dangerous road to take for the publisher: by selectively allocating the most expensive user visits to the non-guaranteed contracts, the publisher risks alienating in the long term the guaranteed advertisers, many of whom pay a large premium for guarantees. In fact as Ghosh et al. [15] recently argued, in these situations price serves as a signal of value, thus the user visits with the highest may also be the ones most desired by the guaranteed contracts.

Therefore, it is in the long-term interests of publishers to allocate each guaranteed campaign a representative sub-set of targeted user visits. Ideally, every eligible user visit should be equally likely to see an ad from . A similar argument holds on a temporal scale. A week long contract should have the same probability of being displayed on all days of the week. That is, it should be allocated uniformly during the course of the week—after all, if an advertiser wanted the contract to be shown only on Tuesday, she would have added that to the targeting constraints.

To model these representativeness constraints, let be the ideal target allocation. Note that directly encodes the fact that no user visit is preferred by over others. To maximize long term revenue, the publisher should strive to find an allocation close to . In this paper we use the -norm distance to measure closeness to the target allocation. We denote the importance of a representative allocation to advertiser and write the objective as:

 min∑j∑i∈BjVj2θij(yij−θij)2 (3)

For consistency with other objectives, we will use the maximization form:

 max−∑j∑i∈BjVj2θij(yij−θij)2 (4)

Note that alternative forms such as an entropy function or K-L divergence can also be used, as they retain the essential features of separability (by advertiser) and convexity. Similarly, other target allocations besides the perfectly uniform target allocation can also be considered but these variants are beyond the scope of this paper.

2.2.3 Clicks/Conversions for Guaranteed Campaigns

An advertiser in a guaranteed campaign may have multiple objectives, such as clicks and conversions, besides obtaining the guaranteed user visits. The publisher’s objective is to maximize the yield from such goals, while also directing such clicks and conversions to the advertisers who value them the most. This can be modeled as trying to maximize the expected value of clicks and conversions across all user visits:

 ∑j∑i∈Bj(Wcjpcijyij+Wajpaijyij)

For compactness we define:

 wij=Wcjpcij+Wajpaij. (5)

Then we can rewrite the performance objective as:

 max∑j∑i∈Bjwijyij. (6)

Note that when we refer to “clicks” below, it is to be understood to include the subsequent conversions.

3 The mathematical models

In the previous section we described the competing objectives faced by a publisher in allocating user visits to guaranteed contracts. In this section we formally state the mathematical problem that incorporates these objectives subject to the feasibility constraints.

There are three types of constraints that the allocation must satisfy to be feasible. First, the desired number of user visits must be allocated for each guaranteed contract:

 ∑i∈Bjyij=dj (Demand Constraints) ∀j

Next, each user visit can be allocated to exactly one guaranteed or non-guaranteed contract.

 ∑j|i∈Bjyij+zi=si (Supply Constraints) ∀i

Finally, we must ensure that the allocation is always non-negative.

 yij≥0 (Non-Negativity Constraints) ∀i,j zi≥0 ∀i

Putting together the objectives from the previous section with the set of constraints, we may state our generic multi-objective optimization:

 max⎡⎢ ⎢ ⎢ ⎢⎣−∑j∑i∈BjVj2θij(yij−θij)2∑j∑i∈Bjwijyij∑irizi⎤⎥ ⎥ ⎥ ⎥⎦ (7)
 subject to ∑j|i∈Bjyij+zi=si ∀i (8) ∑i∈Bjyij=dj ∀j (9) yij≥0 ∀i,j (10) zi≥0 ∀i (11)

Note that the non-negative variables transform what would be inequality supply constraints into equalities. Since is actually the leftover supply inventory that will be sold to the non-guaranteed delivery spot market, the term can be viewed as the total non-guaranteed revenue that can be obtained for an allocation , with remnant inventory . The second objective is the revenue obtained from clicks on the displayed advertisements.

3.1 Ensuring feasibility

In this model formulation, guarantees are treated as constraints (Demand Constraints). Consequently, before we optimize for the other objectives, we need to ensure that the model is feasible, i.e., there is sufficient supply for guaranteed campaigns. Note that even if a publisher is careful to accept only guaranteed campaigns that are feasible at the time of booking, the model could become infeasible at a later point because forecasts of user visits could change due to unforeseen events.

In order to make the model feasible, we add dummy user visits that have unlimited supply but a very high cost of being used, and connect them to all the guaranteed campaigns. The cost associated with using each dummy user visit for a guaranteed campaign corresponds to the penalty incurred by that guaranteed campaign in case of under-delivery (note that if has multiple penalty values for under-delivery, then these can be represented as multiple dummy user visits, each with a different cost of being used). The cost associated with using real user visits is 0.

Given the above set up, the goal is to find the minimum cost allocation to guaranteed campaigns. Since this problem is a pure network with a linear objective function, it can be solved very efficiently [4]. If the cost of the optimal allocation is 0, then it implies that all the guaranteed campaigns can be satisfied, and hence that the original model is feasible. If the cost of the optimal allocation is greater than 0, then it implies that some guaranteed campaigns will under-deliver. Furthermore, the optimal allocation to the dummy user visits will indicate how much each guaranteed campaign needs to under-deliver so that overall penalty cost is minimized. In this case, the user visit goal for each guaranteed campaign is reduced by the amount of allocation to the dummy user visits in order to make the model feasible. We then follow one of the procedures described in the remainder of this section.

3.2 Multi-objective programming

We may approach a multi-objective function model in a number of ways (see [24]). One general approach is to obtain an “efficient frontier” of solutions where at each point on the curve the value of one objective can only be improved at the expense of degrading another (see the generic example in Figure 2, where we notionally trade off total revenue and “representativeness”). The user may then choose any point on this curve as the “solution”.

More algebraic approaches include using a weighted sum of the multiple objectives and/or using “goal programming”, whereby the objectives are handled sequentially, with the additional constraint(s) that previous objectives retain a certain fraction of their optimal value. Since we have three objectives here there are clearly several variations, which we explore below.

In what follows, it will be convenient to define the 3 objective components as follows:

 F1(y) = −∑j∑i∈BjVj2θij(yij−θij)2 (12) F2(y) = ∑j∑i∈Bjwijyij (13) F3(z) = ∑irizi (14)

Depending on the data available, we may formulate solution strategies which employ:

1. A single parametrized objective function.

2. A two-objective function model in various flavors

3. A three-objective function model, also in several flavors.

3.3 Single objective

We consider a multi-component objective function:

 max{γF1(y)+ξF2(y)+F3(z)} (15)

subject to (8)-(11)

The parameter is the weight for the “representativeness” component. The parameter , in conjunction with the reflects the means by which we attribute value to clicks. We observe that a feature of this model is that the shadow value of the supply constraint is always no less than the reserve price, i.e. .

Here, we assume that a value of is available, from either historical data or business considerations. We consider explicitly two cases for the value of :

• The values of the are computed via (5) with . Then is the value of a click relative to a unit of revenue from the objective .

• The are actual expected monetary value of allocating an impression of type to contract , in which case .

In both cases, the model involves the addition of a linear term in to the strictly convex distance function . The objective thus remains strictly convex quadratic in and linear in . Optimization of this model is straightforward in principle, using a commercial solver such as XpressMP [27]. If a sufficiently powerful large-scale nonlinear network code were available, this could also be used since our constraints are of the pure network type.

3.4 Two objectives

If all of the above data are not available to us, we must resort to multi-objective or goal programming. Let us first assume that is not known, but the click-related data ( are available. In this case, we may initially solve:

 max{ξF2(y)+F3(z)} (16)

subject to (8)-(11). Note that this is a linear pure network minimum cost flow problem which can be solved very rapidly by special purpose software (e.g., see Bertsekas [4]). Let the optimal value of this linear program (LP) be .

We may now append a constraint specifying that at least a certain fraction of this monetary value be preserved and solve the model:

 maxF1(y) (17)

subject to (8)-(11) and

 ξ∑j∑i∈Bjwijyij+∑irizi≥ψM∗ (18)

It may be shown (see Appendix) that the unknown parameter is equal to the inverse of the dual value for the constraint (18).

Suppose now that a value for is available but is not. We may initially solve

 maxF2(y) (19)

subject to (8)-(11). Let the optimal value of this linear program (LP) be . We may now append a constraint specifying that at least a certain fraction of this “click value” (however it is quantified) be preserved, and solve the model:

 max{γF1(y)+F3(z)} (20)

subject to (8)-(11) and

 ∑j∑i∈Bjwijyij≥ωP∗ (21)

The third variant combines the two objectives and in the second stage model, after solving a first stage model:

 maxF3(y) (22)

subject to (8)-(11). Since this is also a linear pure network minimum cost flow problem is can be solved very rapidly by special purpose software. Let the optimal value of this linear program be

In this approach, the second model is of the form:

 max{γF1(y)+ξF2(y)}
 subject to (???)-(???) and ∑irizi≥ηR∗ (23)

where is the fraction of NGD revenue we wish to preserve.

This model would require us to have the relative weights on and available. This model is also guaranteed to be feasible if the original constraints (8)-(11) are feasible.

3.5 Three objectives

From an operability point of view, it is unlikely that both the parameters and would be known, or even understood very well. In that case, we cannot avoid turning to goal programming and the use of more intuitive “knobs” for the business to use in the decision making process. Our goal program reduces to a sequence of three models. In principle, these models could be solved in any order, but we take the point of view that the nonlinear objective should be optimized last, in order to avoid imposing a nonlinear constraint. Such a non-linear constraint would be computationally crippling at the scale we are contemplating. The last model therefore must optimize representativeness subject to constraints on non-guaranteed revenue and click value.

We again emphasize that, given appropriate , these last two quantities can reasonably be thought of in monetary terms, whereas may not.

Since non-guaranteed revenue is undeniably monetary, the most intuitive procedure might be to first solve for , i.e. solve the problem (22) and then solve for maximum click value:

 maxF2(y) (24)

subject to (8)-(11) and

 ∑irizi≥ηR∗ (25)

where are as defined in constraint (23). Let the optimum objective function value be .

We may now optimize the representativeness function subject to (8)-(11) and

 ∑irizi≥ηR∗ (26) ∑j∑i∈Bjwijyij≥ωP∗∗ (27)

Clearly we could reverse the first two steps. This would likely produce different results, but both would be feasible.

There is however a severe computational disadvantage to this 3 step process. While step 1 is a pure network optimization model, the second step involves a side constraint (23) or (21) which destroys the orders of magnitude speed advantage of pure network optimizers over general LP solvers. In an effort to avoid this, we might omit the side constraint from the second model, leaving it a pure network model. However there is now no guarantee that the third model, incorporating (26), will be feasible. We might then relax the side constraints until feasibility is obtained, but rigor is lost.

4 Experiments

We now present some experimental results using a snapshot of real online graphical display advertising data sets. The main goal is to quantify the benefits of the multi-objective optimization approach proposed in this paper as compared to the more traditional single-objective optimization approaches. We note that our specific focus is on quantifying the relative benefits of the various optimization approaches for a given data/forecast snapshot, and not on online ad serving mechanisms (e.g., [10, 26]) that account for forecast errors, and could use periodic re-optimization.

4.1 Experimental setup

The data snapshot consists of guaranteed campaigns, forecasts of user visits, non-guaranteed bids and clicks, all based on a subset of historical data from an operational display advertising system. The generated optimizer graph has 32,390 supply nodes, 2,696 demand nodes and 1,407,753 edges. The supply weight () ranges from to . The user visit goal () ranges from to . The non-guaranteed price () ranges from 0.046 to 4.350. The click probability () ranges from to 0.947 (the experiments only evaluate clicks, not conversions).

Figure 3 shows the experimental flow based on the data snapshot. The first step is to invoke the User Visit Forecasting module to generate a forecast of user visits that correspond to the guaranteed campaigns, and construct the allocation graph. The next two (parallel) steps are to invoke the Non-Guaranteed Forecasting and Click Forecasting modules to annotate the allocation graph with the non-guaranteed revenue information () and the click probabilities (, respectively. The final step is to run the Optimizer to solve the various optimization methods proposed in the paper.

The metrics that we measure for the various optimization runs are the non-guaranteed revenue, the total value of clicks, and the representativeness of guaranteed campaigns. The experiments are run for various values of the model parameter settings. For the experiments, all the allocation priorities are set to 1 and all the click values are set to 10.

The experiments were run on a 64bit/64GB/2GHz Linux box using the optimization package Xpressmp333Recently acquired by Fair Isaac (FICO) [27].

4.2 Forecast models

Although the forecast models used here are not the focus of this paper, we include a brief description of each for completeness.

4.2.1 Supply Forecasting

User visit forecasting uses time-series trend predictions to predict the trend/growth in user visits for various pockets of supply such as Sports or Finance. Our specific implementation uses SARIMA [23] for time-series predictions.

In addition, to generate the allocation graph, we need to produce a sample of user visits. For this, we follow the sampling procedure outlined in Vee et al [26], which produces a unbiased sample for the class of optimization models that we consider in this paper. Specifically, for each guaranteed campaign, the supply forecast selects eligible user visits uniformly at random. Once all of the user visits for all campaigns are chosen, the weights given to each user visit is normalized so that the total weight of any subset of user visits is — in expectation — equal to the predicted available supply. The allocation graph is then created by adding edges from the campaigns to their eligible user visits.

4.2.2 Non-Guaranteed Forecasting

The goal of the Non-Guaranteed Forecasting module is to predict the expected revenue obtained by selling a particular user visit in the non-guaranteed marketplace. We observed that the prices paid for ad opportunities by the non-guaranteed contracts followed a log normal distribution, with prices ranging from under $0.10 CPM to above$10 CPM. To predict the price of an individual user visit, we trained a generalized least squares regression model on the logarithm of the prices. Each user visit was annotated with a set of user features, for example, age, gender, etc, and a set of page features, for example Sports, Finance, etc. We used the value predicted by the model as the non-guaranteed price .

4.2.3 Click forecasting

Click forecasting estimates the probability that a displayed ad will be clicked in a particular user visit context. Estimation of click-through rates (CTR) is extensively applied in pay-for-performance systems that attempt to maximize expected revenue [20, 22]. The estimates can be based on historical click-through performance statistics of features that are selected as significant predictors of CTR. In this work, we use a logistic regression model with the following functional form:

 p(click|{f1,…,fK})=11+exp(∑Kk=1wkfk) (28)

where are predicates of features of the user visit and the ad such as user age and gender, page content category, ad position in page, etc. Using historical data from web traffic that consist of page visits with corresponding user visit and click statistics, we learned the logistic regression parameters.

Finally, each edge in the allocation graph, which represents a contract and a corresponding eligible ad opportunity, is annotated with features . The click model is used to produce an estimate of the probability of click for each graph edge.

4.3 Experimental results

We now present our experimental results for various models and parameter settings. Each optimization for a particular parameter combination takes about 5 to 10 minutes, which is quite acceptable as an offline optimization step that can inform online serving algorithms (e.g., [10, 26]).

4.3.1 Baseline and Single-Objective Solutions

As a baseline, we compute the optimization solution that only ensures feasibility by minimizing the total under-delivery penalty, but does not explicitly optimize for the other objectives. The result for this baseline solution is shown in the first row of Table 1) and is used as the basis for normalization. We then optimize for each single objective separately and report the normalized solutions in the same table — here NGD refers to non-guaranteed revenue, and GD refers to guaranteed representativeness. It can be seen that while optimizing a single objective may significantly improve that objective, it has a potentially significant impact on the other objectives.

4.3.2 Two-Objective Formulation

We run the 2-step programming algorithm (Section 3.4) with 100 different values of the parameter. Table 2 shows the objectives in normalized scale for a subset of the generated efficient solutions. The whole efficient frontier by using all the 100 points is depicted in Figure 4, which shows the trade-off between the monetary objective (non-guaranteed revenue plus click value) and the non-monetary objective (representativeness).

Figure 4 also shows the baseline and single-objective solutions as different symbols. The baseline solution and most of the single-objective solutions are located in the interior of the feasible solution region and dominated by efficient solutions on the frontier. Further, the efficient frontier shows that a very small loss in one objective can lead to a significant gain in the other objective, thereby enabling a better combined trade-off as compared to single-objective solutions.

The above results clearly demonstrate that explicitly capturing and solving for multiple objectives dominates ignoring the objectives, or just optimizing for a single objective.

4.3.3 Three-Objective Formulation

We run the 3-step programming algorithm (Section 3.5) with 100 different combinations of the and parameters. Table 3 shows the objectives in normalized scale for a subset of the generated efficient solutions. Note that the efficient frontier for the tri-objective optimization problem is a surface in a 3D space. One way to visualize the efficient frontier is to project it to a 2D space by fixing the level in the third dimension. Figure 5 shows three such contours in the space of click value and GD representativeness for evenly-spaced NGD revenues. The trade-off among the three objectives can be observed by comparing points on the same contour and between different contours.

4.4 Discussion

The results above and especially the efficient frontier give us a global picture of the trade-off among different objectives. It reveals what percentage of one objective can be gained at the cost of one percent of another objective and how the trade-off rate changes with the location of the solution, thereby providing valuable insight in setting the right parameters in a real production system to truly reflect the business priority. Perhaps more importantly, it demonstrates the significant benefit of a combined optimization model for multiple objectives, as opposed to optimizing for just a single objective.

5 Further extensions

We have referred throughout to revenue gained through clicks. We might also include other non-monetary terms, using or some other parameter as a conversion factor. One candidate for this treatment is relevance, when would encode the probability of relevance of ad to user and the payoff to advertiser for such relevance.

Another candidate for future work is the exploration of ways to to incorporte uncertainty into the strictly deterministic model we have described here. Preliminary stochastic programming experiments [5] indicate that uncertainty in the inventory supply can have a significant impact. Other sources of uncertainty arise in sampling error and click and conversion rate estimation.

6 Related work

Operations Research techniques, and optimization in particular, have been used for decades in planning advertising campaigns in other media, such as print, radio and television (see [6] for example). The potential of the WWW for more targeted advertising was realized in the 1990’s and became a subject of research. Langheinrich et al [17] reported on a study where they attempted to target display ads to users in order to optimize expected revenue, without using intrusive data gathering techniques. While “unintrusiveness” seems to have become less of a concern to advertisers and publishers, their optimization approach was influential. Tomlin [25], noting a similarity between this problem and the traffic distribution model (see [28]), suggested adding an entropy term to the linear cost function proposed in [17] to essentially smooth the allocations and prevent “bang-bang” solutions; characteristic of LP models. Chickering and Heckerman [9] employed an alternate smoothing technnique, involving binning, and gave computational experience. A good survey of these and later developments is given in [18].

Since that time, the development of Computational Advertising as a discipline has led to the consideration of many variants of the graphical advertising allocation problem. A crucial development in this process was the promulgation of the concept of “fairness” in allocation to offset extreme LP solutions. While we have used the approach of [15], an alternate approach is taken by [13]. Some of our early work was presented in [1] and  [29]. Feldman et al [14] have considered the online ad allocation problem in the more general setting of the matching problem, while Roels and Fridgeirsdottir [21] have considered a dynamic version assuming the inventory follows a Markov process. Easterly [11] and Han [16] discuss online advertising from a Revenue Management point of view.

Two other modules in the online advertising supply chain make use of the results of an allocation model such as we have described. These are Ad Serving and Admission Control. The Ad Server interprets the output of the allocation model as a set of frequencies with which specific ads should be shown to users in the supply pools when they visit a web page. Considerable practical advantages ensue when the solution can be stored in compact form and rapidly reconstructed on the fly by the ad server when a page requests ads. This process has been studied by Devanur and Hayes [10] and Vee et al [26], using the dual values associated with the demand constraints and, implicitly, the graph structure to determine the contracts for which a new arriving impression is eligible. The optimization models we have studied provide the necessary dual values, but online ad serving is not considered in this paper.

Admission Control is the process of determining whether a proposed new guaranteed campaign should be accepted, that is whether the existing obligations can still be satisfied in a modified solution if the new contract is accepted. Versions of this problem have been studied by Feige et al [12] and Aleai et al [3] and considered as an (NP-hard) combinatorial optimization problem. Radovanovic and Zeevi [19] have proposed a relaxed, more tractable, variant of the Admission Control process.

7 Conclusion

In this paper we have shown that multi-objective optimization provides an efficient and flexible framework for the allocation of user visits to guaranteed and non-guaranteed campaigns. The proposed models also incorporate a very flexible means of taking into account revenue derived from clicks, as well as non-monetary objectives — in particular “representativeness” or “fairness” — in the allocation of eligible user visits to campaigns. We are able to do this using off-the-shelf software, such as a commercial scale optimization system (we used XpressMP) for large scale quadratic programming, or specialized network optimization codes for some steps.

We believe that the proposed models can be extended to other objectives of interest such as ad relevance. As part of future research, we are exploring extensions to the model to include stochastic elements, such as uncertainty in supply and demand, and nonlinear pricing.

8 acknowledgments

We gratefully acknowledge the assistance of Sumanth Jagannath and Wenjing Ma in processing the data for our experiments, and Jianchang Mao for managing much of the click model development.

References

• [1] D. Agarwal, J. Tomlin, and J. Yang. A log-linear model for allocating overlapping inventory to on-line advertisers. Presented at INFORMS, October 2008.
• [2] G. Aggarwal, A. Goel, and R. Motwani. Truthful auctions for pricing search keywords. In Proc. of the 7th ACM Conf. on Electronic Commerce, pages 1–7, 2006.
• [3] S. Aleai, E. Arcaute, S. Khuller, W. Ma, A. Malekian, and J. Tomlin. Online allocation of display advertisements subject to advanced sales contracts. In Proc. of the 3rd Int. Workshop on Data Mining and Audience Intelligence for Advertising (ADKDD), pages 69–77, 2009.
• [4] D. Bertsekas. Network Optimization: Continuous and Discrete Models. Athena Scientific Press, 1998.
• [5] V. Bharadwaj, M. Saunders, and J. Tomlin. Sensitivity of an inventory allocation model for online advertising with stochastic supply. Presented at EURO XXIV, July 2010.
• [6] S. Bollapragada, H. Chen, M. Phillips, M. Garbiras, M. Scholes, T. Gibbs, and M. Humphreville. NBC’s optimization systems increase revenues and productivity. Interfaces, 32(1):47 – 60, 2002.
• [7] A. Z. Broder. Computational advertising and recommender systems. In RecSys ’08, pages 1–2, Lausanne, Switzerland, 2008.
• [8] A. Z. Broder, M. Fontoura, V. Josifovski, and L. Riedel. A semantic approach to contextual advertising. In Proc. ACM SIGIR, 2007.
• [9] D. M. Chickering and D. Heckerman. Targeted advertising with inventory management. In EC ’00: Proceedings of the 2nd ACM conference on Electronic commerce, pages 145–149, New York, NY, USA, 2000. ACM.
• [10] N. Devanur and T. Hayes. The adwords problem: Online keyword matching with budgeted bidders under random permutations. Presented at EC, 2009.
• [11] A. Easterly. Revenue management in online advertising: Challenges and opportunities. Presented at INFORMS, October 2009.
• [12] U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. A combinatorial allocation mechanism with penalties for banner advertising. Presented at INFORMS, October 2008.
• [13] J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein. Online stochastic packing applied to display ad allocation. CoRR, abs/1001.5076, 2010.
• [14] J. Feldman, A. Mehta, V. Mirrokni, and S. Muthukrishnan. Online stochastic matching: Beating 1-1/e. Presented at FOCS, October 2009.
• [15] A. Ghosh, R. McAfee, K. Papineni, and S. Vassilvitskii. Randomized bidding for maximally representative allocation. In Proc. WINE, December 2009.
• [16] P. Han. Yield optimization in display ad networks. Presented at INFORMS, October 2009.
• [17] M. Langheinrich, A. Nakamura, N. Abe, T. Kamba, and Y. Koseki. Unintrusive optimization techniques for web advertising. In Proc. of World Wide Web Conf. (WWW1999), 1999.
• [18] A. Nakamura and N. Abe. Improvements to the linear programming based scheduling of web advertisements. J. Electronic Commerce Research, 5:75–98, 2005.
• [19] A. Radovanovic and A. Zeevi. Revenue maximization in reservation-based online advertising. Presented at INFORMS, October 2009.
• [20] M. Richardson, E. Dominowska, and R. Ragno. Predicting clicks: Estimating the click-through rate for new ads. In Proc. of World Wide Web Conf. (WWW2007), 2007.
• [21] G. Roels and K. Fridgeirsdottir. Dynamic revenue mangement for online display advertising.
• [22] B. Shaparenko, O. Çetin, and R. Iyer. Data-driven text features for sponsored search click prediction. In Proc. of the 3rd Int. Workshop on Data Mining and Audience Intelligence for Advertising (ADKDD), pages 46–54, 2009.
• [23] R. Shumway and D. Stoffer. Time Series Analysis and Its Applications. Springer, 2007.
• [24] R. Steuer. Multiple criteria optimization: theory, computation, and application. Wiley, New York, 1986.
• [25] J. Tomlin. An entropy approach to unintrusive targeted advertising on the web. In Proc. of World Wide Web Conf. (WWW2000), 2000.
• [26] E. Vee, S. Vassilvitskii, and J. Shanmugasundarum. Optimal online assignment with forecasts. Proc. of the ACM Conf. on Electronic Commerce, 2010.
• [27] Dash Optimization. XpressMP—Optimizer Reference Manual, 2008.
• [28] A. Wilson. Entropy in Urban and Regional Modelling. Pion Press, London, 1970.
• [29] J. Yang and J. Tomlin. Advertising inventory allocation based on multi-objective optimization. Presented at INFORMS, 2008.

Appendix

The goal programming model (17), (8)-(11), (18) in section 3.4 is equivalent to finding a value of which preserves a specified fraction of revenue, given a value of . To see this, let us write the Lagrangian of the problem (15), (8)-(11) as:

 Lγ(y,z,αγ,βγ,λγ,μγ)=γf(y,θ)−ξ∑j∑i∈Bjwijyij −∑irizi−∑jαγj(∑i∈Bjyij−dj) +∑iβγi(∑j|i∈Bjyij+zi−si)−∑ijλγijyij−∑iμγizi

where the and are the appropriate Lagrange multipliers on the equality and inequality constraints.

The KKT optimality conditions for this problem are:

 ∂Lγ∂yij=γ∂f∂yij−ξwij−αγj+βγi−λγij=0 ∂Lγ∂zi=−ri+βγi−μγi=0 λγij=γ∂f∂yij−ξwij−αγj+βγi≥0 μγi=βγi−ri≥0 λγijyij=0, μγizi=0

Now consider the Lagrangian of the problem (17), (8)-(11), (18), introducing Lagrange multiplier :

 Lη(y,z,αη,βη,λη,μη,ρ)=f(y,θ) −∑jαηj(∑i∈Bjyij−dj)+∑iβηi(∑j|i∈Biyij+zi−si) −∑ijληijyij−∑iμηizi −ρ(ξ∑j∑i∈Bjwijyij+∑irizi−ψM∗)

The KKT optimality conditions are:

 ∂Lη∂yij=∂f∂yij−ρξwij−αηj+βηi−ληij=0 ∂Lη∂zi=−ρri+βηi−μηi=0 ληij=∂f∂yij−ρξwij−αηj+βηi≥0 μηi=βηi−ρri≥0 ληijyij=0, μηizi=0 ρ(ξ∑j∑i∈Bjwijyij+∑irizi−ψM∗)=0

Comparing terms in the Lagrangians and the two sets of KKT conditions we see that . In particular, we see that . Thus we may obtain the parameter as from the solution to the goal programming problem.

You are adding the first comment!
How to quickly get a good reply:
• Give credit where it’s due by listing out the positive aspects of a paper before getting into which changes should be made.
• Be specific in your critique, and provide supporting evidence with appropriate references to substantiate general statements.
• Your comment should inspire ideas to flow and help the author improves the paper.

The better we are at sharing our knowledge with each other, the faster we move forward.
The feedback must be of minimum 40 characters and the title a minimum of 5 characters


text:
# The implication of zero mixed partial derivatives for multivariate function's minimization

Suppose $f(\textbf x)=f(x_1,x_2)$ has mixed partial derivatives $f''_{12}=f''_{21}=0$, so can I say: there exist $f_1(x_1)$ and $f_2(x_2)$ such that $\min_{\textbf x} f(\textbf x)\equiv \min_{x_1}f_1(x_1)+ \min_{x_2}f_2(x_2)$? Or even further, as follows: $$f(\textbf x)\equiv f_1(x_1)+ f_2(x_2)$$

A positive simple case is $f(x_1,x_2)=x_1^2+x_2^3$. I can not think of any opposite cases, but I am not so sure about it and may need a proof.

• Concerning the passage from $f(\textbf x)\equiv f_1(x_1)+ f_2(x_2)$ to $\min_{\textbf x} f(\textbf x) = \min_{x_1}f_1(x_1)+ \min_{x_2}f_2(x_2)$, see this question. – user147263 Dec 29 '15 at 0:24

For a mixed derivative $f_{xy} = 0$, integrating with respect to $y$ gives: $$f_x(x,y) = \int f_{xy} \,dy + h(x).$$ Integrating with respect to $x$: $$f(x,y) = \iint f_{xy} \,dydx + \int h(x)dx + g(y).$$ Similar result yields if we start from $f_{yx}$, now this implies $$f(x,y) = f_1(x) + f_2(y),$$ and there goes your conclusion in the question.

• Hi again. Can I say $f_1$ and $f_2$ are unique? Excluding constants. – jorter.ji Jun 26 '13 at 6:13
• @jorter.ji If you only know that the mixed derivative is zero, then any differentiable function $f_1$ and $f_2$ will do. So not unique unless you have other conditions. – Shuhao Cao Jun 26 '13 at 12:32
• Like what kind of conditions? Or can you think of any instances such that $f=f_1+f_2=f_3+f_4$? – jorter.ji Jun 26 '13 at 16:49
• @jorter.ji I meant to say that provided only this differential relation $f_{xy} = f_{yx} = 0$ is known, then there are infinitely choices for $g$ and $h$ in $f = g(x) + h(y)$, $f$ can be $f = x+y$, or $f= x^2+y^2$. Not that they are equal or something. – Shuhao Cao Jun 26 '13 at 16:52
• OIC your meaning. Actually, I already know that $f(x,y)=f_1(x)+f_2(y)+V(x,y)$, where $V(x,y)$ is a implicit but determined function, i.e., $f(x,y)$ is somehow implicitly determined, then I wonder if $f=g(x)+h(y)$ is unique. – jorter.ji Jun 26 '13 at 17:41

The answer of @Shuhao Cao needs an assumption that the first partial derivative is integrable.

Here I try to provide a proof without that assumption.

### Restatement

I can restate the conjecture with little weaker conditions:

If $$f(x, y)$$ has $$f_{yx} = 0$$, then $$z(x, y) = f(x) + g(y)$$.

### Proof

From Mean Value Theorem, $$f_y(x, y) = f_y(0, y) + f_{yx}(\xi , y) x, \xi \in (0, x)$$This implies $$f_y = f_y(0, y)$$.

$$\forall x_0$$, $$f(x_0, y)$$ is an antiderivative of $$f_y(0, y)$$. Any two antiderivatives differ by constant. So, we can write that $$f(x, y) = f(0, y) + c(x) = f(0, y) + f(x, 0) - f(0, 0) = f_1(x) + f_2(y)$$

### Annotation

The key is that "any two antiderivatives differ by constant" can be proved only based on Mean Value Theorem, but nothing wih Reimann Integral.

format: plain


text:
The Power Spectrum

October 8, 2016

Often, when calculating the spectrum of a sampled signal, we are interested in relative powers, and we don’t care about the absolute accuracy of the y axis.  However, when the sampled signal represents an analog signal, we sometimes need an accurate picture of the analog signal’s power in the frequency domain.  This post shows how to calculate an accurate power spectrum.

Parseval’s theorem [1,2] is a property of the Discrete Fourier Transform (DFT) that...

Digital PLL's -- Part 2

June 15, 2016

In Part 1, we found the time response of a 2nd order PLL with a proportional + integral (lead-lag) loop filter.  Now let’s look at this PLL in the Z-domain [1, 2].  We will find that the response is characterized by a loop natural frequency ωn and damping coefficient ζ.

Having a Z-domain model of the DPLL will allow us to do three things:

Compute the values of loop filter proportional gain KL and integrator gain KI that give the desired loop natural frequency and...

Digital PLL's -- Part 1

June 7, 201616 comments
1. Introduction

Figure 1.1 is a block diagram of a digital PLL (DPLL).  The purpose of the DPLL is to lock the phase of a numerically controlled oscillator (NCO) to a reference signal.  The loop includes a phase detector to compute phase error and a loop filter to set loop dynamic performance.  The output of the loop filter controls the frequency and phase of the NCO, driving the phase error to zero.

One application of the DPLL is to recover the timing in a digital...

Peak to Average Power Ratio and CCDF

May 17, 20162 comments

Peak to Average Power Ratio (PAPR) is often used to characterize digitally modulated signals.  One example application is setting the level of the signal in a digital modulator.  Knowing PAPR allows setting the average power to a level that is just low enough to minimize clipping.

However, for a random signal, PAPR is a statistical quantity.  We have to ask, what is the probability of a given peak power?  Then we can decide where to set the average...

Filter a Rectangular Pulse with no Ringing

May 12, 201610 comments

To filter a rectangular pulse without any ringing, there is only one requirement on the filter coefficients:  they must all be positive.  However, if we want the leading and trailing edge of the pulse to be symmetrical, then the coefficients must be symmetrical.  What we are describing is basically a window function.

Consider a rectangular pulse 32 samples long with fs = 1 kHz.  Here is the Matlab code to generate the pulse:

N= 64; fs= 1000; % Hz sample...

Use Matlab Function pwelch to Find Power Spectral Density – or Do It Yourself

January 13, 2019

In my last post, we saw that finding the spectrum of a signal requires several steps beyond computing the discrete Fourier transform (DFT)[1].  These include windowing the signal, taking the magnitude-squared of the DFT, and computing the vector of frequencies.  The Matlab function pwelch [2] performs all these steps, and it also has the option to use DFT averaging to compute the so-called Welch power spectral density estimate [3,4].

Coefficients of Cascaded Discrete-Time Systems

March 4, 2018

In this article, we’ll show how to compute the coefficients that result when you cascade discrete-time systems.  With the coefficients in hand, it’s then easy to compute the time or frequency response.  The computation presented here can also be used to find coefficients of mixed discrete-time and continuous-time systems, by using a discrete time model of the continuous-time portion [1].

Evaluate Window Functions for the Discrete Fourier Transform

December 18, 2018

The Discrete Fourier Transform (DFT) operates on a finite length time sequence to compute its spectrum.  For a continuous signal like a sinewave, you need to capture a segment of the signal in order to perform the DFT.  Usually, you also need to apply a window function to the captured signal before taking the DFT [1 - 3].  There are many different window functions and each produces a different approximation of the spectrum.  In this post, we’ll present Matlab code that...

Compute the Frequency Response of a Multistage Decimator

February 10, 20192 comments

Figure 1a shows the block diagram of a decimation-by-8 filter, consisting of a low-pass finite impulse response (FIR) filter followed by downsampling by 8 [1].  A more efficient version is shown in Figure 1b, which uses three cascaded decimate-by-two filters.  This implementation has the advantages that only FIR 1 is sampled at the highest sample rate, and the total number of filter taps is lower.

The frequency response of the single-stage decimator before downsampling is just...

Demonstrating the Periodic Spectrum of a Sampled Signal Using the DFT

March 9, 20196 comments

One of the basic DSP principles states that a sampled time signal has a periodic spectrum with period equal to the sample rate.  The derivation of can be found in textbooks [1,2].  You can also demonstrate this principle numerically using the Discrete Fourier Transform (DFT).

The DFT of the sampled signal x(n) is defined as:

$$X(k)=\sum_{n=0}^{N-1}x(n)e^{-j2\pi kn/N} \qquad (1)$$

Where

X(k) = discrete frequency spectrum of time sequence x(n)


text:
# Newton's law of gravitation

1. Sep 3, 2009

### tonyza2006

Hi there,

I don't understand why the equal of Newton's law of gravitation F = Gm1m2/d(squared) is different for no spherical objects.

In the image of my attachment there are one spherical object and a no spherical object. So why if there are not very distant the equal used is F = Gm1m2/d(d+L).

How It's used (d).(d+L) on the contrary (d).(d), which is the original equal?

Thanks
Tony

File size:
1.7 KB
Views:
80
2. Sep 3, 2009

### Staff: Mentor

Your question isn't quite clear. Your diagram shows (I believe) a spherical body (centered at location x = 0, say) and an extended body that goes from x = D to x = D + L. Given that, I do not understand your first equation for the gravitational force between the two objects.(1) The second equation makes sense, since it says that when the objects are far enough apart they can be treated as point masses and you can ignore the small size of the object.

Strictly speaking, Newton's law of gravity only applies for point masses (and certain special geometries, such as uniform spheres and spherical shells). To get the net force between the two objects you'd have to integrate the force on each mass element of the extended body.

(1)Edit: My bad, as I was too lazy to do the integral. :uhh: As D H points out, your first equation is perfectly fine. Note that this is allowed because your first object is spherical and can thus be treated as a point mass at x = 0.

Last edited: Sep 3, 2009
3. Sep 3, 2009

### D H

Staff Emeritus
Strictly speaking, Newton's law of gravitation only applies to point masses. It can be applied to non-point masses by integrating over the volume. In the case of this (presumably constant density) bar,

$$a = \int_d^{d+L} \frac{G\rho}{x^2}dx$$

where $\rho$ is the density of the bar: $\rho=M_{\text{bar}}/L$

This yields

$$a = \frac{GM_\text{bar}}{d\cdot(d+L)}$$

Note well: This result is valid for all distances d. Another way to write the above is

$$a = \frac{GM_\text{bar}}{d^2}\frac 1 {1+L/d}$$

In the case that $d\gg L$, the final factor is very close to one. In other words,

$$a \approx \frac{GM_\text{bar}}{d^2}\,,\,d\gg L$$

4. Sep 3, 2009

### Feldoh

For d >> L we can validly write the equation as:

$$F =~ \frac{G m_1 m_2}{d^2}$$ because think about it:

If d = 10000000000000000m and L = 1m than d+L = 10000000000000001, so when we square it the numbers are pretty much the same. Using d by itself in this case turns out to only give an error of ~2*10^-8% from the real value.

5. Sep 3, 2009

### D H

Staff Emeritus
You can't (or shouldn't) do that.

Edit
That was a bit too terse. The reason you should not do that is because it is wrong. The gravitational attraction between two non-point masses is the sum of the gravitational attractions amongst all the bits of matter that comprise the two objects (or you can integrate if you ignore that matter is not discrete). The only way this would summed / integrated form would yield the same result as the center of mass to center of mass calculation is if gravitation was a linear function of distance. It is not of course; gravity is an inverse square law.

Last edited: Sep 3, 2009
6. Sep 3, 2009

### tonyza2006

I'm surprise with the number of answers. You really help me!!

And thanks to adivice the matters of integrate.

Thanks
Tony

7. Sep 3, 2009

### Naty1

Good explanation and reminder......That explains why the first equation "looks strange" at first.....I had initially thopught "Should the second term be (d+L)/2??".....before I read further...


text:
2D vector addition calculator calculates the sum of the 2 dimensional vectors. Either the components or magnitude/direction angle values of the vectors can be entered for the calculations. Up to 5 vectors can be added at once with the calculator.

The vector $${ \vec { A } }$$ is:

$$\vec {A} ={A}_{x}\hat {x} +{A}_{y}\hat {y}$$

The magnitude of the vector $${ \vec { A } }$$ is:

$$\left| A \right| =\sqrt { { { A }_{ x } }^{ 2 }+{ { A }_{ y } }^{ 2 } }$$

The x-component of the vector $${ \vec { A } }$$ is:

$${A}_{x}=A\cos {\theta}$$

The y-component of the vector $${ \vec { A } }$$ is:

$${A}_{y}=A\sin {\theta}$$

The angle of the vector $${ \vec { A } }$$ is:

$$\tan{\theta} =\frac{{A}_{y}}{{A}_{x}}$$

The sum of vectors is:

$$\vec { R } =\vec { A } +\vec { B }….+\vec { E }$$
$${ R }_{ x }={ A }_{ x }+{ B }_{ x }….+{ E }_{ x }$$
$${ R }_{ y }={ A }_{ y }+{ B }_{ y }….+{ E }_{ y }$$


text:
## anonymous one year ago Will Medal! If 2tanx/ (1-tan^2x) = 1, then x can equal ____. Check all that apply. A) x=5pi/8 + npi B) x=pi/8 + npi C) x=3pi/8 + npi D) x=7pi/8 + npi

1. anonymous

I think it is A and B. But this is me taking a guess. I am terrible at trig. Sorry

2. welshfella

well first cross multiply to give 2 tanx = 1 - tan^2 x now rearrange this quadratic: tan^2 x + 2tanx - 1 = 0 can you factor this?

3. anonymous

Yes. I am thinking you factor to get tan^2x = -2tan(x)+1?

4. welshfella

no factor as you would any quadratic like x^2 + 3x + 2 = (x + 1)(x + 2)

5. welshfella

oh sorry - on second look this will not factor so you need to use the quadratic formula

6. anonymous

So would a = tan^2x b =2tanx and c=-1?

7. welshfella

no a , b and c are the coefficients of tan^2x and tan x so a = 1 , b = 2 and c = -1

8. anonymous

So x = +/- sqrt (2) in the end right?

9. anonymous

*-1 +/- sqrt(2)

10. welshfella

-2 +/- sqrt(4 - 4*1*-1) / 2 = -2 +/- sqrt8 / 2 = (-2 +/- 2 * sqrt2 )/ 2 = -1 +/- sqrt2 yep

11. anonymous

Awesome! So now do I just plug in this to my original equation?

12. welshfella

well they have the answer options in terms of pi so convert everything to decimals so for example -1 + sqrt2 = 0.4142 so find the angle in radians which is the tangent of 0.4142 and see if one of the options gives the the same angle

13. welshfella

eg angle with tangent 0.4142 = 0.39269 radians now check if pi/8 gives the same value

14. anonymous

Yes it does!

15. anonymous

So I'm assuming that is one

16. welshfella

ok so thats one result pi/8 + npi

17. welshfella

now try the other value for tan x

18. anonymous

-1 - sqrt 2 = -2.4142 degrees right?

19. welshfella

yes

20. anonymous

Ok so then the radians of -2.4142 is -0.042135

21. anonymous

I don't think I did it right

22. welshfella

no the -2.4142 is the value of tan x so you need tan-1(-2.4242)

23. anonymous

Oh ok that would make it -1.1781 which is basically the same as 3pi/8 right?

24. anonymous

So the answers would be pi/8 + npi and 3pi/8 + npi

25. welshfella

yes

26. anonymous

Great!! Thank you for taking the time to help me! I feel I really understand now! Thank you!

27. anonymous

Weird... I hit the sumit button and it told me it was 5pi/8 instead of 3/pi/8

28. welshfella

lets check that out

29. myininaya

$\frac{2tanx}{1-\tan^2x} = 1 \\ \tan(2x)=1$

30. myininaya

$\tan(u)=1 \text{ when } u=?$

31. welshfella

ahh i forgot that identity !

32. welshfella

u = pi/4 of course and x will be pi/8

33. welshfella

much easier that way lol!

34. myininaya

and there is also the u=5pi/4 so yep x=5pi/8

35. welshfella

yes

36. welshfella

-1.1781 is an incorrect result then? - an extraneous result right?

37. myininaya

does give tan(2x) approx 1 what number are you approximating ?

38. myininaya

oh -3pi/8 is what you are approximating

39. welshfella

sorry I dont follow you -yes

40. myininaya

that gives 1

41. myininaya

when you plug in

42. welshfella

and -3pi/8 is equivalent to 5pi/8

43. myininaya

is that not included in the solution: $\frac{5\pi}{8}+n \pi \\ \text{ if } n=-1 \text{ then } \frac{5\pi}{8}-\pi=\frac{-3\pi}{8}$ so I'm not sure why you say it is extraneous

44. welshfella

no - i was wrong its not extraneous

45. welshfella

still i think lehmad learned something along the line...

46. anonymous

Yes I learned a lot! Thank you guys for the help.


text:
# Congruences and Modular Arithmetic

• a is congruent to b mod n means that . Notation: .
• Congruence mod n is an equivalence relation. Hence, congruences have many of the same properties as ordinary equations.
• Congruences provide a convenient shorthand for divisibility relations.

Definiton. Let a, b, and m be integers. (read "a equals b mod m" or a is congruent to b mod m) if any of the following equivalent conditions hold:

(a) .

(b) .

(c) (or ) for some .

(d) (or ) for some .

m is called the modulus of the congruence. I will almost always work with positive moduli.

Note that if and only if . Thus, modular arithmetic gives you another way of dealing with divisibility relations. Another way of saying this is: Mod m any multiple of m is 0.

Remark. Many people prefer to write " ". Since equality mod m is an equivalence relation, since " " is a little less writing than " ", and since there isn't much risk of confusion, I'll write " ".

Example.

(a) Reduce to a number in the range .

(b) Reduce to a number in the range .

(a) , because .

(b) , because .

Proposition. Congruence mod m is an equivalence relation:

(a) ( Reflexivity) for all a.

(b) ( Symmetry) If , then .

(c) ( Transitivity) If and , then .

Proof. I'll prove transitivity by way of example. Suppose and . Then there are integers j and k such that

This implies that .

Theorem. Suppose and . Then:

(a) .

(b) .

Note that you can use the second property and induction to show that if , then

Proof. Suppose and .

(a) and , so by properties of divisibility,

This implies that .

(b) and imply that there are integers j and k such that

Multiplying these two equations, I obtain

Hence, , so .

Corollary. Suppose . Then:

(a) .

(b) .

Proof. Apply the theorem to the equations and .

Assume that the modulus m is a positive integer. By the Division Algorithm, every integer n can be written as

Reducing this equation mod m, I have , so

Since , I have . In other words, mod m every integer can be reduced to a number in . This set is called the standard residue system mod m, and answers to modular arithmetic problems will usually be simplified to a number in this range.

Example.

(a) What are the equivalence classes under the relation of congruence mod 3?

(a) Consider congruence mod 3. There are 3 congruence classes:

Each integer belongs to exactly one of these classes. Two integers in a given class are congruent mod 3.

(If you know some group theory, you probably recognize this as constructing from .)

(b) When you're doing things mod 3, it is if there were only 3 numbers. I'll grab one number from each of the classes to represent the classes; for simplicity, I'll use 0, 2, and 1.

Here is an addition table for the classes in terms of these representatives:

Here's an example: , because as integers, and 3's congruence class is represented by 0. This is the table for addition mod 3.

I could have chosen different representatives for the classes --- say 3, -4, and 4, but I would have gotten an equivalent table. The simplest thing is to use the numbers from the standard residue system mod 3.

Example. ( Reducing an expression mod n) Reduce to an element in the standard residue system .

, so

Example. Simplify to a number in the range .

Rather than deal with large "positive" numbers, I'll convert them to small "negative" numbers:

So

Example. ( A modular binomial theorem) Prove that if p is prime, then

By the Binomial Theorem,

A typical coefficient is divisible by p for . So going mod p, the only terms that remain are and .

For example

The result is not true if the modulus is not prime. For example,

Example. Prove that if , then is not divisible by 5.

The phrase "not divisible by 5" leads one to think of doing things mod 5.

Every integer is equal to one of 0, 1, 2, 3, or 4 mod 5. Make a table:

Example. Give a counterexample to show that does not imply that , for .

For instance, , but (since ).

Example. Solve the congruence

The modular arithmetic properties allow me to solve this equation the way I would solve a linear equation, up to a point. I multiply out the left side, then get the x's on one side:

If this were an equation over the real numbers, you could divide both sides by 4 --- equivalently, multiply both sides by .

What would " " mean mod 7? This is the multiplicative inverse of 4, which we write as (in modular arithmetic you don't use fraction notation). This means: What number multiplied by 4 gives 1 mod 7?

Since there are only 7 numbers mod 7, I can do this by trial and error, multiplying 4 by 0, 1, ... until I get 1. I find that

So for this modular equation, I multiply both sides by 2:

You can see that finding multiplicative inverses mod n can be useful in solving congruences. Sometimes they can be found by more refined trial and error than simply trying all the numbers mod n.

Since multiples of n equal 0 mod n,

I can sometimes use this to find inverses mod n.

Example.

(a) Use trial and error to find .

(b) Use trial and error to find .

(c) Prove that 25 does not have a multiplicative inverse mod 30.

(a) I take multiples of 7 and add 1, stopping when I get a number which is divisible by 5:

Since , I have .

(b) I take multiples of 89 and add 1, stopping when I get a number which is divisible by 45:

Since , I have .

(c) Suppose that (so ). Then

This contradiction shows that there is no such x, so 25 does not have a multiplicative inverse mod 30.

The previous method still has its limitations, as you can see by trying to use it to find . And as you saw, some elements don't have multiplicative inverses mod n. The following theorem says which elements have multiplicative inverses, and how to find them if they exist.

Theorem. m has a multiplicative inverse mod n if and only if .

Proof. Suppose m has a multiplicative inverse mod n. This means that for some a. Then

Hence, .

Conversely, if , then

Reducing mod n, I get , which means that m has a multiplicative inverse mod n.

As the proof shows, you can find by applying the Extended Euclidean algorithm to a and n.

Example. ( Finding elements which have multiplicative inverses) Which elements of have multiplicative inverses mod 12?

The numbers in which are relatively prime to 12 and 1, 5, 7, and 11. Hence, 1, 5, 7, and 11 have multiplicative inverses mod 12.

Example. Find .

Apply the Extended Euclidean Algorithm to 61 and 47:

Write the linear combination, then reduce mod 61:

Hence, .

Proposition. If , then

Proof. Write

Then

(Notice that and are integers, since and .) Now divides the right side, but it's relatively prime to . Therefore, it must divide k:

Hence,

Therefore, .

Notice that you "divide the equality" by c, but you divide the modulus by .

Example. ( Solving a congruence with cancellation) Solve

By the previous result, if I "cancel" the factors of 6, I must divide the modulus by . This makes the modulus 19:

Now , so I can solve this congruence by multiplying by . Noting that , I see that I need to multiply by 10:

(If you didn't see that by trial, you'd use the Extended Euclidean algorithm as before.)

The original congruence was mod 38, so I want all solutions in the range . I have one: . To get others, I add multiples of 19 until I exceed 37. Thus, is the other solution.

All together, the solutions are and .

Example. ( A congruence with no solutions) Show that the following congruence has no solutions:

Suppose that x is a solution. Multiply the equation by 7:

This contradiction shows that the equation has no solutions.

These examples show that linear congruences may have solutions or may be unsolvable. We can understand better what is happening by relating them to linear Diophantine equations.

Contact information


text:
# Chapter 6.2. Nested Loops – Exam Problems

In the previous chapter we got familiar with nested loops and to use them drawing different kinds of figures on the console. We learned how to print different size figures, inventing an appropriate logic to construct them using single and nested for loops in combination with various calculations and program logic:

for (int row = 1; row <= 5; row++) {
System.out.print("*");
for (int col = 1; col < 5; col++) {
System.out.print(" *");
}
System.out.println();
}

We also declared our method repeatStr(…) which helps us to print a given symbol (or a series of characters) a certain number of times:

## Exam Problems

Let's solve several nested loops related exam problems to practice what we have learned so far and to develop our further algorithmic thinking.

### Problem: Draw a Fort

Write a program that reads from the console an integer n and draws a fortress with width 2 * n columns and height n rows like the examples below. The left and right columns on the inside are n / 2 wide.

### Input Data

The input is an integer n in the range of [3 … 1000].

### Output Data

Print on the console n text rows, depicting the fortress, exactly like the examples.

### Sample Input and Output

Input Output Input Output
3 /^\/^\
|    |
\_/\_/
4 /^^\/^^\
|      |
|      |
\__/\__/
Input Output Input Output
5 /^^\__/^^\
|        |
|        |
|   __   |
\__/  \__/
8 /^^^^\____/^^^^\
|              |
|              |
|              |
|              |
|              |
|     ____     |
\____/    \____/

### Hints and Guidelines

From the problem statement, we see that the input data will be one line only containing an integer within the range [3 … 1000]. Therefore, we will use a variable of type int.

Once we have declared and initialized the input data, we need to divide the fort into three parts:

• roof
• body
• base

We can see from the examples that the roof is made of two towers and a middle part. Each tower has a beginning /, a middle part ^, and an end \.

 \ is a special symbol in Java. Using it in the System.out.println(…) method, the console will not print it. That's why using \\ we instruct the console that we want to print exactly this symbol, without being interpreted as a special one (it is shielded- this is called “character escaping”).

The size of the middle part is n / 2, therefore we can write this value in a new variable. It will store the size of the middle part of the tower.

Now we declare a second variable, where we will store the value of space between the the two towers. The middle roof part has size of 2 * n - 2 * colSize - 4.

To print the roof on the console, we will use our repeatStr(…) method, which accepts two parameters (string, int) and concatenate a certain symbol (or series of characters) n times.

The fort body contains a beginning |, a middle part (white space), and an end |. The middle part is a blank space with a size of 2 * n – 2. The number of rows used for walls could be found by the given parameters - n - 3.

To draw the last row, which is a part of the base, we need to print the beginning |, the middle part (white space)_(white space), and an end |. To do this, we can use the declared colSize and midSize variables, because we can see from the examples that they are equal to the _ symbol in the roof.

We add to the values of the blank spaces + 1 because we have one blank space more in the examples.

The fort’s base structure is the same as the roof one. It is made of two towers and a middle part. Each tower has a beginning \, a middle part _, and an end /.

### Testing in The Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#0.

### Problem: Butterfly

Write a program that reads an integer n from the console and draws a butterfly with 2 * n - 1 columns width and 2 * (n - 2) + 1 rows height as in the examples below. Its left and right sides are n – 1 wide.

### Input Data

The input is an integer n in the range of [3 … 1000].

### Output Data

Print 2 * (n - 2) + 1 text lines, representing the butterfly on the console, just like in the examples.

### Sample Input and Output

Input Output Input Output
3 *\ /*
  @
*/ \*
5 ***\ /***
---\ /---
***\ /***
    @
***/ \***
---/ \---
***/ \***
Input Output
7 *****\ /*****
-----\ /-----
*****\ /*****
-----\ /-----
*****\ /*****
      @
*****/ \*****
-----/ \-----
*****/ \*****
-----/ \-----
*****/ \*****

### Hints and Guidelines

From the problem statement, we see that the input data will be read from only one line, which will contain an integer in the range [3 … 1000]. For this reason, we will use a variable of type int.

We can divide the figure into 3 parts - upper wing, body, and lower wing. To draw the upper wing, we need to divide it into parts - a beginning *, a middle part \ / and an end *. After looking at the examples we can say that the beginning has size n - 2.

We also see that the upper wing of the butterfly is of size n - 2, so we can make a loop that iterates halfRowSize times.

From the examples, we can notice that on an even row we have a beginning -, a middle part \ / and an end *, and on an odd line - a beginning *, a middle part \ / and an end -. Therefore, we need to do an if-else condition to check whether the line is even or odd and print one of the two types of lines accordingly.

To create the body of the butterfly, we can use again the halfRowSize variable and print exactly one line on the console. The body structure has a beginning (white space), a middle @, and an end (white space).

It remains to print the lower wing on the console, which is identical to the upper wing.

### Testing in The Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#1.

### Problem: Stop

Write a program that reads an integer n from the console and draws a STOP warning sign with size as in the example below.

### Input Data

The input is an integer N in the range of [3 … 1000].

### Output Data

Print text lines on the console depicting the STOP warning sign, just as in the examples below.

### Sample Input and Output

Input Output Input Output
3 ...._______....
...//_____\\...
..//_______\\..
.//_________\\.
//___STOP!___\\
\\___________//
.\\_________//.
..\\_______//..
6 ......._____________.......
......//___________\\......
.....//_____________\\.....
....//_______________\\....
...//_________________\\...
..//___________________\\..
.//_____________________\\.
//_________STOP!_________\\
\\_______________________//
.\\_____________________//.
..\\___________________//..
...\\_________________//...
....\\_______________//....
.....\\\___________//.....
Input Output
7 ........_______________........
.......//_____________\\.......
......//_______________\\......
.....//_________________\\.....
....//___________________\\....
...//_____________________\\...
..//_______________________\\..
.//_________________________\\.
//___________STOP!___________\\
\\___________________________//
.\\_________________________//.
..\\_______________________//..
...\\_____________________//...
....\\___________________//....
.....\\_________________//.....
......\\_______________//......

### Hints and Guidelines

From the problem statement, we see that the input data will be read from only one line which contains an integer in the range of [3 … 1000]. Therefore, we will use a variable of type int.

We can divide the figure into 3 parts - upper, middle, and lower. The upper part consists of two sub-parts - an initial line and lines in which the character expands. The start row is composed of a beginning ., a middle part _ and an end .. After looking at the examples we can say that the beginning is of size n + 1 and it is better to separate this value into a separate variable.

We need to create a second variable in which we will store the value of the middle of the initial row and is of size 2 * n + 1.

Once we have declared and initialized the two variables, we can print the start line to the console. Let's not forget to pass a new line to the console with System.out.println(…).

To draw the lines where the sign is getting "wider", we have to create a loop, that iterates n number of times. The structure of a line consists of a beginning ., // + middle part _ + \\, and an end .. To be able to reuse the created variables, we need to decrease the dots by 1 and the underscores by 2, because we have already printed the first row and the dots and underscores in the next line of the figure decrease.

At each subsequent iteration the beginning and the end decrease with 1, and the middle part increases by 2.

The middle part of the figure has a beginning // + _, a middle part STOP! and an end _ + \\. The count of the underscores _ is (underscores - 5) / 2.

The lower part of the figure where the sign decreases can be done by creating a loop again, which iterates n number of times. The structure of a single line is a beginning . + \\, a middle part _ and an end // + .. The number of the dots in the first iteration of the loop should be 0 and increase by one on each subsequent iteration. Therefore, we can say that the size of the dots in the lower part of the figure is equal to i.

For our program to work properly, we need to reduce the number of i by 2 at each iteration of the loop.

### Testing in The Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#2.

### Problem: Arrow

Write a program that reads an odd integer n from the console and draws a vertical arrow pointing down, with dimensions as in the examples below.

### Input Data

The input is an odd integer number n in the range of [3 … 79].

### Output Data

Print a vertical arrow on the console with "#" (hash) outlining the arrow and "." outlining the rest.

### Sample Input and Output

Input Output Input Output
3 .###.
.#.#.
##.##
.#.#.
..#..
5 ..#####..
..#...#..
..#...#..
..#...#..
###...###
.#.....#.
..#...#..
...#.#...
....#....
Input Output
9 ....#########....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
....#.......#....
#####.......#####
.#.............#.
..#...........#..
...#.........#...
....#.......#....
.....#.....#.....
......#...#......
.......#.#.......
........#........

### Hints and Guidelines

From the problem condition, we see that the input data will be read from only one line which contains an integer in the range of [3 … 79]. Therefore, we will use a variable of type int.

We can divide the figure into 3 parts - upper, middle, and lower. The upper part consists of two subparts – the initial row and the arrow body. From the examples, we see that the number of the outer dots in the initial row and in the arrow body are (n - 1) / 2. We can store this value in an outerDots variable.

The number of the internal dots in the arrow body is (n - 2). We need to create a variable named innerDots, which will store this value.

We can see from the examples the structure of the initial line. We must use the outerDots and n variables declared and initialized by us to print the starting row. We must remember that we have to move to a new line with System.out.println();.

To draw on the arrow's body on the console, we have to create a loop, which iterates n - 2 times.

The middle part of the figure consists of a beginning #, a middle part . and an end #. We see from the examples that the number of the # is equal to outerDots increased by 1 and that is why we can use the same variable again.

To draw the arrow’s lower part, we need to assign new values to the variables outerDots and innerDots.

The loop, we are going to make must iterates n - 2times and we need to print the last row of the figure separately. On each iteration outerDots increase by 1, and innerDots decrease by 2.

The last row of our figure is made of a beginning ., a middle part #, and an end .. The number of the . is equal to outerDots.

### Testing in The Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#3.

### Problem: Axe

Write a program that takes as an input an integer n and draws an axe with size as shown below. The axe is 5 * N columns wide.

### Input Data

The input is an integer n in the range of [2..42].

### Output Data

Print on the console an axe, exactly like the examples.

### Sample Input and Output

Input Output Input Output
2 ------**--
------*-*-
*******-*-
------***-
5 ---------------**--------
---------------*-*-------
---------------*--*------
---------------*---*-----
---------------*----*----
****************----*----
****************----*----
---------------*----*----
--------------********---
Input Output
8 ------------------------**--------------
------------------------*-*-------------
------------------------*--*------------
------------------------*---*-----------
------------------------*----*----------
------------------------*-----*---------
------------------------*------*--------
------------------------*-------*-------
*************************-------*-------
*************************-------*-------
*************************-------*-------
*************************-------*-------
------------------------*-------*-------
-----------------------*---------*------
----------------------*-----------*-----
---------------------***************----

### Hints and Guidelines

To solve the problem, we first need to calculate the dashes on the left, the middle dashes, the dashes on the right, and the whole length of the figure.

Once we have declared and initialized the variables, we can begin drawing the figure by starting with the upper part. From the examples, we can figure out the structure of the first row, and create a loop that iterates n number of times. At each iteration, of the loop the middle dashes increase by 1, and the dashes on the right decrease by 1.

To be able to reuse the created variables when drawing the axe’s handle, we need to decrease the middle dashes by 1 and increase the dashes on the right by 1.

We can draw the handle of the axe by iterating the loop n - 2 times. From the examples we can understand what its structure is.

The lower part of the figure we have to divide into 2 subparts - the head of the axe and the last row of the figure. We will print the axe’s head on the console by creating a loop that repeats n / 2 - 1 number of times. At each iteration the dashes on the left and the dashes on the right decrease by 1, and the middle dashes increase by 2.

For the last row of the figure, we can use the three declared and initialized variables leftDashes, middleDashes, rightDashes again.

### Testing in The Judge System

Test your solution here: https://judge.softuni.org/Contests/Practice/Index/658#4.


text:
# Silence is Golden

Status
Not open for further replies.

#### saffyangelis

##### Bandwidth Angel
*thinks I can't! He's being all kitty like. He'll turn the puppy-dog eyes on me!*

#### saffyangelis

##### Bandwidth Angel
He'll attack me if I stop! He's vicious!!!

·

#### loveofreason

##### echoes through time
Have you tried telepathic communication to preserve the silence?

Or maybe just stroke his tummy 'til he's he's in a trance before you slip quietly away?

#### saffyangelis

##### Bandwidth Angel
italics = telepathic

I am trying that, that's why I keep stroking him.

*pets Melkor*

#### loveofreason

##### echoes through time
Maybe a hammer between the eyes?

#### saffyangelis

##### Bandwidth Angel
*twitches*

Very tempting, but I'm being responsible.

No killing for a month.

#### loveofreason

##### echoes through time
A month! Oh Saffy!

Can you, er... hire an assassin?

#### saffyangelis

##### Bandwidth Angel
still not responsible....

*sighs* but after the month, I get to be able to kick people and stuff in the IRC chat.

#### Ogion

##### Paladin of Patience
So you think talking telepathically would be better? It is not silence after all.

And nobody is admiring my near-empty post...

#### Melkor

##### *Silent antagonist*
-Curls himself around Saffys hand and purrs in a content manner-

#### Fukyo

##### blurb blurb
I wonder if he has fleas...

#### loveofreason

##### echoes through time
What about worms?Or rabies?

#### Melkor

##### *Silent antagonist*
-Unfolds his velvet wings in indignation-

#### loveofreason

##### echoes through time
Oooo - nice kitty.....

Shit!

#### Melkor

##### *Silent antagonist*
Mriaow?

-Looks at Fukyo carefully-

#### loveofreason

##### echoes through time
No swearing in the sanctum thank you Miss Fukyo.

May I examine your hand a minute?

*cuts a vein in Fukyo's wrist, fills a bowl with blood and puts it down on the polished floor for the temple kitty*

*bandages Fukyo*

Thanks! Enjoy your meditations!

#### NoID10ts

##### aka Noddy
No swearing in the sanctum thank you Miss Fukyo.
Shit, really. How the fuck does someone curse in a silent place anyway? No talking, goddamnit!

Shhhhhhhhhhhhhhhhhhhhhh.

#### Melkor

##### *Silent antagonist*
-Mews contently and leaps down to lap up the blood-

#### Fukyo

##### blurb blurb
*is angry because lor gave Melkor her blood*

#### loveofreason

##### echoes through time
See how much he enjoys it Fukyo? Doesn't that make you feel all warm and fuzzy?

#### Melkor

##### *Silent antagonist*
-Sings a whiny cat song-

#### Fukyo

##### blurb blurb
See how much he enjoys it Fukyo? Doesn't that make you feel all warm and fuzzy?

Actually now that you mention it I am feeling kinda funny,and my vision's getting fuzzy...my...my limbs feel heavy...I-I need to lay down a bit...Just how much blood did you gave hi-

*passes out on the floor*

#### loveofreason

##### echoes through time
Hey Kitty! Fukyo flesh!

Mmmm.... is warm.....

*at least it's quiet now...

#### Melkor

##### *Silent antagonist*
Mriaow?

Tries to climb over Fukyo's body, but finds it incredibly difficult-

#### saffyangelis

##### Bandwidth Angel
*lifts Melkitty onto Fukyo*

good kitty. Clever kitty.

*pets Melkitty*

#### loveofreason

##### echoes through time
*writes an ode to the temple Melkitty... mostly composed of silence....*

#### Melkor

##### *Silent antagonist*
-gorges on the Fukyo sacrifice with little kitty claws-

#### Fukyo

##### blurb blurb
*wakes up due to pain,grabs Melkor by the throath and flings him off her*

#### Melkor

##### *Silent antagonist*
-Is flung afar with a 'nyyyaaaaaaaaa....' and is bashed off the altar in patheic floppy manner'

#### Kuu

*while google earth-ing over the netherlands, a title catches his eye... THIS*

#### Zezon Vice

##### Member
*thinks* "i more associated silence with black as i prefer black to gold." >.> *paints a megaphone gold* "there now apparently thats equal to silence right?"

#### sagewolf

*Stretches out, curls up, and takes a snooze*

-.-
-.^

-.-

(.... ?)

#### saffyangelis

##### Bandwidth Angel
*pokes Sage, passing little notes saying 'Jesin is a bully'*

#### sagewolf

*reads note, gets up, and duct-tapes Jesin to bannister rail, not forgetting to gag her to preserve the silence*

*lies back down*

^o^ Yawn.

O*O

-.-

zzzzzzz.........

#### Auburn

##### Luftschloss Schöpfer
~~~~~~~~~~~~~~~~~~~~~

*Click*

Standby Mode

?

#### Kuu

*sneaks behind Cinna and smothers him with a pillow*

#### Chronomar

##### NOPE
what??? I didn't even say anything!!!!!!!

...

well. now I did. bastard.

...tricking me. How evile.

#### sybyll

##### Member
*sits against a wall and enjoys not talking*

#### bdubs

##### Active Member
*Begins studying chemistry in a corner. The silence is only broken by rapid page turning.*

#### Chimera

##### To inanity and beyond
..
......
......................
......................................
......................................
................................................
..
................
....................
......
.................... ..............
......................
......
.
..

...

#### cheese

##### Prolific Member
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah
blah blah blah blah blah blah blah blah blah blah blah blah blah blah blah

*enjoys the peace of drivel*

Status
Not open for further replies.


text:
RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Forthcoming papers Archive Impact factor Guidelines for authors License agreement Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Trudy MIAN: Year: Volume: Issue: Page: Find

 Tr. Mat. Inst. Steklova, 2016, Volume 292, Pages 209–223 (Mi tm3700)

Algebras of general type: Rational parametrization and normal forms

V. L. Popov

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia

Abstract: For every algebraically closed field $\boldsymbol k$ of characteristic different from $2$, we prove the following: (1) Finite-dimensional (not necessarily associative) $\boldsymbol k$-algebras of general type of a fixed dimension, considered up to isomorphism, are parametrized by the values of a tuple of algebraically independent (over $\boldsymbol k$) rational functions of the structure constants. (2) There exists an “algebraic normal form” to which the set of structure constants of every such algebra can be uniquely transformed by means of passing to its new basis—namely, there are two finite systems of nonconstant polynomials on the space of structure constants, $\{f_i\}_{i\in I}$ and $\{b_j\}_{j\in J}$, such that the ideal generated by the set $\{f_i\}_{i\in I}$ is prime and, for every tuple $c$ of structure constants satisfying the property $b_j(c)\neq 0$ for all $j\in J$, there exists a unique new basis of this algebra in which the tuple $c'$ of its structure constants satisfies the property $f_i(c')=0$ for all $i\in I$.

 Funding Agency Grant Number Russian Science Foundation 14-50-00005 This work is supported by the Russian Science Foundation under grant 14-50-00005.

DOI: https://doi.org/10.1134/S0371968516010131

Full text: PDF file (260 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics, 2016, 292, 202–215

Bibliographic databases:

ArXiv: 1411.6570
Document Type: Article
UDC: 512

Citation: V. L. Popov, “Algebras of general type: Rational parametrization and normal forms”, Algebra, geometry, and number theory, Collected papers. Dedicated to Academician Vladimir Petrovich Platonov on the occasion of his 75th birthday, Tr. Mat. Inst. Steklova, 292, MAIK Nauka/Interperiodica, Moscow, 2016, 209–223; Proc. Steklov Inst. Math., 292 (2016), 202–215

Citation in format AMSBIB
\Bibitem{Pop16} \by V.~L.~Popov \paper Algebras of general type: Rational parametrization and normal forms \inbook Algebra, geometry, and number theory \bookinfo Collected papers. Dedicated to Academician Vladimir Petrovich Platonov on the occasion of his 75th birthday \serial Tr. Mat. Inst. Steklova \yr 2016 \vol 292 \pages 209--223 \publ MAIK Nauka/Interperiodica \publaddr Moscow \mathnet{http://mi.mathnet.ru/tm3700} \crossref{https://doi.org/10.1134/S0371968516010131} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3628462} \elib{http://elibrary.ru/item.asp?id=25772721} \transl \jour Proc. Steklov Inst. Math. \yr 2016 \vol 292 \pages 202--215 \crossref{https://doi.org/10.1134/S0081543816010132} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000376271200013} \elib{http://elibrary.ru/item.asp?id=27155746} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84971201948}

• http://mi.mathnet.ru/eng/tm3700
• https://doi.org/10.1134/S0371968516010131
• http://mi.mathnet.ru/eng/tm/v292/p209

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. Vik. S. Kulikov, E. I. Shustin, “On $G$-Rigid Surfaces”, Proc. Steklov Inst. Math., 298 (2017), 133–151
•  Number of views: This page: 127 Full text: 3 References: 35 First page: 4