# Tag Info

3

If you do not not find a factor less than $\sqrt{x}$, then $x$ is prime for the following reason. Consider the opposite, you find two factors larger than $\sqrt{x}$, say $a$ and $b$. But then $a\cdot b> \sqrt{x}\sqrt{x} = x$. Therefore, if there is a factor larger than $\sqrt{x}$, there must also exist a factor smaller than $\sqrt{x}$, otherwise their ...

1

What you're describing is a prime-testing algorithm known as the sieve of Eratosthenes. It seems like you already understand the concept: Cross out $1$ Circle $2$ as the first prime, then cross out all of the multiples of $2$ in your list. The next not-crossed-out number is the next prime (in this case $3$). If your list has $N$ numbers, you only need ...

5

If a number $N$ has a prime factor larger than $\sqrt{N}$ , then it surely has a prime factor smaller than $\sqrt{N}$. So it's sufficient to search for prime factors in the range $[1,\sqrt{N}]$, and then use them in order to compute the prime factors in the range $[\sqrt{N},N]$. If no prime factors exist in the range $[1,\sqrt{N}]$, then $N$ itself is ...

0

You have a pointer $L$ to the beginning of the list. First, create a new pointer $R$ that also points to the beginning of the list. Now, traverse the list with $R$, looking for the struct with string $w$. While $R$ is traversing the list, you should also keep a count $p$ equal to how many elements $R$ has iterated over. When you find your the struct with ...

1

The second algorithm uses less space, but the first does fewer comparisons in general. In both algorithms you compare every node with alphabetically with the target until you find one that’s greater. In the second you also test each of those nodes except the last to see whether it has the desired property; in the first, however, you test only those back to ...

1

Well these two are not same. Consider the first step in Dijkstra. In Dijkstra, we start with the source, iterate over all the edges starting from source and select the edge with the lowest weight among them . So even though there exists a edge with a lesser wight between two vertices where none of them are the source, Dijkstra will not select that first. ...

0

As reply to @Roger's post I'm writing this answer. It's possible in $\mathcal{O}(\sqrt{n})$. In fact is will be just a little bit optimized brute-force algorithm. We should notice, if we found $d$, such that $\left(\nexists d' \in \mathbb{Z}\right) \left( 2 \leq d' <d \wedge d' \mid n \right) \Rightarrow d \in \mathbb{P}$ ($\mathbb{P}$ - set of prime ...

1

I have a solution that runs in O(n*log(log(n))). Don't worry about factoring n; you can do that indirectly. Here's a crude draft of the algorithm: 1: Run a prime number sieve such as the Sieve of Eratosthenes to generate a list of all prime numbers less than or equal to n. This is the step that takes O(n*log(log(n))) time. 2: Create a total counter that ...

0

Well, you're assigning to the variable $i$ the values from $1$ to $n$ -> $n$ steps assigning to the variable $\pi(i)$ the value $i$ for all $i$ -> $n$ steps assigning to the variable $i$ the value $n-1$ -> $1$ step so $2n+1$ assignments in total

2

I am turning my comment into an answer. RSA is secure under the RSA Assumption, which basically states that RSA is secure. This assumption is not known to be the same as the assumption that factorization is hard. While others have pointed out that factorization is sufficient to break RSA, it has not been proven that factorization is necessary to break RSA. ...

-1

The assumption in RSA is the hardness of computing $\phi(n)$ without knowing $p$ or $q$. Given an algorithm which takes $n$ and computes $\phi(n)$, we can factor $n$ using $\phi(n)$: $n = pq$ $\phi(n) = (p-1)(q-1) = pq-p-q+1 = n-\frac{n}{q}-q+1$ $q^2-(n-\phi(n)+1)q+n = 0$ $q = \frac{(n-\phi(n)+1)+\sqrt{(n-\phi(n)+1)^2-4n}}{2}$ $p = \frac{n}{q}$

-1

The general concept behind cryptography is the requirement that one operation takes a small amount of time, while undoing the same operation without a priori knowledge must take a large amount of time. The entire premise of RSA is the idea that the time complexity to multiply two numbers together is much lower than factoring a number into two numbers. Thus, ...

-1

I think the idea is this: the RSA algorithm is powerful because it relies on the fact that for large numbers, say numbers with 200 digits, it is very difficult to factor them or even find out if they are composite. If we were somehow able to figure a way to factor large numbers relatively easily, then the RSA algorithm would no longer be that powerful, thus ...

3

Define the polynomial $$f(x) = \sum_{i=0}^n(-1)^ie_i(c_1,2!c_2\ldots,n!c_n)x^{n-i}$$ where $e_i(c_1,2!c_2\ldots,n!c_n)$ are the elementary symmetric polynomials then the roots $(x_1,x_2,\ldots,x_n)$ of $f(x) = 0$ are the solution you are after. Thus this method recuces the problem to finding the roots of a polynomial (which numerically is fairly simple). ...

0

I'm not sure if this is what you would consider "efficient," but you can use the first equation to solve for one of the variables. For example, $x_1 = c_1 - x_2 - \dots - x_n$. Then substitute this into the second equation to get $(c_1 - x_2 - \dots - x_n)^2 + x_2^2 + \dots x_n^2 = c_2$. Now you can solve for another variable, say $x_2$. Then plug the first ...

0

You can use the Ford-Fulkerson algorithm to accomplish this task. Simply assign the capacity $c(u,v)$ of each edge $(u,v)$ initially equal to it's minimum capacity, and assign the maximum capacities as you normally would (presumably while you're defining the graph). If you're expecting that a flow will not exist between $s$ and $t$ (as your specification of ...

1

We note a tree $T$ with $n$ vertices has $n-1$ edges. So let $F = \bigcup_{i=1}^{k} T_{i}$ be the forest- a union of trees. Let $n_{i}$ be the number of vertices in each tree. So we have: $|V(F)| = \sum_{i=1}^{k} n_{i} = n$ Since each component of the forest is a tree, we have $n_{i} - 1$ edges for $T_{i}$, giving us: $|E(F)| = \sum_{i=1}^{k} (n_{i} - 1) ... 1 1) Let$f(n) = g(n) = n^{2}$. Clearly both$f, g \in \Theta(n^{2})$. However,$(f-g)(n) = 0$. So that's in$\Theta(1)$. 2) Correct. 3) Correct. 4) We really have$T(n) = T(1) + \sum_{i=2}^{n} i^{2}$. We note that the sum of the first$n$squares is a cubic, so$T(n) = \Theta(n^{3})$. 5) Apply the Master Theorem:$T(n) = aT(n/b) + n$. Here,$a = b = 2$. ... 1 I'm not totally sure what you mean by this, but generally, '$n$is not divisible by$m$' means that there does not exist an integer$k$so that$n=mk$. Please post a comment if you were looking for something different. Thanks! 0 There's a superfast method: Don't look for primes! Look for one tiny class of semiprimes. The product of all twin primes is an even perfect square minus 1. And since we're searching for semiprimes, a primality test is not required. Any factor (prime or not) less than the square root of X^2 - 1 eliminates the composite as a candidate. Furthermore, these ... 1 The first program has two loops, an outer loop that interates$n$times and an inner loop that iterates approximately$\log_4(n^2)=2\log_4(n)$times. Thus there are approximately$2n\log_4(n)$constant time instructions (with the ratio tending to$1$as$n$tends to infinite), hence the program runs in$\Theta(n\log n)$time. For the second program, the ... 1 There is Strassen algorithm, which works at a computational complexity of$\mathcal{O}\left(N^{\log_27} \right)$. Then there is Coppersmith Winograd algorithm at a computational complexity of$\mathcal{O}\left(N^{2.375477} \right)$. Some recent developments have reduced the computational complexity further to$\mathcal{O}\left(N^{2.3728639} \right)$. ... 0 I am not aware of the status of the art in the area of finding solutions of equations in the complex domain. So take my answer for what it is, that is to say not much. What I used to do in the old times was first to avoid calculations in the complex domain since they are very expensive with respect to CPU time. So, I used to do everything in real. Let us ... 0$\sum_{k_{1} = 1}^{333}3k_{1}$Here you are sum up all numbers, which are multiples of 3: 3,6,9,12,15,18,21,...,990,993,996,999$3\cdot 333=999$. That´s why the upperbound is 333. To calculate$\sum_{k_{1} = 1}^{333}3k_{1}$you can faktor out 3:$\sum_{k_{1} = 1}^{333}3k_{1}$Now you can use the identity to calculate it:$\sum_{k_{1} = ...

1

Another interpretation of the specification would be simply to split the savings evenly. Single rides would have cost $4+5+4.50=13.50$, so since the actual price is only $11$ there's a total saving of $2.50$, which is 83 cents per passenger. So they should pay \$3.17, \$4.17, and \$3.67, respectively. 1 I'm not sure there's any one right answer, but taking the original individual fares as the basis, and subtracting the savings proportionally, may work. The individual fares, one would hope, would encompass all factors for the cost of the trip for all concerned, and hence would make any joint savings achieved as fair as they could be. Sum of individual ... 2 To total number of minutes spent is$10+19+7=36$minutes. So according to your specification the three riders should pay$\frac{10}{36}$,$\frac{19}{36}$and$\frac{7}{36}$of the total fare, respectively. Since 1725 is not a multiple of 36, some cent rounding will be necessary. One practical solution would be to decide that each minute in the taxi costs ... 1 I am posting a recursive algorithm to print all such combinations. Hope this will be helpful. //prints all ordered combination of 1 and 2 which sum up to n function printAll(n){ //[] is empty list print(n,[]) } function print(n,list){ //base case if(n==0){ output all the elements in list }else{ //passing a new list by appending "1" ... 0 Hints: Think about how the Sieve of Eratosthenes works. If$n$is a composite number, why/when does it get crossed off? If$n$is a prime number, why does it not get crossed off? 0 OK, I've found one possible method. The key is to have interpolation nodes placed only in points with all four (eight) edges (+ boundaries), e.g. x---o---x---x---x | | | | | | | | | | | | o o---x---x | | | | | | | | | | | | x---o---x---o---x | | | | | | | | ... 0 Yes, that approach is working. Essentially, you first produce a ranom permutaion of all numbers and then pick the first$k$. While inefficient for many scenarios, this may be a nice and simple method e.g. as a one-liner in SQL - but I'm note sure how well the performance will be even ther (for cases of$n\gg k$). 0 For a fixed$r$, if you test all subsets with$|S| \le r$, then you are testing $$\sum_{i=0}^r {n \choose i} = O(n^r)$$ subsets, which is polynomial. However, if you were to attempt to test all subsets up to size, say$r_n$, where$r_n$varies with$n$and is arbitrarily high, then the runtime would be larger than$\theta(n^{r_N})$for any particular ... 0 Algorithm: Remove nodes unreachable from$c$. Sort$G$topologically. Consider vertices in topological order and assign them profit $$\mathrm{profit}(v) = \max_{(u,v)\ \in\ E}\Big(\mathrm{profit}(u) + \mathrm{cost}\big((u,v)\big)\Big)$$ Try to prove why this greedy strategy works and what is its running time. I hope that helps$\ddot\smile$2 Going through a few examples, I finally understood it. The explanation under 2.3.5 in Example 1 actually explains the basics very well. The main idea is that is that you can reduce every coefficient on it's own. Instead of doing division you simply use the fact that the reduction of every power over your maximal degree$m$can be computed by$z^a \equiv ...

0

A minor modification of Dijkstra's algorithm will solve the problem, where instead of looking for the path with the lowest weight we are looking for the path with the highest weight.

0

COMBINATORICS algorithm in dynamic programming

0

Lay the vertices out in a line $1, 2, 3, \ldots$. Put all the rightwards arcs in $E1$ and all the leftwards arcs in $E2$. For $V = \{ v_1, v_2, \ldots v_n \}$, for $<v_i, v_j> \epsilon \ G$, $$<v_i, v_j> \epsilon \ E_1 \iff i < j \\ <v_i, v_j> \epsilon \ E_2 \iff i \ge j$$

0

A simple counterexample with $f(n)=g(n) = n = O(n)$. That's if I correctly understand your question. of course.

0

Can you reformulate what means the $O$ notation? In particular what means $O(1)$? After that you should be able to prove that the result is false.

0

In order to find the coefficient of $x^{n-k}$ is $(1+x+\cdots+x^{n-1})^k$, notice that it is equal to the coefficients of $(1+x+\cdots+x^{n-1}+\cdots)^k = \frac{1}{(1-x)^k}$, and it is known that $$\frac{1}{(1-x)^k} = \sum_{n=0}^\infty \binom{n+k-1}{k-1} x^n.$$

0

For question (1), yes, there is, using maximum matching / flow. Consider the bipartite graph $(L, R)$ -- each of the nodes $l_i$ in $L$ correspond to a canister, and each of the nodes $r_i$ in $R$ correspond to a truck. For every pair of allowed canister $(l_i, r_i)$, such that it is allowed to put canister $l_i$ inside truck $r_i$, construct an edge with ...

0

That is not the way to calculate $\binom{n}{r} \pmod m$. First the modular inverse, you must have $(r!,m)=1,((n-r)!,m)=1$..not the way with $m$ being so little. You can do it without any problem with $m>r!$. The mistake is that you are also dividing by some "0" and they cancel out. If you want to keep that method i suggest you to use Legendre ...

0

It seems like things would be easier if you had no cross edges at all. Maybe you can modify your spanning-tree idea to make that happen.

0

This is the question of active contest www.codechef.com/NOV14 contest. This question should be on hold untill contest is over.

0

I believe that because there is a vast variety of convex problems with totally different structure. The term "convex problem" does not really define a representation for the family of problems that we can play with. Therefore building a library of convex problems seems impossible. Because nobody built such a library, everybody just solves random problems. ...

1

The following C program produces 165K different solutions during a one minute run. This is a literal translation of the Perl code and some C style issues probably remain as I am not an expert C coder. Compiled with GCC 4.8.3. #include <stdio.h> typedef struct { int row, col; } slot; typedef slot region[9]; typedef struct { region regions[27]; ...

2

At least in the context of Morse theory these are known as the (un)stable manifolds of the critical points $m_i$. If $\phi(x,t)$ is the gradient flow of $f$ (or more generally any flow): $$\phi(x,0) = x \\ \frac{\partial}{\partial t} \phi(x,t) = \nabla f(\phi(x,t))$$ then the stable and unstable manifolds at a critical point $p$ of $f$ are defined by  ...

2

Here's a fun algorithm to solve this. The idea is that the employee's schedule is actually a sequence of talks, such that every adjacent talk in this sequence overlaps or touch each other. Thus, we can model this as a graph, where adjacent or touching talks have edge between them. More formally, let's say we have $N$ talks, numbered $1$ through $N$. Let ...

5

By way of approaching this problem from a computational perspective here follows a program that will produce these sudokus in the hope that the reader can profit from the algorithmics that are used and perhaps invent a more compact/efficient algorithm. What is used here is backtracking in its most basic form. We sweep the board row by row, placing compatible ...

1

First, sort the talks by ending times and and denote by $L(x,y)$ the minimum stressfulness that can be achieved considering only the first $x$ talks if the conference lasted for $y$ minutes, that is, we pretend that the conference lasts for $y$ minutes and that only the first $x$ talks exist and try to solve a "smaller" version of the main problem. If all ...

Top 50 recent answers are included