0
votes
0answers
25 views

Number of strings of length n generated using m different characters.

We need to find the number of sequences that can be made from m different characters (X0, X1, ...., X(m-1)). An array arr[m] of size m is given, ith element tells that character Xi should be used ...
0
votes
0answers
19 views

Calculate sum of distinct pairs [on hold]

Given an array A we need to find the sum of all distinct pairs of indexes from the array and adds the value ⌊$A[i]+A[j]\over A[i]×A[j]$⌋ to the sum Note: ⌊$A\over B$⌋ is the integer division ...
-1
votes
0answers
36 views

Distribute coins among N persons [duplicate]

Suppose we have infinite number of coins.Now we need to give some coins to $N$ persons in such a way that product of the number of coins any two adjacent persons have, is not greater than $M$. ...
2
votes
1answer
78 views

Find different sequences of game to find winner

Alice and Bob are having a racing competition to see who is the best runner. They don't want to decide this in a single race, so they choose a number N which is the minimum number of points one of ...
1
vote
1answer
141 views

Count ways to distribute candies

N students sit in a line, and each of them must be given at least one candy. Teacher wants to distribute the candies in such a way that the product of the number of candies any two adjacent students ...
-4
votes
1answer
184 views

Count good numbers in between L and R

Let length(A) denote the count of digits of a number A in its decimal representation. All non-negative numbers of length 1 are Good. Further, a number X with length(X) $≥ 1$ can also be considered ...
0
votes
1answer
20 views

Permutation and Combination - Algorithm

Given Data in the problem For I= 1 to 10 print(x) means executing the immediate next line after for loop command 10 times. So here it prints "x" 10 times. Typical simple for loop construct in ...
-2
votes
1answer
50 views

Find minimum possible area of brush

A rectangular brush has been moved right and down on the painting. Consider the painting as a $n × m$ rectangular grid. At the beginning an $x × y$ rectangular brush is placed somewhere in the frame, ...
-1
votes
0answers
55 views

Maximum pairs of men and women

There are shoes of n different colors. We will enumerate the colors from 1 to n. For each i, there are M[i] pairs of men's shoes, W[i] pairs of women's shoes and S[i] pairs of shoelaces of color i. ...
2
votes
1answer
51 views

Make a one sequence

A sequence of integers is a one- sequence if the difference between any two consecutive numbers in this sequence is -1 or 1 and its first element is 0. More precisely: a1, a2, ..., an is a ...
1
vote
1answer
21 views

Generating sets with exactly one mutual element

I have a quite interesting task. I need to generate all $n$-element sets, such that every two of them have exactly one mutual element. There are $m$ elements to choose from and can be assumed, that ...
4
votes
2answers
31 views

Can we find an $x, y : x < y$ and $x, y > 0$ and $\lfloor \frac{n}{x}\rfloor$ < $\lfloor \frac{n}{y}\rfloor$ for some integer $n > 0$?

I know there are no solutions when we have just the fraction without the floor, but how do we consider solutions when the floor is there?
0
votes
1answer
29 views

Combinatorics counts outcomes, what mathematics lists outcomes?

Since I've been learning combinatorics the past few days I've constantly found myself wanting to implement the combinatorics I've learned in various ways(mostly by writing software that analizes each ...
0
votes
0answers
27 views

Count ways to paint the grid

Given a rectangular grid of dimension N x M. We need to paint the grid with black or white color such that there is no rectangle of size X x Y having same color in each cell. Find the number of ways ...
0
votes
1answer
33 views

Distribute n balls across m bags when bags are not empty to get the same sizes

Thinking about the best solution of the next problem. Suppose we have m bags where $n_1, n_2, ..., n_m$ balls are already laid. We need to distribute new n balls across these bags to get almost the ...
1
vote
0answers
17 views

How to find all maximal chains and antichains in a finite bounded lattice

Is there a (possibly efficient) algorithm to find all maximal chains and antichains in a finite bounded lattice?
0
votes
0answers
41 views

counting the good numbers

We need to calculate Good Numbers in range from $A$ to $B$ (Both inclusive). A number $N$ is said to be a good Number if it satisfy following conditions : If we extract every $2$-digit number of $N$ ...
1
vote
1answer
31 views

How many binary string are there such that there are no k consecutive characters are the same?

Given number $n$ and $k$. Count the number of string with length $n$ such that there are no $k$ consecutive characters are the same. Example with $n = 3, k = 3$, the answer is $6$. ($110, 001, 101, ...
1
vote
1answer
84 views

Divide N Hot dogs among M persons

There are N hot dogs and M people and we need to divide the hot dogs equally. Now we need to calculate the minimum number of cuts required to distribute the hot dogs equally. In order to divide the ...
-1
votes
1answer
116 views

Count ways to form isosceles triangles

Their are N persons sitting on a table with N vertices.We need to count the number of isosceles triangles formed such that each vertex of the triangle is a vertex of the table and all persons seating ...
1
vote
0answers
24 views

Sampling from Cartesian product without replacement, but with balanced totals

I am struggling with a combinatorial task that I cannot reduce to any procedure I know: Given two sets $F, G$, I want to sample from $F \times G$ without replacement, but subject to the condition that ...
-1
votes
0answers
66 views

Door game between alice and bob

Alice and Bob are taking a walk in the Land Of Doors which is a magical place having a series of N adjacent doors that are either open or close. After a while they get bored and decide to do ...
1
vote
1answer
71 views

Count ways to reach Nth row

Given a N*M grid I need to reach last row with following operations : ...
0
votes
1answer
31 views

Sequence of polynomials with rational coefficients

Clearly, the set of all univariate polynomials with rational coefficients is countable. That is, we can enumerate the members, say, as $x_1,x_2, \dots ,x_n, \dots $ How can we find $x_n$ for a given ...
0
votes
2answers
61 views

Making 24 with given number N

Initially we have a sequence of n integers: 1, 2, ..., n. In a single step, we can pick two of them, let's denote them a and b, erase them from the sequence, and append to the sequence either a + b, ...
0
votes
0answers
31 views

Divide N elements in 3 sets

Given N elements in an array where ith element has A[i] value.Now we need to divide these N elements in 3 sets in such a way that difference between sum of all elements in set1 and set3 is minimised. ...
1
vote
0answers
39 views

Count the strings with n0 K zeroes together

Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1. Now , the problem is we need to count the number of ways to fill these ...
0
votes
1answer
13 views

Max no. of piece in k cut

Suppose I have large piece of rectangular sheet. Cutting is allowed only vertically and horizontally. My approach is if no. of cut is even then max. no of piece is (n/2)*(n/2) if no of cut is odd ...
5
votes
0answers
83 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
6
votes
1answer
72 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
1
vote
0answers
14 views

Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
-1
votes
1answer
252 views

Finding winner of flipping game

Alice and Bob play a game with N non-negative integers. Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list. That is, they ...
0
votes
1answer
42 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
0
votes
0answers
29 views

Simple enumeration of discrete simplex

I'm looking for a computationally nice enumeration of the $n$-dimensional discrete simplex $$\Delta^n_N = \{ x \in Z^{n} | 0 \leq x_i \leq N \, \text{and} \, x_1 + \cdots x_n = N \}$$ I have an easy ...
1
vote
0answers
31 views

How to use a computer to give guesses for a counting formula, given the first few terms?

Are there any systematic approaches developed on how to derive some "succinct" combinatorial formulas e.g. using factorials/hypergeometric terms and polynomials with integer coefficients that fit the ...
0
votes
1answer
64 views

The number of ways people standing in a line can be holding hands

I'm writing a program to analyze the maximum unique sequences of data in a string, given certain sets of two can be interpreted in two ways. There's a bit of math that I can't figure out, I've ...
2
votes
2answers
120 views

How to find the optimal mapping between two sets?

Given two sets $A$ and $B$, both of $n$ points $p \in \mathbb{R}^3$. I want to find a bijective function $f:A \rightarrow B$ so that the cost $C$ is minimal. It's defined as the sum of all pair's ...
0
votes
0answers
21 views

Inclusion-wise minimal feedback arc set

How is the term inclusion-wise defined? More precisely, I am trying to get a hold of what an inclusion-wise minimal feedback arc set is. Let $G = (V,E)$ be a (directed) graph. A feedback arc set $F ...
2
votes
1answer
57 views

Count ways to make total coin value [closed]

For any non-negative integer K, suppose we have exactly two coins of value 2^K (i.e., two to the power of K). Now we are given a long N. We need to find the number of different ways we can represent ...
2
votes
0answers
53 views

Minimise total cost and count ways [closed]

A country has a + b cities located in a row, which are uniformly placed. There are two large telecommunication operators in this country. The first operator will ...
1
vote
1answer
35 views

Algorithm for retrieving all the permutations (randomized) for a vector sequence 1…N with only unique values

Here is the problem: I have a vector of $N$ elements long (containing only unique values from $1...N$). I am searching for an algorithm to obtain all the (randomized) combinations possible, where ...
1
vote
1answer
38 views

For an alphabet of size $N$, how many strings have all of its substrings of length $\geq 2$ unique?

For an alphabet of $N$ characters, how many strings can be formed (including the empty string) so that no substring of length $\geq 2$ appears more than once in the string? The maximum length of such ...
0
votes
1answer
81 views

Find if permutation is possible

Given a permutation of natural integers from 1 to N, inclusive. Initially, the permutation is 1, 2, 3, ..., N. We are also given M pairs of integers, where the i-th is (Li,Ri). In a single turn we ...
8
votes
2answers
195 views

Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal

Assign one number from 1 to 12 to each edge of a cube (without repetition) such that the sum of the numbers assigned to the edges of any face of the cube is the same. I tried a bunch of equations but ...
0
votes
1answer
97 views

Subtraction game between alice and bob

Alice and Bob decide to play a number game. Both play alternately, Alice playing the first move. In each of their moves, they can subtract a maximum of k and a minimun of 1 from n ( ie.each of them ...
1
vote
1answer
49 views

Arrange blocks to form matrix of $N \times 3$

Given are the blocks of 3 different colors (Red,Green and Blue). Red colored block of size $1 \times 3.$ Green colored block of size $1 \times 2.$ Blue colored block of size $1 \times 1.$ ...
0
votes
1answer
61 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
1
vote
1answer
50 views

Find if arrangement is possible or not

The company has k buses and has a contract with a school which has n students. The school planned to take the students to d different places for d days (each day in one place). Each day the company ...
1
vote
2answers
127 views

What algorithm do i need to solve my problem?

unfortunately I even don't know what kind of problem I deal with. But I'll try to explain as good as I can and maybe you can tell what kind of problem this is and how to solve it. I want to find ...
1
vote
0answers
60 views

Integer partitions without rotated solutions?

I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of ...