All Questions
Tagged with dynamic-programming c
18 questions
2
votes
5
answers
299
views
Sum of bitwise XOR of each subarray weighted by length
here is the problem statement
You are given an array a of length n consisting of non-negative integers.
You have to calculate the value of \$\sum_{l=1}^n \sum_{r=l}^n f(l,r)\cdot (r - l + 1)\$ where \...
Mast♦
- 13.7k
8
votes
3
answers
305
views
Splitting a rectangular chocolate bar
I'm having trouble with my school homework. I have a chocolate bar that consists of either black, white or black&white (mixed) squares. I'm supposed to divide it in two groups, one that has only ...
- 84.9k
1
vote
1
answer
80
views
Longest Increasing Subsequence of Rectangles
Background
I was looking at some programming Olympiads the other day, and I found this ACM-ICPC Ukraine 2013 pdf.
The part I am working on is Problem D, which consist of finding out how many rectangle ...
- 25.7k
2
votes
0
answers
140
views
Bellman-Ford algorithm implementation
I have used an adjacency list to represent the graph.
This implementation is based on the procedure given in the book 'Introduction to Algorithms'.
...
- 321
1
vote
2
answers
120
views
A function to scan user input as string
I know that multiple functions are already available. However, I thought of writing my own because I wanted to learn the logic (and also because I thought there wasn't enough confusion :P). Please ...
- 35.7k
1
vote
0
answers
96
views
selecting 5 best players out of 2 team
Let us assume that we need to develop an application which can select best 11 players to score maximum points. The application will select the best players after completion of a match. The rules are ...
- 58k
4
votes
2
answers
5k
views
Project Euler #15 -- count possible lattice paths
I'm not a C programmer, just wanted to make a fast solution to the problem.
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 ...
- 295
3
votes
3
answers
2k
views
Tower Hopper problem recursive approach
The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from ...
Mast♦
- 13.7k
5
votes
3
answers
312
views
Largest contiguous sub-array sum
Challenge
Determine the largest contiguous sum of integers in a list.
Specifications
The first argument is a path to a file.
The file contains multiple lines.
Each line is a test case represented by ...
CommunityBot
- 1
3
votes
2
answers
160
views
Count the number of ways to obtain a sum, with consecutivity restriction
A cricketer can score 1, 2, 4 or 6 in a ball. Find in how many ways the player can score a total of "n" runs without hitting 3 consecutive boundaries. Note: Scoring 4 or 6 is considered as a boundary. ...
CommunityBot
- 1
11
votes
3
answers
3k
views
Coin Change: Minimum number of coins
Problem:
You are given n types of coin denominations of values \$v(1) < v(2) < ... < v(n)\$ (all integers). Assume \$v(1) = 1\$, so you can always make change for any amount of money \$C\$. ...
CommunityBot
- 1
8
votes
2
answers
265
views
Minimum number of coins problem using dynamic programming - follow up
I previously posted a code here. It turns out that the code is not following the correct dynamic programming principles and instead it was based on a greedy approach. Hence, I started again, keeping ...
CommunityBot
- 1
8
votes
2
answers
2k
views
Counting Increasing Subsequences of size K recursive
The original description of the problem can be found here, its input here and its expected output here.
The problem:
Given a integer sequence a1 ... an (-10000
\$\leq\$ ai \$\leq\$ 10000). Where ...
CommunityBot
- 1
6
votes
1
answer
121
views
Optimal way to annihilate a list by removing items from the ends
I'm stuck with a contest problem.
Description:
What is the minimum number of moves to annihilate an int array where the possible moves are:
Remove both the first and last elements if they are equal ...
CommunityBot
- 1
4
votes
1
answer
240
views
NGON (many polygons) on SPOJ
I am trying to solve NGON problem. I am using bottom up dynamic programming here. Recurrence function is:
$$\begin{array}{rl}
f(a,b) &= f(a-1,b) + f(a-1,b-1)\,a_i +\frac{f(a-1,b-2)\,a_i(a_i-1)...
- 13.4k