-2
votes
1answer
258 views

Modulo of a large sequence of $1$s

Given two numbers $N$ and $M$, we need to find the remainder when $111 \cdots1$ ($N$ times) is divided by $M$. Here $N$ can go up to $10^{16}$ and $M$ up to $10^9$. How to solve this problem? ...
2
votes
0answers
33 views

Speed dating/networking challenge

I am trying to organise an event with 54 participants. I want them to participate in 9 different activities at stations around a hall. Obviously this will require 9 sessions to allow the participants ...
-6
votes
0answers
107 views

Solve fibonacci equation

Given two numbers M and N we need to solve : ( ∑ ( 6 * x * y * z * Fibo[x] * Fibo[y] * Fibo[z] ) ) % M , where x + y + z = N. Here x, y, z ≥ 0 and are integers. ...
-1
votes
0answers
50 views

Counting distinct nonempty sequences

Given N and an array of length N i need to count nonempty sequence (p[1], p[1]+1), (p[2], p[2]+1), ..., (p[s], p[s]+1), where p[k]+1 ≤ p[k+1] for k = 1, 2, ..., s − 1. Here p[i] is the point number i ...
-1
votes
0answers
98 views

Minimum penalty calculation

Their are N tables in a restaurant.Now customer visit the restaurant and they will be provided seats. Each customer has following properties : The customer don't leave the table unless they are ...
0
votes
1answer
268 views

Select elements from N sets

N sets are given which can have any number of elements from 1-100 each.Now we need to count arrangements in which we select 1 element from each set under the condition that we can not choose same ...
2
votes
0answers
56 views

An algorithm for solving linear diophantine equations?

I am entering an interesting team based math contest called the purple comet, and quite a lot of questions on this contest involve Diophantine equations. For this contest, you are given a computer, ...
0
votes
0answers
47 views

Solving the recurrence $F(0) = X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$

Moderator Note: This is a current contest question on codechef.com. I am given $F(0)=X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$ for $1 \leq i \leq N$. Now given $N,A,B,C$ and $X$, how ...
-2
votes
2answers
169 views

Even or Odd for factorial

Moderator Note: This is a current contest question on codechef.com. Given $N$ and $M$ I need to tell whether $\left\lfloor \large\frac{N!}{M} \right\rfloor$ is even or odd.How to do this ...
1
vote
0answers
263 views

Finding the number of arrangement of N people of different height such that K of them are visible from front

Moderator Note: This is a current contest question on codechef.com. [Initially, I had asked this question in stackoverflow, but someone suggested to post it here, and hence this question is ...
4
votes
0answers
62 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
3
votes
2answers
127 views

The number 3211000 is 7-special

Define a positive integer $k$ to be $n$-special if it satisfies the following properties: It has $n$ digits (0, 1, ..., 9) The 1st digit is equal to the number of 0's in the decimal representation ...
2
votes
2answers
103 views

Finding the index such that all partial sums are nonnegative

Given an array a[] of integers of arbitrary size N that sum to 0 (for example, a[] = {-1, 0, 5, 3, -9, 2}), does there always exists an index i ($0\le i\le N-1$) such that each partial sum $S_j = ...
0
votes
1answer
130 views

Minimum number of moves to equalize a list

Given a list of $n$ integers. In one move we can either decrease exactly one element by $1,2$ or $5$. What is the minimum number of moves required to equalize the list? For example: If the list is ...
1
vote
1answer
242 views

No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$ (integer division) (nodes ...
1
vote
1answer
76 views

Vertex of a pentagon-Does the algorithm always stop?

To each vertex of a pentagon,we assign an integer $x_{i}$ with sum $s=\sum x_{i}>0$. If x,y,z are the numbers assigned to 3 successive vertices and if $y<0$,then we replace $(x,y,z)$ by ...
2
votes
2answers
204 views

How to factor 30 digit number

I need to find the prime factorization of a number having 30 digits. I used the Pollard rho method but unfortunately it is not sufficient enough. It needs a more advanced prime factorization ...
4
votes
1answer
543 views

Card Shuffling [SPOJ]

The original question is posted on SPOJ, and included below: Here is an algorithm for shuffling N cards: 1) The cards are divided into K equal piles, where K is a factor of N. 2) The ...
1
vote
2answers
109 views

Non-Standard Deviation

Given a list of integers, how to find the sum of the differences of all possible pairs of numbers ? For example if the number are $3,1,2$ then, answer should be $$\lvert 3-1 \rvert + \lvert 3 -2 ...
2
votes
1answer
268 views

Counting digits in an arithmetic sequence

Given $a, d, n, x$. Suggest me a suitable algorithm to compute the number of times the digit $x$ appearing in the arithmetic sequence $a, a + d, a + 2 \times d, \cdots, a + n \times d$. For ...
1
vote
1answer
2k views

Solving systems of linear congruences (modular equations)

This is a task from an old programming contest the task is as follows, A list of system of linear equations is given in the inputs.If the system is solvable we have to output the solution in the form ...
2
votes
2answers
301 views

Finding GCD of all permutations of a decimal number [duplicate]

Possible Duplicate: Computing GCD of all permutations (of the digits) of a given number. How can we find the greatest common divisor (GCD) of all numbers that can be obtained by permuting ...
4
votes
6answers
1k views

Finding the Heavy Coin by weighing twice

Suppose you have 100 coins. 96 of them are heavy and 4 of them are light. Nothing is known regarding the proportion of their weights. You want to find at least one genuine (heavy) coin. You are ...
5
votes
5answers
697 views

Least wasteful use of stamps to achieve a given postage

You have sheets of 42-cent stamps and 29-cent stamps, but you need at least $3.20 to mail a package. What is the least amount you can make with the 42- and 29-cent stamps that is ...