text:
Search for a tool
Matrix Product

Tool to calculate matrix product algebra. The matrix product consists of the multiplication of matrices.

Results

Matrix Product -

Tag(s) : MATRIX

dCode and you

dCode is free and its tools are a valuable help in games, puzzles and problems to solve every day!
You have a problem, an idea for a project, a specific need and dCode can not (yet) help you? You need custom development? Contact-me!

Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best Matrix Product tool. Thank you.

This page is using the new English version of dCode, please make comments !

# Matrix Product

## Matrix Product

### Alphabet

Tool to calculate matrix product algebra. The matrix product consists of the multiplication of matrices.

## Answers to Questions

### How to multiply 2 matrices?

Consider $$M_1=[a_{ij}]$$ a matrix of $$m$$ lines and $$n$$ columns and $$M_2=[b_{ij}]$$ a matrix of $$n$$ lines and $$p$$ columns. The matrix product $$M_1.M_2 = [c_{ij}]$$ is a matrix of $$m$$ lines and $$p$$ columns, with: $$\forall i, j : c_{ij} = \sum_{k=1}^n a_{ik}b_{kj}$$

$$\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 \times 1 + 2 \times 0 & 1 \times 0 + 2 \times 1 \\ 3 \times 1 + 4 \times 0 & 3 \times 0 + 4 \times 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$$

The order of the operands matters with matrix computations, so $$M_1.M_2 \neq M_2.M_1$$

### How to multiply a matrix by a scalar?

The product of the matrix $$M=[a_{ij}]$$ by a scalar $$\lambda$$ is a matrix of the same size than the initial matrix M, with each items of the matrix multiplied by $$\lambda$$. $$\lambda M = [ \lambda a_{ij} ]$$

### What are matrix multiplication properties?

Associativity : $$A \times (B \times C) = (A \times B) \times C$$

Distributivity : $$A \times (B + C) = A \times B + A \times C$$

$$(A + B) \times C = A \times C + B \times C$$

$$\lambda (A \times B) = (\lambda A) \times B = A \times (\lambda B)$$

### How to multiply 2 matrices of incompatible shapes?

There is a matrix product compatible with any matrix sizes: the Kronecker product.

## Source code

dCode retains ownership of the source code of the script Matrix Product. Except explicit open source licence (indicated Creative Commons / free), any algorithm, applet, snippet, software (converter, solver, encryption / decryption, encoding / decoding, ciphering / deciphering, translator), or any function (convert, solve, decrypt, encrypt, decipher, cipher, decode, code, translate) written in any informatic langauge (PHP, Java, C#, Python, Javascript, etc.) which dCode owns rights can be transferred after sales quote. So if you need to download the Matrix Product script for offline use, for you, your company or association, see you on contact page !

## Questions / Comments

Team dCode read all messages and answer them if you leave an email (not published). It is thanks to you that dCode has the best Matrix Product tool. Thank you.

Source : http://www.dcode.fr/matrix-multiplication
© 2017 dCode — The ultimate 'toolkit' to solve every games / riddles / geocaches. dCode

format: plain


text:
# Codes for Distributed Storage: The repair problem

The first two talks in this session

Explicit and Optimal Exact-Regenerating Codes for the Minimum-Bandwidth Point in Distributed Storage by K. V. Rashmi , Nihar B. Shah , P. Vijay Kumar , Kannan Ramchandran

and

A Flexible Class of Regenerating Codes for Distributed Storage by Nihar B. Shah, K. V. Rashmi, P. Vijay Kumar

where given by Vijay Kumar.  To summarize the results in these two papers (and also

Exact-Repair MDS Codes for Distributed Storage Using Interference Alignment

by Changho Suh and Kannan Ramchandran

that appeared in another session), it is useful to briefly explain the current landscape of the repair problem:

(for more information see the Distributed storage wiki and this survey paper which however do not contain these new results yet.)

Assume a file to be stored, of size $B$ (sometimes also found as $\mathcal{M}$ in the literature) one can use an $(n,k)$ MDS code for storage with maximum reliability: just cut the file into $k$ packets of size $B/k$, encode into $n$ pieces (of the same size $\alpha=B/k$ ) and store each packet into a storage node. The reliability achieved is that any $k$ storage nodes contain enough information to recover the file, which is the best possible. So we can tolerate any $n-k$ failures without losing data. But most of the time we only have one failure. We then want to repair this failure by creating a new encoded packet by communicating as little information as possible from $d$  surviving storage nodes. There are two cases:

1. If we ask that the new packet still forms a good code (i.e. any $k$ out of the new $n$ nodes suffice to recover), the problem is called functional repair and is completely solved and equivalent to multicasting.  The minimum repair bandwidth can be determined by a cut-set bound and we will refer to the achievable region as the cut-set region.

2. If we ask that the new packet formed is exactly identical to the lost one: This problem is called exact repair and is very difficult. It is equivalent to a multicasting network coding problem with intermediate nodes having requests for subsets and therefore prior tools from network coding do not suffice. The repair problem seems close to locally decodable codes but this connection has not been investigated yet.

The amount of information communicated from $d$ surviving nodes is called the repair bandwidth $\gamma=d\beta$. Another issue is that one can reduce this repair bandwidth if the storage per node $\alpha$ is allowed to increase and there is a tradeoff involved.

The two most important points of this tradeoff are called Minimum Storage point (MSR)  (where $\alpha=B/k$ corresponds to MDS codes) and Minimum Bandwidth point (MBR) (where $\alpha$ is larger but the repair bandwidth is minimized).

Clearly exact repair is a strictly harder than functional repair and the cut-set region is still a valid outer bound. A substantial amount of recent work has been focused on understanding the communication required for exact repair. All the results here establish that the cut-set region is achievable for exact repair for the parameters discussed.

Vijay presented a storyline that concluded to the settings which were known before.

This paper had completely solved the problem for the Minimum Bandwidth (MBR) point, for any $(n,k)$, but fixing $d=n-1$.

The first paper (Explicit and Optimal Exact-Regenerating Codes for the Minimum-Bandwidth Point in Distributed Storage) in this session established that the MBR cut-set bound point can be achieved with exact repair for any $d$, corresponding to an arbitrary number $d\leq n-k$ of failed nodes. The second result in this paper is that all the other interior points of the tradeoff curve (except the points of minimum repair and minimum storage) cannot be achieved with linear codes for exact repair. ( Of course this does not preclude the possibility that they can be approached infinitely close by making the code packets smaller and smaller).

In the second paper A Flexible Class of Regenerating Codes for Distributed Storage, the authors generalize the requirements of the distributed storage system: the initial requirement was that any data collector who connects to any $k$ storage nodes (and receives all their stored data ) obtains enough information to recover the file. Here the authors want to enable data collectors who have limited communication with each storage node to reconstruct the file. The only requirement is that the total amount of information communicated is sufficient. This is, of course, a harder requirement on the storage code and the authors characterize the repair bandwidth for functional repair under this new requirement of flexible recovery. The technical part involves graph theoretically bounding the flow for these flexible information flow graphs. The question of exact repair of these flexible regenerating codes naturally arises and it seems to me that previous exact regenerating code constructions do not immediately generalize.

Finally, in another session was the closely related paper

Exact-Repair MDS Codes for Distributed Storage Using Interference Alignment

by Changho Suh and Kannan Ramchandran

Changho presented two new results: both are for the minimum storage point (MSR) and hence correspond to results for MDS codes.

One is that for the low-rate regime $k/n \leq 1/2$ if the number of nodes helping for the repair is sufficiently large $d \geq 2k-1$,  the MSR cut-set point can be achived for exact repair. For this regime the paper presents explicit code constructions that use a small finite fields and build on this paper which established similar results but only when repairing systematic nodes (and not nodes storing parities).

The second result of this paper closes the open problem of MSR exact repair for the high-rate $k/n\geq 1/2$ regime. The paper uses the symbol extension technique introduced in the Cadambe-Jafar paper Interference Alignment and the Degrees of Freedom for the K User Interference Channel to MDS codes that asymptotically approach the cut-set bound.

This paper appeared simultaneously with

Distributed Data Storage with Minimum Storage Regenerating Codes – Exact and Functional Repair are Asymptotically Equally Efficient, by Viveck R. Cadambe, Syed A. Jafar, Hamed Maleki,

Which independently obtain very similar results using the same technique. Note that the symbol extension approach requires vector linear network coding (sub-packetization of each stored packet) and to approach the cut-set bound an enormous amount of subpacketization (and field size) seem to be required. I think it is correct to interpret these results as existence proofs of high-rate regenerating codes approaching the cut-set bound for exact repair, rather than explicit constructions.

I think that the applicability of interference alignment to problems that seem to have nothing to do with wireless channels is quite remarkable. Another related case is the paper

Network Coding for Multiple Unicasts: An Interference Alignment Approach

by A. Das, S. Vishwanath, S. Jafar, A. Markopoulou.

I will blog my notes on this paper (hopefully) soon. Are the slides available anywhere? I took pictures of slides from other talks but my camera run out of battery.

This site uses Akismet to reduce spam. Learn how your comment data is processed.


text:
[This article was first published on Statistical Reflections of a Medical Doctor » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

The Bayesian counterpart to the frequentist analysis of the Randomized Controlled Trial is in many aspects more straightforward than the Bayesian analysis. One starts with a prior probability about the probability of a patient being assigned to each of the three arms and combines it with the (multinomial) likelihood of observing a given assignment pattern in the 240 patients enrolled in the study. Bayes theorem gives the posterior probability quantifying our belief about the magnitudes of the unknown assignment probabilities. Note that testing the strict equality is bound to lead us straight to the arms of the Lindley paradox so that a different approach is likely to be more fruitful. Specifically, we specify a maximum tolerable threshold for the difference between the maximum and the minimum probability of being assigned the trial arms (let’s say 1-5%) and we directly calculate the probability for this difference (“probability of foul play”).

In the absence of prior evidence for (or against) foul play we use a non-informative prior in which all possible values of assignment probabilities are equally plausible. This (Dirichlet) prior corresponds to a prior state of knowledge in which three individuals were randomized and all three ended up in different treatment arms. Under this prior, the posterior distribution is itself a Dirichlet distribution with parameters equal to the number of individuals actually assigned to each arm+1. The following R code may then be used to calculate the probability of foul play, as previously defined i.e.

 event<-c(105,70,65)
set.seed(1234);
r<-rdirichlet(10000,event+1);
res0<-mean(apply(r,1,function(x,tol)
I(abs(max(x)-min(x))<=tol),0.01))
res0*100

This probability comes down to 0.4% which is numerically close to the frequentist answer, yet with a more intuitive interpretation: based on the observed trial sizes and a numerical tolerance for the maximum tolerable difference in assignment probability the odds for “foul play” are 249:1.
Increasing the tolerance will obviously decrease these odds, but in such a case we would be willing to tolerate larger differences in assignment probabilities. Although these results are mathematically trivial (and non-controversial), the plot will become more convoluted when one proceeds to use them to make a declaration of “foul play”. For in that case, a decision needs to be made which has to consider not only the probability of the uncertain events: “foul play” v.s. “not foul play” but also the consequences for the journal, the study investigators and the scientific community at large. At this level one would need to decide whether the odds of 249:1 are high enough or not for subsequent action to be taken. But this consideration will take us to the realm of decision theory (and it already 11pms).

To leave a comment for the author, please follow the link and comment on their blog: Statistical Reflections of a Medical Doctor » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

# Never miss an update! Subscribe to R-bloggers to receive e-mails with the latest R posts.(You will not see this message again.)

Click here to close (This popup will not appear again)


text:
## Elementary and Intermediate Algebra: Concepts & Applications (6th Edition)

$-\dfrac{7}{4}$
Interchanging the numerator and the denominator, then the reciprocal of the given expression, $-\dfrac{4}{7}$, is \begin{array}{l}\require{cancel} -\dfrac{7}{4} .\end{array}


text:
# Create a Tag field using Django-Select2.

The excellent framework – Select2, have had support for tags for a long time, but Django-Select2 lacked that, until now (version 4.2.0).

Tag fields are very much like any multiple value input field except that it allows users to enter values which does not exist in the backing model. So, that the users can add new tags.

For this purpose few new fields have been added to Django-Select2. They all have the suffix – TagField. Few widgets too have been added to auto configure Select2 Js to run in “tagging mode”.

You can see the full reference in docs – http://django-select2.readthedocs.org/en/latest/ref_fields.html and http://django-select2.readthedocs.org/en/latest/ref_widgets.html.

## Simple tag field implementation example

You can find this code in testapp too.

models.py:-

class Tag(models.Model):
tag = models.CharField(max_length=10, unique=True)

def __unicode__(self):
return unicode(self.tag)

class Question(models.Model):
question = models.CharField(max_length=200)
description = models.CharField(max_length=800)
tags = models.ManyToManyField(Tag)

def __unicode__(self):
return unicode(self.question)

forms.py:-

class TagField(AutoModelSelect2TagField):
queryset = Tag.objects
search_fields = ['tag__icontains', ]
def get_model_field_values(self, value):
return {'tag': value}

class QuestionForm(forms.ModelForm):
question = forms.CharField()
description = forms.CharField(widget=forms.Textarea)
tags = TagField()

class Meta:
model = Question

Above I am trying to create a form which the website users can use to submit questions. Things to note in TagField is that it is almost like we use any other AutoModel fields in Django-Select2, except that here we override one new method get_model_field_values().

When users submit a tag field, the usual validation runs, but with a twist. While checking if the provided value exists, if it is found not to exist then the field, instead of raising error, creates that value. However, the library does not know how to create a new value instance, hence it invokes create_new_value() to do that job.

Model version of the tag field already knows that it is dealing with Django models so it knows how to instantiate that, but does not know what values to set for the attributes. So it implements create_new_value() which in-turn invokes get_model_field_values() to get required attribute names mapped to their values.

## Before you continue

One key thing to remember is that unlike other widgets, you ideally should not be using tag widgets with normal Django fields. Django fields do not allow creation of a new choice value. However, if you want tagging support but do not want to allow users to create new tags then you can very much use the tag widget here and pair it up with normal Django fields. However, that may not be a good idea, since then UI would still allow creation of new tags, but on submit the user would get an error.

## Making it better

We can make this better and interesting. A typical tagging system should have the following features.

• Ability to detect misspellings. Peter Norvig’s essay on this is excellent. More information can be found on Stack Overflow.
• Use statistics to order the results. This very much useful when the tag counts ballon up. The statistics could be based on how many tags are frequently used together. Of course when you start a site you would not have any data, in that case for a period of time you can set the algo to only learn.
• Cache frequently used tags. This is a normal optimization technique which is frequently used. A memcache like layer is usually used to cache the DB data, and if the data is not found there, then a DB hit is made.
8 Responses to “Create a Tag field using Django-Select2.”
1. David Miller says:

I’m new to this so I have a question about this TagField that may seem basic. In my application, each Tag belongs to a specific User so I don’t want to return the list of all Tags, I want to apply a “user” filter to the list of Tags.

queryset = Tag.objects

I’d like to do something like this –

queryset = Tag.objects.filter(user=user)

I can’t seem to figure out how to do it. How would I add filters to the queryset? Is there a tag equivalent to the “ModelSelect2MultipleField” field (because I’ve figured out how to apply a filter to that field)?

Thanks for the help.

• Tag extends ModelMultipleChoiceField. So I guess in this case you need to define your own queryset property getter. In the getter return queryset which is limited to this user.

• David Miller says:

I have no idea how to do that. Would you be kind enough to send me sample code that adds a getter for the above example. I’m not sure what to do from here.

• David Miller says:

I was able to do this and it worked:

self.fields[‘tags’] = TagField(
required=False,
queryset=Tag.objects.filter(model=self.model)\
.order_by(‘name’))

However, I don’t know how to pass the additional “model” field in get_model_field_values(self, value) so I’m getting this error when I save my form:

null value in column “model_id” violates not-null constraint

Any idea how to pass an extra value when saving a new Tag?

• In Tag fields you are required to override get_model_field_values(). Here you return all the fields and their values in a map. These will be used to create a new tag instance.

• David Miller says:

How do I add the model field and its value into get_model_field_values()? I tried this and it didn’t work.

class TagField(AutoModelSelect2TagField):
queryset = Tag.objects
search_fields = [‘name__icontains’, ]
def get_model_field_values(self, value, model):
return {‘name’: value, ‘model’, model}

—-in form—-
self.fields[‘tags’] = TagField(
queryset=Tag.objects.filter(model=self.model),
model=self.model)

2. Ed says:

Hi!
models.py:
—-
from django.contrib.postgres.fields import ArrayField

class Tag(models.Model):
slug = models.CharField(max_length=40, primary_key=True, blank=True)
name = models.CharField(max_length=40, db_index=True)


text:
PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

Volume 35, Number 2, April–June, 1999
Back to contents page

CONTENTS

On the Sphere-Packing Bound, Capacity, and Similar Results for Poisson Channels
M. V. Burnashev and Yu. A. Kutoyants
pp. 95–111

Abstract—A new approach to obtaining upper bounds on the capacity and reliability function of a Poisson channel is suggested. It is based on a new sphere-packing bound for the error probability. A strong conversion of the coding theorem is also proved.

Efficient Conversion of Random Sequences into Equiprobable and Independent Sequences
B. Ya. Ryabko and E. P. Machikina
pp. 112–116

Abstract—We consider the problem of efficient conversion of sequences generated by an arbitrary Bernoulli source into sequences of independent and equiprobable symbols. This problem was previously considered by J. von Neumann, P. Elias, etc. For the proposed method based on the Elias algorithm, the memory used and the time required for processing one symbol is exponentially smaller than for previously known algorithms.

On the Hamming Bound for Nonbinary Localized-Error-Correcting Codes
R. Ahlswede, L. A. Bassalygo, and M. S. Pinsker
pp. 117–124

Abstract—For nonbinary codes it is proved that the Hamming bound is asymptotically sharp in some range of the code rate.

The Berlekamp–Massey Algorithm over a Finite Commutative Ring
V. L. Kurakin
pp. 125–135

Abstract—An algorithm for finding a monic polynomial of the least degree that generates a given sequence of length $\ell$ over a finite commutative ring $R$ with identity is presented. The complexity of the algorithm is $O(\ell^2)$ operations in $R$ as $\ell\to\infty$.

A Statistical Approach to Some Inverse Problems for Partial Differential Equations
G. K. Golubev and R. Z. Khas'minskii
pp. 136–149

Abstract—Some inverse problems for the Laplace equation and heat-conduction equation are considered. The solutions of these equations are assumed to be observed under the Gaussian white noise of low intensity. The problem consists of the renewal of the unknown smooth boundary conditions or initial conditions from the solution observed against a noise background. It is shown that the minimax estimates of the second order are linear for low spectral density of the noise.

Nonparametric Estimation of Linear Functionals of the Regression Function for a Known Conditional Distribution of the Observation Noise
Yu. I. Pastukhova
pp. 150–157

Abstract—For the case where an observation plan is given and the distribution function of the additive noise of observations is known, we obtain a nonparametric estimate of linear functionals of the regression function. This estimate asymptotically attains the minimax bound of risks for the quadratic loss function.

Nonstationary Time Series with a Close Alternative Hypothesis: Locally Asymptotic Distribution of the Likelihood Ratio
P. Boulongne, K. A. Ol'shanskii, and V. I. Piterbarg
pp. 158–165

Abstract—Within the framework of the autoregressive model, we solve the problem of testing the hypothesis of the existence of the unit root of the characteristic polynomial against a close alternative hypothesis of this root to come infinitesimally close to unity. The asymptotic distribution of the likelihood ratio is calculated. This distribution is found to be substantially dependent on the information amount of the innovation noise distribution.

Large-Deviation Principle for Conditional Distributions of Diffusion Processes
M. L. Kleptsyna and A. P. Serebrovski
pp. 166–171

Abstract—The large-deviation principle for measures corresponding to marginal conditional distributions of diffusion processes is considered.

Universal Graph Model of Cyclic Networks and Their Reliability
A. A. Chernyak
pp. 172–179

Abstract—In the present paper, we extend the domination theory to cyclic monotone graphs, which are a universal graph model for the analysis of complex-structured system reliability. In particular, we derive a formula for calculating the reliability of arbitrary monotone graphs, which reduces the system level of reliability analysis to the element level. As a corollary, we prove that for any fixed integer $k$ the problem of calculating the reliability of monotone graphs of degree $k$ can be solved in a time that polynomially depends on the dimension of graphs and the number of their acyclic monotone subgraphs. At the same time, we show that the reliability determination problem is NP-hard even in the class of acyclic $dc$-trivial monotone graphs of degree $2$ with the number of minimal acyclic subgraphs being proportional to the graph vertex number.

Variance of the Number of Departed Messages in a Simple Queueing System
A. I. Ovseevich
pp. 180–185

Abstract—We study a simple queueing facility consisting of two servers in tandem, separated by a finite buffer. The servers are independent and their sequences of up/down modes are Bernoullian. The input flow is deterministic (one new message per time unit). We compute explicitly the coefficient $A$ in the asymptotics ${\bf D}(T)\sim AT$ of the covariance of the number of departed messages per interval $[0,T]$.

Computer Logic in Information Processes
N. A. Kuznetsov and V. A. Lyubetsky
pp. 186–189


text:
# Pseudogap of liquid Tl 2 Te

@article{Cutler1974PseudogapOL,
title={Pseudogap of liquid Tl 2 Te},
author={M. Cutler},
journal={Physical Review B},
year={1974},
volume={9},
pages={1762-1776}
}
• M. Cutler
• Published 1974
• Physics
• Physical Review B
• Analysis of experimental curves for the electrical conductivity $\ensuremath{\sigma}$ and thermopower $S$ of ${\mathrm{Tl}}_{x}{\mathrm{Te}}_{1\ensuremath{-}x}$ alloys near the composition ${\mathrm{Tl}}_{2}$Te has yielded a quantitative description of the pseudogap. A model expressed in terms of two bands with a negative temperature coefficient for the band gap has been fitted with parameters which yield very good agreement with the experimental curves. The theoretical expressions for $S$ and… CONTINUE READING
6 Citations


text:
# HEP Experiment-Theory DESY Pizza seminar

chaired by , , , , , , ,
Wednesday, August 7, 2019 from to (Europe/Berlin)
at Seminar Room 3 (DESY)
 Description The goal of this new seminar series is to foster discussion and exchange between the various high energy physics groups at DESY. Specifically, we are trying to enhance the exchange between the experimental and theory community, with in-depth talks about a specific topic in a more informal setting. We will order pizza (vegetarian and meat options with cheese) to eat for lunch. In order to have a better estimate of how many people come, please click on the "Apply here" link below. We will collect 5 Euros from every participant who registers and wants to eat some pizza. If you have any specific food requirements (vegan, gluten free, etc.) please let us know in advance and we will see what we can do. If a reference paper exists, we will link it from the page and encourage you to read it before the seminar. In order to plan for future seminars we appreciate your input. Please add any topic suggestions you would find interesting to hear about in the google doc below. Participants Daniela Boerner; Yu-Heng Chen; Sam Cunliffe; Christophe Grojean; Sarah Heim; Beate Heinemann; Dirk Kruecker; Jan Kuechler; Valerie Lang; Mareike Meyer; Johannes Michel; Paul Moder; Riccardo Nagar; Abtin Narimani; Navid Rad; Othmane Rifki; Jordi Sabater; Christian Oliver Sander; Lais Schunk; Claudia Seitz; Rickard Ström; Frank Tackmann; Jim Talbert; Hamish Teagle; Emily Thompson; Fang-Ying Tsai; Janik von Ahnen; Chaowaroj (Max) Wanotayaroj; Alicia Wongel Material:
Go to day
• Wednesday, August 7, 2019
• 11:45 - 12:15 Searches for invisible Higgs decays in the VBF channel with ATLAS 30'  Speaker: Dr. Othmane Rifki (DESY) Material: Paper


text:
## UVA Problem 10432 – Polygon Inside A Circle Solution

UVA Problem 10432 – Polygon Inside A Circle Solution:

Solving Technique:

This is a rather easy geometry / computational geometry problem. Given the radius of a Circumscribed circle and count of sides of a polygon the task is to find the area of the polygon. A Circumscribed circle is a circle that passes through all vertices of a plane figure and contains the entire figure in its interior.

The formula below can be written into a single formula by combining all the formulas. More information and the combined formula can be found here.

##### Visual Explanation:

I have tried to explain the concept below using figures. They are not drawn to scale. The small circles represent intersection point between polygon vertices and the circumscribed circle.

##### Example:

It is an example with radius, r = 2 and sides, n = 8.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

2 2000
10 3000

Output:

12.566
314.159

### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10432 - Polygon Inside A Circle
* Technique: circumcircle Or, Isocele Area calculation.
*/

#include<stdio.h>
#include<string.h>
#include<math.h>

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

double r;
int n;

while( scanf( "%lf%d", &r, &n ) == 2 ){

// Angle between each two points for every point.
double PHI = ( double ) 360 / n ;

// For each Isosceles in the polygon the angle between the base and radius.
double THETA = (double) 90 - ( PHI / 2 );

// Convert Degree angle to Radian to use in code.
double THETA_RADIAN = THETA * M_PI / 180;

//  a is base.
double a = 2 * r * cos( THETA_RADIAN );

// H is the height.
double h = r * sin( THETA_RADIAN );

// S represent Area of a single segment.
double S = (a * h) / 2;

// S * n is the are of complete polygon.
printf("%.3lf\n",  S * n );

}

return 0;
}

## UVA Problem 11716 – Digital Fortress Solution

UVA Problem 11716 – Digital Fortress Solution:

Solving Technique:

This is an easier string problem. The task is to arrange the characters within the string in a certain order.

If the input string length is not square of a number then print INVALID. Ex: “DAVINCICODE” has length of 11. Squaring no number results in 11.

“DTFRIAOEGLRSI TS” has length of 16 including the space character. Square root of 16 is 4 and 4 * 4 is 16. So this is valid input.

Now if the input is valid then next task is to rearrange them. Instead of following given solution technique in the question it can solved much faster in another way. Following instruction in the question gives intuition that first the string must be positioned on 2 dimensional matrix in row major order. Then traverse them column by column.

A better way is find out each group length from square rooting the original string length. Next starting from first group take a character then skip by group length to get next column major character. After its done do this from the next character of first group.

##### Visualization:

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

3
WECGEWHYAAIORTNU
DAVINCICODE
DTFRIAOEGLRSI TS

Output:

WEAREWATCHINGYOU
INVALID
DIGITAL FORTRESS

### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 11716 - Digital Fortress
* Technique: Square String Traverse from row major
*            to column major by skipping.
*/

#include<stdio.h>
#include<string.h>
#include<math.h>

#define N 10002
static char s[N];
static char output[N];

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int n;
scanf("%d", &n);
getchar();

while( n-- ){
gets(s);

// Get the length of string and length of each string group.
int len = strlen(s);
int rc = sqrt(len);

// Reset in case there are characters from previous iteration.
memset(output, 0, sizeof output);

// If the string length can be divided into equal parts
// then traverse by skipping certain length.
if( rc * rc == len ){

int k = 0;

for( int j = 0; j < rc; ++j ){
for( int i = j; i < len; i = i + rc ){
output[k++] = s[i];
}
}

puts(output);

}
else{
puts("INVALID");
}

}

return 0;
}

## UVA Problem 913 – Joana and the Odd Numbers Solution

UVA Problem 913 – Joana and the Odd Numbers Solution:

Solving Technique:

Todo:
1. Reorganize.
2. check for mistakes.

This problem can be solved in quite a few ways. Brute force won’t work. I have given the brute force code anyway. It will give correct answer from 1 < n < 199999999 but the requirement is 1 < N < 1000000000, which is way way larger.

Another approach is to do mathematical calculation to come up with a formula to solve this. Multiple formula can be generated such as a single formula or, one formula complementing other or, multiple formula's combined. I have provided two formula in the codes below.

One thing to mention, the output or input must be long long data type. Other data types will give incorrect output.

Unfortunately I won’t be elaborate more than this. It took 5 pages to solve this many way with proof, but that’s a lot to write. I will try to explain a way for coming up with these formula.

##### The brute force way:

A simple way to do this is, for values greater than 1 set offset 10 and start multiplying with 5. For each step increase offset by 4 and add value to previous multiplying value.

Input -> Sum

3 -> 3 * 5
5 -> 3 * 15, [ 15 = 5 + 10 ]
7 -> 3 * 29, [ 29 = 15 + 14 ]
9 -> 3 * 47, [ 47 = 29 + 18 ]
11 -> 3 * 69, [ 69 = 47 + 22 ]
13 -> 3 * 95, [ 95 = 69 + 26 ]

Although this approach will not work since the range is huge. It is possible to pre-calculate for a certain range and anything outside that calculate with formula.

##### Trying to Come up with a Closed Form Expression:

First thing is to notice is that the numbers differ by 2 and are odd. So, if the first number is n, then the sum of n and next two numbers is,

$n + ( n + 2 ) + ((n + 2) + 2) = n + n + 2 + n + 4 = 3n + 6$

Ex:
If n was 67, then result of 3n + 6 = 207.

The opposite is also true. For example, given sum of three numbers we can find the first number by,
if sum was 141 then,

$3n + 6 = 141 => n = 45$

Expanding and writing the sequence in format below,

###### Input – Values in the Row(Last three numbers bracketed) – Sum
1 - [ 1 ] - 1
3 - [ 3 5 7 ] - 15
5 - 9 11 [ 13 15 17 ] - 45
7 - 19 21 23 25 [ 27 29 31 ] - 87
9 - 33 35 37 39 41 43 [ 45 47 49 ] - 141
11 - 51 53 55 57 59 61 63 65 [ 67 69 71 ] - 207
13 - 73 75 77 79 81 83 85 87 89 91 [ 93 95 97 ] - 285

This means for a given value there are that many numbers in that row.

##### Trying to come up with a Brute Force Approach:

This is extra and not required to solve this problem but it will understand creation of the formula.

The first numbers of every row can be generated and memoized in a table sequentially using the formula below,
row – number break down – first number

1 -> 1 -> 1
3 -> 1 + ( 1 * 2 ) -> 3
5 -> 3 + ( 3 * 2 ) -> 9
7 -> 9 + ( 5 * 2 ) -> 19
9 -> 19 + ( 7 * 2 ) -> 33

Let n1 be equal to 1 and n2, n3 …, nk be next generated sequences. So the formula is,
n1 = n1
n2 = n1 + (1 * 2)
n3 = n2 + (3 * 2)
n4 = n3 + (5 * 2)
n5 = n4 + (7 * 2)
……………..
……………..
nk = n(k-1) + (i * 2)

this can be converted to an algorithm,
Let, T be table to store value of the first number.
n1 = 1
T[n1] = n1

i = 3

for i to size
T[i] = T[i-2] + (i-2) * 2
increment i by two
End

#### Generating Solution From the Output:

Similarly, The sum can also be calculated in terms of input by creating a sequence and finding out the formula.

1 -> 1
3 -> 15
5 -> 45
7 -> 87
9 -> 141
11 -> 207
13 -> 285

when they are written in a sequence,

1 + 15 + 45 + 87 + 141 + 207 + 285 + …………..

So, for 11 the output should be 207. The formula can be calculated from the picture above

207 = 141 + 66
207 = 141 + (54 + 12)
207 = 141 + ((12 * 5) – 6 + 12)
207 = 141 + ((12 * 6) – 6)
207 = 87 + 54 + ((12 * 6) – 6)
207 = 87 + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 45 + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 15 + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 1 + ((12 * 2 – 6) – 4) + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = (12 * 2 – 6) + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6) – 3

this can be written as summation formula,

$-3 + \sum_{i = 2}^{ceil( \frac{n}{2} )} 12i - 6$

this can be rewritten as,
$-3 + 6 * \sum_{i = 2}^{ceil( \frac{n}{2} )} 2i - 1$

The input for this formula is the input for the program,
for, n = 17 the sum of last three numbers should be 477.
Setting n = 17 in following the formula it will give,

-3 + 6 * ( 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 ) = 477

The formula above doesn’t quite work out for 1. Although we know for 1 output is 1 but it should be included in the formula. Expanding and changing values the summation will get the formula for all values.

Similarly, this is the formula to calculate the first number to sum from a row. It was calculated making a sequence of first summing numbers and find out the the summation formula,

First number,
$N = 3 + 2 * \sum_{i = 2}^{floor( \frac{n}{2} )} 2i + 1$

Separating the summation,
$\sum_{i = 2}^{floor( \frac{n}{2} )} 2i + 1 = 2 * \sum_{i = 2}^{floor( \frac{n}{2} )} i + \sum_{i = 2}^{floor( \frac{n}{2} )} 1$

$= 2 * ( \sum_{i = 1}^{floor( \frac{n}{2} )} i - \sum_{i = 1}^{ 1 } i ) + \sum_{i = 1}^{floor( \frac{n}{2} )} 1 - \sum_{i = 1}^{ 1 } 1$

$= 2 * \sum_{i = 1}^{floor( \frac{n}{2} )} i - 2 + \sum_{i = 1}^{floor( \frac{n}{2} )} 1 - 1$

$= floor( \frac{n}{2} ) ( floor( \frac{n}{2} ) + 1 ) + floor( \frac{n}{2} ) - 3$

I won’t simplify anymore.

Put the value of summation in the equation,
$N = 3 + 2 * \sum_{i = 2}^{floor( \frac{n}{2} )} 2i + 1$
because i only expanded the summation. Multiply result with 2 and add 3 to get the first number.

From, the equation above place the value of first number in 3n + 6 to get the summation of last three numbers for a given number.

The 3n + 6 and the summation formula can be combined into a single formula.

#### Generating Solution based on First Number of Last Three:

Similarly the first number to sum from every row can be calculated. If the first number from every row are written in a sequence,

1 + 3 + 13 + 27 + 45 + 67 + ………………..

The first number can be generated following this,

For input n = 11, task is to generate first number from the graphical representation above. Then the value can be placed in equation, 3N + 6 to generate sum of that value and next two (basically the answer).

67 = 45 + 22
67 = 45 + ( 18 + 4 )
67 = 45 + ( 14 + 4 + 4 )
67 = 45 + ( 10 + 4 + 4 + 4 )
67 = 45 + ( 10 + 4 + 4 + 4 )
67 = 27 + 18 + ( 10 + 4 + 4 + 4 )
67 = 27 + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 13 + 14 + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 13 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 3 + 10 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 3 + 10 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )

this way the formula can be,

$First \ number = 3 + \sum_{i = 1}^{ floor( \frac{n}{2} - 1 ) } 10 + \sum_{i = 1}^{ floor( \frac{n}{2} - 2 ) } 4i$

$First \ number = 3 + 10 * \sum_{i = 1}^{ floor( \frac{n}{2} - 1 ) } 1 + 4 * \sum_{i = 1}^{ floor( \frac{n}{2} - 2 ) } i$

$First \ number = 3 + 10 * ( floor( \frac{n}{2} ) - 1 ) + 2 * ( floor( \frac{n}{2} ) - 2 ) * ( floor( \frac{n}{2} ) - 1 )$

This can be further simplified.

For n = 15 the first number should be 123. Setting n = 15 in equation above,

first number = 3 + 10 * ( 7 – 1 ) + 2 * ( 7 – 2 ) * ( 7 – 1 )
first number = 3 + 60 + 60 = 123

That’s it. There are other approaches but it will take a long time to write.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

3
5
7

Output:

15
45
87

### Formula Generate sequence sum, first number & sum Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 913 Joana and Odd numbers
* Technique: Generate Sequence Sum, First number
*            then generate sum of next numbers
*            including the generated number.
*/

#include<stdio.h>
#include<string.h>

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

long long n;

while( scanf("%lld", &n) == 1 ){

long long m = n >> 1;

long long part = ( (n * (n + 1)) >> 1 ) - ( m * ( m + 1 ) ) - 4;

long long firstNum = 2 * part + 3;

printf("%lld\n", 3 * firstNum + 6);

}

return 0;
}

### Reduced Formula Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 913 Joana and Odd numbers
* Technique: Reduced formula.
*/

#include<stdio.h>
#include<string.h>

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

unsigned long long n;

while( scanf("%lld", &n) == 1 ){

long long ans =  3 * ( (n + 1) * ( n - (n >> 1) ) )  - 9;

printf("%lld\n", ans);
}

return 0;
}

### Brute Force Code( Won’t be Accepted ):

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 913 - Joana and the odd numbers
* Technique: Brute Force. Won't get Accepted.
*            This is just for demonstration. This
*            won't get accepted due to huge size that
*            array can't process. But it will give correct
*/

#include<stdio.h>
#include<string.h>

#define N 100000000
//#define M 1000000000

static long long value[N];

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

value[0] = 1;
value[1] = 15;
long long offset = 30;

for( long long i = 2; i < N; ++i ){
value[i] = value[i-1] + offset;
offset = offset + 12;
}

long long n;
while( scanf("%lld", &n) == 1 ){
printf("%lld\n", value[n/2] );
}

return 0;
}

## UVA Problem 10106 – Product Solution (Lattice Multiplication)

UVA Problem 10106 – Product Solution:

Solving Technique:

This problem is quite simple. Given two very large integers multiply them and print them. By large I mean almost 251 characters long for this problem. So string or character array must be used.

This problem can solved in many ways Big Integer, FFT, Grade School etc. But I have implemented lattice multiplication / Chinese multiplication to solve this problem.

Code Explanation:

The code below requires quite a bit of polish to understand easily ( A lot other post require the same. Maybe I will update this post sometimes in future or not. ).

This code is not quite space efficient. I have used several arrays to make it easy to understand but all of the tasks below can be done using the large array. Also the running time can further be improved to $O(m*n)$ instead of $O(n^2)$. Where, m and n are length of two arrays and they may not be equal in size.

I have provided some graphical representations below to make it easier to understand.

This is an example of how the multiplication works in this code. As mentioned above the process can be sped up using rectangular matrix instead of square if the length is not equal.

This is a representation of how the table / square matrix is filled for further processing.

Multiplication starts with the last character of string 1 and proceeds to first character. For string 2 multiplication starts from the first character till last character. This way each character from string 1 and string 2 is first converted to a digit, then they are multiplied. If the result is two digits it is divided by 10.

The remainder is written as the lower left portion ( indicated by lower in the structure ) and the quotient is written as the upper left portion ( indicated by upper in the structure ).

This is graphical representation of how the structure is traversed. If you have trouble understanding how the recursive function traversing the structure, then take a look at UVA problem 264 – Count the Cantor Solution. The traversal is somewhat similar to that and I have provided explanation int that post.

Rest is explained in the code comments.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

12
12
2
222222222222222222222222

Output:

144
444444444444444444444444

### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   Lattice Multiplication.
* Technique: High precision large number multiplication.
*            Structure array representing upper left and
*            and lower right corner in single cell.
*/

#include<stdio.h>
#include<string.h>

#define M 260

int N;

// Assuming both strings are of same length.
struct multiplicationTable{
int upper;
int lower;
};
struct multiplicationTable node[M][M];

static char string1[M];
static char string2[M];

// stores the diagonal sums;
int sum;

// decides whether to get the upper or lower
// value based on even or odd.
int m;

int recursiveAdder( int i, int j ){

// Termination condition.
if( j < 0 || i >= N )
return sum;

int val;

// Whether to get the upper left corner or
// the lower right corner.
if( m % 2 ){
val = node[i][j].upper;
j = j - 1;
}
else{
val = node[i][j].lower;
i = i + 1;
}
++m;

// store the sum of the whole diagonal.
sum = sum + val;

// recursively visit all row ans column
// diagonally ( at least on pen and paper format ).
// actually moves more like the snake in the snakes game.

return sum;
}

// Debug.
// Print the matrix showing the multiplications.
// Please note left and right directions may be different.
void printMultiplicationMatrix(){

printf("\n\n");
for( int i = 0; i < N; ++i ){
for( int j = N - 1; j >= 0; --j )
printf("%d,%d, ", node[i][j].upper, node[i][j].lower );
printf("\n");
}

}

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

while( gets(string1) ){
gets(string2);

int len1 = strlen(string1);
int len2 = strlen(string2);

// Fix length if both string are not equal size.
if( len1 > len2 ){
N = len1;

int shiftWidth = len1 - len2;

for( int i = len1 - 1; i >= 0; --i )
string2[i + shiftWidth] = string2[i];

for(int j = 0; j < shiftWidth; ++j)
string2[j] = '0';

}
else if(len2 > len1){
N = len2;

int shiftWidth = len2 - len1;

for( int i = len2 - 1; i >= 0; --i )
string1[i + shiftWidth] = string1[i];

for(int j = 0; j < shiftWidth; ++j)
string1[j] = '0';

}
else N = len1;

//printf("%s \n%s \n", string1, string2);

int k = N - 1;

// Multiply the numbers digit by digit and set in the lattice.
for( int i = 0; string2[i]; ++i ){
for( int j = 0; string2[j]; ++j ){

int num1 = string1[k] - '0';
int num2 = string2[j] - '0';

int multiply = num1 * num2;

node[j][k].upper = multiply / 10;
node[j][k].lower = multiply % 10;

}
--k;
}

//printMultiplicationMatrix();

// Lattice is divided into two parts upper left half and
// lower right half.

// result of upper half
int upperHalfResult[N];

int i = N - 1;
for(; i >= 0; --i){
sum = 0;
m = 1;
}

// result of upper half
int lowerHalfResult[N];

i = 0;
for(; i < N; ++i){
sum = 0;
m = 0;
lowerHalfResult[i] = recursiveAdder(i, N - 1);
}

// Combine upper and lower left half to a single array to fix addition
// problems.
int combinedRawResult[N + N];
i = 0;
for(; i < N; ++i )
combinedRawResult[i] = upperHalfResult[i];
for(k = 0; i < N + N; ++i, ++k )
combinedRawResult[i] = lowerHalfResult[k];

// If a cell has more than 9 then it should be added to the next cell.
for( int i = N + N - 1; i >= 0; --i ){

if( combinedRawResult[i] > 9 ){
combinedRawResult[i - 1] = combinedRawResult[i - 1] + combinedRawResult[i] / 10;
combinedRawResult[i] = combinedRawResult[i] % 10;
}

}

for(i = 0; i < N + N; ++i)
if(combinedRawResult[i]) break;

// print if the result can be printed or its zero.
bool zero = true;
for(; i < N + N; ++i){
printf("%d", combinedRawResult[i]);
zero = false;
}

// If the result is zero.
if( zero )
printf("0");

printf("\n");

}

return 0;
}

## UVA Problem 12646 – Zero or One Solution

UVA Problem 12646 – Zero or One Solution:

Solving Technique:

The input is all possible combination of 3 bits. If A, B, C are thought as bits then possible binary combination are,

$000 \rightarrow * \\ 001 \rightarrow C \\ 010 \rightarrow B \\ 011 \rightarrow A \\ ---- \\ 100 \rightarrow A \\ 101 \rightarrow B \\ 110 \rightarrow C \\ 111\rightarrow * \\$

This problem can be solved in multiple ways such as using string, checking equality, performing xor equality etc. My code below is exactly same as equality checking but it perform xor operation between them.

XOR Table,

$\begin{tabular}{l*{6}{c}r} X & Y & X XOR Y \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{tabular}$

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

1 1 0
0 0 0
1 0 0

Output:

C
*
A

### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 12646 - zero or one
* Technique: XOR Bits to check equality.
*/

#include<stdio.h>

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int A, B, C;
while( scanf("%d%d%d", &A, &B, &C) == 3 ){

if( !( A ^ B ) && !( A ^ C ) )
putchar('*');
else{
if( A ^ B ){
if( B ^ C )
putchar('B');
else
putchar('A');
}
else
putchar('C');
}
putchar('\n');
}

return 0;
}

## Translating C Code to MIPS Code to Machine Language with Machine Instruction in Binary and Hex Format

The code won’t be exactly translated to MIPS code but similar code is written so the output is same as the c code.

#### C Code:

#include<stdio.h>

int main(){

int a = 2;

// Prints 20 in Hexadecimal which is equivalent to 32 in Decimal
printf("%x\n", a << 4);

return 0;
}

Let, $t0 represent a and$t1 represent the output value in Hex.

#### MIPS Code:

# This is Comment.
# $0 register is always 0. ori$t0, $0, 2 sll$t1, $t0, 4  The first line of of MIPS code is or immediate. It can be used to load the value 2 into register$t0. Any value or’ed with another value is the same value. Remember $t0 in represents a in the C Code above. The sll command shifts contents register$t0 by 4 bits. It is equivalent to, $t1 =$t1 << 4. 2 Shifted by 4 bits in decimal is 32 and in Hexadecimal is 20.

#### Machine Language:

Here the first line of MIPS code ori is I-Format and the second line of code sll is R-type / Format instruction.

##### Machine Instruction in Binary:

Since ori is an I type instruction it will have 4 fields. It has opcode, rs, rt and immediate. $t0 is numbered 8,$0 register is 0. Opcode for ori is 13.

 001101 00000 01000 0000000000000010 opcode rs rt immediate 6 bits 5 bits 5 bits 16 bits

In order to convert the binary to Hex format instruction make group in 4 bits.

##### Machine Instruction Bits in Group of four:
 0011 0100 0000 1000 0000 0000 0000 0010
###### 0x34080002

It matches the instruction in the pictures above. Look at the codes column.

##### Machine Instruction in Binary:

Since ori is an I type instruction it will have 6 fields. It has opcode, rs, rt, rd, shamt (shift amount) and funct. Here rs is not used so set to 0. $t0 to$t7 registers are numbered from 8 to 15. So $t0 is numbered 8,$t1 is 9. The Opcode for sll ( Shift Left Logical ) is 0 and funct ( function ) is also 0.

 000000 00000 01000 01001 00100 000000 opcode rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

In order to convert the binary to Hex format instruction again make group in 4 bits.

##### Machine Instruction Bits in Group of four:
 0000 0000 0000 1000 0100 1001 0000 0000
###### 0x00084900

Which again matches the instruction in the code column shown above.

## UVA Problem 10189 – Minesweeper Solution

UVA Problem 10189 – Minesweeper Solution:

Solving Technique:

Given a mine field that is a matrix / 2D array, produce an output that contains count of adjacent mines for each squares.

In a 2D array for each squares there are at most adjacent 8 squares. If the current position is i and j then,

$\begin{bmatrix} (i-1,j-1) & (i-1,j) & (i-1,j+1) \\ (i+0,j-1) & (i,j) & (i+0,j+1) \\ (i+1,j-1) & (i-1,j) & (i+1,j+1) \\ \end{bmatrix}$

Just traverse the matrix row-column wise and check its adjacent squares for getting mine count for current position. The adjacent squares check can be implemented with 8 if conditions for each one.

###### Here the arrow from the center shows where checking starts. The 1D arrays drow and dcol hold the row and column values the way shown above. It can be changed by modifying drow and dcol arrays.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

4 4
*...
....
.*..
....
3 5
**...
.....
.*...
0 0

Output:

Field #1:
*100
2210
1*10
1110

Field #2:
**100
33200
1*100

### Code Using Multiple if Conditions:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10189 - Minesweeper
* Technique: 2D Array / Matrix Boundary checking using
*            if conditions.
*/

#include<stdio.h>
#include<string.h>

#define MAXSIZE 101

static char MineField[MAXSIZE][MAXSIZE];

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int n, m;

int FieldNumber = 0;

while( scanf("%d%d", &n, &m), n ){

getchar();

for(int i = 0; i < n; ++i)
scanf("%s", &MineField[i]);

if( FieldNumber )
printf("\n");

for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){

if( MineField[i][j] == '*' )
continue;

int temp = 0;

if( i + 1 < n && MineField[i + 1][j] == '*' )
++temp;
if( i + 1 < n && j + 1 < m && MineField[i + 1][j + 1] == '*' )
++temp;
if( j + 1 < m && MineField[i][j + 1] == '*' )
++temp;
if( i - 1 >= 0 && j + 1 < m && MineField[i - 1][j + 1] == '*' )
++temp;
if( i - 1 >= 0 && MineField[i - 1][j] == '*' )
++temp;
if( i - 1 >= 0 && j - 1 >= 0 && MineField[i - 1][j - 1] == '*' )
++temp;
if( j - 1 >= 0 && MineField[i][j - 1] == '*' )
++temp;
if( i + 1 < n && j - 1 >= 0 && MineField[i + 1][j - 1] == '*' )
++temp;

MineField[i][j] = temp + '0';

}
}

printf("Field #%d:\n", ++FieldNumber);

for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j)
putchar(MineField[i][j]);
printf("\n");
}

}

return 0;
}

### Code Bound checking using Array & for Loop:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10189 - Minesweeper
* Technique: 2D Array / Matrix Boundary checking using
*            co-ordinate array and for loop.
*/

#include<stdio.h>
#include<string.h>

#define MAXSIZE 101

static char MineField[MAXSIZE][MAXSIZE];

// Co-ordinates / directions of adjacent 8 squares.
// W, SW, S, SE, E, NE, N, NW
static const int drow[] = {0, 1, 1, 1, 0, -1, -1, -1};
static const int dcol[] = {-1, -1, 0, 1, 1, 1, 0, -1};

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int n, m;

int FieldNumber = 0;

while( scanf("%d%d", &n, &m), n ){

getchar();

for(int i = 0; i < n; ++i)
scanf("%s", &MineField[i]);

if( FieldNumber )
printf("\n");

for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){

int temp = 0;

// If mine found do nothing.
if( MineField[i][j] == '*' )
continue;

// For each adjacent squares of the current square calculate mine count.
// and set the count in current square.
for(int k = 0; k < 8; ++k){

// Check if out of bound of the 2D array or matrix.
if( i + drow[k] < 0 || j + dcol[k] < 0 || i + drow[k] >= n || j + dcol[k] >= m )
continue;

// Check the appropriate co-ordinate for mine, if mine found increase count.
if( MineField[i + drow[k] ][j + dcol[k]] == '*' )
++temp;

}

// All adjacent squares checked set the mine count for current squares.
MineField[i][j] = temp + '0';

}
}

printf("Field #%d:\n", ++FieldNumber);

for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j)
putchar(MineField[i][j]);
printf("\n");
}

}

return 0;
}

## UVA Problem 11565 – Simple Equations Solution

UVA Problem 11565 – Simple Equations Solution:

## UPDATE:

As a commenter below pointed out the solution is wrong due to the fact I made some wrong assumptions. Kindly check other sources for correct solution. This was accepted due to weak test cases. Also check udebug for different test cases.

Problem Statement Description:

Given input of $A, B, C$ where $0 \leqslant A, B, C \leqslant 10000$ and three equations,

$\mathbf{ x + y + z = A }$
$\mathbf{ x.y.z = B }$
$\mathbf{ x^2 + y^2 + z^2 = C }$

The task is to find values of x, y, z where x, y, z are three different integers which is ( x != y != z ). Meaning x can not be equal to y, t can not be equal to z and z can not be equal to x.

The problem asks to output the least value of x then y then z meaning the output will be in x < y < z order.

#### Things to notice:

One very important thing to notice is that for all three equation the values of x, y, z can be interchanged and it will still satisfy the problem.

For example,
$\mathbf{ if, x = 5, y = 0, z = 9 }$

then it can also be written as,
$\mathbf{ x = 0, y = 5, z = 9 }$
$\mathbf{ x = 9, y = 5, z = 0 }$

etc. all possible combinations. But the problem asks for least value of x then y then z.

So if after calculation the result is x = 9, y = 0, z = 5 which is supposed to be x = 0, y = 5, z = 9. In that case the values can be sorted which will result in x = 0, y = 5, z = 9 and this still satisfies the equations.

#### Solution Technique Explanation:

The simple approach to solve this problem is try all possible combinations of x, y, z and see if it produces a correct result.

The values of x, y, z being negative also satisfies this problem. Forgetting the value of negatives for the moment and focusing on the positive values. To get the naive loop count limit see x or y or z can be at least 0 and at most 100.

Same goes for the negative portion so looping for -100 to 100 for each 3 nested loops seem easy ( I haven’t given the 3 nested loop solution here. It can be found on other sites ). So from -100 to 0 to 100 there are 201 number in between. So naive solution requires 201*201*201 which is more than 8 million (8120601). This program should do 117 * 45 = 5265 iterations per test case.

###### This problem can be solve much faster using some algebraic substitution. Notice,

$\mathbf{ x + y + z = A ........ (i) \\ }$
$\mathbf{ x.y.z = B ........ (ii) \\ }$
$\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) \\ }$

from equation (ii),

$\mathbf{ x.y.z = B }$

This can be rewritten as,

$\mathbf{ z = \frac{B}{x.y} ........ (iv) }$

from equation (i),

$\mathbf{ x + y + z = A }$

substituting value of z from (iv) to (i) gives,

$\mathbf{ x + y + \frac{B}{x.y} = A }$

This can be rewritten as,

$\mathbf{ \frac{B}{x.y} = A - x - y ........ (v) }$

similarly from (iii) and (iv),

$\mathbf{ x^2 + y^2 + z^2 = C }$

plugging in the value of z and solving for x and y,

$\mathbf{ x^2 + y^2 + ( \frac{B}{x.y} )^2 = C ........ (vi) }$

Now from (v) and (vi),
$\mathbf{ x^2 + y^2 + (A - x - y)^2 = C }$

Notice this equation above does not contain z. Now z can be calculated in terms of B, x, y.

This will completely remove one of the nested loops. Further improvements can be made by cutting down number of loop iterations.

###### Important point to notice that A, B, C can be at most 10000. Also x, y, z can differ by 1 and satisfy the equation. From above equations,

$\mathbf{ x + y + z = A ........ (i) }$
$\mathbf{ x.y.z = B ........ (ii) }$
$\mathbf{ x^2 + y^2 + z^2 = C ........ (iii) }$

So if x, y, z differ by 1 then,

$\mathbf{ y = x + 1 }$
$\mathbf{ z = x + 2 }$

from equation (i),

$\mathbf{ x + (x + 1) + (x + 2) = A }$

but A can be at most 10000.

$\mathbf{ x + (x + 1) + (x + 2) = 10000 }$
$\mathbf{ 3x + 3 = 10000 }$

So, x = 3332.3333….

But to keep it simple, notice the lower order term 3 does not make much difference. By setting x = y = z the equation can be,

$\mathbf{ x + x + x = 10000 }$
$\mathbf{ 3x = 10000 }$
$\mathbf{ x = 3333.3333.... }$

###### from equation (iii) since x is squared so it to get its iteration just calculate the square root. or, setting x = y = z and B = 10000 in equation (iii) gives,

$\mathbf{ x^2 + x^2 + x^2 = 10000 }$
$\mathbf{ 3x^2 = 10000 }$
$\mathbf{ x = 57.735.... }$

after rounding of,
x = 58

So the loop range for x is [-58…58].

###### Again from equation (ii) the iteration limit for y can be counted using x = y = z,

$\mathbf{ y.y.y = 10000 }$
$\mathbf{ y^3 = 10000 }$
$\mathbf{ y = 21.544.... }$

Rounded of to,
y = 22

So iteration limit for y will be from [-22…22].

Calculating using y + 1 result in rounded range [-21…21]. Although I have not tested it.

###### Doing further algebraic simplification will remove another loop as z can be calculated in terms of A,B,C using,

$\mathbf{ (A-z)^2 - 2.\frac{B}{z} = C - z^2 }$

where,

$\mathbf{ xy = \frac{B}{z} }$

and,

$\mathbf{ x + y = A - z }$

using the main equation above, the value of z can be found and by solving the other equations the values of x and y can be calculated.

Also the loops can be input dependent. If max of A, B, C is bigger than 58 than choose 58 other wise choose the max as the loop counter.

There may be more improvements possible but that’s all I can come up with now. One final improvement can be made by breaking from all loops at once once the values are found. Although goto isn’t recommended c++ doesn’t support label to break out of multiple loops unlike java.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

2
1 2 3
6 6 14

Output:

No solution.
1 2 3

### Optimized Code without goto:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 11565 - Simple Equations
* Technique: Mathematical elimination and substitution
*/

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

int n;
scanf("%d", &n);

int A, B, C;

while( n-- ){
scanf("%d%d%d", &A, &B, &C);

bool solutionFound = false;
int x, y, z;

for( x = -58; x <= 58; ++x ){
for( y = -22; y <= 22; ++y ){

if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

int temp = x * y;

if( temp == 0 ) continue;

z = B / temp;

if( z != x && z != y && x + y + z == A   ){
if(!solutionFound){
int tmpArray[3] = {x, y, z};
std::sort(tmpArray, tmpArray + 3);
std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

solutionFound = true;
break;
}
}

}
}
}

if(!solutionFound) std::cout << "No solution." << "\n";

}

return 0;
}

### Optimized Code without goto:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 11565 - Simple Equations
* Technique: Mathematical elimination and substitution
*/

#include<cstdio>
#include<algorithm>
#include<iostream>

int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

int n;
scanf("%d", &n);

int A, B, C;

while( n-- ){
scanf("%d%d%d", &A, &B, &C);

bool solutionFound = false;
int x, y, z;

for( x = -58; x <= 58; ++x ){
for( y = -22; y <= 22; ++y ){

if( x != y && ( (x * x + y * y) + (A - x - y) * (A - x - y) == C )  ){

int temp = x * y;

if( temp == 0 ) continue;

z = B / temp;

if( z != x && z != y && x + y + z == A   ){
if(!solutionFound){
int tmpArray[3] = {x, y, z};
std::sort(tmpArray, tmpArray + 3);
std::cout << tmpArray[0] << " " << tmpArray[1] << " " << tmpArray[2] << "\n";

solutionFound = true;
goto done;
}
}

}
}
}

if(!solutionFound) std::cout << "No solution." << "\n";
done:;

}

return 0;
}

## Digital Logic: Binary to Gray Code Converter

Before starting with this read Digital Logic: Designing Decimal to 4 bit Gray Code Converter if you are unfamiliar.

##### Binary, Decimal and Gray Code Table:

Here I am representing gray code bits with A, Decimal values with D and Binary bits with B.

 Binary Decimal Gray Code B3 B2 B1 B0 D A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 2 0 0 1 1 0 0 1 1 3 0 0 1 0 0 1 0 0 4 0 1 1 0 0 1 0 1 5 0 1 1 1 0 1 1 0 6 0 1 0 1 0 1 1 1 7 0 1 0 0 1 0 0 0 8 1 1 0 0 1 0 0 1 9 1 1 0 1 1 0 1 0 10 1 1 1 1 1 0 1 1 11 1 1 1 0 1 1 0 0 12 1 0 1 0 1 1 0 1 13 1 0 1 1 1 1 1 0 14 1 0 0 1 1 1 1 1 15 1 0 0 0
##### Binary to Gray Code Converter:

This same technique can be applied to make gray to binary converter. There will be 4 input bits, which represent binary and 4 output bits which represent equivalent gray code.

Since we are creating binary to gray code converter so, we need to find expressions for each gray code output in terms of input binary bits.

So, there will be four output bits $A_3, A_2, A_1, A_0$. For these output bits the input will be different combinations of $B_3, B_2, B_1, B_0$ based on minimized expression.

## A3:

Minimized expression from the above k map,
$A_3 = B_3$

## A2:

Minimized expression from the above k map,
$A_2 = B_3 \overline{B_2} + B_2 \overline{B_3}$

But, the expression of XOR Gate is (Let, A and B be the inputs),
$A.\overline{B} + B.\overline{A} = A \oplus B$
[Note: This is not related to this problem but, only showing how XOR can be made from And, Or, Not gates]

Similarly,it can be shown that,
$B_3 \overline{B_2} + B_2 \overline{B_3} = B_2 \oplus B_3$

If XOR gate is not available then the former expression can be used with and, or and not gates to design the gray code converter.

## A1:

Minimized expression from the above k map,
$A_1 = B_1 \overline{B_2} + B_2 \overline{B_1}$

Similarly,it can be shown that,
$B_1 \overline{B_2} + B_2 \overline{B_1} = B_1 \oplus B_2$

## A0:

Minimized expression from the above k map,
$A_0 = B_0 \overline{B_1} + B_1 \overline{B_0}$

Similarly,it can be shown that,
$B_0 \overline{B_1} + B_1 \overline{B_0} = B_0 \oplus B_1$

## Digital Logic: Designing Decimal to 4 bit Gray Code Converter

##### Gray Code:

Difference of gray code from binary is that, for each group only one bit changes when going from one number to the next. In case of binary it can be seen from the table that multiple bit may change when going from one number to next.

##### How to Create Gray Code Sequence:

There are multiple shortcut technique to write gray code. This is the technique I follow,

0
1

Next step, Add 0’s before both of them,

0 | 0
0 | 1

Next Mirror ( Write the values bottom to top instead of top to bottom ) all bits except for Left Most bit and Add 1’s in the place left most bit,

0 | 0
0 | 1
------> Mirror
1 | 1
1 | 0

Continuing this process again of adding 0’s before all numbers and Mirroring all bits except left most bit, then adding 1’s in place of left most bit,

0 | 0 0
0 | 0 1
0 | 1 1
0 | 1 0
-------> Mirror
1 | 1 0
1 | 1 1
1 | 0 1
1 | 0 0

Now following same procedure for 4 bits,

0 | 0 0 0
0 | 0 0 1
0 | 0 1 1
0 | 0 1 0
0 | 1 1 0
0 | 1 1 1
0 | 1 0 1
0 | 1 0 0
--------> Mirror
1 | 1 0 0
1 | 1 0 1
1 | 1 1 1
1 | 1 1 0
1 | 0 1 0
1 | 0 1 1
1 | 0 0 1
1 | 0 0 0

finally 4 bit gray code representing Decimal 0 to 15,

0 0 0 0
0 0 0 1
0 0 1 1
0 0 1 0
0 1 1 0
0 1 1 1
0 1 0 1
0 1 0 0
1 1 0 0
1 1 0 1
1 1 1 1
1 1 1 0
1 0 1 0
1 0 1 1
1 0 0 1
1 0 0 0

Now just start from the top with 0 and increment it by 1. That will be the decimal equivalent of the gray code.

##### Binary, Decimal and Gray Code Table:

Here I am representing gray code bits with A, Decimal values with D and Binary bits with B.

 Binary Decimal Gray Code B3 B2 B1 B0 D A3 A2 A1 A0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 2 0 0 1 1 0 0 1 1 3 0 0 1 0 0 1 0 0 4 0 1 1 0 0 1 0 1 5 0 1 1 1 0 1 1 0 6 0 1 0 1 0 1 1 1 7 0 1 0 0 1 0 0 0 8 1 1 0 0 1 0 0 1 9 1 1 0 1 1 0 1 0 10 1 1 1 1 1 0 1 1 11 1 1 1 0 1 1 0 0 12 1 0 1 0 1 1 0 1 13 1 0 1 1 1 1 1 0 14 1 0 0 1 1 1 1 1 15 1 0 0 0

##### Making Decimal to Gray Converter:

Since this is Decimal to Gray Code converter, the Binary part of the table could be omitted.

$A_3 = D_8 + D_9 + D_{10} + D_{11} + D_{12} + D_{13} + D_{14} + D_{15} \\ A_2 = D_4 + D_5 + D_6 + D_7 + D_8 + D_9 + D_{10} + D_{11} \\ A_1 = D_2 + D_3 + D_{4} + D_{5} + D_{10} + D_{11} + D_{12} + D_{13} \\ A_0 = D_1 + D_2 + D_5 + D_6 + D_9 + D_{10} + D_{13} + D_{14} \\$

Let,

$X_1 = D_4 + D_5 \\ X_2 = D_8 + D_9 \\ X_3 = D_{10} + D_{11} \\ X_4 = D_{12} + D_{13} \\ X_5 = X_2 + X_3 \\$

From the above expression,

$A_3 = X_2 + X_3 + X_4 + D_{14} + D_{15} \\ .... = X_5 + X_4 + D_{14} + D_{15} \\ \\ A_2 = X_1 + D_6 + D_7 + X_2 + X_3 \\ .... = X_1 + D_6 + D_7 + X_5 \\ \\ A_1 = D_2 + D_3 + X_1 + X_3 + X_4 \\ \\ A_0 = D_1 + D_2 + D_5 + D_6 + D_9 + D_{10} + D_{13} + D_{14} \\ \\$

##### Inputs and Outputs:

For the circuit there will be inputs each representing a decimal number. The number of outputs will be 4 from $A_3 \text{ to } A_0$ where, $A_0 \text{ is the LSB and } A_3 \text{ is the MSB}$.

##### How to test if its working:

Just press each buttons in the left one at a time then check to see if the values given match the value in table. The values are read bottom to top, equivalent to reading values from table left to right.

##### Circuit Diagram:

Download the file named 4 bit decimal to gray code converter circuit diagram from my Github.


text:
# If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$. [duplicate]

Edit: The $F$'s are Fibonacci numbers.

I need an idea on how to show the following:

If $m$ and $n$ are positive integers, then $(F_m,F_n)=F_{(m,n)}$.

I believe that using the fact that $F_{m+n}=F_mF_{n+1}+F_nF_{m-1}$ could come in handy. Moreover, Euclid's algorithm may as well be needed. But I am not certain, as there may be better methods to achieve this.

-

## marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); May 9 '15 at 15:09

What is $f_m$, $f_n$? – Daan Michiels Apr 25 '12 at 18:16
Hint. $F_{kn}$ is divisible by $F_n$ – Arturo Magidin Apr 25 '12 at 18:22
This is most probably a duplicate though I can't find the link right now. – lhf Apr 25 '12 at 18:23
Here is one answer: math.stackexchange.com/questions/60340/… – sdcvvc Apr 25 '12 at 18:30
Josué: The proof is induction on $n+m$, so this is inductive hypothesis you can assume. – sdcvvc Apr 25 '12 at 18:40

As noted in the comments by sdcvvc, this answer to an earlier question completely answers this question as well.

-